Last week we looked at rolling and locking games like Yahtzee. This week, you’ll need to indulge me as I went down quite the rabbit hole recently. What started as reading about trick-taking games led to reading combinatorial game theory and the game of Nim.1 While Nim is a mathematically solved game, it’s exactly the kind of game I think we should be aware of.
Let’s take a look at how to play a basic game of Nim and the lesson it holds for tabletop game designers.
How to play Nim
There are countless variations of Nim, but here is perhaps the most simple and widespread way to play:
There are multiple rows of sticks or piles (heaps) of tokens. The number of groups varies but it is often 3-4 total groups. The number of starting objects in each group can be any number as well. Here’s an example:
Pile A: ⬤ ⬤ ⬤ ⬤ ⬤
Pile B: ⬤ ⬤ ⬤
Pile C: ⬤ ⬤
On a player’s turn, they can take any number of tokens from any one of the piles. They can’t take from more than one pile in the same turn. You could take any number from 1-5 tokens from Pile A in the example above.
This repeats until someone takes the last token.
The player that takes the last token wins.2
In an extreme example of play, Alice is the first player and takes all the tokens in Pile A. Bob takes all the tokens in Pile B. Alice takes the remaining tokens in Pile C and wins the game. In practice, you could take any number of tokens on your turn.
We can also imagine simplified versions of this game to illustrate how it works:
Single pile, one token: The first player always takes the token and the second player always loses.
Two piles, one token in each: The first player takes one of the piles. The second player takes the other pile. The first player always loses.
These versions don’t have much interesting player agency. The winner is determined by player order and nothing more!
But what if we increased the number of choices presented to the player each turn?
Increasing the decision space
With one token in each pile, the players only have a single choice on their turn: take the available token or not. It’s a Hobson’s Choice — take the token available or don’t play the game.
Adding tokens retains the same underlying gameplay, but increases the decision space of the game. Consider the following two examples:
Single pile, three tokens: The first player can take 1, 2, or 3 tokens on their turn. If they take 1, there are 2 tokens left for the second player, leaving them with the choice of taking 1 or 2 tokens.
Two piles, three tokens in each: The first player can now choose to take 1, 2, or 3 tokens from either of the two piles. This is a much larger decision space. The second player will also have a larger decision space on their turn.
Now imagine the classic “matchstick game” version of Nim where there are four rows of matchsticks. The rows contain 1, 3, 5, and 7 items. Same game, but a vastly larger starting decision space, albeit a decreasing one as the game continues.
Impartial games
The notable thing about Nim is that it is an impartial game with perfect information.
Impartial games (using the combinatorial game theory definition) is one in which a player’s available moves depends only on the current game state — the position of the pieces in the game.3 The players are fully equivalent and have the same options. The only difference between them is which of the two players went first.
In addition, both players have perfect information, meaning nothing is hidden and both players can see all of the information in the game.
Finally, the outcomes of the game for each player are the same: either to win or to lose.
Chess is not an impartial game because each player has their own pieces (black and white) which restrict which pieces they can move.4 Checkers is similarly not an impartial game. Other games introduce dice rolling, card draws, and asymmetric powers that may prevent them from being an impartial game.
Commercially successful impartial games are hard to find, or at least have been difficult for me to find. Babylon (reimplemented as Soluna) by Bruno Faidutti was one of the few I identified by a well-known designer.5 Most examples are made as mathematical curiosities instead of packaged games.
The Sprague–Grundy theorem
Even though everything is pointcrawl, not everything is Nim.
Nim is special because it is a two-player, impartial game with perfect information.6 That said, every two-player, normal-play, impartial game with perfect information can be theoretically reduced to the same behavior as a single-pile game of Nim.7
That’s what the Sprague–Grundy theorem states, as alluded to in the intro to one of the articles about it:
“In any game between two opponents playing alternately, in which the legality of moves is not governed by chance, it is intuitively clear that there must be some best method of playing; and if both play correctly the result of the game is determined by the initial position.”8
Specifically, the theorem means that every impartial game can be reduced to a single-pile game of Nim. It doesn’t matter if your Nim variant has one pile or thirty piles. It doesn’t matter if there are two tokens in each pile or a hundred tokens in each pile. The game can be reduced to a single number — the size of the pile in an equivalent single-pile game of Nim.9
This number is known as the Grundy value or nim-value of the impartial game.
The actual method of calculating the Grundy value for an impartial game is beyond what I can cover here. It uses methods like bitwise XOR sums that are fairly complicated.
The point is that just like some game mechanisms are probabilistically equivalent, impartial games can be reduced to equivalent games of single-pile Nim. We can increase the decision space, add more piles, more tokens, but the outcome largely depends on the initial position and which player goes first.
The lesson of Nim
We just went on a mathematical tour of Nim, impartial games, and the Sprague–Grundy theorem — admittedly a lot to take in.10
So what’s the point here?11 For me, it reiterates that mechanical complexity is different from the actual strategic complexity of the game.
You can have normal-play, impartial games with rows of matchsticks, piles of stones, or even stacks of quarters but at some level they can all be analyzed with Sprague–Grundy theorem. At a theoretical level, they are all reducible to a Grundy number as a single-pile game of Nim.12
Similarly, you can add more tokens, create larger decision spaces, and apply ever more mechanical complexity to a game, and yet not make it more strategically dense. The decisions might be more plentiful, but no more interesting.
To me, in a very roundabout way, the lesson of my trip down the Nim rabbit hole is that it is the core behavior of the game that is key, not all the bits around that core.13
Create a minimum viable product (MVP) version of your game.14 Find the core and playtest it hard before adding significant complexity.
Conclusion
Some things to think about:
Nim games are interesting: There are so many variations on the basic game of Nim, many of which are quite fun. Sprouts has players drawing curved lines to connect dots on a sheet of paper. Grundy’s game splits stacks of quarters. Even though they are “solved” games, I’d still like to try them!
Yes, math is hard: Sure, combinatorial game theory is complex and most of us have neither the time nor desire to understand the mathematics behind it in detail. That doesn’t mean we can’t read about it and learn lessons from it. It’s such an interesting field of research!
Applications in other games: I usually try to come up with some ways to apply the week’s topic in board games and TTRPGs. While I’m not sure I’d recommend dropping Nim directly into your design, I do think there’s something interesting there. I’ll continue to think about it, even if it is just retaining the “take a number of things away from a group” as a possible mechanism.
What do you think? Are there lessons to be learned from studying Nim? Can you think of other impartial games?
— E.P. 💀
P.S. MÖRKTOBER is coming! The prompt preview is available now. Get ready to make 31 days of dark and weird things starting October 1. 🎃
Skeleton Code Machine is a production of Exeunt Press. All previous posts are in the Archive on the web. Subscribe to TUMULUS to get more design inspiration. If you want to see what else is happening at Exeunt Press, check out the Exeunt Omnes newsletter.
Skeleton Code Machine and TUMULUS are written, augmented, purged, and published by Exeunt Press. No part of this publication may be reproduced in any form without permission. TUMULUS and Skeleton Code Machine are Copyright 2026 Exeunt Press.
For comments or questions: games@exeunt.press
How did I start at trick-taking games and end up reading about the Sprague–Grundy theorem? Good question. Trick-taking led me to misère bids where the player tries to win no tricks at all. In combinatorial game theory, misère play (as opposed to normal play) is where the player unable to move wins (i.e. the last move loses). In normal play, it’s the other way around: the last move wins and the player unable to move loses. These two modes of play are important in the game of Nim. And the normal play mode of Nim can be analyzed using the Sprague–Grundy theorem and assigned a Grundy value. Q.E.D.
If the last person to take a token wins. That’s called normal play. It’s also common to play where the last person to take a token loses. In that case, it’s called misère play. This article mostly assumes normal play as that is what the Sprague–Grundy theorem requires.
The opposite of an impartial game is not a partial game. They are called partisan games.
Tic-tac-toe (noughts and crosses) is an interesting example. Is this an impartial game? Does it matter that you are placing an X or O on your turn? It appears that the consensus is that it’s a partisan (i.e. not impartial) game. There is a variant called Notakto in which both players use Xs, turning it into a fully impartial game.
I haven’t played Babylon and am relying on the BGG description here.
Before the mathematicians come for me with pencils sharpened, there are quite a few conditions that must be satisfied to be a Nim game or one that can be reduced to a game a of Nim: two players, finite game positions, alternating player turns, and guaranteed ending condition.
Just because you theoretically can do this doesn’t mean it is easy. Games such as John Conway’s Sprouts makes this extraordinarily difficult to calculate this. I might cover Sprouts in more detail in a future article.
This quote is from “Mathematics and games” (1939) by P.M. Grundy. It is similar in some ways to Zermelo’s theorem from 1913. Interestingly, R.P. Sprague and P.M. Grundy, according to Wikipedia, independently came up with this same theory within about three years of each other. Thus the theory was named after both of them.
The Grundy value for a single pile game of Nim is the same as the number of tokens in that pile. This makes sense because there’s no reduction or equivalence necessary. It’s already in the most simplified or reduced state.
I resisted the urge to call this article The Secret of Nim. 🐀
I can’t even type “So what’s the point here?” without hearing Matthew Carlson saying “What are we even doing here?” in my head.
Note that I’m saying they are equivalent at some theoretical level involving math and behavior, not that they are the same game. A game of Nim with matchsticks feels worlds apart from a game of Sprouts with pen and paper. The mechanisms and components themselves change the feel of the game. Also, Sprouts is a mathematically complex game that is actually quite hard to analyze.
Those other bits include thematic elements which are deeply important. So this is not to claim that only the core of the game matters, but rather that it is critical that we can identify the core of the game during the design process. Then, after we can do that, all of those other bits are what can turn a good game into a great one.
I’m using the term minimum viable product (MVP) here in the broadest of ways. The term means different things in different contexts (e.g. automotive design vs. software development). In game design, it usually means the earliest playable prototype that is restricted to the core elements of the game.
Very much appreciate the breakdown of the game (Nim.) When I saw the word, I immediately flashed back to sixth grade (the last time I played it or heard the word out loud - and that was over 45 years ago.) Thanks also for defining terms - I got a lot of the article (even a potential idea for incorporating Nim at it's most basic into a real world puzzle for one of my projects :) )
I recommend Quarto (by Gigamic) as a fairly fun and quick commercial impartial game!