1
$\begingroup$

Imagine you have 5 different territories on a game board. Suppose two players each have 100 soldiers. They both independently distribute their 100 soldiers throughout the 5 territories. The two players then reveal where they placed their soldiers; Whoever has the most soldiers on each territory takes control of that territory. Which-ever player has the most territories wins the game. If neither player has more territories than the other, then a stalemate occurs.

Essentially I want to determine the optimal strategy or strategies. I am at least a semi-decent Java programmer, so I thought I might be able to write a program to test every possibility excessively, so as to see which one results in the highest probability of winning.

However, how would I systematically test every possibility, I am having a hard time conceptualizing how I might do that? Would the number of possibilities be too astronomical to test on my home computer?

Here is a rough algorithm I thought up for solving the problem:

1) Record all possible strategies and number them each 1 to x (e.g. one of many possibilities: {40,40,10,10,0})

2) Start with strategy 1 and randomize the numbers

3) Make another randomization of strategy of 1

4) Commence "battle" between the two

5) Record who wins

6) Repeat steps 2 to 4, say 100 times

7) Move onto strategy 1 vs 2, then 1vs3, 1vs4, etc...until all are exhausted, using process stated above

8) Move onto strategy 2vs2, 2vs3, 2vs4, etc...until we reach x vs x.

So basically, what I need help with is: 1) How many possibilities are there? Is it too astronomical to test? 2) General mathematical algorithm for generating all possibilities.

Thanks!

Edit (for clarification): Suppose strategy 1 = <100,0,0,0,0>, 2 = <99,1,0,0,0>, etc... Oh, I think I may have just answered my own question? If this continued until a in (a,b,c,d,e) equals zero and b = 100, then that would be 100 different ways, then we continue this making 400 or 500 ways (fence post problem, not sure). Anyone else follow what I am trying to say here? :)

For anyone who wanted to know, if we assumed the program took 10 operations and we needed to do 2 quadrillion operations and our computer was capable of doing 3.3billion operations/sec, then it would take about 10 weeks to complete.

  • 0
    @BrianM.Scott Yes, that looks correct. Chris Not sure what you mean. If there are two territories, with 2 soldiers/player then we can have: {2,0},{0,2} or {1,1}.{1,1}, so it ends in stalemate no matter what?2011-10-24

3 Answers 3

3

A Nash equilibrium mixed strategy is to first decide how to split up your soldiers into groups by picking a row at random from the following matrix, and then assign each group to a territory at random. This answer assumes A=B=100 soldiers per player, K=5 territories, and uses the results of this paper, in particular Theorem 7 and case 2.1 of the proof of Proposition 6.

 [[ 0  0 20 40 40]  [ 0  2 18 40 40]  [ 0 18 22 22 38]  [ 0 20 20 20 40]  [ 2  2 22 36 38]  [ 2  6 16 38 38]  [ 2 16 24 24 34]  [ 4  4 24 32 36]  [ 4 10 14 36 36]  [ 4 14 26 26 30]  [ 4 18 18 22 38]  [ 6  6 26 28 34]  [ 6 12 14 34 34]  [ 6 12 26 28 28]  [ 8  8 24 28 32]  [ 8 10 18 32 32]  [ 8 10 22 30 30]  [ 8 16 16 24 36]  [10 10 20 30 30]  [12 12 16 28 32]  [12 14 14 26 34]] 
  • 0
    Thanks opt, I will have to print this paper out and read it when I get a chance.2011-10-24
3

These are known as Blotto games. Here's a relevant, previous StackOverflow question.

  • 0
    Thanks for the additional references!2011-10-25
1

The set of all possible strategies is the set of all ordered 5-tuples $(a,b,c,d,e)$ of nonnegative integers that add to 100. The number of such 5-tuples is well-known to be the binomial coefficient $\binom{104}4 ={}$ 4,598,126. (Proof: consider the number of ways of putting 100 dots and 4 dividing bars in a row.) You can generate all of these by enumerating the "cut points" $(i,j,k,l) = (a,a+b,a+b+c,a+b+c+d)$. So to generate them all with a program, you can simply have a 4-fold FOR loop, with $i$ going from 0 to 100, $j$ going from $i$ to 100, $k$ going from $j$ to 100, and $l$ going from $k$ to 100.

Exhaustively searching through all pairs of strategies would be quite a lot: $\binom{104}4^2 \approx 2\times10^{13}$. I agree that trying with 2 or 3 territories will be easier, and might yield a guess as to the right answer.

  • 0
    Just wanted to say that I agree: the "right" way to think about this problem is by searching for the optimal mixed strategy.2011-10-25