### Shisuko's blog

By Shisuko, history, 3 years ago,

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 make them more intuitive. Why does XOR work for Nim? Why does mex produce the Grundy numbers? When it was taught to me, it was more or less just as 'magic' to memorize, but now I think I have a decent understanding of why they are true, so now that I have a grasp of the intuition behind it, I decided I should record my thoughts into a blog.

# Nim games

Suppose we are playing a Nim game. As we know, Nim games usually follow this sort of template:

• There are $n$ piles of stones, and each pile contains $p_1, p_2, p_3, \cdots p_n$ stones, where each of the $p_i$ is some nonnegative integer. This collection of piles defines our game state.

• There are two players who take turns removing stones. The current turn player may remove as many stones as they wish, so long as all the stones come from the same pile. More formally, they choose a pile $i$ and a number of stones to remove $0 < s \leq p_i$, then replace $p_i$ with $p_i-s$. You cannot pass your turn doing nothing. Then, it is the other player's turn to remove stones, and so on.

• The game ends when there are no stones left on the board. The winner is the one who took the last stone; alternatively, the loser is the first one who cannot take a stone on their turn.

• The game state is called a winning state if there exists a winning strategy for it. That is, the current turn player has some series of moves such that they will always be able to win, no matter what the other player does---a checkmate, so to speak. Or, more specifically, think of when someone would say that white can mate in 5 moves. This means the game of chess will inevitably end in a checkmate in 5 moves; even if the board is not literally in a checkmate position yet, there is nothing that black can do to prevent it (assuming white plays optimally). Conversely, a game state is called a losing state if no matter what the current turn player does, their opponent has a winning strategy to eventually win.

The question then usually goes something like this: Given an initial game state $p_1, p_2, p_3, \cdots p_n$, is the first player going to win, or the second player, assuming both play perfectly? I.e., is the initial game state a winning or a losing state?

There exists a fairly standard $O(n)$ formula to solving the Nim game, though I'm not sure how many people actually know why it is true. While I am normally against memorization without proof, it is far, far easier to explain the actual strategy compared to the effort needed to prove that it works, and understanding why it works doesn't really add too much insight in the contest problems themselves, so I can see why most people don't bother with the proof. But, we are nerds, and we like knowing why the things we do work, and so here is my attempt to naturally and intuitively derive for ourselves what this magic formula is.

You can only take stones from one pile at a time, so it seems like a good idea to get some information from each pile, then find some way to compose that information together to describe the board state as a whole. It's rather mathy, but as an analogy, think about multiplicative functions---to evaluate a multiplicative function at $n$, we decompose $n$ into its prime powers, more easily evaluate the function at each prime power $p^k$, then compose the answers for each $p^k$ together to get the answer for $n$.

So, what we will do is:

• For each game state $g$, let us assign to it some integer "Nim-value" $G$ which tells us whether this is a winning state or a losing state.

• Given two game states $a$ and $b$, let $a+b$ be the game state that is simply the piles of $a$ together with the piles of $b$. If their Nim-values are $A$ and $B$ respectively, then define $A\oplus B$ to be the Nim value of the game state $a+b$. We are assuming (and hoping) that there does in fact exist some operator that allows us to compose together the Nim-values of different games together easily.

Now, let's tackle the simplest possible game---one that consists of a single pile with $p$ stones in it.

• Intuitively, since the only information that distinguishes the piles from one another is the number of stones in them, let's say that the Nim-value of a game that consists of only a single pile is $p$.

• We see that a single pile is a winning state if $p>0$, and is a losing state if $p=0$. That's something we'd like to see reflected in the Nim-values as well---a Nim-value $G$ corresponds to a winning game state when $G>0$, and corresponds to a losing game state when $G=0$.

Next step, let's find a way to compose Nim-values together with this operator $A \oplus B$. We should notice the following properties about it though:

• $(A \oplus B) \oplus C = A\oplus(B \oplus C)$, and $A \oplus B = B \oplus A$. That is to say, $\oplus$ is associative and commutative. Since we're just combining the piles together, order shouldn't really matter, so this should be apparent.

• $A \oplus 0 = A$. That is to say, the identity for this operator is 0. We obviously want this to be true since if you place an empty pile next to an existing game, you should still effectively have the same game after all.

• $A \oplus A = 0$. That is to say, the inverse of each game state is itself. Think about why this is true---suppose we have two piles that each have $p$ stones in them. The second player always has a winning strategy here, which is to just mirror the first player's move! For some generic game state $A$, note that the game state $A\oplus A$ guarantees a respective 'mirror image' for each pile; if the first player makes a move on some pile, the second player can always take the same number of stones from the 'mirror image' of that pile. Thus, the first player will always be the one to run out of moves first, therefore this is a losing state, and therefore $A \oplus A = 0$.

You'll notice that together, these properties define a commutative group over the nonnegative integers! In fact, take a look at that last property in particular, that $A \oplus A = 0$. The inverse of every element is itself, i.e. every non-zero element in the group has order 2. This is actually a huge hint because it turns out the only family of groups that have this property is the group with the set $\{0,1\}$ and the operation of addition modulo 2, or some ordered $n$-tuple of $\{0,1\}$ with the operation of addition modulo 2 done between each corresponding component (or some subset of it, up to isomorphism); aka, the logical XOR and the bitwise XOR. This claim is stated without proof.

Bingo! We have a winner. It seems our operator $A\oplus B$ is just the bitwise XOR of the two Nim-values. In fact, since XOR is just addition modulo 2, in literature, the Nim-values are usually called the Nim-sums of the game state. However most of what I gave consists of heuristics and intuitions---now that we have this operator as a candidate, let's try to formally prove that our magic formula works.

Given a game of Nim whose current game state consists of $n$ piles with $p_1, p_2, p_3, \cdots, p_n$, then the current game state is a winning state if the Nim-sum $p_1 \oplus p_2 \oplus p_3 \oplus \cdots \oplus p_n$ is non-zero, and a losing state if it is equal to zero, where $\oplus$ is the bitwise XOR operation.

1. The empty game is a losing state with Nim-sum 0. This follows from our observations earlier.

2. If the current Nim-sum is 0, then any move will make it non-zero. Recall that a move replaces $p_i$ with $p_i-s$. So, keeping in mind that the XOR-inverse of each integer is itself, that means the new Nim-sum after a move is made becomes $(p_1 \oplus p_2 \oplus p_3 \oplus \cdots \oplus p_n) \oplus p_i \oplus (p_i-s)$; we remove $p_i$ from the Nim-sum, then add in $p_i-s$. But, if the current Nim-sum was already 0, then this is just $p_i \oplus (p_i-s)$, and this is only equal to 0 when $p_i=p_i-s$. But, the rules state you have to always take at least one stone on your turn, so $s \neq 0$, and it is impossible for this new Nim-sum to still be 0.

3. If the current Nim-sum is non-zero, then there always exists a move to make it equal to 0. Suppose the current Nim-sum is $N>0$. We need to choose $p_i$ and $s$ such $p_i \oplus (p_i-s)=N$, subject to the constraint that $0 < s \leq p_i$. Consider the fact that $N$, since it is nonzero, must have a greatest significant bit, the $g$th bit. Furthermore, at least one of the piles $p_i$ will have the $g$th bit as a 1 as well; if all the piles had a 0 there, then it couldn't have been the greatest significant bit of their XORsum after all. So, we choose one such pile as our $p_i$, and we construct our $p_i-s$ as the following:

• All bits greater than the $g$th bit we keep the same as $p_i$.

• The $g$th bit is set to 0.

• All bits less than the $g$th bit we make match those of $N \oplus p_i$.

Notice that this construction is always less than $p_i$, since we know their first difference is at the $g$th bit, therefore this is a valid choice of $p_i-s$, from which we can easily recover what the $s$ should be. We can see that the $p_i \oplus (p_i-s) = N$ because

• All bits in $N$ greater than the $g$th bit were already 0 (since the $g$th bit was defined to be the greatest significant bit). Then, we know that all bits in $p_i \oplus (p_i-s)$ greater than the $g$th bit are also 0, since that was how we constructed it.

• The $g$th bit in $N$ is 1, by definition as the greatest significant bit, and the $g$th bit in $p_i \oplus (p_i-s)$ is also 1, since it is 1 in $p_i$ and 0 in $p_i-s$.

• All bits in $p_i \oplus (p_i-s)$ less than the $g$th bit are guaranteed to match that of $N$, since $p_i \oplus (p_i-s) = p_i \oplus (p_i \oplus N) = N$ in this range.

So, $N \oplus p_i \oplus (p_i-s) = 0$, and thus the new Nim-sum after the move has become 0.

The best way to convince yourself and see that this does in fact set the new Nim-sum to 0 is to write it out yourself and try it with some concrete values.

Now, with these tools in hand, we can see that:

• If the current turn player has a zero state, they have no choice but to 'disturb' it into a nonzero state.

• The next player then, given a nonzero state, always is able to 'restore' it back into a zero state.

• Thus, if the players know what they are doing, the first player is helpless if the Nim-sum is 0. The second player can always ensure that the Nim-sum is 0 if and only if it is the first player's turn. There are only a finite number of moves in a game of Nim (obvious, but you can prove it by induction, using the fact that pile sizes only get smaller). Eventually, the game ends when the last stone is taken, meaning the Nim-sum is 0. So, we know that it is the first player's turn when the game ends, thus the second player can ensure that the first player loses.

• Similarly, if the current turn player has a nonzero state, they can restore it to a zero state and pass the board over to the second player, who by our logic, must be the loser, thus the first player is the winner.

This proves our theorem, and what's nice is that it actually tells us how to construct the winning move (if one exists) for any given board state.

# Extensions on NIM and Grundy Numbers

No self-respecting problem-setter would ever give just a vanilla Nim game, though, now that it has become well-known. Usually, there will be some variation on the rules somehow. Consider the following, for instance.

Say you are similarly given a game state of $n$ piles with stones $p_1, p_2, p_3, \cdots p_n$. The normal rules of Nim apply, except there is an extra move: instead of removing stones from a pile, the current turn player may choose to spend their turn adding any number of stones to a pile instead. They can add as many stones as they want, so long as, again, they are all added to the same pile. Assume this addition move may only be done a finite number of times per player.

It turns out that... this is exactly the same as normal Nim! Why? Assume that the current turn player is in a losing state, under the normal set of Nim rules. If they add $s$ stones to some pile, the other player can just spend their turn removing $s$ stones from that same pile, effectively undoing the last move, and then the losing player is back exactly where they started. A winning player, meanwhile, can just play the game like normal Nim, only deviating from the strategy to undo any additions the opposing player makes, as necessary. Since the game will still end after a finite number of moves (and this is important), the winning player can be determined the same way as with normal Nim.

Other games though are not quite as simple. A common tweak is putting a limitation on the number of stones you can get from a pile. What if there is a condition that you can only take a perfect square number of stones from a pile? What if you can take no more than half the stones in a pile?

Let us turn back to our original strategy---decompose the game state into several piles, find some property for each of the piles, then compose them again together to get the answer.

So, given only a single pile with $p$ stones, how do you know if it is a winning state or a losing state? Earlier, we simply operated on $p$, but we'll need something a bit more sophisticated here.

Let's reframe this as a directed graph. Let there be $p+1$ vertices in this graph, labelled $0$ to $p$. Each vertex corresponds to some game state, where its label indicates how many stones are in the pile at this state. Then, draw a directed edge from $u$ to $v$ if it is possible to transition from $u$ stones to $v$ with a valid move. For instance, if you may only take a square number of stones from the pile, then vertex 11 would have a directed edge to vertices 10, 7, and 2, since I could take 1, 4, or 9 stones from that pile. The terminal vertices---the ones with outdegree 0---are our loss states.

We could imagine solving this with DP then. Let the terminal vertices be, by definition, losing states. Then, if a vertex points to at least one losing state, it is a win (the current turn player takes that moves and puts the opposing player in a loss state). If a vertex only points to winning states, then it is a loss (the current turn player has no ways out). Assume there are no cycles in the graph, i.e. the game ends in a finite number of moves.

Let's take this a step further though and treat it like our Nim-values from earlier; instead of just assigning win/loss, let's assign some integer value to each vertex such that 0 is a loss and nonzero is a win. This is usually called the Grundy number, or more cutely, the Nimber of a pile. I will be using Grundy numbers because that's what I'm used to, but I think Nimber is an absolutely fantastic word.

Let $G(u)$ be the Grundy number of a pile with $u$ stones. The Grundy number of a terminal state is 0; otherwise, $G(u)$ is recursively defined as the minimum excludant of the Grundy numbers of all the states it points to. We usually write minimum excludant as mex, and it basically means "return the smallest nonnegative integer that is not in this set." Let's consider a basic example, such as the Nim game where you can only take a square number of stones from a pile. If there is a pile with 5 stones, then we can take $1^2=1$ stone and transition to a pile with 4 stones, or take $2^2=4$ stones and transition to a pile with 1 stone. So, $G(5)=mex(G(5-1),G(5-4))=mex(G(4),G(1))=mex(2,1)=0$. So, it turns out that a pile with 5 stones in it is a loss state (you can verify the values of $G(4)$ and $G(1)$ for yourself, but even without Grundy numbers, you should be able to see why 5 stones is a losing state).

How about when there are multiple piles though? Amazingly, we can apply the same strategy we did earlier for Nim, except on the Grundy numbers. The important Sprague-Grundy theorem states that these games are equivalent to playing Nim, but instead of getting the Nim-sum by taking the XOR of the piles, we take the XOR of their Grundy numbers.

Let's consider that square number Nim again. We see that the Grundy numbers for $0, 1, 2, 3, 4, 5, 6$ are $0, 1, 0, 1, 2, 0, 1$, respectively. You can verify this. Therefore, if we have a game state with piles of $1, 2, 3, 4, 6$ stones, the Nim-sum of this game is $G(1)\oplus G(2) \oplus G(3) \oplus G(4) \oplus G(6) = 1\oplus 0 \oplus 1 \oplus 2 \oplus 1 = 3$, which is non-zero, therefore the first player has a winning strategy.

Note that in our normal game of Nim, each state points to every state smaller than it (since taking any number of stones is a valid move). Therefore, $G(p)=p$, which is consistent with our results about the original Nim.

When I first learned this, I thought it was magic! But the helpful commenters over at the math subreddit helped give me this wonderful intuition. The mex function is so weird. What's that all about?

Basically, the mex function is a promise. The promise is that: if $G(p)=g$, then it means every integer from $0$ to $g-1$ is "accounted for" in the list of valid moves from $p$. Imagine that every pile in our game was transformed from having $p$ stones but with weird rules, to having $G(p)=g$ stones but with normal Nim rules. You can see that we can do this because in Nim, we can transition from a pile of size $p$ to any other pile of size less than $p$; in our transformed Grundy number world, the mex property guarantees that we can transition from our 'pile' of size $g$ to any 'pile' of size less than $g$. The mex encodes information about which states are available to us, and having access to every state from 0 to $g-1$ looks a lot like Nim. So, we use this transformed mex world to reframe our view of the directed graph---the list of states available to each state makes it analogous to a normal Nim pile, which we already know how to deal with.

However, unlike in Nim, it's possible to transition from a pile of size $g$ to a pile of size greater than $g$. Consider in the square number game earlier, if we have a pile of size 5 and we take away one stone, we end up with 4; in the transformed Grundy number world, we went from a pile of size 0 to one of size 2!

But not to worry, we already accounted for this! Remember we said that "Nim where you can add stones" is just the same as normal Nim. Suppose I started with a Grundy number of $g$, then after making a move I ended up with a larger Grundy number in the new pile. But, recall that the Grundy number of some state is the minimum excludant of all the states it can transition to; it's our promise from earlier. So, if we transition from $g$ to some larger number $h$, we have been promised that from $h$, we can visit any of the numbers from 0 to $h-1$. And, since $g<h$ we can always just transition back to $g$! Just like in our Nim-with-addition from earlier, we can always just undo any additions that the losing player might try.

Therefore, if we use Grundy numbers, Nim with any weird restrictions on the amount of stones we can take per pile can be reduced to Nim with addition, which itself can be reduced to normal Nim.

The complexity in these kinds of programming problems in contests usually then comes down to finding some efficient formula for the Grundy numbers. The Sprague-Grundy theorem is actually far more general, and says that any impartial combinatorial game is essentially Nim, due to the Grundy numbers. Why? Well, the argument in our proof would work with any graph, not just Nim-games with piles. Any game which can be represented as a DAG can also be formulated in terms of Grundy numbers, and thus Nim!

I hope this guide helped you understand where the XOR came from (the self-inverse property) and where the Grundy numbers being mex came from (mex is a promise). I was very fortunate to talk to people who gave me a better understanding of this, and I hope to share this knowledge with the community too :)

Edit: Here are some sample problems which use the idea of Nim and Grundy Numbers, in no particular order of difficulty. I know Project Euler don't like posting spoilers outside their discussion forums, but these problems are so blatantly about Game Theory that I hope it's okay.

(Non-comprehensive) Problems that use Nim and Sprague-Grundy:

https://projecteuler.net/problem=306

https://projecteuler.net/problem=310

https://projecteuler.net/problem=400

https://www.codechef.com/problems/FDIVGAME

https://onlinejudge.org/external/14/1482.pdf

• +173

 » 3 years ago, # |   +8 Auto comment: topic has been updated by Shisuko (previous revision, new revision, compare).
 » 3 years ago, # |   +10 This is a very good tutorial, I learned a lot and you should get more upvotes.
 » 3 years ago, # |   +8 Auto comment: topic has been updated by Shisuko (previous revision, new revision, compare).
 » 2 years ago, # |   +20 This needs more upvotes. Thank you for writing this!
 » 2 years ago, # |   0 Wonderful explanation
 » 2 years ago, # |   0 Auto comment: topic has been updated by Shisuko (previous revision, new revision, compare).
 » 2 years ago, # |   +13 Here is a list of problems for practicing (see game_theory). Excelent explanation!
 » 23 months ago, # | ← Rev. 2 →   0 This is simply one of the most beautiful blog i have ever come across. Thank you.
 » 23 months ago, # |   +5 Added to my list of all time favorites, thank you so much!
 » 23 months ago, # |   +8 awesome.
 » 23 months ago, # |   +14 This is an awesome explanation! I had previously been aware of the XOR solution, but I think the "mex" solution to solve Nim with restrictions on moves (like only perfect squares) is new to me and I think it's super cool. Thanks for the post!
 » 22 months ago, # |   0 Auto comment: topic has been updated by Shisuko (previous revision, new revision, compare).
 » 22 months ago, # |   +16 Do you happen to know some good CF exercises to practice this?
•  » » 22 months ago, # ^ |   +8 I learned this technique doing 1312F - Attack on Red Kingdom.
•  » » 22 months ago, # ^ |   0 I learned it from 305E - Playing with String
•  » » 22 months ago, # ^ |   0 I edited the post to add a problem list! That's something it should have had since the beginning.
 » 21 month(s) ago, # |   0 Auto comment: topic has been updated by Shisuko (previous revision, new revision, compare).
 » 20 months ago, # |   +6 Hi, I read your blog, and it addresses only NIM, which is not hard to understand.I still cannot understand how Grundy Numbers can be assigned to states of other games, and how to assign the concept of piles to various states of those other games.As an example, consider this (from CP-ALGORITHMS)-> CROSSES-CROSSES GAMEWhen I put a cross at an $i$ such that $2\leq i\leq n-1$, and assuming I have already calculated Grundy values for states $G(i-2)$ and $G(n-i-1)$, why on earth is the Grundy value of the whole state MEX of $G(i-2) \oplus G(n-i-1)$ for all such $2\leq i\leq n-1$? Can you please atleast provide an intuition for this? Why do we take XOR at all here? (if I can understand why we take XOR, MEX part is obvious from your blog).
•  » » 20 months ago, # ^ |   -7 I am also trying to solve this problem: 768E - Game of Stones.I just don't get how can XOR of all pile sizes being non-zero in THIS VERSION OF NIM can be equivalent to a winning state, and XOR of zero to a losing state. Nothing in the editorial and comments.
•  » » » 20 months ago, # ^ |   +5 Notice that in the entire discussion about the Grundy numbers, the fact that there are piles had actually not come up. You could use the same argument to assign Grundy numbers to any DAG and everything still holds.
•  » » » » 20 months ago, # ^ |   0 But i do not ask about the nodes in the DAG representing game states and there relation to other nodes, but about the games states itself. Consider a game state with several piles. How do you show that in any variation of nim, for example as in problem E linked above, XOR of piles determine the outcome of the game state.
•  » » » » » 20 months ago, # ^ |   0 Suppose there was only a single pile. The Sprague-Grundy theorem says that the set of moves available to you at that pile is equivalent to the set of moves available to you in Nim, if you were playing with the Grundy numbers. Thus, if you are playing with multiple independent piles of your game, then it is equivalent to multiple independent piles of Nim.
•  » » » » » » 20 months ago, # ^ | ← Rev. 2 →   0 OK, so the Sprague Grundy theorem says that. That clears it up totally for Problem E.But what about the Crosses-Crosses game game from CP algorithms? Where is any "pile" now?EDIT: I kinda know those piles are the segments, but how do we prove it rigorously using Sprague-Grundy Theorem? It seems very hand-wavy to me.
•  » » » » » » » 20 months ago, # ^ |   +5 A game with "multiple independent piles" really just means multiple independent subgames. When you take a stone from a pile in Nim, you don't affect the set of available moves in any of the other piles.In the Crosses-Crosses game, when you place a cross somewhere, you split the game into two independent subgames, the left and the right. Those are your piles.
•  » » » » » » » » 20 months ago, # ^ |   0 I know this sounds kinda obvious and natural, but how do we determine mathematically what EXACTLY are subgames in a game? Which exact part of The Sprague-Grundy Theorem deals with how to find those subgames?
•  » » » » » » » » » 20 months ago, # ^ |   0 For the Crosses-Crosses game, if we started the game with one strip of length $m$ and another strip of length $n$, the Sprague-Grundy Theorem would help us determine if it's a winning state or not.Suppose we make a move in the game, which splits it into two independent strips---then it's pretty much the same position as if we had started with those two separate strips.
•  » » » 20 months ago, # ^ |   +8 When I think of a compound game composed of $n$ "independent sub-games", I imagine the move in the compound game formulated as the following two-step process: Choose some sub-game $G_i$ ($1 \leq i \leq n$) Make a valid move in sub-game $G_i$ In NIM, in particular, you have $n$ "independent sub-games" (one for each pile), and a valid move in a sub-game consists in taking some number of stones from a pile.In the crosses problem, once you make a move in the middle at position $i$, you are left with a game composed of two independent sub-games of size $i - 1$ and $n - i - 1$, because you can formulate the next move of the player as being this process: Choose one of the two remaining strips; sizes are $i - 1$ and $n - i - 1$ respectively (because once the previous player has chosen position $i$, positions $i - 1$ and $i + 1$ become unavailable, therefore you consider the left strip as having only $i - 1$ positions, and the right strip as having only $n - i - 1$ positions) Make a valid move on one of the remaining strips; here, a valid move is choosing any position; See how these two-subgames are in fact the same as the original game, but with lower lengths? This is when dynamic programming becomes useful.
 » 20 months ago, # |   +8 Thank you very much, arigatogosaimasu
 » 20 months ago, # |   +8 A great effort and a great explanation , the best out there on this topic imo!!!!
 » 19 months ago, # |   0 This is great........but still really hard!
 » 17 months ago, # |   0 Another problem: https://codeforces.com/contest/1451/problem/F
 » 16 months ago, # |   0 How can we find the period (repetition of Win and Lose pattern) of the game? This is many times useful when the input size is too large.
•  » » 16 months ago, # ^ |   +13 In general, the grundy numbers of the states of a game are not periodic. In the special cases where they are, it depends on the game.A typical approach to follow is to just compute the first few grundy numbers, and look for a periodic pattern. If you find one, try to prove that the entire sequence follows that pattern (usually involving some argument like, the grundy number of state $i$ depends only on the states in the range $[i-k, i-1]$ where $k$ is a fixed constant, although there are other possible arguments as well).