A pile holds 21 counters. Two players take turns removing one, two or three counters, and whoever takes the last counter wins. You move first, so is there a way to win however well your opponent plays, and if there is, how many counters should you take? This page works backward from the empty pile, finds that the multiples of four are the positions to hand your opponent, and gives a strategy from 21 that has an answer to every possible move.
Key terms
Subtraction game
Definition A subtraction game is a game for two players with one pile of counters and a fixed set of positive whole numbers, called the subtraction set. The players take turns, and a move removes counters for some in that is no larger than the pile. Both players see the pile at all times, and nothing is decided by chance. Under normal play, the rule used on this page, the player who makes the last move wins, so a player who has no legal move loses. When is in , every nonempty pile allows a move, so the last move is the one that takes the last counter.
The take-away game is the subtraction game with , here started from counters. A pile of counters is a losing position for the player about to move, meaning that this player cannot force a win against correct play, exactly when is a multiple of , including . Since is not a multiple of , the first player can force a win. The only winning opening is to take counter and leave . After that, whenever the opponent takes counters, the first player takes , which leaves a multiple of again. If the game started from counters instead, the first player would already be in a losing position, and the second player could force a win with the same reply rule.
In plain words Think of the counters as groups of four plus a few left over. Your opening move removes the leftovers. After that, each round of one move by your opponent and one by you removes exactly one group, because your move always tops up the opponent’s move to four. When the last group is gone, you are the one who took the last counter.
Example You open by taking from , leaving . The table shows one way the rest of the game can go.
| Pile before the round | Opponent takes | You take | Pile after the round |
|---|---|---|---|
Your reply is always legal. Before each round the pile is for some whole number . The opponent takes counters with , which leaves , so the opponent never takes the last counter. Your reply of is also between and , and it is at most , so the counters are there to take. It leaves , the next smaller multiple of . The other two openings fail. Taking leaves and taking leaves , and the opponent then takes or to hand you .
Normal play
Definition A game is played under the normal play rule when the player who makes the last move wins. Equivalently, the player whose turn comes when no legal move is left loses. Under the misère rule the player who makes the last move loses instead. In a counter game in which a single counter can always be taken, normal play means that taking the last counter wins, and misère play means that taking the last counter loses. Winning and losing positions are worked out backward from the end of the game, so changing this one rule can change the answer for every pile.
In plain words Normal play rewards the player who moves last. Misère play punishes that player, so each side tries to leave the last counter for the other.
Example Play the take-away game under the misère rule. A pile of is now a losing position, because the player to move must take the last counter. Piles of , and are winning, because taking , or leaves a single counter for the opponent. A pile of is losing, because every move leaves , or , and each of these is winning for the opponent. Continuing in the same way, the losing piles under misère play are
the numbers that leave remainder when divided by . So with counters the first player, who wins under normal play, is in a losing position under misère play. The second player now wins with the same reply rule. After a move of counters, the second player takes , which keeps the pile one more than a multiple of four until the first player faces a single counter and has to take it.
Winning position
Definition Consider a game for two players who take turns, see the whole position and leave nothing to chance. A position is a winning position if the player whose turn it is has a strategy, a rule for choosing each move, that wins against every possible sequence of moves by the opponent. In a game that always ends after finitely many moves and cannot end in a draw, such as a subtraction game, a position from which a move is possible is winning exactly when at least one legal move from it leads to a losing position.
In plain words A position is winning when you have at least one good move, one that hands your opponent a losing position. It does not matter how many bad moves are available as well.
Example In the take-away game the piles , and are winning, because taking , or respectively leaves , a losing position. From , taking or would be a mistake, since it leaves or and hands the win to the opponent, but one good move is enough. The starting pile of is winning for the same reason, and taking is its only good move.
Losing position
Definition In the same kind of game, a position is a losing position if the player whose turn it is has no strategy that wins against every possible reply. In a finite game with no draws this happens exactly when the opponent has such a strategy. A position from which a move is possible is losing exactly when every legal move leads to a winning position. A position with no legal move gets its label from the rule for the end of the game, and under normal play it is losing.
In plain words Whatever you do from a losing position, your opponent has an answer that keeps you losing. You can still win if your opponent makes a mistake, but you cannot force a win against correct play.
Example In the take-away game the pile of is losing. You cannot take all four, and taking , or leaves , or , which your opponent takes at once. The pile of is losing too, since every move leaves , or , and from each of these the opponent can leave you . A player facing counters against an opponent who knows the reply rule loses whatever they do, but against an opponent who once leaves a pile that is not a multiple of four, they can take over the reply rule and win.
Backward induction
Definition Backward induction is a method for solving a game that always ends after finitely many moves. It labels the positions starting from those where the game is over. A position with no legal move gets the label given by the rule for the end of the game. Any other position is labeled once every position one move away from it is labeled, and it is winning if at least one of those is losing and losing if all of them are winning. In a subtraction game every move makes the pile smaller, so labeling the piles in increasing order reaches every pile. In any finite game for two players who alternate, with full information and no chance or draws, the method shows that every position is either winning or losing, never both and never neither.
In plain words Start at the end, where the answer is obvious, and work back one step at a time, using the answers you already have to find the next one.
Example For the take-away game under normal play, the table lists the piles from to , where their moves lead and the label that follows.
| Pile | Moves lead to | Label |
|---|---|---|
| no move | losing | |
| winning | ||
| winning | ||
| winning | ||
| losing | ||
| winning | ||
| winning | ||
| winning | ||
| losing |
The labels repeat with period four, and the same reasoning proves this for every pile. Suppose the piles below are labeled losing exactly at the multiples of four. If with , every move leaves , or , none of them a multiple of four, so is losing. If with equal to , or , taking counters leaves , so is winning.
Check yourself
- Play the take-away game with counters, moves of one, two or three counters, and normal play. Should you move first, and if so, what should you take?
Show the answer
Yes, move first. The pile is not a multiple of four, so it is a winning position for the player to move. Take counters and leave . After that, answer every move of counters with , so that after your moves the pile is , , , , , and finally . Taking or at the start would be a mistake, because it leaves or , and the opponent could take or to hand you or .
- Change the rule so that a move takes one, two, three, four or five counters, still under normal play, and start with counters. Which piles are losing, and what is the winning first move?
Show the answer
The losing piles are now the multiples of . Backward induction proves it as before. The empty pile is losing. From a pile with , every move of counters with leaves , which is not a multiple of . From a pile with , taking counters leaves . Since
the winning first move is to take counters and leave . After that, answer a move of counters with . In general, when a move takes from one up to counters, the losing piles are the multiples of .
- Now allow moves of one, three or four counters, under normal play, with counters. A guess based on the largest move says to leave a multiple of five. Find the losing piles by backward induction and decide whether you should move first.
Show the answer
Label the piles in increasing order. The empty pile is losing. The pile of is winning, since taking it leaves . The pile of is losing, since its only move leaves . The piles of and are winning, since you can take them whole. The piles of and are winning, since taking or leaves . The pile of is losing, since its moves leave , and , all winning. The pile of is winning, since taking leaves , and the pile of is losing, since its moves leave , and .
The guess fails already at , which is winning. The losing piles are exactly those with remainder or when divided by . From remainder the moves give remainders , and , and from remainder the legal moves give remainders , and , so a losing pile never leads to another losing pile. From remainders , and , taking , or counters reaches remainder , and from remainders and , taking or counters reaches remainder . These moves are always legal, because a pile with remainder has at least counters.
Since , the pile of is losing for the player to move, so you should let your opponent go first. If the opponent takes and leaves , take to leave . If they take and leave , take to leave . If they take and leave , take to leave . Keep leaving a pile with remainder or , and you will take the last counter.