Combinatorial Game Theory
who wins, and by how much
Generator

A board in pieces costs the sum, not the product

A board in pieces costs the sum, not the product
A board in pieces costs the sum, not the product. A Domineering board with squares blocked out, so that it falls into regions no domino can span. The number of positions in the whole board is exactly the product of the numbers in its regions — which is why evaluating the regions separately, and adding the values, is an exponential saving rather than a tidier way of writing the same search.

A Domineering board with squares blocked out, so that it falls into regions no domino can span. The number of positions in the whole board is exactly the product of the numbers in its regions — which is why evaluating the regions separately, and adding the values, is an exponential saving rather than a tidier way of writing the same search.

9 essays call decomposition. 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.

Where it is called

Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.

A board in pieces costs the sum, not the product. A Domineering board with squares blocked out, so that it falls into regions no domino can span. The number of positions in the whole board is exactly the product of the numbers in its regions — which is why evaluating the regions separately, and adding the values, is an exponential saving rather than a tidier way of writing the same search. What it costs

The board falls apart, and the arithmetic changes

A 4×5 Domineering board with a wall down the middle has 2,916 positions in it, and that number is exactly 54 × 54 — the product of its two halves. Solving the halves separately costs 108. Decomposition is the one saving in this subject that turns a product into a sum.

 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.

 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.

 Three questions about the same board. For each sum of two positions: the cost of deciding who wins each part alone, of deciding who wins the whole sum by search, and of computing what each part is worth. The middle question is in the middle on seven of the eight, and the exception is the sum whose two parts are identical. What it costs

The question in the middle

Between knowing who wins each part and knowing what each part is worth sits the question a player actually has: who wins the board. Priced on sums of two it lands between the other two on seven of eight, cheaper than the values by up to eight times. On sums of three, with nothing repeated, it is dearer than the values on five of six — because a component multiplies a search and only adds to a value.

 Where in a game a board falls apart. Every position reachable from an empty Domineering board, grouped by how many dominoes have been placed, with the share that have fallen into two or more live pieces. The share is nought at both ends of the game and around three fifths in the middle. What it costs

How often a board falls apart

A decomposition turns a product into a sum, so a solver wants to know how often one arrives. Over every position of a 4 × 4 Domineering board the answer is 47 per cent — nought for the first two moves, three fifths in the middle, and nought again at the end. What one decomposition is worth is the other half of the answer and it is a factor of 1.8.

 When a catalogue starts paying. How many decomposed boards a catalogue of regions has to answer before building it costs less than searching each board directly. Five boards for regions of four squares, two hundred for regions of eight. What it costs

When the catalogue starts paying

The rung below priced two questions — who wins one board, and what it is worth — and named the third: a program pays for a family of regions once and answers every board over them by addition. The crossover is between five boards and two hundred, depending on how far the catalogue reaches, and it falls as the board grows. The whole catalogue of every region to eight squares costs one part in seventy-six of one undecomposed five-by-five board.

 One board, two answers to how many pieces it is in. Every position reachable from a small Amazons opening, counted by depth, under two ways of deciding whether two squares are in the same region. Counting only edge neighbours, a third of all positions are in pieces; counting corners too, an eighth are. What it costs

A wall an amazon can walk through

An arrow burns a square for good, so an Amazons board that has fallen into pieces should stay in pieces. Over 127,583 positions it does not: fifty-one thousand moves put two regions back together. Every one of them is a single diagonal step, and what is wrong is not the game but the rule used to find the regions — which was borrowed from a game whose pieces lie along the board's own lines.

 A Clobber board in three pieces. A four-by-four Clobber position after seven moves: the stones form a live region along the top row, a second live region at the lower left, and a dead pair of red stones at the lower right that has no move for either player. The regions can split further but never rejoin. What it costs

Pieces that can only come apart

Amazons broke the promise that a board once split stays split, because a moving piece can step diagonally between two regions. Clobber keeps it with no walls at all: a move lifts a stone onto a neighbouring enemy stone, so it empties one square and fills none, and pieces of stones can only shrink. Checked on every move from every position of four boards — 16.3 million moves — not one joins two pieces. The promise holds and is worth less than it sounds. A four-by-four Clobber board is in two live pieces a third of the time, against nearly half for Domineering, and most of what a solver saves comes not from the split but from the stones that no longer have a move.

 A piece, its mirror, and its negative. A Clobber piece of ..o/oox worth ↑∗, drawn as it stands, mirrored, with its colours swapped and both. The mirrored piece is worth ↑∗ and the two colour-swapped pieces ↓∗. What it costs

The colour swap pays through a mirror

A Clobber piece with its colours swapped is the same piece with the players exchanged, so a solver could store one and read the other off by negation. On its own that folds the piece table by about a tenth, because a piece's negative is rarely in the table at all. Beside symmetry it nearly doubles the fold on three boards of four, because on a board with an even side a mirror carries every position to the negative of another. And the opening of every such board is worth its own negative — a theorem from the mirror, not a search.

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