Wednesday, October 05, 2011

Project Waterloo

I tried playing Microsoft Research’s Project Waterloo on Facebook; details are here, see also here. It’s a Colonel Blotto game: each player (there are 2) has 100 soldiers that he uses to attack 5 hills1, and you capture any hill if you attack it with more troops than your opponent. In each round you divide your soldiers between the hills, doing your best to guess how the opponent is dividing his, and you win the round if you capture 3 or more hills. Quoting the MSRC site:
The game is complex from a game-theoretic perspective, involves randomized strategies, and can be approached by reasoning about the opponent's reasoning. We have also found it to be fun, engaging, and slightly addictive. It is thus a great test case for studying actual strategic behaviour of people on Facebook.

I’m wondering whether it’s meant to be straightforward to devise an optimal strategy... it’s a zero-sum game, the catch is, there’s a large number of pure strategies — but do you have to mix over a large number of pure strategies (to guarantee to break even over time)? Maybe there’s a set of 5 good numbers (e.g. 34,26,21,15,4) that work if you allocate them at random to the hills; those suggested numbers look like a good bet against opponents who split their troops about equally amongst 3,4 or 5 hills.

Next I start thinking up ideas for improvement, usually after losing a round... how about a multi-round variant, in which the surviving troops get to defend the hills they captured? In a subsequent round, a defender would cancel out (say) three attackers, and you are allowed to send additional troops to a hill you already captured, in which case, you have to cancel them out with opponent’s attackers, and if any survive, they add to the defenders of that hill. It looks like eventually, all hills will end up with so many defenders that further attacks should be futile, but there is no guarantee of how long it will take to reach that state.

1“Hill” comes from the Gross and Wagner paper linked-to in the Wikipedia page. More abstractly they are sometimes called battlefields or sites.

1 comment:

Siddharth Bhattacharya said...

Sir, found this post interesting so wanted to try my hands at the analysis.

In the original form proposed by MSR, the Game doesn't have any specializations- repeated, Bayesian etc. - but is a one-stage simultaneous game. Finding the Nash Equilibria is difficult as stated due to the vast number of pure strategies (which I believe are (104 C 5)^ 2 in number in the specific example). Moreover, I can't see any intuitive NE.

I feel a good strategy would be to play 30,30,30,5,5 (in random order). This is of course not dominant. However if the opponent must defeat me, he must capture both the battalions using at least 12 soldiers, and another using at least 31 soldiers. Not that this is impossible or unlikely, but since the order is random as well the chances of winning with only 12 soldiers would be very less, since he must synchronize these 2 hills with Player 1. Thus either he will have to be lucky enough to attain this, OR be crazy like Player 1 and play a similar strategy.

Moreover, I failed at understanding your attempt at modeling this into a Repeated Game. I thought once the hill is lost, the soldiers are lost. So gradually there will be attrition?