Last Stone looks like a game you play by feel. Three rows of stones, three, five and seven. You take some from one row, I take some from another, and whoever takes the last one wins.
It is not a game of feel. It is a version of Nim, and Nim was solved completely by a mathematician called Charles Bouton in 1901. If you know the method and your opponent does not, you will win every game in which you get the chance to. This post is the method, without the algebra.
The idea of a safe position
Every position in the game is one of two kinds.
A safe position is one you want to leave for your opponent. Whatever they do next, you will be able to reach another safe position, and so on until you take the last stone.
An unsafe position is everything else. If you are handed one, you can always turn it into a safe one, as long as you know which move does it.
So the whole game is: after every move you make, leave a safe position.
The positions to remember
With rows that start at three, five and seven, you only need to know a short list. These are the safe positions, written as the number of stones in each row, in any order.
- 1, 1 and nothing else. Or 2, 2. Or any two equal rows with the third empty.
- 1, 2, 3
- 1, 4, 5
- 2, 4, 6
- 2, 5, 7
- 3, 4, 7
- 3, 5, 6
If what you leave behind matches one of those, you are winning.
Why two equal rows are safe
This is the one worth understanding, because it shows how the whole thing works.
Suppose you leave two rows of four and the third row is gone. Your opponent takes some from one row. You take the same number from the other. The rows are equal again. Repeat. Sooner or later they empty one row, you empty the other, and the last stone is yours.
They have no way out. Any move breaks the balance, and you can always put it back.
Every safe position has that property. It is a kind of balance, and any move disturbs it.
The first move
The starting position, 3, 5, 7, is not on the list. That is good news if you are going first.
Take one stone from any row. That leaves 2, 5, 7 or 3, 4, 7 or 3, 5, 6. All three are safe. Whichever you choose, you are now winning, provided you keep it up.
In our version the game picks at random who goes first. If it is you, take one stone. If it is not, wait for a mistake. Against anyone who does not know the list, you will get one.
A game, move by move
You go first and take one stone from the row of seven. 3, 5, 6. Safe.
Your opponent takes three from the row of five. Now it is 3, 2, 6. Look for a safe position you can reach. Take five from the row of six: 3, 2, 1. Safe.
They take the row of three. It is 2, 1. Take one from the row of two: 1, 1. Safe.
They take a stone. You take the last one.
When you do not have the list in your head
There is a rule that produces the list. Break each row into fours, twos and ones.
- 3 is a two and a one.
- 5 is a four and a one.
- 7 is a four, a two and a one.
A position is safe when there is an even number of fours, an even number of twos and an even number of ones, counting across all the rows.
At the start there are two fours, two twos and three ones. The ones are odd. Remove a single stone from any row and they become even. That is the same first move as before.
This rule works for any number of rows of any size, which the list does not.
When they know it too
Then whoever goes first wins, and the game becomes a question of who makes a slip. That is rarer than you might think. Most people have never heard of this, and those who have often cannot remember it under pressure.
It is also worth changing the game slightly between friends who both know it. Agree that whoever takes the last stone loses. The strategy is almost the same, with a twist at the very end, and working out that twist is a nice puzzle of its own.
Why it matters beyond one game
Nim is the starting point for a whole branch of mathematics about two-player games. Many games that look nothing like it turn out to be Nim in disguise.
For our purposes it is enough that a tiny game, played in a minute, hides a complete and beautiful solution. Among HTML5 games you can play on one phone with a friend, there is nothing else quite like the moment they realise you cannot be beaten, and ask how.