Combinatorial Game Theory
who wins, and by how much
Generator

A boundary drawn, and a boundary there

A boundary drawn, and a boundary there
A boundary drawn, and a boundary there. One Domineering board split two ways. Above, a line imagined down the middle: the two halves are evaluated separately and their sum is not the value of the board, because every horizontal domino that would have crossed the line has been thrown away. Below, the same column blocked out: the halves are then genuinely independent and the sum is exact. Every value is computed from its own board.

One Domineering board split two ways. Above, a line imagined down the middle: the two halves are evaluated separately and their sum is not the value of the board, because every horizontal domino that would have crossed the line has been thrown away. Below, the same column blocked out: the halves are then genuinely independent and the sum is exact. Every value is computed from its own board.

6 essays call cut-vs-wall. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

11 distinct positions, harvested by running this generator again at the options each essay passed it.

PositionWorth OutcomeDrawn in
1×4 cut at column 1 −1 R Independence is a claim
1×4 whole −2 R Independence is a claim
2×4 cut at column 2 0 P Independence is a claim · The sum is the object
2×4 whole {{2 | 0} | 0} R Independence is a claim · The sum is the object
2×5 cut at column 2 {{3 | 1} | {1/2 | −3/2}} L Finding the parts · How wrong a nearly-independent split is · Independence is a claim · When the regions add
2×5 cut at column 3 {{3 | 1} | {1/2 | −3/2}} L Independence is a claim
2×5 whole 1/2 L Finding the parts · How wrong a nearly-independent split is · Independence is a claim · When the regions add
3×4 cut at column 1 2 | 0 N How wrong a nearly-independent split is · Independence is a claim
3×4 whole −3/2 R How wrong a nearly-independent split is · Independence is a claim
4×3 cut at column 1 {2 | {2 | 0}} L Independence is a claim
4×3 whole 3/2 L Independence is a claim

Where it is called

Changing this generator changes every one of these figures.

A position is the sum of its parts. Four separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable. Sums and comparison

The sum is the object

Real positions come apart into independent regions, and a move happens in exactly one of them. That operation — the disjunctive sum — is what the whole theory is built to survive, and it is the reason values exist at all.

 A boundary drawn, and a boundary there. One Domineering board split two ways. Above, a line imagined down the middle: the two halves are evaluated separately and their sum is not the value of the board, because every horizontal domino that would have crossed the line has been thrown away. Below, the same column blocked out: the halves are then genuinely independent and the sum is exact. Every value is computed from its own board. Sums and comparison

Independence is a claim

Splitting a position into parts and adding the values is the whole method of this subject, and the splitting step is a claim about the position rather than a fact about the drawing. Where it is false the two answers differ — and the failures that matter are the ones that keep the same winner and change the value, because nothing reports those.

 Finding the parts costs the same whether there are any or not. Domineering boards of 4 squares by 5 with different squares blocked out, and what the decomposition is worth on each. The pass that finds the regions is a flood fill and visits every square once, so it costs the same on all of them. What it buys ranges from nothing — on the boards that do not decompose — to a saving of 2,808 positions, and it cannot tell which case it is in until it has run. What it costs

Finding the parts

Decomposition turns a product into a sum and is the largest saving in the subject. Nobody labels the regions. The pass that finds them costs the same on every board of a size — including the boards where there is nothing to find — and what it buys ranges from four orders of magnitude to nothing at all.

 When the regions add. Every board in the independence census — 117 positions whose empty points fall into two or more regions — tested against a stated criterion and against the guess it replaces. The criterion is that no stone group has liberties in two different regions, which makes a move in one region unable to change what is legal in another. It holds on 9 boards and the regions add on every one of them. Particular games

When the regions add

The rung below described the NoGo boards whose regions add as the ones with symmetric walls, and said the description was a guess made from six examples. It is wrong: fourteen symmetric boards do not add and sixteen that add are not symmetric. What replaces it is a criterion about liberties — sound on all 117 boards, provable in a line, and complete on only nine of the twenty-four.

 Four candidate bounds, and the one that holds. Each candidate bound tested against every failing cut. One domino and the height of the cut both fail on six; twice the height holds on all twenty-two; the whole board's temperature fails on eighteen. Sums and comparison

How wrong a nearly-independent split is

Treating a connected board as a sum of two halves is a claim, and the rung below counted how often it fails. This one prices it: over every vertical cut of every small Domineering rectangle the error is a game rather than a number, it is never in Right's favour, and it is bounded below by twice the height of the cut — a bound the height alone does not supply.

 One number, two statements. The smallest true bound on the cost of splitting a board, in both of the currencies it can be stated in. Sums and comparison

One number, stated two ways

Twice the height of the cut held and was loose; the height alone failed. The smallest true constant is three halves — exact and attained as a bound on how far the value can fall, and an infimum attained nowhere as a bound on the value. The gap between the two is one move.

The whole library · The position index · The figures that play back