Combinatorial Game Theory
who wins, and by how much
Concept

Ending condition — where it appears

The clause naming who wins when somebody cannot move, which is the single line separating normal play from misère. One line separates two games with the same rules whose theories have almost nothing in common.

Named by 9 essays across 4 fields — each of them below, with the objects they name alongside it.

a cycle of three: what the backward analysis settles. A position graph in which the moves can lead back to where they started. The labels are the order in which a backward analysis settles each position, starting from the ones where a player has already run out of moves. Positions the analysis never reaches are drawn — and there is no test for that; being unreachable is what a draw is.

An outcome with no value behind it

Retrograde analysis labels positions in rounds, outward from the ones already lost. Whatever is still blank when nothing more can be deduced is a draw — and there is no separate test for a draw, because a draw is exactly the residue the method never reaches.

limits · Loopy Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued.

The condition the recursion rests on

Not that the moves run out, and not that the options are few. Poker Nim's heaps can grow without bound and it ends; the game called `on` has one option and never does. What every value on this site needs is that no infinite run of moves exists — and there are three separate ways to fail it.

limits · Termination Hydras, and how long each takes to kill. Six small hydras with the ordinal the termination proof assigns to each and the exact number of chops it takes to finish it. Two of them are not finished here: the fight is guaranteed to end and the machine runs out of memory long before it does, which is the gap between a termination proof and a bound.

It ends, and nothing says when

The recursion this site runs needs every line of play to reach a position with no moves, and the condition is usually met by an obvious decreasing quantity. The hydra meets it with no such quantity anywhere: the tree grows at nearly every step and the fight ends regardless, because the only thing that decreases is an ordinal. A four-node hydra dies in twenty chops; one level deeper and 279 chops reach forty thousand nodes with no end in sight.

limits · Termination Push and Shove over every strip up to 6 squares. The same strips under both rules. A cliff lets coins fall off and a wall does not, and the census says what that one clause is worth: both games are entirely made of numbers, they never agree on a value, and the obvious board-reading is right far more often under the wall than under the cliff.

The other way to move a row

Shove has a cliff and Push has a wall, and that is the whole of the difference. Both games make every one of the 728 strips up to six squares a number, so neither ever has anything worth fighting over — and the two rules do not agree on the value of a single position. The obvious board-reading is exact on 446 strips under the wall and on 140 under the cliff, and 486 strips contain a coin its owner cannot move at all.

positions · Push Every empty NoGo board a build can solve. The empty boards, with the value the recursion returns and the outcome that follows from it. The one-row boards run 0, star, switch and repeat, which is a pattern with no reason behind it that survives past six squares.

Every group must keep breathing

NoGo is Go with no captures at all: a stone may be placed only if, afterwards, every group on the board still has a liberty. That makes a move's legality a fact about the whole board rather than about the squares it occupies — and a board therefore almost never breaks into independent parts. Of 117 boards here whose empty points fall into two regions, 24 are the sum of their regions and 93 are not.

positions · Nogo Where running out of moves is permanent. Eleven rulesets, each walked position by position from three small boards, with every position at which a player has no move examined for whether any continuation gives them one back. Nothing here is evaluated: dead-ending is a property of the rules, and two boards worth the same value can differ on it. 9 of the 11 are dead-ending and 2 are not.

Nobody comes back

There is a class of games in which running out of moves is permanent, and it is the setting almost every modern misère result is stated in. Nine of this site's eleven rulesets belong to it across 5,334 positions; the two that do not are Toads and Frogs and Amazons, and Toads and Frogs loses the property to a single clause — delete the hop and it joins the list.

limits · Dead-ending Moore’s rule, reversed. Moore’s Nim under the misère convention at three values of k, with the normal-play rule and the same rule plus a clause about heaps of one. The patch is the one Nim takes, with the modulus the normal-play rule already carries, and it is right on every position swept.

The patch that generalised

Misère Nim takes a one-line patch: play the normal-play strategy until every heap holds a single counter, then invert. Moore's Nim, where a move may take from up to k heaps at once, takes exactly the same patch with exactly the same modulus — and the two rules disagree on six positions out of 923.

impartial · Moores-nim What a pass buys, and what it costs. Rows of coins solved with and without a pass. Milnor's mean-value theory needs a non-negative incentive to move, and rows containing a coin nobody wants break that condition — a player forced to take is a player who would rather have passed. Allow a pass and the condition is not merely satisfied but unbreakable, on every row in range. The price is that a player who may pass is never stuck, so the last-move convention has nothing to attach to and the game needs a separate rule to end at all.

What a pass is worth to a theory

The rung below finds fifteen of twenty-seven coin rows where having the move is a disadvantage, and those are exactly the rows Milnor's mean-value theory has to assume away. Allow a pass and the hypothesis stops being a hypothesis — nought violations, on every row in range. What it costs is the convention the rest of this site is built on.

applied · Scoring The money played out, and it never mattered. The bidding rule played move by move with a countable pool of chips, at every way of splitting it. The verdict is constant across the splits and opposite under the two ways of resolving equal bids, so what settles these positions is the tie-break rather than the money.

The auction never gets to the money

The critical fraction is computed and never played. Played out with a countable pool of chips — twelve positions, four pool sizes, every split of the chips, every bid answered — the verdict does not move with the money on a single one of the forty-eight sweeps, and the rule for equal bids settles all forty-eight. The reason is one line long: declining every auction wins, and bidding nothing declines.

limits · Bidding

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchNormal playOutcome classNimTemperatureTerminationComplexityDrawDyadic rationalGoInductionLoopy

All concepts