Combinatorial Game Theory
who wins, and by how much
Concept

Hydra — where it appears

A rooted tree that grows several new copies of a branch each time one is cut. It terminates, and nothing bounds when: the only quantity that decreases is an ordinal, which is why it is the standing example of a game whose ending is a theorem rather than a count.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Two ways to be certain and ignorant at once. Ten positions from two games that both terminate for reasons no bound comes out of. Sylver Coinage's proof counts something that goes down and can be counted; the hydra's counts an ordinal, which cannot, and the last column shows what that difference is worth.

Two ways to end with no bound

Sylver Coinage and the hydra are both guaranteed to finish and neither will say when. The difference is that one of them carries its own bound: every move in Sylver removes at least one gap, the gaps can be counted in a moment, and over ten openings the longest play uses every single one. The hydra has no decreasing quantity a solver can hold — three hydras of five nodes each take seven chops, twenty-one, and a number past two hundred and seventy-nine that this machine never reaches.

limits · Termination Two ways to be certain and ignorant at once. Ten positions from two games that both terminate for reasons no bound comes out of. Sylver Coinage's proof counts something that goes down and can be counted; the hydra's counts an ordinal, which cannot, and the last column shows what that difference is worth.

Which games end at which level

Between a game that ends within a computable bound and one that ends with no bound at all there are levels, each corresponding to a strength of induction. This site's games sit at three of them, and which level a game is at is decided by exhibiting its termination measure and checking that every move lowers it.

limits · Termination

Named alongside it

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

Exhaustive searchInductionOrdinalProofSylver CoinageTerminationBoundDecreasing quantityEnumerationFixed length gameFrobenius numberGame length

All concepts