Combinatorial Game Theory
who wins, and by how much
Concept

Endgame — where it appears

The stage at which a position has broken into independent parts, which is where every technique on this site applies. It is the stage at which the sum arrives, and on a small board it arrives within three moves rather than at the end.

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

Which questions are answerable. The theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space.

How hard is it

Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.

complexity · Complexity 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 thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

What is at stake

Some positions both players are desperate to move in, and some neither player wants to touch. The difference is a number — how much the move is worth — and it turns out to be the most useful single quantity for deciding where to play.

temperature · Temperature Domineering on 2 by 3. Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. The two players see different games on the same board, which is what partizan means — and the value that results is not a number.

Domineering

One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it.

positions · Domineering A position that comes back. Three positions whose moves lead round in a circle. Every value in this subject is defined by recursion on the options, and that recursion assumes play ends — here it need not, so the definition has nothing to stand on and the outcome may be a draw, which normal-play theory has no name for.

Loopy games

The whole theory assumes play stops. Allow a position to recur and the induction that every value rests on has nothing to stand on — and a fifth outcome appears that normal-play theory has no name for.

limits · Loopy 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 Move where it is hottest. four independent components of one position, ordered by temperature. The temperature is how much a player loses by moving somewhere else instead, so the hottest component is the one to take — and a component that is already a number has no temperature at all, because nobody gains by moving in it.

Playing the hottest

Given several independent fights, play in the one with most at stake. The rule is simple, it is what strong Go players do without being told, it is provably close to optimal — and it is provably not optimal, which is the interesting part.

temperature · Temperature a loop with a way out: 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.

Start at the end and work backwards

When play can return to where it started there is no bottom for the recursion to stand on. What replaces it begins at the positions where somebody has already lost and propagates outwards — and the positions it never reaches are exactly the draws. There is no test for a draw, and there does not need to be.

limits · Loopy The endgame, accounted for. Several independent regions, each a fight with a settled value and a size. The account plays them hottest first: add up what each is worth on average, then add the largest amount at stake, subtract the next, and so on down. The exact value of the whole position is computed beside it, and the figure prints both.

The endgame, accounted for

Add up what each region is worth, then add the biggest thing at stake, subtract the next, and so on down. On a board of simple fights the result is exact — and the moment one region has a fight inside it, the account is out by a point.

temperature · Thermograph Why nobody moves in the number. A hot position added to a number. Left wins the sum whoever moves — but only by moving in the fight. Spending the move on the number instead hands the position back as a first-player win, with Right to move, which throws the win away. The theorem says this is always so, and here it is happening.

Numbers avoid numbers

In a position with a number in it and anything else, the number is never the right move. That is a theorem rather than a heuristic, and it is the closest this subject comes to advice a player can carry into a real game.

values · Numbers {2 | 0} + {2 | 0} — where the temperature goes. Three thermographs on one frame: two positions and their sum. The mean of the sum is the sum of the means, every time. The temperature is not: it is bounded by the hottest of the parts and is often far below it, so the number that says how much is at stake in a whole board cannot be got by adding up the parts.

Two hot fights that add to a cold number

The mean of a sum is the sum of the means, every time. The temperature is not — it is bounded by the hottest part and is often far below it. Two positions each worth fighting over can add to a plain number that neither player wants to touch.

temperature · Thermograph Amazons, after the arrows have cut the board in 2. An amazon moves like a queen and then shoots an arrow, also like a queen, which burns the square it lands on. Late in a game the burnt squares cut the board into regions no amazon can cross — and from that moment the position is a sum of independent games, which is the shape the whole theory was built for, arrived at by the play rather than assumed.

Amazons, and when a position becomes a sum

Every technique on this site starts from a position already broken into independent parts. Amazons does not begin that way — the board is one fight until the arrows cut it, and the moment of cutting is something the play produces rather than the analyst assumes.

positions · Amazons A switch, its mean and its temperature. Positions of the form {a | b} with a above b: both players want to move there, so neither is settled. The bar spans the two options, the marked point is the mean the position is worth once the fighting is over, and the temperature is half the gap — which is exactly what moving first is worth.

Worth nothing, and worth fighting for

A switch is a position both players want to move in. Its average value can be zero while the difference between getting there first and second is enormous, and that gap is a second number every position carries.

values · Switches {4 | 0} played out in a stack of 5 coupons. An idealised environment: coupons worth a fixed step less each, which either player may take instead of moving in the game. The rows are the line optimal play takes over the whole board, in order. What the game turned out to be worth is set beside its mean value, and the coupon the players stopped at beside its temperature — two quantities measured from the play, and two computed from the thermograph.

An environment made of coupons

Beside the game sits a stack of coupons worth 4, 3, 2, 1, 0, and a player may always take the top one instead of moving. Play the whole thing out and two quantities the theory computes are measured instead: {4 | 0} comes out worth exactly 2, its mean value, and the coupons stop at 2, its temperature. For {10 | {9 | 1}}, whose temperature is 1, they stop at 7/2 — because what the stopping coupon measures is the hottest temperature anywhere in the tree.

temperature · Coupons 4 | 0 and {2 | {1 | 0}} in the same environment. Two positions and one coupon stack, solved as a single board. The rows are the line optimal play takes; the coupon on top when each position is first entered is compared with the coupon it was entered at when it had the environment to itself. The mean contributions still add and the entry coupons need not agree.

Two games in one environment

A coupon stack measures a position: play the whole board out and the coupon the players stop at is the temperature, the score is the mean. Put a second position beside the first and one of the two measurements stops working. Over 36 ordered pairs the contributions still add to the means every time, and the coupon a fight is entered at moves on 13 of them — without either position changing.

temperature · Coupons Every part on its own is worth nothing. The Grundy value of each chain and loop considered as a game by itself, and three real Dots and Boxes boards used to check the turn-by-turn walk against the win-or-lose solver already used here. Every component alone is a second-player win, which is exactly what makes the nim-sum useless.

The parts are worth nothing and the sum is not

Every chain and every loop in Nimstring, taken alone, has Grundy value nought. So the Sprague–Grundy theorem predicts that every position built from them is worth nought — and ninety-six of the two hundred and seven positions checked here are not. The theorem is not being misapplied; it does not apply, because a capture keeps the turn. What replaces it is smaller and sharper: count the short chains, and one long component of any kind reverses the parity.

applied · Dots and Boxes How much of a board the endgame theory reaches. Every subset of a board's strings, counted by whether the surviving coins fall into chains and loops. The share is taken over the positions with no free box on the table, since a position with a capture available is one a player takes rather than chooses from.

The endgame theory arrives late

Every component the chain-and-loop theory names has coins of degree two, so a position it can read is one where every surviving coin holds exactly two strings. Over a six-box board that is 1,033 of the 28,028 positions with no free box on the table — 3.7 per cent — and more than half of them only after twelve of the board's seventeen strings have been cut.

applied · Dots and Boxes The law, on a board rather than in a bag. The parity law applied to every position of a real board that has fallen into chains and loops, with the verdict computed independently from the board's own strings. The components are the ones the geometry produces rather than the ones a sweep constructs.

A thousand positions and no exception

The parity law was fitted to constructed bags of chains and loops inside a string budget. A board's positions are a different population — the sizes are what the geometry allows, the components come correlated, and a six-box board holds exactly one position that is a loop of six. Tested on all 1,032 of them and all 160 of the four-box board's, the law is right every time, against a verdict computed from the strings by a walk that has never heard of a component.

applied · Dots and Boxes The components the theory does not name. Grundy values of strings-and-coins components with a branching coin, grouped by the value. A chain or a loop is worth nothing on its own whatever its size; a coin with three strings takes four different values depending on its arms, and a coin with four strings is back to nothing.

A coin with three strings is worth something

Every chain and every loop is worth nought on its own, whatever its size, and that is exactly what makes their nim-sum useless. A coin with three strings on it is worth nought, one, two or three depending on its arms — 31 of the 35 measured are not nought, and the four that are are the ones whose arms are all long. A coin with four strings is back to nought every time.

applied · Dots and Boxes 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

Named alongside it

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

DecompositionExhaustive searchNormal playTemperatureComponentDots and BoxesStrings and coinsSwitchHot gameImpartialSenteThermograph

All concepts