[Solved]: Number of winning combination in Nim

Problem Detail: 

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.

Asked By : Kaidul Islam

Answered By : sashas

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57980

 Ask a Question

 Download Related Notes/Documents