3
$\begingroup$

I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are possible. like [1, 2, 4, 3, 490], [100, 100, 100, 100, 100], [100, 200, 100, 100], [0, 200, 200, 50, 50] and so on. So basically there are stones^piles combinations possible. Among these, some will yield Xor > 0 and considered as winning possible.

My question is - how many winning initial positions are possible for given stones and piles? Instead of checking all possible combinations(which is impossible for larger inputs), is there any smart way to solve this?

This is not a homework or programming contest problem.

$\endgroup$
  • $\begingroup$ what can be the maximum number of stones and piles ? $\endgroup$ – sashas May 28 '16 at 11:14
  • $\begingroup$ Also can each pile have stones stones or is it the total number ? $\endgroup$ – sashas May 28 '16 at 11:18
  • $\begingroup$ Suppose maximum piles 10 and stones 300. No, no piles can have stones stones. But some piles can be empty. $\endgroup$ – Kaidul Islam May 28 '16 at 11:21
3
$\begingroup$

I assume there are k piles and each pile can have stones in the range [0,n]. Then we can find the losing positions ( you can subtract from total to get no. of winning positions ) using dynamic programming. Let the number of bits in binary representation of n be b. We take a 2-D array called dp of size $kx2^b$, where dp[i][j] denotes number of ways of assigning no. of stones to first $i$ piles such that xor of no. of stones in these first $i$ piles is $j$. It is easy to see that no. of losing positions is dp[k][0]. Now what's left is to come up with the recurrence relation ( I leave the base cases for you to come up with ).

           // take care of the base case  
           for i in range 1 to k:
               for j in range 0 to 2^b:
                   dp[i][j] = 0
                   for m in range 0 to 2^b:
                       // first i piles have nim-sum j
                       // ... if first i-1 piles have nim-sum m in the last
                       // ... pile we keep (m xor j) stones
                       dp[i][j] = dp[i][j] + dp[i-1][m]

EDIT
If $k$ piles in total have $n$ stones , you can again solve it by dynamic programming , but this time keeping a 3-D dp array of size $k$x$2^b$x$n$, where dp[x][y][z] means number of arrangements of first x piles having in total z stones and the nim-sum being y. Although I point it out that this method would be feasible only for small values of $k$ and $n$ ( in the order of few hundreds ). Following is a pseudo code ( again take care of base cases, if you have problem with them you could comment )

            // take care of base cases
            // our answer would be ( no. of losing ) positions = dp[k][0][n]

            for i in range 1 to k:
                for j in range 0 to 2^b:
                   for l in range 0 to n:
                      dp[i][j][l] = 0
                      for m in range 0 to l:
                            dp[i][j][l] = dp[i][j][l] + dp[i-1][m^j][l-m]

Clearly the above method works for small $k$ and $n$ ( you can reduce the memory, which I leave up to you to figure out ).

$\endgroup$
  • $\begingroup$ Thanks :) Can you give some more insight on case where k piles have total n stones? May be some pseudo code will be better. $\endgroup$ – Kaidul Islam May 28 '16 at 18:10
  • $\begingroup$ sure, I will add it. $\endgroup$ – sashas May 28 '16 at 18:22
  • 1
    $\begingroup$ I've solved it using top-down approach with memorisation using 3 state dp[PILE_MAX][XOR_MAX][REST_STONE_MAX] as you shown. I wrote the recursive function yesterday but overlooked that there are some overlapping structure. Thank you :) $\endgroup$ – Kaidul Islam May 28 '16 at 18:59
2
$\begingroup$

(added) As I now realise, you are asking for the number when the total number of stones is given.

It seems to be easy to count the number of loosing positions when the maximum number of stones in each pile is a power of two (minus one). Remember that a postion is loosing if the nim-sum of all the piles is zero, that is xor-ing all the bits will give $0$ at each bit position. So if there are $k$ piles each with at most $2^n-1$ stones, for each bit position, half of the initial positions xor's to $0$. So for each of the $n$ bit positions there are $2^k$ possible combinations for the $k$ piles. Half of these, $2^{k-1}$ xor to zero. This is to be combined to for each bit position, so ${(2^{k-1})}^n$. The total number of initial positions is ${(2^{k})}^n$.

For an arbitrary number of stones there is not such a nice formula, I am afraid.

$\endgroup$
  • $\begingroup$ Thanks! Great Insight :) And what the rules for any n, not only for power of 2? $\endgroup$ – Kaidul Islam May 28 '16 at 10:11
  • $\begingroup$ I believe that the OP is fixing the total number of stones, not the maximum number of stones per pile. $\endgroup$ – Yuval Filmus May 28 '16 at 13:49
  • $\begingroup$ @YuvalFilmus Thanks, you are right. Don't see any fast solution to that one. $\endgroup$ – Hendrik Jan May 28 '16 at 20:42

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.