Grundy numbers
The Grundy number of a game state is mex({g1, g2,…, gn}).
where g1, g2,…, gn are the Grundy numbers of the states to which we can move, and the mex function gives the smallest non-negative number that is not in the set.
For example:
mex({0,1,3}) = 2. If there are no possible moves in a state, its Grundy number is 0, because mex(Ø) = 0.\
For example in the state graph:
The Grundy numbers are as follows:
The Grundy number of a losing state is 0, and the Grundy number of a winning state is a positive number.
The Grundy number of a state corresponds to the number of sticks in a nim heap. If the Grundy number is 0, we can only move to states whose Grundy numbers are positive, and if the Grundy number is x > 0, we can move to states whose Grundy numbers include all numbers 0,1,…, x−1.
As an example:
Example: consider a game where the players move a figure in a maze.
- Each square in the maze is either a floor or a wall.
- On each turn, the player has to move the figure some number of steps left or up.
- The winner of the game is the player who makes the last move.
The following picture shows a possible initial state of the game, where @ denotes the figure and # denotes a square where it can move.
The states of the game are all floor squares of the maze. In the above maze, the Grundy numbers are as follows:
Thus, each state of the maze game corresponds to a heap in the nim game. For example, the Grundy number for the lower-right square is 2, so it is a winning state.
We can reach a losing state and win the game by moving either four steps left or two steps up.
Note that unlike in the original nim game, it may be possible to move to a state whose Grundy number is larger than the Grundy number of the current state.
However, the opponent can always choose a move that cancels such a move, so it is not possible to escape from a losing state.
Game Theory
Game Theory is a topic in competitive programming that involves a certain type of problem, where there are some players who play a game based on given rules and the task is often to find the winner or the winning moves. Game Theory is often asked in short contests with a mixture of other topics like range querying or greedy or dynamic programming.
Game Theory for Competitive Programming
- Objectives Game Theory for Competitive Programming:
- 1. Game states:
- 2. Winning and Losing states:
- 3. Nim game:
- 4. Misère game:
- 5. Sprague–Grundy theorem:
- 6. Grundy numbers:
- 7. Subgames:
- 8. Grundy’s game:
- Practice Problems on Game Theory