Combinatorial Game Theory
who wins, and by how much
Series

Decomposition — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    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.

    part 1 · complexity
  2. 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.

    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.

    part 2 · complexity
  3. 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.

    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.

    part 3 · complexity
  4. 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.

    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.

    part 4 · complexity
  5. 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.

    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.

    part 5 · complexity
  6. 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 ↓∗.

    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.

    part 6 · complexity

All series