prachi jain prachi jain

Nim is a famous game in which two players take turns removing items from distinct piles. During each turn, a player must remove one or more items from a single, non-empty pile. The winner of the game is whichever player removes the last item from the last non-empty pile.
Now, For each non-empty pile, either player can remove zero items from that pile and have it count as their move; however, this move can only be performed once per pile by either player.
Given the number of items in each pile, determine who will win the game; Player 1 or player 2. If player 1 starts the game and both plays optimally.

Approach:
Grundy number for each pile is calculated based on the number of stones.To compensate the zero move we will have to modify grundy values we used in standard nim game.
If pile size is odd; grundy number is size+1 and
if pile size is even; grundy number is size-1.
We XOR all the grundy number values to check if final Grundy number(G) of game is non zero or not to decide who is winner of game.

Explanation:
Grundy number of a state is the smallest positive integer that cannot be reached in one valid move.
So, we need to calculate mex value for each n, bottom up wise so that we can induce the grundy number for each n. where n is the pile size and valid move is the move that will lead the current player to winning state.

Winning state: A tuple of values from where the current player will win the game no matter what opponent does. (If G!=0)
Losing state: A tuple of values from where the current player will loose the game no matter what opponent does. (If G=0)

prachi jain

prachi jain Creator

(No description available)

Suggested Creators

prachi jain