Combinatorial Game Theory
who wins, and by how much
Series

Decomposition — the series

4 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

All series