Solving finite chip games backward

What you will learn

Derive next-player values from terminal outcomes in a finite subtraction game, select winning continuations when available and distinguish unavoidable loss from a reasoning error.

Prerequisites: Credible continuations and commitment · Complete plans and information sets

State the game before solving it

Two players alternate removing whole chips from one visible pile. A rule specifies which removal amounts are allowed and whether taking the final chip wins or loses. Chips are counters, not payments: every removed chip moves to a tray. There are no hidden cards, draws, opponent types or random outcomes. Both players want to win and know the rules.

The pile size and player to move determine the future. Different action histories can reach the same remaining pile, so storing a state value avoids solving identical continuations repeatedly. This compression works because the allowed actions and objective depend only on the present state. A history-dependent penalty would require a richer state.

Always name whose value you are labeling

Write W(n) for whether the NEXT player can force a win from a pile of n. Under last-chip-wins, W(0)=false: the previous player already won. For a positive pile, each legal removal k switches the player to move. Therefore W(n) is true exactly when at least one legal successor n−k has W(n−k)=false. If every successor is winning for the opponent, the present state is losing.

This is an existence test over all legal moves, not a majority vote over successors or a probability estimate. A losing position can still end in a win against an opponent mistake, but it has no forced winning policy against perfect play. In this activity, legal tied winning actions are all accepted. At a losing state any legal move is acceptable; there is no promised escape.

Build small states and reuse their values

For removals1or2and last-chip-wins, piles1and2are W because a player can take the last chip. Pile3is L: both destinations,2and1, are W. Piles4and5are W by leaving3. Pile6is L. Starting from7, remove1to leave6; after any opponent removal, return the opponent to a smaller multiple of3.

Change the removal set to1or3. Both moves change parity. With the same last-chip-wins terminal rule, odd piles are W and even piles are L. The activity starts this model at8: all legal moves leave a winning odd pile. An optimal opponent forces a loss. Correctly mapping and auditing that outcome completes the learning task; a fake win requirement would reward opponent mistakes instead of valid reasoning.

Terminal conventions are part of the model

Under last-chip-loses, use W(0)=true as a terminal bookkeeping convention: the previous player took the last chip and lost, so the next player is already the winner. No move is taken from zero. For removals1or2, pile1is now L, piles2and3are W and pile4is L. The losing positive piles are1modulo3. Starting from8, remove1to leave7.

The same recursion with a different base value gives a different strategy. Do not import the last-chip-wins pattern into the last-chip-loses game. These are exact finite perfect-information calculations. They do not solve poker with hidden hands, justify a heuristic for an enormous game tree or establish general results for games with chance, cycles or draws. The source illustrates recursive and cached game values; our finite removal rules, misère comparison and ledgers are original constructions.

Hands-on: Map backward states and play an optimal opponent

Classify eight positions under three explicit removal/terminal rules, play legal winning continuations when possible and audit conserved counters and unavoidable loss.

Reading backward workshop…

Common mistakes

• Labeling a position for the original learner when the recurrence describes the next player.
• Calling a state winning because most, rather than at least one, successor is losing.
• Forgetting to change the terminal base when the last chip loses.
• Treating removed counters as profit or creating extra chips on a retry.
• Assuming state compression is valid when future rewards depend on omitted history.
• Equating perfect-information finite recursion with solving full poker.

Keep these ideas

• Specify legal moves, terminal objective and whose value is stored.
• A nonterminal state is W exactly when some legal move leads to L.
• Cache values when multiple histories have the same future decision problem.
• An optimal policy cannot force a win from every starting state.

Further reading

• Charles University programming course — Week12, simple games ↗

  Bounded review of the simple-games section: next-player boolean values, recursive moves and cached state values. Our removal sets, terminal-rule comparison, chip ledgers and artwork are original; not full-course/video review or a full-poker solution. Checked 2026-10-22.