If you're here because you're looking for the HTML version, you're in the right place. If you're looking for the interactive version, or you don't know why you're here, go to the github repo.
Nim is a simple board game played between two people, invented in China some time before 1500. In 1902, a mathematician named Charles L. Bouton published a 5-page paper describing and solving Nim. Later mathematicians Roland Sprague and Patrick M. Grundy independently discovered an important theorem in the 1930s that uses Nim, as we will see, to say unexpected things about many other games.
The field of mathematics that studies Nim is called "combinatorial game theory"—separate from but with parallels to the better-known field of "game theory." While game theory, a concept used in economics, social sciences, and evolutionary biology, deals with chance, hidden information, and numerical payoffs, combinatorial game theory eschews all that and sticks to games with simple win/loss conditions without any randomness.
This lesson should serve as an introduction to combinatorial game theory, not just to the terms and proofs, but also to the curious and careful manner that one must approach it with. It will get very in-depth, but even someone with no experience whatsoever should be able to follow along.
In Nim, the board consists of piles, or “heaps,” of objects, often sticks or stones. There can be any number of piles, and each pile can contain any number of stones. For example, one game might start with a pile of 3 stones, a pile of 5 stones, and a pile of 6 stones.
Players alternate removing stones from piles until all the stones are gone, when that happens, the last player to take a stone wins. On a player's turn, they can take any number of stones from one pile. For example, in the game from above, Alice might start by removing 2 stones from the pile of 3. She could also decide to take only one stone, or to take all three.
You don't have to keep track of who removes which stone. Once a stone is gone, it's gone. Bob continues by removing 4 stones from the third pile.
Alice responds by removing all of the second pile. Now there are only 2 piles left.
Bob removes 1 stone from the last pile.
Alice, realizing her impending doom, removes 1 stone from the first pile.
Bob takes the last stone. Alice, being unable to remove any stone, cannot make a move and loses. Bob wins.
In combinatorial game theory, when there are no legal moves in a position, the player whose turn it is loses. This rule, common across many combinatorial math games, is called the normal play convention. Given this rule, the strategy of Nim revolves around being the person to take the last stone (or stones) from the board.
Why not make it so the person to take the last stone loses? In fact, you can, if you like. That alternative is the misère convention games, from the French word for misery. It's slightly harder to analyze misère Nim, so we will stick to normal play during this lesson.
Now that you know what the rules are, let's have you play a few practice games against a robot to get you familiarized with the game. It might be tough at first, but try to pay attention to which types of moves lead to wins or losses, espically towards the end of the game, when the piles get small and there are less possible moves to analyze.
We'll play with 4 heaps of numbers less than 10, nothing too crazy. Type "Quit" at any time to quit the current game.
source("nim_functions.R") # Run this cell to load the functions - won't work if in HTML.
play_babybot()
Click on the cell with the play_babybot() function and hit the "Run" button. You will be prompted to select which heap and how many stones to remove at certain times, so when that happens, input the corresponding number and hit enter. When you are done playing, make sure that the cell has stopped running. If the cell is still running, the next bot you play will not work.
AI is coming for us all.
More concretely, this robot wins every time at Nim. I confess, this is by design. The piles, which may have seemed random, were selected from a pool of predetermined positions. I programmed the robot so it knew beforehand what the perfect strategy was for all of the positions. There was no way for you to win.
Questions arise. What is this strategy, and how was it found? Does it work only on certain starting positions, or can it be applied to every position? These questions we will answer, and more, as we figure out the mathematics behind the game of Nim.
Nim is a good example to use when trying to teach someone how to solve a game, because it lacks several properties that other games have that make those games hard to analyze. Its simplicity puts it in a category of games we call "determined": meaning that if the two best players in the world play this game, it is "determined" to be a win for only one of them, depending on who goes first or second.
Many common games that people might think are determined are actually not. For example:
Nim cannot end in a draw, has no hidden information, does not involve chance, and will end in a finite number of moves. Thus it is a determined game. Any two-player game that meets those four criteria is also determined.
Note that games can still be "solvable" even if they are not determined: e.g. Tic-Tac-Toe, a game that can end in a draw, has been solved as a draw. A determined game is always solvable, but a solvable game is not always determined.
There are generally four steps to finding a strategy for a game. Firstly, you should play around and familiarize yourself with the game. You have already done this by playing against the bot, and feel free to go back at any time to play it again by selecting the play_babybot() cell and hitting "Run" again. The point of this is to build an intuition around how the game works, and what some potential strategies are. Even if you lose, observing how you lost can teach you a lot.
Secondly, you should find and solve the simplest case of the game—we are about to do this. This usually takes very little effort and gives us a jumping-off point for deeper analysis. We can accomplish this by brute force: looking at every possible move and thinking through whether it leads to a win or a loss. Later, we will use more efficient methods, but for now a brute force approach is the best.
Thirdly, you try to solve more complex cases, working upwards by solving slightly more difficult positions each time. As you do this, you will build up "heuristics", ways of quickly evaluating a position as a win or a loss without having to calculate every option. Using these heuristics, supplemented by a bit of brute force calculation, the internal beauty of the game will tend to reveal itself to you in little lightbulb moments as you explore its depths.
Lastly, you will generalize your heuristics to find a complete strategy for the game. Patterns previously undetected will pop out at you, and you will expose the underlying mathematical structure of the game as if it came straight out of The Book.
Just as often, though, the truth will elude you, and you will find yourself banging your head against the wall with no clear way forward. Sometimes the solution is inelegant and seems arbitrary. With Nim, fortunately, that isn't the case, but often taking a break from a problem and returning to it later is the key to finding the next insight. With that said, let's begin our analysis.
The very simplest case is when there are no heaps at all—the end of the game. This position, by our rules, is a loss for the first player (who cannot move), and thus a win the second player. There is little else to say, so we will move on.
The next simplest case is when there is only one heap, and it contains one stone. In this case, the only legal move for the first player is to remove the one stone, leaving the second player in the zero-heap position.
A convention in combinatorial game theory is to define positions like these as P- or N-positions. The zero-heap position is called a P-position because the "p"revious player wins—the next to move in the zero-heap position will lose. Likewise the one-heap one-stone position from above is called an N-position because the "n"ext player to move wins—by removing the one stone.
This convention is applicable here because Nim is what is called an impartial game—the available moves are the same for both players. This is not true of most games. For instance, Chess is not an impartial game, because the white player is only allowed to move the white pieces, and the black player is only allowed to move the black pieces. Games like this are called partisan games, and cannot be described using P- or N-positions.
As the options for the first and second player in any position are the same (each can remove stones from any heap), Nim is impartial, and this makes the game easier to analyze. We only have to consider the position, because it doesn't matter whose move it is.
If 0 is a P position, and 1 is an N position, what about the other positions with only one heap? From a heap of 2, you can reduce it to either 1 or 0. Obviously removing only one stone would lose you the game—your opponent would remove the remaining stone and win. So you should remove both stones to win. This makes 2 an N-position as well.
Though you have the option of losing by moving from 2 to 1, we still classify it as an N-position because we are looking for the optimal strategy: even if there are 99 losing moves and 1 winning move, it counts as an N-position because the next player to move will choose the winning move.
By this we conclude that any one-heap position is a win for the next player to play—the strategy is simply to remove the entire heap, and your opponent will lose on the next move.
To recap:
The next bot will test your knowledge of one-heap positions. Shouldn't be that hard...
(If the bot doesn't run, you need to go back to the Baby Bot and make sure that there isn't a game in progress.)
play_childbot()
We just learned that every one-heap position is an N-position, where the next player to play wins. It turns out that two-heap positions are a trickier, but not by much. Again, let's start with the simplest case, and build up from there. If at any point you feel like you have an insight, take a pause and see if you can find the general two-heap strategy—I think that anybody can find it if they invest a bit of time and effort.
The simplest case is two heaps of one stone each. Alice will remove a stone from one of the heaps, Bob will remove the other stone, and Alice will lose. Note that there was nothing Alice could have done—removing a stone from the first heap has the same result as removing a stone from the second heap, as both lead to a loss in the same manner.
Thus (1,1) is classified as a P-position—losing for the next player to play, winning for the previous player. (I hope I'm not beating a dead horse by repeating these definitions, but they are very important.) Thinking one step further, we realize that any two-heap position where one of the heaps is 1 (besides (1,1)) is winning position. For example, in positions like (8,1) or (1,2) or (3000, 1), the winning strategy is to reduce the larger heap to 1, making the position (1,1), your opponent must remove one of them, and you can remove the last one to win.
So all positions (1,n) excluding (1,1) are N-positions, which are won by reducing n to 1. (Note that a (1,n) position is the same as an (n,1) position.) We now know:
What might (2,2) be?
As we will see, (2,2) is indeed a P-position. We will verify this by checking that no matter what, the first player loses.
And just like we showed for (1,n) positions, we can show that (2,n) positions excepting (2,2) are N-positions—the next player wins by reducing N to 2, and since (2,2) is a P-position, the previous position (2,n) must be an N-position.
You might be catching on to a pattern here, so let's again take stock of our P- and N-positions:
We notice that only the positions where both heaps are equal are P-positions, and all the rest are N-positions. Looking at what we have so far, we might hypothesize that this pattern continues, that all positions (n,n) are P-positions and all positions (n,m) where n≠m are N-positions. We might prove this by induction, showing that (n+1,n+1) is a P-position if (n,n) is a P-position, but there is a more elegant way that I would like to use instead.
Consider some position (n,n)—for example (9,9). I will go second, and my strategy will simply be to copy every move you make. If you remove, say, 3 stones from a pile, I will remove 3 stones from the other. If you remove 5, I will remove 5. Eventually, you will have to remove a pile completely—once we get to (1,1) there is no other choice. When that happens, I will remove all of the second pile, and I will win.
This strategy of copying your opponent's moves is called the Tweedledum and Tweedledee argument, and it can often be used to evaluate games where a position consists of two copies of the same element. Since the last player to move wins, you can ensure victory by copying onto the second element whatever move your opponent makes onto the first element. In Nim, the elements are piles, and the strategy works because the piles are equal and the possible moves are the same.
This works well because Nim is, as we remember, an impartial game—the same moves are available to both sides. It doesn't work as well for partisan games—games where the players have different moves—because you might not be able to make the same move as your opponent
Back to two-heap Nim strategy. If we know that any (n,n) position is a P-position, then we know that any (n,m) position where n≠m is an N-position, and the strategy is to reduce n to m, or m to n, depending on which is greater. I will test you on that in a minute, but I should talk a bit more about P- and N-positions before that.
The definition of P- and N-positions as being winning for either the previous or the next player is good, but I should shed some light on the relationship between the two.
Say you have a position, and you can play a move that makes it a P-position. Your position, therefore, must be an N-position. You are winning, because you can take the position to a P-position where your opponent will lose.
Likewise, say you have a different position, and all of your moves lead to N-positions. Your position must be a P-position, because any move you make gives your opponent a winning position.
So we can recursively define a position by looking at its moves:
The table above shows the classifications of small two-heap games. When the piles are equal, it is a P-position, when the piles are unequal, it is an N-position.
Now, let's test your knowledge of two-heap strategy.
play_teenbot()
At this point, we are getting into the mathematical weeds, so take a quick breath. I don't expect everyone to get everything immediately, and you might need to reread a section a few times to get what its saying. Go outside if you need to, but come back if you do. I promise that it will be worth your time to learn the whole thing.
We continue to start with the simplest case, (1,1,1). It is not hard to see that this is an N-position: Alice will remove a stone, Bob will remove another, Alice will remove the last stone, and Bob will lose. In fact, we realize quite quickly that any such (1,1,n) is also an N-position, by removing the n and getting (1,1). These observations are how we continue: building up knowledge of P-positions, such as (1,1), and analyzing new positions by seeing if, in one move, they can become P-positions that we already know. For instance, we can look at the position (2,5,2) and see that it is an N-position, because you can move to (2,2), a known P-position.
Thus we realize quickly that any position (n,n,m) is an N-position, because we can remove the m pile to get (n,n), a P-position. (In this case, m may equal n, for instance, (7,7,7) -> (7,7) is how one would win that position.) Having that thought, how might you win the five-heap position (1,1,2,2,3)? Take a minute to answer this.
Indeed the answer will be to remove the heap of three: the position (1,1,2,2) is a P-position. One way to find this is using the Tweedledum and Tweedledee argument: separating the position into two groups of (1,2), and whatever your opponent does to one group, you do to the other. You could also get to this faster by realizing that adding a pair of the same numbers to a position does nothing to it, so the strategy for (1,1,2,2,3) is the same as the strategy for (1,1,3), which is the same as the strategy for 3: Remove the pile of 3. Indeed the position (1,1,2,2,3,3,4,4,5,5,6) can be evaluated quite simply: remove the pile of 6, and whenever your opponent removes stones from a pile, remove the same number from that pile's twin.
This is a key insight: that adding 2 piles of the same size onto a position does nothing to change the strategy. For a crazy position like (4,2,9,6,3,5), the strategy (whatever it may be) will be the same as strategy for the position (4,2,9,6,3,5,10,10). In your mind, you can split the position into two parts, when your opponent makes a move on the (4,2,9,6,3,5) part, you respond with the strategy for that, and when your opponent makes a move on (10,10), you respond with the strategy for that.
This splitting up of a position into different parts is a common tactic in combinatorial game theory. There is much to learn about it, too much for this lesson, but in Nim we can think of it in a bit of a simpler manner.
We'll start not by splitting up positions, but by putting them together. Adding a heap of 0 stones to a position changes nothing about it, and if we weren't thinking mathematically, the concept wouldn't make any sense. But let's try. Let's invent a new function, a "nim-sum", perhaps, that will take heaps and "add" them together to get a number that somehow represents the position. A position of 1 "plus" a position of 0 will be a position of 1, thus: 1 "+" 0 = 1. I use quotes around the plus to indicate that this is not normal addition, but something similar.
What, then, is 1 "+" 1? We might guess it is 2, but I do not think so. A single heap of two acts very differently from two heaps of one, one is an N-position and one is a P-position. As we have seen previously, adding pairs of heaps to a position does not change its overall strategy, e.g. (2,4,5) has the same strategy as (2,4,5,1,1). As we might say, 2 "+" 4 "+" 5 = 2 "+" 4 "+" 5 "+" 1 "+" 1. These quotations are getting annoying, so I will remove them from now on. Just know that they represent nim addition, not regular addition. Removing (2,4,5) from both sides, we get: 1 + 1 = 0.
A strange result, but not a wholly unexpected one. Adding two heaps of 1 to a position does nothing to change the strategy, just like adding a heap of 0 does nothing. One side effect is that if 1 + 1 = 0, then 1 = -1. If we have some position p with an extra heap of 1 ({p},1), we know that removing the heap of one is the same as adding another heap of 1. ({p}) is strategically equivalent to ({p},1,1). In fact we can use this to prove that every number is its own negative, because adding it twice to a position is the same as adding it and then removing it.
Let's head back to our analysis of three-heap positions. The first non-trivial example is (1,2,3), because we already solved all positions where two or more piles are equivalent.
The six options (legal moves) from (1,2,3) are:
Since all legal moves go to N-positions, by definition, (1,2,3) must be a P-position.
Going back to our idea of separating and combining positions, let's think about what adding (1,2,3) to a position does. If we add it to an N-position, it does nothing—the new position will still be an N-position, and the winning strategy will be the same as in the previous N-position. In the same way that 1 + 1 = 0, 1 + 2 + 3 = 0.
Let's more clearly define what we get when we combine P- and N-positions.
P + P = P, and N + P = N, and N + N = ?. From the first two, we learn that any position A + P must equal A. This leads us to the conclusion that every P-position has a nim-sum of 0, because adding it to another position does nothing. We can prove that the converse is true as well, that every position with a nim-sum of 0 is a P-position. (You can also just take my word for it, and skip the next paragraph.)
Suppose there exists a position X that has a nim-sum of 0, but is an N-position. Because it is an N-position, that means there must be a move that takes it to a P-position. This will take some heap H and replace it with a smaller heap I, as per the rules of the game, making a P-position ({X} - H + I). Because this is a P-position, its nim-sum must equal 0. Because {X} - H + I = 0, and X = 0, this means that -H + I = 0, as we can replace X with 0. Now if we move H to the other side, we get that H = I, in words, that the number of stones in heap H is the same as the number of stones in heap I. But this is a contradiction, because I is smaller than H! Thus we prove by contradiction that every position with a nim-sum of 0 is a P-position, because there cannot exist an N-position with a nim-sum of 0.
Using contrapositives, we get these definitions:
So our nim-sum turns out to be very useful. If we can find out how it works, we can use it to tell us if we can win a position. It remains to be seen whether or not it tells us how to win a position.
We currently know little about nim-sums, so let's remember what we do know. Any number plus itself is 0, like 3 + 3 or 8 + 8. We also know that 1 + 2 + 3 = 0. Currently, that's it. But we can actually derive a nice piece of information from the second equation, when we remember that a number is its own negative. Shifting the 3 to the other side, we get:
1 + 2 = 3
Nice and normal. But what if we switch another number over instead?
1 + 3 = 2
2 + 3 = 1
I think we're at the point where we can't call these heaps "numbers" anymore. I think that another name is necessary for these numbers from Nim ... these so-called Nim-numbers ... nimbers?
Yes, they are called "nimbers." It turns out that the properties of nimbers have uses beyond the game of Nim. Our current endeavor, though, should simply be to find out how they add. By analyzing using brute force some other non-trivial three-heap positions, we should find some more facts about nimber addition.
We know that any (1,2,n) position other than n = 3 is an N-position, because we could reduce n to 3 and win. (We can also see this because 1 + 2 + n = 0 if and only if n is 3.) Same with any (1,3,n) where n ≠ 2, and (2,3,n) where n ≠ 1. So the next non-trivial three-heap position is (1,4,5), which we quickly see is a P-position.
This brute force method is tedious, but it shows that 1 + 4 + 5 = 0. A smarter way would be to notice that every move either brings us to two unequal piles, two equal piles and a third pile, or where the position can be reduced to (1,2,3). Anyway, from this we can garner that 1 + 4 = 5, 1 + 5 = 4, and 4 + 5 = 1.
To top it off, since 2 + 3 = 1, we also learn that 2 + 3 = 4 + 5, so 2 + 3 + 4 + 5 = 0, meaning (2,3,4,5) is a P-position.
Since 0 + 1 = 1, 2 + 3 = 1, and 4 + 5 = 1, one might suppose that 6 + 7 = 1, that is, that (1,6,7) is a P-position. This turns out to be the case. From (1,6,7), one is forced either to remove the 1, which loses, to make the 7 a 6, which loses, or to reduce one of the large piles to a size less than 6, which loses when one's opponent makes the position a (1,2,3) or a (1,4,5). Thus we also conclude that 2 + 3 + 6 + 7 = 0, and also that 4 + 5 + 6 + 7 = 0, because 2 + 3 = 4 + 5 = 6 + 7 = 1.
We suppose than this pattern continues on, that all (1, 2n, 2n+1) positions are P-positions. This is correct, but I will leave it as an exercise to the reader to prove it. The next bot will test your knowledge of (1,2n,2n+1) type positions.
play_adultbot()
What we want now, if we look at our little table of sums, are sums like the sum of 2 and 4. That is, we want some N so that 2 + 4 = N; a P-position (2,4,N). Indeed we know that only one N will satisfy this, because the answer to 2 + 4 cannot have multiple answers. So let's run through the possible options.
When we get to N=6, we're stuck if we try to continue by substitution, but we can instead play out (2,4,6) and see if it's a P-position.
Even with 12 possible options, there is no way to win from (2,4,6), so we conclude it is a P-position, and 2 + 4 + 6 = 0. Let's update our sum table now, and see what we get.
You should notice a few things. First, like in a Sudoku, no nimber is ever repeated in a row or column, because there can't be more than one solution when you add a pair of nimbers. Second, this interesting 0,1,1,0 square is repeated along the diagonal. And thirdly, it seems that more of these 2 by 2 squares might repeat. Let's calculate these missing nim-sums and fill them in. I'll color-code the result.
A fascinating pattern. At the 2x2 level, two consecutive nimbers form a checkerboard pattern. At the 4x4 level, the 2x2 squares form a checkerboard pattern, and at the 8x8 level, the 4x4 squares form a checkerboard. We now wish to prove that this pattern continues at the 16x16 level and beyond.
We notice first that the sum of two nimbers is never greater than the sum of the regular numbers. For example, 3 + 4 = 7 both in the number world and the nimber world, and 3 + 6 = 5 in the nimber world and 9 in the number world, but we don't get any result like 3 + 4 = 8, because 8 is greater than the normal sum of 7.
This is proven when we remember what 3 + 4 = 7 means. For any move on a heap of 7, and there are 7 possible moves in total, there is a corresponding move on either 3 or 4 that makes the nim-sum 0 again (e.g. 7 -> 5 and we respond by playing 3 -> 1). If, for example, 3 + 4 = 8, that wouldn't make sense, because there are 8 possible moves from 8 and only 7 possible moves from (3,4), meaning that there would be a move from 8 that you wouldn't have a winning response to. So for any two nimbers, the nim sum ≤ the normal sum, or else there would be too many possible moves on the nim-sum value.
It turns out that combining this rule, the nim sum ≤ the normal sum, with another rule, that a nim-sum has only one solution, is enough to give us a function that recursively defines nimber addition. This function is called the minimum excludant function, or mex for short.
The mex assumes we have a set (in this case, all of the nimbers) that is "well-ordered", meaning we can list it out—0, 1, 2, 3... and so on. The input for the mex is a subset of this set, some smaller collection of nimbers from the big set, and it outputs the smallest nimber that is not in the subset—the minimum of the excluded nimbers. For example: mex(0,1,3,4,10) would be 2, as 2 is the smallest nimber not in that set.
But we don't apply this mex function directly to the two nimbers we want to add, because that would output 0 for every nim-sum: a nonsensical result. Instead, to sum two nimbers A and B, we take the mex of every nim-sum of B and nimbers less than A, combined with every nim-sum of A and nimbers less than B. This sounds confusing, but it has a very nice visual representation.
To get the nim-sum (3 + 5) circled in red, we take the mex of the previous nim-sums in the same row and in the same column, circled in purple. In this case, this is mex(3,2,1,0,7,5,4,7) = 6, because the smallest nimber not in there is 6.
Really what the mex function is asking is "What is the smallest value that this nim-sum 3 + 5 could take, given that it can't be the same as the nim sum of 3 + 0, 3 + 1, 3 + 2 etc., and it also can't be the same as 0 + 5, 1 + 5, or 2 + 5?"
The nim-sum table ends up filling outwards like an infinite Sudoku, where you have to find the smallest value not already in the row or column. This is what creates the checkerboard pattern, because each value has to avoid itself, resulting in these strange 2^n-sized squares that also avoid themselves, on and on to infinity.
This allows us to find the nim-sum of any position—we can just add all the heap sizes together one by one to get the resulting nimber. If that value is 0, remember, the position is a P-position, and if it's not, it's an N-position. Our next step is to find out how to win those N-positions.
Okay, so we can nim-sum the heaps in a position to see if it is a win or a loss. But how do we win an N-position? If the position is small enough, we can look for familiar P-positions to move to. But what if the N-position is something like (20,31,37,83)? How are we supposed to do that?
The first thing we have to do is check that the position is, indeed, an N-position. It turns out that the nim-sum of those four numbers is 125, which isn't 0, so it is an N-position. But how do we turn our nim-sum into a strategy? Well, remember that if we know that 20 + 31 + 37 + 83 = 125, we know that 20 + 31 + 37 + 83 + 125 is 0. We have to do something to the position (20,31,37,83) that makes it into a P-position. We wish we could add another heap of 125 to it, because that would make it 0, but that is against the rules (and besides, our opponent would remove the new heap, bringing us to the same position again).
So we have to instead find a way to remove a heap of 125 from the position, as nimbers are their own negatives. But there is no heap of 125 in the position, so that also doesn't work. So we have to instead find a way to do the same thing as removing a heap of 125 without removing a heap of 125. This is where nim-summing helps again.
We know, because 20 + 31 + 37 + 83 = 125, that 125 + (one of the four heaps) = (the other three heaps). This is how we will "subtract" 125: by finding the heap (or heaps, sometimes there are multiple winning moves) where 125 + that heap = some nimber less than that heap. Because we can make a heap smaller, making the heap smaller in a certain way will correspond to "removing" a heap of 125. So we check, for each heap, whether 125 + that heap = a smaller heap.
Aha! So we win by reducing 83 to 46. We can check that 20 + 31 + 37 + 46 = 0, and indeed it does. So our strategy for any position becomes:
I will include a function below that will nim-sum a list of piles.
nim_sum(1,2,3) # Enter the nimbers to sum, e.g. nim_sum(1,2,3) or nim_sum(23,65).
For several reasons, when playing a game of Nim against a friend, it is not viable to calculate a large nim-sum table by hand. Luckily, there is an easier method of summing nimbers that has the same effect. If you represent the nimbers in binary (e.g. 83 is 1010011, 125 is 1111101) you can nim-sum very quickly by taking the bitwise XOR function (in effect, adding in binary without carrying digits). So the nim-sum of 83 and 125:
Two 1s in the same place cancel out to make a 0, a 0 and a 1 make a 1, and if there were two zeros in the same place, they would make a 0.
This incidentally also confirms that nimbers involving different powers of 2 add up to their normal sum, e.g. 2 (2^1) + 4 (2^2) = 6. Whereas in 1 (2^0) + 3 (2^1 + 2^0), the 2^0s cancel out and you get 2^1 (2). Any nimber can be expanded into its constituent powers of 2 without changing the overall sum.
This is how I would get the nim-sum of 125 for the position (20,31,37,83):
This one is large, so it's a bit tricky to do in your head, but it's more manageable for smaller heaps. Also, with smaller heaps, it's more likely that there will be a known trio of heaps like (1,4,5) that you can mentally set aside, so you only have to deal with the remaining heaps (until your opponent changes an element of the trio, in which case you can respond in the trio).
Now, I hope, you should have the tools to win at Nim. The next bot will test you on everything you've learned so far.
play_grandmabot()
What we have just learned about Nim is all well and good, but is it of use beyond the game itself? Yes. There is a result, proven independently by mathematicians Roland Sprague and Patrick M. Grundy, which states, in brief, that every position in every impartial game is equivalent to a one-heap game of Nim. We can use the tools of Nim heaps to evaluate a whole host of games, knowing that those games are subject to the strategy of Nim.
Let's more carefully define the notion of "equivalence." Say we have a rook on a chessboard, as shown below:
The rook, which normally can move horizontally or vertically (though not at the same time), has a restriction: it can only move towards the red circle. Two players take turns moving the rook, and the first player who can't move the rook loses. Take a minute and see if you can figure out when the first player wins, and when the second player wins.
Indeed, the second player will win only when the rook starts on the same diagonal as the red square. This rook game is equivalent to a game of 2-heap Nim: The horizontal distance from the red circle is the size of one heap, the vertical distance the size of the other. Moving the rook is like reducing one of the heaps. This is what I mean when I say equivalent: the game has the same fundamental structure, but different decoration. What the Sprague-Grundy theorem says is that all impartial games are but decorations of Nim.
We can test the equivalency of positions in games by considering what happens if we add some third position to both of the positions we want to compare. If the two new positions are always the same outcome (P-position or N-position) no matter what third position we add to both, then the positions must be equivalent—they are the same in every possible situation.
In the example, we showed that this rook game is equivalent to two-heap nim. Remember that two-heap Nim positions can be summed to get an equivalent one-heap position—what the Sprague-Grundy theorem tells us can be done for all impartial games.
One more example to show how even games with rules that look different from Nim are still Nim under the hood.
The game above, Sprouts, is played with some number of starting points, where a turn consists of connecting two points with a lines and adding a point in the middle of the new line. A point can be connected to itself, but the number of lines coming from a point cannot exceed three. The last player to move wins (when your opponent cannot connect any two points), in this example, the first player won.
How we apply Nim strategies to other games is actually not that hard. You define the losing position as 0, and you work backwards from there. To get the nim-value of a position, you take the mex of the (unique) nim-values of the possible options. Because all positions can become the losing position in a finite number of moves, you can always find the nim-value of any position—you may end up producing a massive game tree, but everything is connected to the root. Here's how you would do this for 1-point Sprout, the simplest case.
Iterating all possible moves from the 1-point position, we get two possible ending positions (worth 0), reached from an intermediate position (worth 1, because mex(0) = 1), which is the only move from the starting position, so 1-point sprout is worth mex(1) = 0, a second-player win.
Now just because we can use Nim and mex functions to evaluate impartial games does not mean that it is easy to solve those games. Sprouts, as an example, has been solved for 1-point through 44-point starting positions, as well as 46, 47, and 53-point positions, and it is conjectured but remains unproven that the first player wins n-point starting positions only when n mod 6 = 3, 4, or 5.
Another caveat of Sprague-Grundy is that it only works for normal-play games, not misère versions. It turns out that analyzing those is a misery in itself. I might leave that for next time...
Combinatorial game theory is super interesting to me, and if you've gotten this far, it's probably interesting for you too. I would recommend some books on combinatorial game theory that I have used as sources for this lesson, namely, Winning Ways for your Mathematical Plays, by Berlekamp, Conway, and Guy; On Numbers and Games, by Conway; and Lessons in Play: An Introduction to Combinatorial Game Theory, by Albert, Nowakowski, and Wolfe.
For a more lighthearted approach, and one that will appeal to casual and mathematical audiences, Math Games with Bad Drawings, by Ben Orlin, contains a trove of fascinating combinatorial and non-combinatorial games that beg to be analyzed. This book was what got me into CGT. I was lucky enough to have the advice of Ben while working on this lesson, and his experience was a great deal of help on making this lesson rich but accessible.
If you have any comments or find any spots where the code breaks, let me know.
Happy gaming!
-Nolan