How often a board falls apart

A Domineering board that has fallen into two regions is two games, and the value of the whole is the sum of the values of the parts. That is the largest economy the subject offers: the number of positions a solver must enumerate goes from the product of the parts’ tables to their sum.

Finding the parts priced the detection — a flood fill over the free squares, once per node — and closed by naming what it had not measured:

The rung above is the distributional one — how often positions decompose during a real search, at what depth, and therefore whether a per-node flood fill pays. That is a measurement this site’s machinery could make on Domineering and Amazons, and it is the number a solver author would actually want.

Here it is. On a 4 × 4 board, 2,680 of the 5,700 reachable positions have fallen into two or more live pieces — forty-seven per cent — and the distribution over the game has a shape that decides how a solver should be written.

Not at the start, not at the end #

The distribution is not flat and it is not monotone. It rises from nought and falls back to nought, and both ends have reasons.

Nothing decomposes in the first two moves. One domino covers two adjacent squares and cannot cut a 4 × 4 board in two; the earliest a decomposition can appear is two dominoes down, and 28 of the 215 positions at that depth have one.

The peak is at four dominoes, halfway through the game: 1,118 of 1,911 positions, fifty-nine per cent. Depth five is nearly as high at fifty-six.

Nothing decomposes in the last two depths. At seven dominoes there are two squares left; a position with two free squares is one live piece or none, and the census counts a region with no room for a domino as dead space rather than as a component. That is the right convention — a solver that counted a stranded single square as a part would report a decomposition worth nothing — and it is why the tail is exactly nought rather than nearly.

So a solver meets decompositions in the middle game and nowhere else, which is the same place a human player meets them and for the same reason.

Always into two #

The other number a solver author wants is how many pieces, and it barely varies.

The mean is 2.16 pieces on a 4 × 4 board, 2.08 on 3 × 5 and 2.04 on 3 × 4. Decompositions into three or more exist and are rare; a board of this size does not have room to be cut twice before it runs out of squares.

The share climbs with the board, which is the direction that matters. A larger board has more room for a wall of dominoes to separate two areas, and there is no reason for the trend to reverse: a 6 × 6 board should decompose more often than a 4 × 4, and an 8 × 8 more often still. The three sizes here are the ones a build can enumerate exhaustively, and they point the same way.

What one split is worth #

Frequency is only half the question. A saving that arrives on half the nodes and is worth nothing is worth nothing.

Each decomposition is priced by the ratio between the two tables a solver would build: without the split, the positions below this node number the product of the parts’ tables; with it, the sum. That ratio is what the split saves at that node.

The mean is 1.8 and the best is 7.5.

Those two numbers are worth reading together rather than in sequence. A mean of 1.8 with a best of 7.5 says the distribution has a tail: most splits save very little and a few save a great deal, and a solver’s total saving is dominated by the few. That is the ordinary shape of a saving that multiplies rather than adds, and it means the average is the wrong summary — what a solver gets is the product of the savings along a path, not their mean.

That is the discouraging half of the answer and it needs to be read correctly. The saving is small because the pieces are small: two regions with tables of five and six give a product of thirty and a sum of eleven, a saving of 2.7. The same construction on regions with tables of a thousand each gives a saving of five hundred.

So the measured saving is a fact about 4 × 4 boards and not about decomposition. What the census establishes is the frequency, which is a structural property, and it prices the splits at a size where the price is necessarily low. A solver author reading this page should take the 47 per cent seriously and the 1.8 as a lower bound that grows with everything.

The best split on the board is worth 7.5 and it arrives at depth two: two dominoes placed so that the board becomes two regions of fifteen positions each, giving 225 against 30.

Why the middle and not the end #

The shape of the distribution has an explanation and it is worth having, because it is the part that transfers to a game this census does not cover.

A decomposition needs two things at once: enough dominoes on the board to build a wall, and enough free squares left for two live pieces. Those two requirements pull in opposite directions as the game goes on, and the peak is where they cross.

Early there are not enough dominoes. Two dominoes can cut a 4 × 4 board and most arrangements of two do not; by four dominoes half the board is covered and a great many arrangements separate what is left.

Late there are not enough squares. At six dominoes there are four free squares, and four squares split into two live pieces only if they are two adjacent pairs; at seven there are two, and two squares are one piece or none.

So the peak is at the depth where the board is half covered, and that is a statement about area rather than about Domineering. Any game whose moves cover squares and whose components need room should have the same shape, with the peak at half and nought at both ends — which is a prediction this census makes and does not test.

Does the flood fill pay? #

The question the rung below asked, answered with the two numbers together.

A flood fill over sixteen squares is a few dozen operations. Evaluating a node is a recursion over its options. So the check costs a small constant and pays a factor of 1.8 on 47 per cent of nodes — and the arithmetic is not close. Even at this size, where the saving is at its smallest, the fill pays for itself many times over.

There is a sharper way to put it that does not depend on the ratio at all. A solver that never checks for a decomposition is enumerating the product where it could be enumerating the sum, on nearly half its nodes. Whatever that costs, the check costs a flood fill, and a flood fill is not a recursion.

The only version of the question where the answer could be no is a game whose positions almost never decompose, and the census says which games those are: ones where a move cannot separate the board. End-Nim is the standing example, and Shove is another — a row of heaps never falls apart, because taking counters off an end leaves a shorter row — and there the fill is pure cost. On a board game it is not.

Where a solver should check #

There is a refinement the distribution suggests and it is worth naming because it is nearly free.

Nothing decomposes above depth two or below the last two depths. A solver that skips the flood fill outside the window where decompositions occur saves the check on the opening moves and the endgame, which on a 4 × 4 board is 90 of the 5,700 nodes — not worth having.

But the window is a fact about this board size and it scales the wrong way. On a large board the opening is a larger fraction of the game and the endgame is not, so the saving is a constant number of plies at the start and grows with nothing. The refinement is not worth implementing, and saying so is more useful than proposing it, because the shape of the distribution invites it.

What is worth having is the observation that a decomposition, once it appears, persists. A move inside one region cannot rejoin two regions, so a position that has fallen apart stays apart — and a solver that records the split rather than rediscovering it at every node below pays for one fill instead of a subtree of them. That is the standard implementation and this census says how much of the tree it applies to.

What it says about the two savings together #

This site measures three savings a Domineering solver can take, and putting this page’s number beside the other two changes the ranking.

Memoisation collapses routes into positions and is worth the ratio between the number of games and the number of arrangements, which is enormous and grows with the board. Symmetry divides by a group of four and cannot do better whatever the board. Decomposition turns a product into a sum, on 47 per cent of nodes here.

The ranking that comes out is not the one the arithmetic alone suggests. Memoisation is unconditional and enormous. Symmetry is unconditional and small — a factor of four, forever. Decomposition is conditional and its condition holds about half the time, which puts it firmly ahead of symmetry and behind memoisation at every size measured.

And the ordering is stable in the direction that matters, because decomposition’s frequency climbs with the board and its saving climbs with the size of the pieces, while symmetry’s factor of four does neither. So the gap widens, and a solver that implements symmetry and not decomposition has spent its effort on the one saving that cannot grow.

What the numbers are counting #

Two definitions in the census are choices rather than facts, and both change the answer.

A position is an arrangement of covered squares, not a route to it. Two different sequences of dominoes reaching the same covered set are one node here, which is the identification a real solver makes and the saving what counts as the same position prices and is why the count is 5,700 rather than the number of games. Counting routes would multiply every figure on this page by a large factor and would answer a question about play rather than about search.

A piece is live when a domino fits in it. A 4 × 4 board with fourteen squares covered has two free squares, and if they are not adjacent it has two regions and no moves. Calling that a decomposition would put a large spike at the last depth and would mean nothing: a solver splitting there splits a game with no positions in it. The convention is the one a solver would use and it is what makes the tail nought.

Both are stated because the 47 per cent moves if either changes.

A rate and a size are the two halves of a saving #

The two numbers here — how often a decomposition arrives, and what one is worth — have to be multiplied to say anything, and they behave completely differently, so it is worth keeping them apart.

The rate is a property of the game’s geometry. It is nought at the start, because a fresh board is one region; it is nought at the end, because a board with nothing left on it has nothing to split; and it peaks in the middle, where placements have accumulated enough to cut the board and not enough to exhaust it. That arc is a fact about how fast a rule destroys connectivity, and it is why Amazons and Domineering have such different profiles under the same theorem.

The size is a property of arithmetic and of the split’s shape. A product becomes a sum, so an even split of a board with $N$ positions turns $N$ into roughly $2\\sqrt{N}$ — an enormous saving — while a split that shears off a single square turns $N$ into $N/2 + 2$, which is barely anything. Real splits are lopsided, and that is why the average saving is a factor of 1.8 where the demonstration board on the rung below shows twenty-seven.

Neither number alone is the answer and their product is. A rate of a half at a factor of 1.8 is a modest expected saving per node, and it is still worth testing at every node, because the test is a flood fill against a subtree and the payoffs compound down the tree rather than adding.

The habit that follows is to distrust any single headline about decomposition. It turns a product into a sum is the size at its best; boards usually split is the rate at its best; and the honest figure is what a solver actually experiences, which is both of them at once and neither at its best.

What the census does not say #

Four limits.

Three small rectangles. Every number is over boards of twelve, fifteen and sixteen squares, exhaustively enumerated. The trend across the three is the evidence for anything larger and it is three points.

Domineering only. The rung below named Amazons as the other candidate and this page has not run it. Amazons decomposes far more dramatically — an arrow cuts a board permanently — so the share should be higher and the savings much larger, and neither is measured here.

The price is a local price. Each split is valued by the ratio at the node where it first appears, and the parts of a split can split again. Compounding those is a different calculation and it makes the saving larger, so 1.8 is a floor rather than an estimate.

And the census is over reachable positions rather than over a search. A real solver with alpha-beta or a transposition table visits a subset chosen by its own move ordering, and whether that subset decomposes more or less often than the whole is a question about the ordering. Enumerating everything is the neutral measurement and it is not the same as instrumenting a solver.

The convention, named #

Normal play. Left places vertical dominoes and Right horizontal ones; a position is the set of covered squares, and both players’ moves are followed, so the reachable set is every arrangement of dominoes that can be built on the board.

Depth is the number of dominoes placed, which is half the number of covered squares. A region is a connected set of free squares, four-connected; a region is live when a domino fits in it. A position decomposes when it has two or more live regions.

The table of a region is the number of distinct positions reachable inside it with both players moving, computed by the same enumeration. The saving at a split is the product of the parts’ tables divided by their sum, which is exactly the ratio the rung below’s figure asserts is a product.

Where the ladder goes next #

The decomposition anchor has three rungs: what a split saves, what finding it costs, and now how often one arrives.

The rung above is Amazons, which the rung below named and which is the game the answer should be different for. An arrow cuts a board permanently and cannot be undone, so a decomposition there is not merely common but monotone — once split, always split, and split further with every arrow. Whether the share reaches nine tenths and whether the savings reach the factors of a thousand the arithmetic allows is a computation of the same shape on a game whose positions are much dearer.

Two neighbours are worth the trip. The board falls apart is where the saving is established and where a single decomposed board is priced exactly; this page is that price multiplied by how often the situation occurs. And knowing who wins and knowing what it is worth is the other cost measurement in this field, where the ratio between two answers grows with the board — which is what this page’s 1.8 would do if the board did.