Notakto Is Secretly Nim: Why the Boards Behave Like Heaps

Notakto is dressed as tic-tac-toe, but underneath it is a relative of Nim, the first game of this kind to be fully worked out (Charles Bouton, 1901). You can see the family resemblance in a fact you can check at the board: one or three empty boards are a win for the player to move, and two are a loss. The reason is not the one a Nim player would guess, and that is where the interesting part starts.

If the rules are new to you, read what is Notakto first.

A One-Minute Tour of Nim

Nim is played with a few heaps of objects. On your turn you take any number of objects from one heap, and in ordinary Nim whoever takes the last object wins. The famous trick is copying: two equal heaps cancel, because whatever your opponent takes from one, you take the same from the other. You always have a reply, so you make the last move and win.

Notakto is impartial in exactly the same way as Nim: both players place X, so a position is just a pattern of marks, never “yours” or “mine”. That is why game theorists treat each board like a heap. But Notakto is misère, played so that finishing the last board loses, and misère play is where the copying trick breaks.

Why Two Empty Boards Don’t Cancel

In ordinary Nim, two equal heaps cancel: you copy every move and win. Try that in Notakto and you lose, because when your opponent finishes one board, your copy finishes the last one. Misère play breaks the copying trick. What survives is the 2013 result: every board reduces to one of 18 values, and a fixed table says how they combine. Two empty boards happen to combine to a losing value for the player to move, three to a winning one.

So the parity rule from how to win at Notakto is real, but it is a result read off that table, not a cancellation:

From empty boards, the mover wins iff the number of boards is odd. One → win, two → loss, three → win.

Why It Is Secretly Nim, Not Just Nim

A half-played board is not a heap of pebbles; it is a tangle of X marks. The achievement of the 2013 solution is showing that every board, however filled, still reduces to one of a small set of values, and that a fixed table says how those values combine. Track how the combinations behave across any pile of 3×3 boards and you get an algebraic structure, the misère quotient, with exactly 18 elements. (A single board only ever realises a few of those values; the 18 is the size of the whole system that describes piles.) Eighteen elements are enough to describe any number of 3×3 boards, which is why a computer can play the multi-board game perfectly from a compact table.

“Misère” is the catch. In ordinary (“normal”) play the last player to move wins, and equal heaps cancel, so values can simply be added up. In misère play, finishing the last board loses, and that one change breaks simple addition: the copying argument fails at the very end, as above. The misère quotient is the replacement, a small table of how values combine that is exact where the Nim intuition is not.

See It for Yourself

The quickest demonstration is to play. Start on two boards, move first, and notice you cannot win against the Perfect level: the position is lost from the off. Try copying its moves and watch where that leads. Add a third board and the win is suddenly yours. You are not learning tic-tac-toe; you are learning how the boards combine. For the family resemblance to Notakto’s sibling game, which hides a different theorem under a different grid, see misère games.