Combinatorial Game Theory
who wins, and by how much
Concept

Move — where it appears

A legal transition from one position to another, made by one player, and the only thing a game is built out of. A position is its list of moves and nothing else, so every value on this site is a fact about the moves available rather than about the pieces on the board.

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

Which description of a surviving option is right. The two candidate readings of what the reduction keeps, scored over every Domineering option list on six boards. Taking the most room is right on under half the lists, which is what a description with no content scores on lists this short. Leaving the opponent fewest replies is right on nine in ten.

Which option the reduction keeps

Domination deletes an option when another is at least as good, so what survives is the top of an order. On a board that order is made of moves, and two descriptions of the surviving move suggest themselves. Over 1,586 Domineering option lists one of them is right 47% of the time and the other 90%, and the one that wins is not the one a player would guess.

values · Dominance How much a domino count knows about a region. The difference between the two players' largest domino packings, set against the value of the region. On the regions worth numbers the count is the value under half the time; on the rest it lands somewhere between the two stops on 85 per cent of them.

Counting the moves each side has

How many dominoes could each player still place? Subtract, and there is a whole number computable from the drawing with no game theory in it. Over 1,042 regions it is the value on 141 of the 315 worth numbers, lands between the stops on 619 of the other 727, and its failures are two different kinds — one of which was inevitable and one of which is a fact about the game.

positions · Domineering

Named alongside it

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

CounterexampleDecompositionDomineeringEnumerationValueAntichainApproximationCanonical formComparisonDominanceHot gameInfinitesimal

All concepts