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