Hello, this short blog is meant to provide the motivation behind the things we do in solving Game Theory problems. There are already many wonderful resources online for learning the basics to combinatorial game theory, but the intention I have for this guide in particular is to try to derive these properties from scratch and hopefully make them more intuitive. Why does XOR work for NIM? Why does mex provide the Grundy numbers? When it was taught to me, it was more or less just as 'magic' to memorize, so once I got a grasp of the intuition behind it, I decided I should record my thoughts into a blog.
If you're already familiar with Combinatorial Game Theory and just wanted some intuition, I recommend skipping straight to the part about NIM and Grundy Numbers.
What is a combinatorial game?
Combinatorial games usually have the following general pattern in most problems I've seen:
There are players. The players want to win.
There are game states. Think of all the possible valid positions in tic-tac-toe or chess. The state is basically 'what the game board looks like right now', so to speak.
There are moves. Players, on their turn, have some set of moves which they can choose from to transition from one game state to another.
Of course, players want to win — but how? Some subset of the game states are marked as goal states. Your objective as the player is to choose some series of moves that will eventually end up with you at the goal state.
That all seems awfully abstract, so let's formalize it with a concrete example. I've been using tic-tac-toe as an example, so let's go with that. In tic-tac-toe, there are two players. The game states would be our $$$3\times 3$$$ grid which may have some of its squares filled up with Xs or Os, and the goal states would be those grids that have 3 Xs (or Os) in a row. A move here would be the player drawing an X (or an O) in one of the cells, transitioning from one grid configuration to another.
However, we usually won't be talking about games like tic-tac-toe in combinatorial game theory. We usually have the following assumptions as well:
There will only be 2 players playing a game. The game consists of these two players taking turns making some move.
Both players will play optimally. Imagine they are supercomputers who can examine every possible timeline that results from every possible move they could make. If they find at least one timeline where they win, they will always choose that one and make that move.
The games are impartial, which means the set of moves each player can make is identical to one another. Chess and tic-tac-toe are instead known as partisan, because the pieces have 'sides' to them (black or white, X or O, etc).
The games are finite. An end state (win or lose) will be achieved after a finite number of moves.
The games are deterministic. There is no probability involved (unlike say in Poker or roulette).
The Game is a Graph
One way that I find it helpful to model the games in my head is as a directed graph. Here, the game states will be your vertices, and the moves are your edges; there exists a directed edge from $$$u$$$ to $$$v$$$ if there is a move that lets you transition from game state $$$u$$$ to game state $$$v$$$.
We said earlier that players play optimally, meaning that if there exists at least one move which will eventually result in them winning, then they will take it. They will only ever lose if they've been checkmated — no matter what they do, all the possible moves they could take will lead them to a loss. If there exists a sequence of moves that allows a player to win from their current state, then that is called a winning strategy.
As such, we can label each of our nodes as either win states or loss states. Win states are those with winning strategies. Loss states are those where no matter what you do, you're always going to end up losing. A state is a win state if and only if it points to at least one loss state. A state is a loss state if and only if all of the states that it points to are win states. Intuitively, this should make sense as a translation of what we were saying earlier.
This
