# Help determining best strategy for game?

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})

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.

-
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. – Yuval Filmus Oct 24 '11 at 22:35
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. – Mr_CryptoPrime Oct 24 '11 at 22:38
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. – Chris Taylor Oct 24 '11 at 22:40
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? – Brian M. Scott Oct 24 '11 at 22:42
@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? – Mr_CryptoPrime 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]]

-
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? – Mr_CryptoPrime Oct 24 '11 at 23:04
Thanks opt, I will have to print this paper out and read it when I get a chance. – Mr_CryptoPrime Oct 24 '11 at 23:27

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

-
Thanks for the additional references! – Mr_CryptoPrime 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.

-
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 – Mr_CryptoPrime Oct 24 '11 at 23:06
When you say "strategy", you mean "pure strategy"? – joriki Oct 24 '11 at 23:13
@Greg: The answer to OP's question is probably a mixed strategy which is not found by the exhaustive search that you describe. – opt Oct 24 '11 at 23:15
@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. – opt Oct 24 '11 at 23:35
@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.) – joriki Oct 25 '11 at 1:15