Combinatorial Game Theory
who wins, and by how much
Concept

Scoring game — where it appears

A game that ends with a count rather than with somebody stuck, so that its answer is a margin and not a value. The group structure goes with the convention, and recovering any of it needs the class of games to be restricted first.

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

A 2 × 3 board of boxes, 6 still on the table. A Dots and Boxes position drawn as dots and lines, and — where the figure asks for it — the same position as a strings-and-coins graph: one coin per box, one string per line, and the border lines running to the ground. Lines already played are solid, lines still available are dashed, and a box with no strings left has been pocketed. The footer carries the exact net score the solver computes from here and the normal-play verdict on the same position.

The game in every exercise book

Dots and Boxes is played by more people than every game in this collection put together, and everybody is taught the same rule — take every box available. The rule is wrong. Establishing that takes a solver rather than an opinion, and the solver says how wrong, on which boards, and by how many boxes.

applied · Dots and Boxes The impartial game inside the scoring one. For every position of a Dots and Boxes board, two questions asked separately: who wins the scoring game, and who wins Nimstring — the same position under the normal-play convention, with no score kept. The bars show how often the two answers agree, grouped by how many boxes are still on the table. Agreement is near-total when there is enough left to be worth controlling and falls away when there is not.

The chains decide it before the boxes do

Under every game of Dots and Boxes there is an impartial game with no score in it, and it settles the question the scoring game keeps asking — who ends up having to open. The rule players learn as folklore falls out of it, and so do the exceptions nobody mentions.

applied · Dots and Boxes A game where the last move decides nothing. Rows of coins taken from either end, with the exact score for each side moving first. Under the normal-play convention this family is settled entirely by the parity of the row — nobody is ever without a move until the coins run out — so normal-play theory returns the same answer for every row and it is not the answer anybody wants. The scoring answer depends on nothing but the numbers.

Counting at the end changes everything

Go is scored. So are Dots and Boxes, chess and almost everything anybody plays for money — and none of them is the kind of game this site's whole apparatus is built for. The simplest scoring game there is shows what that costs — the normal-play theory gives every position of it the same answer, and the answer is useless.

applied · Scoring Cancellation, by exhaustion. The law checked on every triple of values born by day two, and then put to work: two Domineering regions compared directly and compared again inside a larger board. The comparison never changes, which is the licence every decomposition on this site is drawn under.

What can be struck out

From G + X = H + X it follows that G = H, in one line, by adding −X to both sides. It is the shortest theorem here and the most used: it is what makes comparing two boards region by region legitimate. Over 10,648 triples the hypothesis fires 484 times and the conclusion holds 484 times — and the licence expires in three separate directions, each of which loses the same axiom in a different way.

sums · Negation Where the two conventions come apart, counted. Every small Go endgame solved under both scoring conventions. The scores agree exactly when the number of neutral points is even and never when it is odd, which is the parity of the stones each side ends up placing. A counted fraction name different winners. And a smaller fraction are played differently, which is the half of the finding a rules argument does not predict: a neutral point is a one-point play under one convention and worth nothing under the other, so the two rule sets disagree about the order of the endgame and not only about its total.

Two ways to count a finished board

Territory scoring and area scoring are both in daily use and they are not variants of one rule. Over seventy-nine small endgames they agree exactly on the thirty-nine with an even number of neutral points and on none of the forty with an odd number — sixteen name a different winner, and twelve are played differently, which is not something a convention is supposed to do.

applied · Go 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 condition has to hold underneath, not on top. Pairs of coin rows sorted by where the incentive condition holds, with Milnor's bound checked on each pair. Rows that satisfy the condition at every subposition never break the bound. Rows that satisfy it only at the top break it on a counted fraction — and a reader who tested the row rather than the row's insides would have called those safe. The distinction is invisible from the position and decides whether the theorem applies to it.

A hypothesis has to hold all the way down

Milnor's bound is proved by induction over the play, so the condition it needs has to hold at every position the play can reach. Checked on the row instead, ninety-two pairs pass the test and twenty-four of them break the bound. Checked at every subposition, twenty-eight pairs pass and none breaks it.

applied · Scoring A game beside its own mirror, and what is left over. Every coin row added to its own negative, played out exactly, with the resulting scores counted. Under the last-move convention every such sum is worth nothing, because the mirroring strategy guarantees the second player the last move. Here the same strategy is available and the score it produces is not nothing: the mirror of a coin conceded is another coin conceded. Gold is the sums that do come to nothing, which are a minority.

Nothing to subtract with

Comparison is defined by contexts and computed by subtraction, and the equivalence between the two is a theorem about groups. A scoring game is not one — sixty-six of eighty-one coin rows do not cancel against their own negatives — and the difference test then fails on a row compared with itself, which every context accepts and nothing certifies.

applied · Scoring Four restrictions, and what each one buys. Four candidate classes of scoring game — every row, the incentive condition at the top, the same condition at every subposition, and the rows that cancel against their own negatives — scored on two families of coin rows for the mean-value bound, for comparison by subtraction, and for cancellation.

The restriction that buys the most

Four candidate classes of scoring game, scored on the same two families and the same three questions. The class everyone expects to be tiny — the rows that cancel against their own negatives — is empty on rows of three and the widest restriction on rows of four, where it holds fifteen rows against the hereditary class's twelve and gets all 225 of its comparisons right against 108 of 144. The trade everyone expected does not exist.

applied · Scoring What control is worth, to a box. The margin the player who does not have to open nets, beside the formula that predicts it: the total less four boxes for every long chain after the first. Computed against the solver on every endgame of long chains in range.

Four boxes for every chain after the first

Nimstring answers who is forced to open and says nothing about the score. The margin has a formula: the controller nets the total less four boxes for every long chain after the first — two surrendered and two not taken, each time control is kept. Checked against the solver on 175 endgames it is exact on 172, never too generous, and exact wherever it promises the controller anything at all. The three it misses are the three where it promises nothing.

applied · Dots and Boxes The fee the geometry charges. The same endgames solved with the cost of declining changed. Two boxes on a chain and four on a loop are what a single cut and a pair of cuts complete; altering them changes the winner of a large share of positions, which is what says the law depends on them.

Two and four are not conventions

Declining costs two boxes on a chain and four on a loop, and those numbers are read off the geometry rather than chosen: one cut completes the last two boxes of a chain and two cuts complete the last four of a loop. Solved again with the fee changed, 418 endgames give a different winner on up to a third of themselves — so the endgame's law is a law about the fee as much as about the shapes, and the fee is not a free parameter.

applied · Dots and Boxes Cancelling is not pairing. For three sets of coin values and rows of two to seven coins, how many rows cancel against their own negatives, how many pair off as nested equal pairs, how many do both, and how many do one without the other.

Cancelling is not pairing

The coin rows that cancel against their own negatives looked like the rows whose coins pair off as nested equal pairs, and on rows of four they are exactly those. From six coins the description fails in both directions — twenty rows pair off perfectly and do not cancel, and one coin set has a hundred and thirty-six that cancel with no pairing at all — and a row of five coins cancels, though an odd row can never pair off. What does hold, on every row swept, is that the first player in a row plus its negative never finishes behind.

applied · Scoring Cancelling rows add to cancelling rows. Every pair of cancelling coin rows of two, four and five coins from minus two, one and three, grouped by their lengths, with the number of pairs whose sum cancels against the sum of their negatives.

A cancelling pair is a zero

Two cancelling coin rows side by side cancel against their two negatives — all 190 pairs from rows of two, four and five coins, the odd row that cancels without pairing off included. And a cancelling row beside its negative is invisible next to any other row: in 741 tests against every row of one to three coins, neither score of the context moves. A non-cancelling pair moves a score in 452 of 780. Scoring games have no inverses in general; this class has them, and they behave as inverses must.

applied · Scoring Even rows always reward the move. For four coin sets and rows of one to seven coins, the number of rows in which the player to move does at least as well as when the opponent moves first. Every even column is full.

Even rows always reward the move

Milnor's mean-value theory needs an incentive to move — the player to move must do at least as well as if the opponent moved first. On a coin row with an even number of coins that is not a hypothesis but a theorem: the first player can collect one whole parity class of coins, and one of the two classes holds at least half the total. So the condition excludes no even row whatever the coins, the class the earlier table called 'incentive at the top' was every row of four, and the hereditary condition is a condition on odd intervals alone.

applied · Scoring

Named alongside it

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

Exhaustive searchNormal playComparisonComponentCounterexampleDecompositionDots and BoxesGroupIncentiveMean valueTemperatureAdditivity

All concepts