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.


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.

  • $\begingroup$ What do you mean by "best strategy"? Are you looking for a Nash equilibrium? At any rate, it's best to start with smaller numbers. Perhaps a hand-computation will give the solution. $\endgroup$ Oct 24 '11 at 22:35
  • $\begingroup$ Sorry, not entirely up with the math lingo, per se. I am actually an undergrad computer science major. I honestly don't know what a Nash equilibrium is (though I did see A Beautiful Mind)? This is just a little project I wanted to take up on my spare time. $\endgroup$ Oct 24 '11 at 22:38
  • 2
    $\begingroup$ If I were you I'd start by thinking about the case with 2 territories and 2 soldiers, which is certainly small enough to simulate on a computer and probably small enough to solve by hand. If you want to enumerate all the strategies you're out of luck. Even with 2 territories and 2 soldiers, you can distribute the soldiers as (2,0) or (1,1) or (0,2) each with some probability $p_1$, $p_2$ and $p_3$ (with the constraint that $0\leq p_i\leq 1$ and $\sum p_i=1$) which already gives you infinitely many strategies. $\endgroup$ Oct 24 '11 at 22:40
  • 1
    $\begingroup$ Let me see if I understand. In effect each player chooses a $5$-tuple of non-negative integers summing to $100$, say $\langle a_1,a_2,a_3,a_4,a_5\rangle$ and $\langle b_1,b_2,b_3,b_4, b_5\rangle$. $A$ wins if the number of $i$ for which $a_i>b_i$ is greater than the number for which $b_i>a_i$. Is that correct? $\endgroup$ Oct 24 '11 at 22:42
  • $\begingroup$ @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? $\endgroup$ Oct 24 '11 at 22:47

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]]
  • $\begingroup$ Could you provide a link on how to "compute the large payoff matrix and nash equilibrium"? If I can decpipher the basics I can probably get Wolfram|Alpha or something to do the dirty math, if necessary? $\endgroup$ Oct 24 '11 at 23:04
  • $\begingroup$ Thanks opt, I will have to print this paper out and read it when I get a chance. $\endgroup$ Oct 24 '11 at 23:27

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

  • $\begingroup$ Thanks for the additional references! $\endgroup$ Oct 25 '11 at 0:19

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.

  • $\begingroup$ Thanks, I think this is what I was looking for! :) Now I will probably go bug the comp sci peoples to find out how long it will take my computer to run my algorithm 2 quadrillion times (literally!)? Haha $\endgroup$ Oct 24 '11 at 23:06
  • $\begingroup$ When you say "strategy", you mean "pure strategy"? $\endgroup$
    – joriki
    Oct 24 '11 at 23:13
  • $\begingroup$ @Greg: The answer to OP's question is probably a mixed strategy which is not found by the exhaustive search that you describe. $\endgroup$
    – opt
    Oct 24 '11 at 23:15
  • 2
    $\begingroup$ @Mr_CryptoPrime: That is like doing a simulation to see if rock or paper or scissors is best. The underlying problem is not too tricky but it was subtle enough to get a Nobel prize. $\endgroup$
    – opt
    Oct 24 '11 at 23:35
  • 1
    $\begingroup$ @Mr_CryptoPrime: I think you're missing the point that opt is making. You speak of "all possible strategies" and "every possibility", but you never define what you consider a strategy. The sort of strategies that you and Greg are considering are called "pure strategies". In a game like rock, paper, scissors, every pure strategy is dominated by another pure strategy, and the "best" strategy, in a certain sense, is a mixed strategy. Taking only pure strategies into account and trying to find "the best one" simply makes no sense for such games. (You can find all these terms on Wikipedia.) $\endgroup$
    – joriki
    Oct 25 '11 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.