Finding the parts

The board falls apart makes the case for decomposition and makes it decisively. A board in k independent regions costs the sum of their searches where the whole board costs the product, and that is not an optimisation — it is the difference between a table that fits and one that does not.

The essay assumes the regions. On a real board nobody hands them over.

The pass, and what it costs #

Finding the regions of a board is a flood fill. Start at an unvisited free square, walk to every square reachable through free squares, mark them all as one region, and repeat. It visits every square once.

That is cheap, and it is cheap in a specific and awkward way: it costs the same whatever it finds. A board that falls into four regions and a board that falls into one are the same amount of work to examine, and the pass cannot know which it is looking at until it has finished.

The two rows at the top are the ones worth staring at. A board with nothing blocked has 58,830 positions in its graph and one region, so the flood fill returns “one region” and the solver has to walk all 58,830. Block one square in the middle: 24,864 positions, still one region, still nothing saved. Twenty squares visited, twice, for no return.

Then the third row blocks a staircase and the same twenty-square pass turns 2,187 positions into 108.

Why the saving is so large when it comes #

The reason is the one the earlier essay establishes and it is worth restating in the form that makes the cost comparison sharp.

A board’s position graph is exactly the product of its regions’ graphs — every position of the whole is a position of the first paired with a position of the second — so evaluating the regions costs their sum and evaluating the whole costs their product. That identity is asserted rather than described wherever this site draws a split board: the whole board’s table and the regions’ tables are computed separately and the drawing is refused if the product is not the whole.

A product against a sum is the whole story, and it says why the payoff column swings over four orders of magnitude while the cost column does not move. What it does not say is how far any of this depends on the board being twenty squares, and the same six questions asked one row down are a cheaper way to find out than an argument.

Five squares off the board and the prize falls by a factor of ten, because the undecomposed table it is measured against fell by a factor of nineteen. That is the direction that matters: the pass gets better value the larger the board, and the boards a solver cannot afford are exactly the boards where the pass is worth most.

Where this sits among the savings #

The complexity field has three savings and they are not the same kind of thing.

Memoisation turns a recursion tree into a position graph and changes an exponent. The tree and the graph measures it: a 4 × 4 Domineering board unfolds to 6,257,129 recursion nodes over 5,700 distinct positions.

Decomposition turns a product into a sum and changes an exponent again, and it is this essay’s subject.

Identification folds positions by symmetry and divides by at most the size of the group, which is a constant. What counts as the same position measures the ceiling: at most four, on a board of any size.

The three sit differently against the board, and the difference is the subject of this page. A table’s cost is a hash lookup per node, a canonicalisation’s is a fixed amount of work per position, and both are paid inside the search. The pass is paid before it, on the whole board, and its price is written on the board’s face.

What this essay adds is the observation that only one of the three has a discovery cost. Memoisation costs a hash lookup per node and pays for itself immediately. Identification costs a canonicalisation per position and its saving is bounded, so the arithmetic is a wash and has to be checked. Decomposition costs a pass over the whole board before any search happens, and the pass is a bet.

The bet, priced #

The pass costs the number of squares. The saving is the difference between a product and a sum. So the bet is overwhelmingly good whenever it pays at all, and the question is only how often it pays.

On the six twenty-square boards it pays four times out of six, with ratios of 104, 140, 56 and 6 positions saved per square visited. On the two where it does not pay, the loss is twenty squares — which is nothing against a search of tens of thousands of positions.

That invites the conclusion that the pass is always worth running, and on a board worth searching it is. The qualification is not decoration, and the way to see it is to price every decomposition in range by the square rather than by the board.

A region with one position in it contributes a factor of one to the product and a whole term to the sum, so a board chopped into scraps is a board on which the identity runs backwards. That is not an argument against the pass; it is the boundary of the argument for it. The pass is worth running on any board a solver would want to search, because the inequality that matters is between an exponential and a linear cost and the exponential wins as soon as the pieces are big enough to hold anything. On the boards where it fails, the whole search was affordable anyway.

An exact statement of the trade #

It is worth writing the arithmetic down, because “a product against a sum” is the kind of phrase that is easier to repeat than to check.

Let the regions have position counts p₁ … pₖ. The whole board’s table has ∏ pᵢ entries; solving the regions separately needs Σ pᵢ. The flood fill costs s, the number of squares. So the pass is worth running whenever

∏ pᵢ − Σ pᵢ > s

and with two regions of a hundred positions each that is 10,000 − 200 against twenty. The inequality is not close.

Where it is close is k = 1, where the left side is zero and the pass costs s for nothing. Where it goes the other way is a case the phrase “a product against a sum” gives no warning of at all: a region holding a single position contributes a factor of one to the product and a whole term to the sum, so a board chopped into four scraps can have ∏ pᵢ smaller than Σ pᵢ and a left-hand side below zero. That is the bottom row of the table above, and it is the only shape in which the inequality genuinely fails. So the whole question is the probability that a board decomposes into pieces with something in them, and the pass is worth running whenever that probability times the typical saving exceeds s — which, given savings in the thousands and costs in the tens, means “essentially always”.

The reason to write it out anyway is that the same inequality with different magnitudes is a real decision elsewhere. A canonicalisation pass for identification has a saving bounded by a constant, so its version of this inequality is genuinely tight and has to be measured rather than waved at. Two savings, one shape of arithmetic, and opposite answers.

Where the pass is not enough #

Two cases complicate the picture and both are real.

The regions may be found and still be too large. A 10 × 10 Amazons endgame splits into regions of twenty or thirty squares, each of which is past exhaustive evaluation on its own. The pass has done its job and the answer is still out of reach — which is why Amazons programs count territory in large regions and compute values only in small ones.

The split may be found and be wrong. The flood fill uses four-adjacency because that is what a domino uses, and a game whose pieces move differently needs a different notion of connectedness. In Kōnane a stone hops over a neighbour into the square beyond, so a single empty square is not a barrier and a run of three is not either — a flood fill on emptiness would report regions that are not independent, and the values computed from them would be wrong with no symptom.

What the pass should actually be computing #

The Kōnane warning is worth turning into a rule, because “use the adjacency the game’s moves use” is right and is still a description rather than a recipe.

The quantity a decomposition needs is not connectedness of empty squares. It is connectedness under the relation some move touches both of these squares. Build a graph on the squares, join two squares whenever a single legal move of the game reads or writes both of them, and take the connected components of that. Two squares in different components cannot be affected by one move, which is exactly the independence the product identity requires.

Every case above is that recipe evaluated for a particular game. A domino occupies two orthogonally adjacent squares, so the relation is four-adjacency and the flood fill is the right pass. A Clobber move takes a stone onto an adjacent enemy, so it is four-adjacency again. A Kōnane hop reads three squares in a line — the mover’s stone, the stone jumped, and the landing square — so the relation reaches two squares away, a single gap joins rather than separates, and a fill on emptiness partitions a board the moves do not.

The failure mode is what makes this worth stating as a rule. A wrong adjacency does not produce an error. It produces a partition, the solver evaluates the parts, adds the values, and returns a number — and the number is wrong with nothing to indicate it, because every step after the partition is correct. The essay one rung over calls that an independence claim, and the recipe here is what turns the claim into something a program can be held to: the pass and the move generator must be derived from the same relation, and a solver that hard-codes four-adjacency beside a move generator that does not is carrying a silent inconsistency.

Now, or ever #

There is a second trap in the recipe and it is sharper than the first, because it bites in a game whose adjacency is right.

Some legal move touches both — legal when? A move that is illegal in the position in front of the solver may become legal later, after the pieces have moved, and if it ever becomes legal then the two squares were never independent. So the relation has to be built from the rules, over every move the game could ever offer, not from the move list of the position at hand.

Domineering hides this, which is why it is a poor game to learn the rule from. A blocked square is blocked for ever, dominoes never leave, and the board only ever gets more disconnected — so the partition found now stays valid for every position below it. That is a special property and it is doing a lot of work in the six boards above.

It fails wherever pieces can move or be removed. A Clobber region is separated by an empty square, and Clobber stones are removed as play goes on, so the gaps only widen — safe again, for the same reason and by luck. Kōnane removes stones too, and there a widening gap is not a widening barrier, since a hop needs the jumped stone rather than the space. And in a game where anything is ever placed, a barrier can close: two regions that were separate become one, and a decomposition taken at the root and trusted for the whole search is unsound rather than merely wasteful.

So a solver that decomposes at every node is not only getting a bigger saving; it is the version that is correct in general. Decomposing once at the root and reusing the partition is an optimisation available to games whose boards only ever fall further apart, which is a real class and not the whole of one — and it is worth knowing which of the two a game is before the answers stop being checkable.

What the numbers say about board shape #

Running an eye down the six rows, the saving is not a function of how many regions there are.

Four regions saves 128 positions. Two regions saves 2,808. The reason is that the sizes matter more than the count: a board cut into two halves of eight squares each has two tables of 108, and their product is 11,664 — but the board also lost ten squares to the wall, so the whole board’s table is 2,916 rather than 58,830.

Blocking squares does two things at once. It splits the board, which helps, and it removes squares, which shrinks everything including the undecomposed table. The measured “saving” is the difference between the two effects, and a board blocked heavily enough to fall into four small regions has so little left that there was not much to save.

So the honest reading of the table is that the saving is largest for a board barely cut — a long wall through an otherwise full board — and shrinks as the cutting gets more aggressive. That is the opposite of the naive expectation and it matters, because the positions a real search meets are barely cut: a few pieces placed, one accidental barrier, and two large regions.

The other half of the shape is where the barrier falls, and it can be isolated by holding the board still and moving the wall. Every cut below blocks four or five squares of the same twenty, so the pass costs twenty squares on all of them and nothing but the split is different.

A product is largest when its factors are equal, so the evenness of the split is most of what the payoff is. Both halves of the shape point the same way and both are invisible to the pass: it cannot see how much of the board is left, it cannot see where the wall falls, and it has to visit every square before it learns either.

The order of the work #

There is a practical point buried in all this about when the pass should run.

A solver that decomposes once, at the root, gets the saving on that position only. A solver that decomposes at every node gets it whenever a position falls apart during the search — which for a game like Domineering or Amazons is most of the time, because pieces accumulate and boards break up as play proceeds.

The second is much better and much more expensive: a flood fill per node rather than one per search. Whether that trade is worth taking depends on how often positions decompose, which is a property of the game rather than of the algorithm, and it is the sort of question that gets settled empirically per game and stated as folklore afterwards.

There is a middle course that real solvers take and that is worth naming: run the pass only after a move that could have split the board. In Domineering every move occupies two squares, so every move could; in Amazons an arrow lands on one square and only that square can complete a barrier, so a cheap local test — did this square join two existing walls? — decides whether the full pass is worth running. That turns an unconditional cost into a conditional one and is the ordinary way an expensive check earns its place inside a hot loop.

What makes decomposing at every node cheap in practice is that the values of small boards are known: a region that matches one is answered by a lookup rather than by a search, so the saving compounds — the pass finds the small boards and a table answers them.

What decomposition does to the answer, not just the search #

One more thing separates this saving from the other two, and it is not about cost at all.

Memoisation and identification are implementation techniques: they change how long a search takes and leave the answer alone. A solver with a bigger table gets the same value faster.

Decomposition changes what is computed. It replaces one value with several, and the several are more useful than the one — a region’s value can be reused in any position containing that region, compared against another region’s, and added to whatever else is on the board. The tree and the graph makes a search cheaper; decomposition produces a different and better object.

That is why the small-board value tables exist at all. The value of a 2 × 3 Domineering board is worth computing once and storing, and it is worth storing because decomposition guarantees it will be asked for again as a component of something larger. A memo table is discarded at the end of a search; a table of component values is the accumulated output of every search anybody has run.

So the honest summary of this essay is not “the pass is cheap”. It is that the pass is cheap, the saving is unbounded, and the thing it produces is more valuable than the thing it replaces — which is three separate reasons pointing the same way, and rarer than it sounds.

What the picture cannot show #

Every board here is twenty squares, which is chosen so that the whole board table can be computed for comparison.

That is exactly the range where the saving does not matter. A twenty-square board is solvable either way, and the point of decomposition is boards that are not — where the undecomposed number cannot be computed at all, so the ratio cannot be measured and has to be argued.

The figures therefore report a saving in the one regime where it is unnecessary, and the reader is asked to extrapolate. The extrapolation is safe, because the product identity is exact rather than empirical, but it is an extrapolation and the pictures do not contain it.

The second thing not shown: the pass on a position that has just been split by a move. All six boards here start blocked. A real search reaches them by playing dominoes into a full board, and the interesting question — how deep into a game a position typically decomposes — needs a distribution rather than six examples.

The convention, named #

Normal play, and here it is doing something the essay leans on without saying.

The product identity — that the whole board’s position graph is the product of its regions’ — is a statement about positions, not about values, and it holds under any convention. What needs normal play is the step after it: that the value of the whole is the sum of the values of the parts, so that solving the regions separately answers the question about the board.

Under misère play the first still holds and the second does not, so the pass would find the regions, the search would be cheap, and the answers would not compose. The saving is real and useless. That is worth knowing before writing a misère solver that decomposes.

Where the ladder goes next #

decomposition has two rungs: what a split saves, and what finding it costs.

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.