Pieces that can only come apart

A solver that notices a board has fallen into separate pieces can value each piece on its own and add the results — a product of positions becomes a sum, which is the largest saving in the subject. How often a board falls apart measured how often that happens during a Domineering search, and a wall an amazon can walk through went looking for the game where it should happen most. Amazons burns a square with every arrow, so its regions ought to fall apart and stay apart. They did not: fifty-one thousand moves on a small board put two regions back together, every one of them a diagonal step through a corner the region rule had counted as a wall.

The promise that essay wanted — once split, always split — does hold in another game, and it holds without any walls. In Clobber the pieces of the board are the stones themselves, and a move can only make them fewer. What that promise is worth when it is kept is a separate question, and the answer is less than the argument suggests.

A move that only empties #

Clobber starts from a board full of stones in a checkerboard of two colours. On a turn a player picks up one of their own stones and puts it down on an orthogonally adjacent square holding an opposing stone, which is removed — clobbered. A player with no stone beside an opposing one cannot move, and loses.

Look at what a move does to the set of occupied squares. The stone’s old square becomes empty. The square it lands on was already occupied, by the stone it removes, and is still occupied, by the stone that arrived. Nothing else changes. So every move takes exactly one square out of the occupied set and puts none in. The game begins with every square full and ends when the stones left can no longer reach each other, and in between the occupied set only shrinks.

Now call two stones connected when they are orthogonal neighbours, and call a maximal connected group a piece. A stone can only ever capture into its own piece, because a capture is a step to an orthogonal neighbour, so pieces never interact: a Clobber position is the disjunctive sum of its pieces. Independence is a claim insists that a split into parts has to be checked rather than assumed, and here the check is one line — a capture never leaves its piece. And since a move only removes a square from the occupied set, it can split a piece into several and can never join two pieces into one — removing an element from a set cannot connect two parts that were apart.

That is the argument Amazons appeared to have and did not. There the argument was about walls of burnt squares, and it failed because the pieces that move are not walls and can step between regions at a corner. In Clobber there are no walls to fail. The things that move are the pieces’ own members, they only move within their piece, and they vacate more than they fill.

The contrast in numbers is stark. The Amazons walk covered 127,583 positions and 2,300,392 moves on a three-by-four board, and fifty-one thousand of those moves joined two regions the edge-neighbour rule had kept apart. The Clobber walk below covers nearly twenty times as many positions on four boards and finds none.

The census is not needed for the argument, which is complete. It is there because the Amazons essay was a demonstration that a complete-looking argument can be wrong about the instrument it relies on, and a check on sixteen million moves is how an argument about a region rule earns trust. It also fixes the convention precisely. The region rule here counts only edge neighbours, and that is correct for Clobber for the same reason it was correct for Domineering and wrong for Amazons: a Clobber capture is a step to an edge neighbour and never to a corner one, so two stones touching only at a corner can never interact.

How often it pays #

A promise that the board will stay split is only worth something if the board splits. The census counts, at each point of the game, how many positions hold two or more live pieces — pieces in which some stone has an opposing neighbour, so that somebody can still move there.

The shape is the same on every board. For the first few moves the stones are one piece, because a full checkerboard is a single connected block and removing two or three stones from a block that size does not cut it. In the middle of the game — seven moves in, on four by four — two positions in five are in two or more live pieces. And then the share falls, which looks at first like the promise being broken and is nothing of the kind. A piece that splits stays split; what happens late in the game is that the pieces die. A piece loses its last opposing pair, its stones become permanent furniture, and the position drops back to one live piece or none.

Averaged over all four-by-four positions the share is a third: 32.9 per cent of positions hold two or more live pieces. When a position does split, it is almost always into two; the mean is 2.09 live pieces.

Stones that no longer play #

The falling right-hand side of that curve is the part of Clobber that no decomposition measured before, in Domineering or Amazons, had to account for.

A stone is dead when nothing in its piece can move — every stone in the piece is the same colour, or the piece is a single stone. Such a piece has no options for either player; it is the game nought, and adding nought to a sum changes nothing. So a solver can simply delete every dead stone before it looks at the position, and the position it then has to value is smaller and, more to the point, the same as many others. Three quarters of all four-by-four positions carry at least one dead stone, which means three quarters of the positions a naive solver would store are duplicates of smaller positions padded with furniture.

In Domineering the corresponding thing is a region of empty squares too small to hold a domino, and the Domineering census already discounted those as dead space. In Clobber they are far commoner, because every capture both removes an opposing stone and moves one’s own stone into a position where it may have no enemies left beside it.

What a solver actually stores #

The practical question is how much each of these facts shrinks the table a solver has to build.

The table is read left to right. A solver that stores whole boards stores 1,809,927 of them for four by four. Deleting dead stones first leaves 791,655 distinct boards — the largest single saving, a factor of 2.29. Valuing live pieces separately instead of boards leaves 424,085 distinct pieces: a further factor of 1.87, which is what the split is worth. And recognising that a piece is the same game wherever it sits on the board, so that a piece can be shifted to its corner before it is looked up, takes the count to 395,947 — only seven per cent more. The whole saving is a factor of about four and a half.

Dead stones are so large a saving because they are so common and so cheap to recognise: a piece is dead as soon as it holds no blue stone beside a red one, which a solver can see in the same pass that finds the pieces, and every dead piece removed collapses a whole family of boards — the same live position with its furniture in different places — onto one entry.

The order of those factors is the finding. The decomposition that the Amazons essay was chasing, and that the promise protects, is the second-largest saving on three of the four boards; on those three, deleting pieces that are worth nothing saves more than splitting the live ones apart. Only on two by six, a board one stone wide in places, does the split win narrowly — 2.30 against 2.20 — because a narrow board is cut by the removal of a single stone.

What the promise buys a solver #

The census so far has measured the decomposition. The promise that pieces never rejoin is a separate thing, and it buys a separate saving, which is worth pricing on its own because it is the part Amazons could not have.

A solver that exploits decomposition has to find the pieces of every position it visits — the flood fill finding the parts priced, which costs the same on every board of a size whether or not there is anything to find. In a game where pieces can rejoin, that fill has to be redone over the whole board after every move, because any move might have connected anything. In Clobber it does not. A move is made inside one piece; the other pieces are untouched and are still exactly the pieces they were; only the piece the move was made in can have changed, and only by splitting. So the solver needs to redo the fill on that piece alone.

The saving is real and it is modest. On four by four the piece a move is made in holds on average 72 per cent of the stones, so re-examining only that piece saves about a quarter of each flood fill; once the board has come apart it saves about a third. Before the first split it saves nothing, because the whole board is one piece. The promise, in other words, is worth most exactly when decomposition itself is worth most, in the middle game, and does not compound it. A flood fill over sixteen squares is cheap in any case, and a quarter of a cheap thing is not what makes a solver fast.

The pieces a solver stores are large #

The saving that does matter is the table, and its composition is worth a look, because the obvious hope for a decomposing solver is that the board breaks into small pieces whose values could be settled once and looked up.

The hope is not what happens. There are only forty distinct live pieces of three stones or fewer — a two-stone piece is a blue and a red side by side, four ways — and a table of them is trivially small. But they are not what fills the solver’s memory. The distinct pieces are overwhelmingly large, peaking at nine stones out of sixteen, because a split in Clobber typically cuts one or two stones off a big piece rather than cutting the board in half. The small piece is the same few shapes over and over; the large piece is new every time. So the table a decomposing solver builds is made of pieces nearly as large as the board, and decomposition shrinks it by the factor of 1.87 above rather than by the orders of magnitude a split into equal halves would give.

Domineering splits more often #

That comparison sharpens against the game the decomposition method was built for.

Domineering’s regions only shrink as well. A domino covers two empty squares and uncovers nothing, so a region of empty squares can only be cut, never rejoined — the same one-line argument, run on empty squares rather than on stones. Both games keep the promise. Domineering keeps it and splits nearly half its four-by-four positions; Clobber keeps it and splits a third.

The reason offered here is a reading of the rules rather than a measurement. A Domineering move takes away two squares, which is enough to cut a region across a narrow neck; a Clobber move takes away one, and a piece of stones is cut by one removal only where it is one stone wide. And Domineering’s positions are fewer and simpler — 5,700 on four by four, against 1,809,927 for Clobber, because Clobber’s positions carry colours — so there are fewer ways for a Domineering region to stay whole.

There is a surprise in the combination. The game in which splitting is guaranteed permanent is the game in which it is rarer, and the game with the richer state space is the one where decomposition buys less than simply throwing away what cannot move. Monotonicity is a property a solver can exploit — it never has to re-check whether two pieces have merged — but it is not the property that makes decomposition pay. What makes it pay is how often the board comes apart, and that is a fact about how much of the board a move removes.

The rules the counts depend on #

Clobber here is the standard game on a rectangle: two colours in a checkerboard, a move lifts one of the mover’s stones onto an orthogonally adjacent opposing stone and removes that stone, and a player unable to move loses. Positions are every board reachable from the checkerboard start by any sequence of moves by either player, identified by which squares hold which colour; this counts more positions than a strictly alternating game would reach, and it is the convention of the Domineering census it is compared with, so the two shares compare directly. Pieces are orthogonally connected groups of stones; a piece is live when some stone in it has an opposing orthogonal neighbour. Distinct pieces are counted with their colours, once in place and once shifted to the top-left corner of their bounding box; reflections and rotations are not identified.

What the counts cannot show #

That no move joins two pieces is proved above for every board, and the census confirms it on four. Everything else is measured on four boards of at most sixteen squares, and none of it is proved to continue: the share of split positions may rise on larger boards, where there is more room for a piece to be cut, and the relative sizes of the three savings may change. The table counts what a solver would store, not what it would spend: a piece stored once is valued once, but the cost of valuing a large piece is not the cost of valuing a small one, and nothing here weighs the entries. And the explanation of why Domineering splits more often is offered as a reading of the rules and is not tested.

Still open: a table halved by its own colours #

Two identifications are left that the table did not make. A piece and its mirror image are the same game, and since a Clobber capture looks the same in all four directions, every reflection and rotation of a piece is too — up to eight copies of each shape that a solver could store once. What counts as the same position is the essay about that identification and its ceiling, and on Clobber’s pieces, most of which have no symmetry of their own, the saving should sit much nearer the ceiling than the shifting did. And a piece with its colours swapped is the negative of the original: the same moves with the players exchanged, which every game has a negative shows is a game whose value is the original’s with its sign turned over. A solver that stores one piece of each negative pair and reads the other off by negation should roughly halve the piece table for nothing — unless a large share of pieces are their own negatives, which on a checkerboard of two colours they may well be. How many pieces are self-negative, and so how close the table comes to halving, is the next measurement; it would say whether Clobber’s colours, which multiply its four-by-four positions three hundredfold over Domineering’s, can be made to pay for part of what they cost.