# 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