This blog intends to give you a kickstart with game theory and it'll cover all the core concepts of Combinatorial game theory with some insights. If you're new, game theory studies behavior of games, most commonly answering which player will win the game in an optimal gameplay.

Contents:

1. Intro
2. Combinatorial games
3. Game States
4. The Game of Nim
5. Sprague Grundy theorem
6. Solving Games and Coding

Combinatorial Games

Combinatorial Game theory studies a special class of games, as the name suggests. A combinatorial game has the following properties:

• Two-Player: The game is played between two players, each alternatingly taking turns.
• Perfect Information: Both Players always have complete knowledge about the game state and all rules.
• No Randomness: The game is completely determined by the player's moves only.
• Deterministic Outcome: The game will end in finite moves, making one of the players win. (We will be ignoring Draw in this discussion as handling that will be trivial.)

Before we move forward, there are a few important terminologies we should know.

Partiality: If the available moves depend on which players move it is. e.g. Chess is an partial game, as one player can only move white/black pieces.

Normal Games: The game is Normal if the last person to make the move wins. If the last person to make a move loses, it's a Misère game.

Game States

A game state is the complete information of some game, at some point in time. When a player makes a move, some game state transits to another game state. As we want to know who'll win the game, Game states are generally classified into two types.

1. N-state/Winning state: If the player at the current state wins the game (if he plays optimally), then the game is at a N-state. where N stands for the Next player to move wins.
2. P-state/Losing state: If the player at the current state loses the game(if the other player plays optimally), it's a P-state. P here stands for Previous player wins.

It's time for our first example, here's the setup. There is a pile of stones, and the player, in alternate turns, takes one or two stones from the pile. The one taking the last stone wins.

Here, the number of stones left represents the game state. 8 (for 8 stones left) is a game state.

A game state is either winning or losing. But 2 critical observations that you must understand is

1. Every move from a losing state leads to a winning state.
2. At least one move from a winning state leads to a losing state.

Realize why, because it's the single most important thing in today's blog. Let's say A and B are playing. If it's As turn, and the game is in winning state, there will be at least one move(for A) that takes the game to a losing state(for B). It is also noteworthy that, that move from a winning state to a losing state is the optimal move. Again, B will be losing after A makes the move, and every move(for B) will take the game to a winning state(for A).

Game of Nim

There is a reason why Game of Nim is found everywhere. That is, Every two-player Normal Impartial combinatorial game can be reduced to a game of (single pile) Nim. so if we understand the behavior of game of Nim, we understand all two-player combinatorial normal games. Let's go through the setup:

there are k piles of stones each containing some n1, n2 ... nk stones. In alternate turns, the player removes any nonzero number of stones from a pile. The player taking the last stone wins.

K=1 or single pile case: It should be easy to see, that any nonzero number of left stones is a winning state. we consider an empty pile, or 0, a losing state.

K=2 case: I will just say n1=n2 is a losing state, otherwise it's a winning state. why? finding that intuitively is left as an exercise.

k>2 cases: the state is losing iff the Xor sum all ni is 0. Explanations coming in the next section.

The Sprague Grundy theorem

Remember we knew that, any two-player normal combinatorial game can be reduced to a single pile Nim? This theorem explains how, but first, we need to learn what a Grundy number is.

Grundy Number: of a state P, G(P) represents the pile size of equivalent state P' if the game was reduced to a single pile. Similar to single pile Nim, G(P)=0 means it is a losing position, and G(P)!=0 means the game is winning.

Now, there are 3 statements of this theorem: 1. All terminal positions are losing positions; meaning you lose if you can't make a move. 2. For any state P in an impartial game, the Grundy number G(P) is calculated as the MEX of the Grundy numbers of all states that can be reached in one move from P; 3. The Grundy number of a sum of independent games is the bitwise XOR of the Grundy numbers of the individual games. (this explains the k>2 case of Nim)

I recommend you take some time to sink these in, there will be examples later in the blog. The proofs of these should be easy to find, the research is on you if you are interested. Keep in mind that although statement 1 and 2 works for misère games too, statement 3 does not. And, there is no general way to combine more than one independent misère games, which is a reason why misère games are so uncommon in problems.

Solving and coding

First of all, considering game-states as nodes, and moves as edges, every combinatorial game can be modeled as a Directed Acyclic Graph. So, it is always possible to form a DP like we do on DAGs; and most generally that is the case. We start from the terminal states, and DP by using the two observations we learned in "Game States". If some cells remain undetermined, that's a draw case.

It is a good time to run through a complete example. Let's consider a game, which is a hybrid of our two previous examples. there are k piles, and each player, in alternate turns, can take 1 or 2 stones from any pile. The player taking the last stone wins.

This is the generalized approach. It is easy to see the game is a combination of k independent single pile cases. Thus, if we can calculate the Grundy numbers for a single pile, we can Xor sum all k Grundy numbers to find the Grundy number for the complete game state.

In the terminal position, 0 stone left has a Grundy number 0. Let's consider for 1; the only state we can go from 1 is 0, Thus the set of all Grundy numbers reachable from one is {0}. The MEX of this set is 1, giving G(1) = 1; For 2, the set is {0, 1} and G(2) = MEX of {0, 1} = 2.

It is not unusual to see repeating patterns, and these can be generally proved through induction, But it is not guaranteed that such a pattern will always exist.

Let's now consider 3 piles, each with 4, 5, and 7 stones respectively. What's the Grundy number of this entire state? from the 3rd statement of Sprague Grundy theorem, it is G(4)^G(5)^G(7) = 1 ^ 2 ^ 1 = 1; which is nonzero making it a winning state.

What about the optimal move? If you've understood all so far, you should realize our game with {4, 5, 7} stones is equivalent to a Nim game with {1, 2, 1} stones. the optimal move in this Nim game is taking 2 stones from a pile with 2 stones (Basically you remove some stones so that the Xor-sum becomes zero; Calculating this needs a bit more explanation but it's easy to do the research and code). Removing two stones means changing the middle pile, and the move is 2 stones -> 0 stones. Thus, in our actual game, the move will be taking the middle pile to a state with the Grundy number zero; or 5 stones -> 3 stones.

To design solution for a problem, I like to use this mental model:

1. Work with independent components, as Sprague Grundy can be applied later.
2. mentally sort per the game timeline: let's say from end to start. It's similar to how we calculated Grundy numbers from 0 to n.
3. Figure out the terminal states.
4. Work out how second last move transits into terminal state, and determine P-states and N-states, backwards; like a DP.

I'll end the blog with two homework.

1. Grundy's Game
2. CF1965A

PS: For better understanding, some terms are used a bit more flexibly than what they formally mean. It's the first time I'm writing a blog, so any constructive criticism or corrections will be much appreciated.