Game states

Objectives Game Theory for Competitive Programming:

...

1. Game states:

Here we will focus on two-player games that do not contain random elements. Our goal is to find a strategy we can follow to win the game no matter what the opponent does if such a strategy exists.  Game theory or combinatorics game theory in which we have perfect information (that is no randomization like a coin toss) such as game rules, player’s turn, minimum and maximum involved in the problem statements, and some conditions and constraints. There will be three possible cases/ state win, loss or tie. A terminal condition is well-defined/ specified clearly.E.g. player who picks the last coin will win the game, or a player who picks the second last time coin will win the game or something like that. It is assumed that the game will end at some point after a fixed number of moves. Unlike chess, where you can have an unlimited number of moves possible especially when you are left with the only king, but if you add an extra constraint that says “game should be ended within ‘n’ numbers of moves”, that will be a terminal condition. This is the kind of assumption a game theory is looking for. It turns out that there is a general strategy for such games, and we can analyze the games using the nim theory. Initially, we will analyze simple games where players remove sticks from heaps, and after this, we will generalize the strategy used in those games to other games....

2. Winning and Losing states:

Let us consider a game where there is initially a heap of n-sticks. Players A and B move alternately, and player A begins. On each move, the player has to remove 1, 2, or 3 sticks from the heap, and the player who removes the last stick wins the game....

3. Nim game:

A winning state is a state where the player will win the game if they play optimally, and a Losing state is a state where the player will lose the game if the opponent plays optimally. It turns out that we can classify all states of a game so that each state is either a winning state or a losing state...

4. Misère game:

The nim game is a simple game that has an important role in game theory because many other games can be played using the same strategy.First, we focus on nim, and then we generalize the strategy to other games.There are n heaps in nim, and each heap contains some number of sticks.The players move alternately, and on each turn, the player chooses a heap that still contains sticks and removes any number of sticks from it. The winner is the player who removes the last stick....

5. Sprague–Grundy theorem:

In a misère game, the goal of the game is the opposite, so the player who removes the last stick loses the game.It turns out that the misère nim game can be optimally played almost like the standard nim game.The idea is to first play the misère game like the standard game, but change the strategy at the end of the game....

6. Grundy numbers:

The Sprague–Grundy theorem generalizes the strategy used in nim to all games that fulfil the following requirements:...

7. Subgames:

The Grundy number of a game state is mex({g1, g2,…, gn})....

8. Grundy’s game:

Next, we will assume that our game consists of subgames, and on each turn, the player first chooses a subgame and then move into the subgame. The game ends when it is not possible to make any move in any subgame.In this case, the Grundy number of a game is the nim sum of the Grundy numbers of the subgames.The game can be played like a nim game by calculating all Grundy numbers for subgames and then their nim sum....

Practice Problems on Game Theroy:

Sometimes a move in a game divides the game into subgames that are independent of each other. In this case, the Grundy number of the game is mex({g1, g2,…, gn}),...