Colonel Blotto's game

Colonel Blotto's game, in one form, goes as follows:

Colonel Blotto and his opponent each have 100 divisions, and are going to fight over 10 pieces of territory (regions). They therefore (independently) divide their forces up into 10 parts and send each part to one region. Ten fights take place, and the one with the larger force wins the region (or there may be a stand-off). The winner of the battle is the one with the most won territory.

Example:

Blotto divides his forces as
10, 10, 10, 10, 10, 10, 10, 10, 10, 10

His cunning opponent anticipates this and divides his as
11, 11, 11, 11, 11, 11, 11, 11, 11, 1.

As a result Blotto loses the battle 9-1.

Now it is not hard to show that given any distribution of troops there is another one which will beat it, but some distributions are clearly worse than others, e.g. 25 25 25 25 0 0 0 0 0 0 is quite likely to lose 6-4 against most opposing formations. The optimal strategy is some sort of mixed strategy, but too hard to analyse, as far as I can tell (though smaller versions of the game, e.g. 6 divisions and 3 regions, can be analysed quite simply.)

The rules of the Colonel Blotto competition run in January 1990 were therefore as follows:

Entrants should send me by E-mail a sequence of 10 non-negative integers totalling at most 100. Entries totalling more than 100 are disqualified. After the closing date (midnight on January 31st) I shall play off entries in an all-play-all tournament, as above, giving 2 points for a won battle, 1 for a draw, 0 for a loss: so the actual margin of victory (9-1, 6-4, or whatever) does not affect the points scored. The winner is the entrant with the greatest score at the end.

Not more than one entry per person will be accepted.

To make it more interesting, a small prize of 5 pounds will be awarded to the winner (or shared between equal winners). The referee's decision is final.

Note also that the order of positions is relevant, e.g.
100 0 0 0 0 0 0 0 0 0 is not the same as 0 100 0 0 0 0 0 0 0 0.

Several people pointed out the similarity between this and other enjoyable games. Jonathan Mestel recalled a Problems Drive involving several teams, who were given 100 goals to score against all the other teams in a simulated football league tournament. Peter Killworth recalled a card game for two devised by Hubert Phillips: two identical hands, of 30 cards each, are obtained using two packs. Players sort cards into six Poker hands, and these are played off pairwise, one after the other.

Colin Wright has run a game called 'Psychological Jujitsu', which goes something as follows: remove the hearts from a pack of cards, give the spades to player A, the clubs to player B; this leaves the diamonds, which are turned over one by one and bid for by the two players, each simultaneously offering one of their remaining (black) cards. A draw means that the bid card is held over and offered with the next one (or lost altogether, if it was the last). There are various ways of determining the winner: either on a count of the number of diamonds won, or on a total pip count (1, 2, 3, ..., 10, J=11, Q=12, K=13).

Anyway, this was the final league table of the Colonel Blotto competition. Players are identified by their computer user identifiers.

Player
Number   Disposition of forces........         W    D    L  pts  who
 26      17  3 17  3 17  3 17  3 17  3        64   33    9  161  PNT12
 80      19  1  1 19 19  1  1 19 19  1        56   44    6  156  AG120
 27      19  2 16 18  3 19  0  3 17  3        61   33   12  155  CDW10
 39       1 19  1  1 19 19 19  1 19  1        54   46    6  154  BCK1
 24       7 18 18  2  9  3 18  5  2 18        61   30   15  152  GRB10
 82       2 10  1 18 19  3 20  2  8 17        61   26   19  148  JML11
  3      17  0 17  0 17  0 16  0 17 16        64   19   23  147  JDG14
  7      17  0 17  0 16  0 16 17 16  1        64   17   25  145  JPMG1
 22      16 17  5  2  4 19  1 18 15  3        57   31   18  145  GKS1
 38      16  0 17 16  0  0 17 17  0 17        64   17   25  145  RMR12
 43       0  0  0  0 17 17 17 17 16 16        61   23   22  145  RDHW
  4      17 15  0  0 17 17 17  0  0 17        59   26   21  144  CET1
 66       1 17  1  1 21 19 17  1  1 21        50   41   15  141  MTB3
 53       2  4  8 16 16 20 15  0 15  4        54   32   20  140  HTL10
 35       6  6 16  6 16 16  6 16  6  6        55   29   22  139  JS138
 17       5 10 18 16  1  5 18 16 10  1        56   26   24  138  SEW10
 63       1  1 15  1 18 18 10  2 17 17        52   32   22  136  SV14
 11       4 16  0  0 16 16 16  0 16 16        58   19   29  135  CRB11
 42      18  0 18 18  0 10 18  0 18  0        46   43   17  135  MAW13
  2      17  2 12 17  2 17  2 12 17  2        49   36   21  134  REB5
 94       1  1 17 14  1  2 13 18 14 19        57   20   29  134  FM11
 14      16  1 15 16  1 16 17  1 16  1        54   25   27  133  JBOM1
 52       3 16  0 16 16 16  0 16 16  1        54   25   27  133  DRV10
 58       1 16  1 16 16 16  1 16 16  1        51   31   24  133  SJ106
 25       1  2  1  1 21 19 17 15 13 10        51   30   25  132  SKB13
 54       1  1  1  1 16 16 16 16 16 16        53   26   27  132  EJH12
 32       0 18  0 18  0 17  0 16 16 15        52   26   28  130  VAAP1
 64      16  1 16  2  8 18  4  1 18 16        46   38   22  130  PER10
 95       1 16  1 16  1  1 16 16 16 16        50   29   27  129  AGW14
100       5 12 20  3  8  6 13 21  4  8        45   39   22  129  AJG14
 92      16 16  1 16 16 16  1 16  1  1        50   28   28  128  IR11
 87       1 16 16 16  1  1 16 16  1 16        48   31   27  127  IF10
  1       4  2 21 11 18 11 17 11  3  2        49   28   29  126  RJW15
 75       1 16 16  1  1 16  1 16 16 16        47   32   27  126  KW102
 81       1 16 16  1 16 16  1 16 16  1        46   34   26  126  RJS22
 85       1  1 14 16 18 18 16 14  1  1        49   28   29  126  MJO11
 91       1 16 16 16  1  1 16 16 16  1        47   32   27  126  BEQ10
 44       1 16 16 16  1 16  1 16 16  1        45   34   27  124  MFSY1
 59      16  1 16  1 16 16  1 16  1 16        49   25   32  123  TJC1
 72      16  1 16  1 16 16  1 16  1 16        49   25   32  123  RDMG1
102       1 15 17 12  3  1 12 21 15  3        44   35   27  123  IG17
 83       1  1 16 16 16 16 16 16  1  1        48   26   32  122  DJS6
 71       3 14  2 16 14 15 16  2 15  3        49   23   34  121  DR105
 10      18  1  1 16 15  1 15 16  1 16        50   20   36  120  RR108
 73       2  2  3  8 14 13 15 17 14 12        39   41   26  119  APG12
 13       6 16  6  6 16  6  6 16  6 16        35   47   24  117  DT108
 90       1  1 15 18 15 15 18 15  1  1        48   21   37  117  RJB17
 86      16 19 16 16 16 17  0  0  0  0        46   24   36  116  HHL10
  5       0  2  4  6  8 12 14 16 18 20        41   33   32  115  CRJ10
 15      18  0 20  0 24  0 20  0 18  0        24   67   15  115  XXM10
 41       0  0  0 16 16 16 16 16 16  4        43   28   35  114  DTS12
 89      15  8 17 16  3  1  3 15 13  9        42   27   37  111  MO101
107       2 20  6  8 16  4 12 14 18  0        36   39   31  111  JPM19
 47      10 12  8 14  6 16  4 18  2 10        33   44   29  110  AJP15
 93      17 17 17 16 15 14  4  0  0  0        50   10   46  110  AHS10
 51       0 16 16  0 16 20  0 16 16  0        44   21   41  109  SMWI1
 98      14  3 12 16  5  9 13 17  6  5        33   42   31  108  APS14
 56       0  0 17  6 19 17 12  1 12 16        40   27   39  107  APAK
105       4  1 13 18  6 15 11 14  1 17        36   35   35  107  TJL13
 28       0  0 21  2 24 22  1 23  3  4        40   26   40  106  RJD4
 34       1  3  7 15 24 24 15  7  3  1        35   32   39  102  WYN10
  9       2 10  8 18 12 12 18  8 10  2        30   40   36  100  LR106
 16       1 19  3 17  5 15  7 13  9 11        30   39   37   99  ARP11
  8      13  1 22  7  7 13  1 22  7  7        32   34   40   98  AG109
 31       0 17 13 17  0 17 10 13  0 13        32   30   44   94  JDS11
 57       6  7  8 10 11 20 11 13  4 10        27   39   40   93  DJC17
 21      14  1 14 14  0 14 14  1 14 14        39   14   53   92  FJMT1
 97      14  6 14  6 14  6 14  6 14  6        26   40   40   92  AK110
 49      12  5 18 16  6 11 10 11  5  6        29   33   44   91  DRTR1
 99       5  8 14  9  9 12 12 11 17  3        25   41   40   91  RJFH1
 74       2 14 14 12  2  2 14 14 12 14        33   23   50   89  RJH21
 76      15  2 15  3 14 10 13  2 12 14        31   27   48   89  RFD10
 77       3 13 13  3 13 13 13  3 13 13        32   24   50   88  AJC21
 40      15  0 15 15  0 15  0 10 15 15        32   23   51   87  PJB10
 78       3 12 13 13  4 13 13  4 13 12        30   27   49   87  GJC11
 79       0 17 15 13 10  0 13 15 17  0        33   21   52   87  MAE14
 19       2 10  4 12  6 14  8 16 10 18        26   34   46   86  JMC17
106      17  1 12 14 18 12  6  9  5  6        27   32   47   86  RJS23
 20       6  7  5  0  6 15 29  5 16 11        23   38   45   84  CR24
 55      18 16 13  9 11 14  6  8  2  3        27   29   50   83  DAC11
 12       4 13 13 13 13  1 13 13 13  4        31   20   55   82  PAS14
 23      14 14  1 14 14  0 14 14  1 14        31   20   55   82  MRAO
 29       0 17 18  0 11 12 11 14  4 13        28   26   52   82  JRXR1
 88       1  1 14 14 14 14 13 14 14  1        33   15   58   81  SBR11
104       0 14 14 14 16 14 14 13  0  1        31   17   58   79  DSTM1
 36      14 16 14 16 14 16 10  0  0  0        29   20   57   78  PRT10
 18      15 15 15 15 15 15 10  0  0  0        32   13   61   77  TN101
 69       4 11 12 18 20 10  8 12  5  0        18   40   48   76  GJCT1
 30      17 16 15 14 13 12 11  1  1  0        28   19   59   75  SW118
 65      16 15 13  1 14 16 12  0 12  1        33    8   65   74  WB103
 45      15  3 32  1 16  2  8  4  4 15        19   33   54   71  BTCK1
 84      12 14  4  4 12 14 10 14 12  4        25   21   60   71  JPAC1
 60       0 15 12 11 12  0 14 12 11 13        25   14   67   64  SRW14
 61      11 11  0 11 11 12 11 10 12 11        24   16   66   64  DKP10
 67      12 10 13  2  4 13 12  9 12 13        21   22   63   64  IDR10
 33       6 11 11 11 11 12 11 10 11  6        22   19   65   63  PGN10
 70       8  8 12  8 12  8 12  8 12 12        18   26   62   62  DG106
  6       8  5 10 12  8 10 11 16  8 12        19   23   64   61  NMM1
 96       5 15 10  5 15 10  5 15 10 10        13   35   58   61  NKB11
 68      13 12 13 13  0 12 12 13 12  0        24   10   72   58  MJB12
103      16  4 10  6  8 10 13 13 11  9        14   29   63   57  JMLW1
 46      12 12 12  1 12 14 12 12  1 12        18   19   69   55  GS104
101      11 11 11 11 11 11  1 11 11 11        18   19   69   55  PD106
 62       0 11 11 12 11 11 11 11 11 11        16   22   68   54  MM106
 37      15  6  7 13  9  5  8 12 11 14        14   24   68   52  GDR11
 48      10 10 10 10 10 10 10 11 11  8        16   20   70   52  MW121
 50       7  3 14 11  2  5  9  6  1 42         2   27   77   31  DCC10

The winner was therefore Paul Taylor (PNT12).

Various strategies were employed, and here follows a selection of some of the rationales provided.

Let us note first that the game is highly non-transitive. In the rather simpler 3-region, 6-division version, 222 loses to 330, which loses to 411, which loses to 222 again. So the aim of the game is to beat as many of the other participants as possible, even though their own strategies can vary widely. This recalled to Ted Sohn an (illegal) strategy called 'fiddling the board order' in chess tournaments, where a team puts a weak player on the top board, in the hope of cleaning up by winning on the lower boards; rather than, as is supposed to happen, arranging the players in descending order of strength.

Some people (e.g. Nick Maclaren, NMM1 in the notation above) went for the straight multinomial distribution, using a random number generator. David Robinson, DRTR1, a physicist, took a more sophisticated view, by letting the probability distribution of the number of divisions in a region be Poisson-like. Apparently, it can be shown that this distribution (at least, in the limit of many divisions in a region) is the one that maximises the entropy (i.e., some measure of the randomness of the distribution) subject to a constraint on the total number of divisions. He referred me to an article by S.F. Gull (another Cambridge physicist), entitled: 'Monkeys, Kangaroos and N'.

Those who went for a more deterministic strategy tended to do better. They noted that (as Ian Farquharson, IF10, put it) there really appear to be 2 distinct problems: choosing the numbers, which must be amenable to rational analysis, and choosing the order, which seems to be pure psychology in a contest of this sort, and so might be done at random. There seemed to be various theories suggesting that a `big 6' strategy (most of the divisions concentrated on six regions) would tend to have good chances, because one would be likely to win 6 regions against many opponents. However, a `big 5' strategy turns out to be even better, and each of the top 4 entrants used this.

Alex Perry, ARP11, and several others, burned up disturbingly large amounts of computer time trying to solve the game `exactly' for smaller wars. For example, he concluded that, in some sense, the best strategy for the 4-region 24-division battle is 8 8 8 0, in some order; for 4-28 he found 10 6 6 6; for 4-32 he found 11 7 7 7; and for 4-36 the suggestion was 12 12 12 0. This does not seem to give a meaningful recommendation for 10-100.

Alex Selby, APS14, proceeded by trying to solve continuous versions of the game, e.g., 3 (non-integral) numbers adding up to 1 on each side. The advantage of continuous versions is that there is some hope that calculus can be used. However, even this version seems to be difficult, and the 10-region version is beyond analysis so far.

John Levine, JML11, wrote a Lisp program to generate random sequences and play them against each other. He used about 5000 sequences and scores and tried to simulate the contest itself playing 30 random sequences, 13 `good' sequences and 7 spoilers (sequences designed to beat the `good' sequences, in the way that, say 17 17 17 17 17 3 3 3 3 3 would be defeated by 8 18 18 18 18 4 4 4 4 4). To his horror, one of the random sequences won in his simulated contest, by a fairly big margin, so he decided to play it. In the event it did quite well.

Graham Brightwell, GRB10, noted that his strategy did very well against the others in the top 12 (it beat 9 and drew with 2), although it was less efficient at beating the weaker strategies.

Well, a good time was had by all, except the long-suffering computing service. The game is a fascinating one, even if played between just two people. With over a hundred participants, enough variety was seen to test all the proposed strategies.

However, the last word has not been spoken: John Levine later ran his computer programs again to find an even better strategy, in the sense that, had it been in the competition with all the actual entries, it would have won quite easily. The entry he obtained was 2 3 0 3 17 17 18 17 17 6, and it would have won by a massive 23 points. He obtained this by (in his own words) a process of iterative swap-and-diddle: take a sequence, see what score it gets, then either swap two numbers over (swap), or add 1 to one of the numbers and subtract 1 from another of them (diddle). If it gets a score greater than or equal to the score of the last sequence, it becomes the new best sequence. Of course, all this relies on knowing what the other entrants are. Sometimes hindsight is a wonderful thing.

Last updated on December 7th 2002 by Jonathan Partington

Hosted by www.Geocities.ws

1