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
    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.2011-10-24
  • 0
    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.2011-10-24
  • 2
    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.2011-10-24
  • 1
    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?2011-10-24
  • 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
    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?2011-10-24
  • 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
    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!)? Haha2011-10-24
  • 0
    When you say "strategy", you mean "pure strategy"?2011-10-24
  • 0
    @Greg: The answer to OP's question is probably a mixed strategy which is not found by the exhaustive search that you describe.2011-10-24
  • 0
    @opt This answer is actually sufficient. I don't need to prove anything. I just want to test every possibility against all other possibilities, several times, determine which show most potential and retest. E.g. testing a coin flip 1,000 times, it converges to 50% as you approach infinity. This is what I was initially looking for. Not sure it is feasible? Thanks for your input though opt, it was also helpful.2011-10-24
  • 2
    @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.2011-10-24
  • 0
    Studying rock-paper-scissors got a Nobel prize, interesting...Yes, I suspect that a good number of strategies will be equally probable for winning and it probably comes down to luck and psychology, much like r-p-scissors, but this is just a "for fun" project, so as long as I learn one or two things it's a success, n'est pas? :)2011-10-24
  • 1
    @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.)2011-10-25
  • 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