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})
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.
 A: 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]]

A: These are known as Blotto games. Here's a relevant, previous StackOverflow question.
A: 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.
