Please explain me the Winning Strategies of Nimble Game of Game Theory and how it is similar to trivial Nim Game ?
1 Like
I also want to learn it.
Can you post the rules of the “Nimble Game”?
How are the rules different from Nim?
Please elaborate.
The Game of Nim
The most famous mathematical game is probably the Game of Nim. This is the game that you will probably encounter the most times and there are many variations on it, as well as games that can be solved by using the knowledge of how to play the game. Usually you will meet them as Division I 1000 pointers (though hopefully your next encounter will seem much easier). Although these problems often require a clever idea, they are usually very easy to code.
Rules of the Game of Nim: There are n piles of coins. When it is a player’s turn he chooses one pile and takes at least one coin from it. If someone is unable to move he loses (so the one who removes the last coin is the winner).
Let n1, n2, … nk, be the sizes of the piles. It is a losing position for the player whose turn it is if and only if n1 xor n2 xor … xor nk = 0.
How is xor being computed?
6 = (110)2 1 1 0
9 = (1001)2 1 0 0 1
3 = (11)2 1 1
--------
1 1 0 0
xor of two logic values is true if and only if one of them is true and the second is false
when computing xor of integers, first write them as binary numbers and then apply xor on columns.
so xor of even number of 1s is 0 and xor of odd number of 1s is 1
Why does it work?
From the losing positions we can move only to the winning ones:
– if xor of the sizes of the piles is 0 then it will be changed after our move (at least one 1 will be changed to 0, so in that column will be odd number of 1s).
From the winning positions it is possible to move to at least one losing:
– if xor of the sizes of the piles is not 0 we can change it to 0 by finding the left most column where the number of 1s is odd, changing one of them to 0 and then by changing 0s or 1s on the right side of it to gain even number of 1s in every column.
Examples:
Position (1, 2, 3) is losing because 1 xor 2 xor 3 = (1)2 xor (10)2 xor (11)2 = 0
Position (7, 4, 1) is winning because 7 xor 4 xor 1 = (111)2 xor (10)2 xor (1)2 = (10)2 = 2
I hope you got it.
1 Like
Here are some good resources:
2)http://www.geeksforgeeks.org/combinatorial-game-theory-set-3-grundy-numbersnimbers-and-mex/
2 Likes
@kashyap2108 first you need to be familiar with the game of Nim. @shubhiks has provided two excellent resources for that.
Moving forward to the problem, with a little bit of observation we can realize that the “Nimble” game is exactly the Nim game in another form. In Nim we can pick any one of many heaps and choose to reduce its value to some value less than its current value. In Nimble we can pick a coin and choose to reduce its index to some index less than its current index. They are the exact same thing. So each coin at position i in Nimble corresponds to a Nim heap of size i.
To determine who wins in Nim we calculate the xor-sum of all the heaps. Similarly, here we need to calculate the xor-sum of each coin’s index. If this value is non-zero, the first player wins, and if not the second player wins.
I hope this explanation will be sufficient for you to solve the problem 
1 Like