The board falls apart, and the arithmetic changes

Block out the middle column of a 4×5 Domineering board and it is no longer one board. It is two boards of four squares by two, standing beside each other, and no domino can ever bridge them.

The number of positions a solver must evaluate on the whole thing is 2,916. The number in each half is 54.

54 × 54, and not by coincidence #

That 2,916 is 54 × 54 exactly is not an approximation, an empirical observation, or a fact about this particular board. It is forced.

A position of the whole board is a choice of position in the left half together with a choice of position in the right half, and every such pair is reachable, because the two halves never interfere. So the positions of a sum are the pairs of positions of its parts, and there are as many pairs as the product says.

The generator behind that figure computes both numbers independently — one walk over the whole board, one walk per region — and refuses to draw anything if the product does not come out exactly. A picture whose caption asserts a theorem should fail rather than mislead if the theorem is not holding.

Everything about the cost of playing real games follows from that one multiplication. Every extra independent region multiplies the search and adds to the work.

Both of those cuts fall in the middle, and it is worth knowing how much of the saving is the splitting and how much is the evenness of it. Move the wall one column across, block exactly the same number of squares, and the answer changes by more than the arithmetic suggests.

The identity is exact in both cases and only the size of the prize moves. That is worth holding onto, because it is the difference between decomposition as a theorem and decomposition as an optimisation: the theorem does not care where the wall goes, and the saving cares a great deal.

Addition is what the theory is for #

The disjunctive sum is usually introduced as a modelling idea: real positions break into independent parts played at once, so the theory had better be able to say what a sum of games is worth. That is true and it is not the whole of why the definition earns its place.

The other half is computational, and it is this. Once each component has a value, the value of the whole is the sum of the values, and adding two values costs nothing whatever compared to searching. So a solver that decomposes pays

• the cost of finding each component’s value — the sum of the parts’ searches, and
• an addition.

instead of the product. The theorem that makes this legal is the one that says values add, and without it the decomposition would be a hopeful heuristic rather than an identity.

Written out for a board of four components, that is four searches and one addition, against a single search over every combination of the four. The expensive step happens once per part and the addition at the end costs nothing measurable — a board with $k$ regions has exponentially many combined positions and exactly $k$ parts, and the whole of the saving is the difference between those two sentences.

What it does not license #

Three things do not decompose, and the temptation to assume they do is the standard way to misuse a sum.

Outcomes do not add. Two positions from which the player to move wins can add to a position from which the player to move loses. The whole essay on that exists because the failure is so natural to make: the outcome is a coarse summary and coarse summaries do not compose.

Temperatures do not add. The sum’s temperature is bounded by the hottest part rather than by the total, so a board of two hot components is not twice as hot. That is a separate rung and its point is the same: values add, and functions of values generally do not.

The best move does not decompose. Knowing every component’s value tells a player what the whole is worth without telling them where to play. Choosing the part to move in is its own question, answered by comparing what each move changes rather than by looking for the largest component.

Those three failures share a shape. The sum’s value says who wins and says nothing about where to play, and a reader who has just been handed an exponential saving on evaluation will reasonably expect it to buy something on the playing side as well. It does not. Decomposition is a statement about evaluation, not about play, and every one of the three things above is a question about play or about a summary of play rather than about a value.

The boards that split themselves #

A board with a wall drawn down it is a demonstration. The interesting case is a game that decomposes on its own, part-way through, without anybody arranging it.

Amazons does this to a spectacular degree. Each move fires an arrow that burns a square permanently, and after a dozen moves the board is cut into territories that no queen can move between. From that point the position is a sum, whether or not anybody notices, and a solver that continues to treat it as one board is doing exponentially more work than one that splits it.

Domineering does it too, less dramatically: placed dominoes leave awkward single squares and isolated strips, and by the middle of a game a board is usually several small regions with dead squares between them. The 4×4 board in the counting essay reaches such positions constantly, and its 5,700-entry table contains a great many boards that are really pairs of small boards being stored separately.

That last point is the practical lesson. Decomposition is not something a solver does once at the start. It is a test to run at every node, because a position that has just split is a position whose remaining cost has collapsed from a product to a sum.

The saving, priced against the other two #

Three things reduce the cost of a search in this subject and they are not comparable in size.

A table removes duplicate routes to the same position, which on a 4×4 board is a factor of about a thousand and grows with the board. Decomposition replaces a product by a sum, which on the board above is 2,916 against 108, and on a board of four regions of the same size would be 8.5 million against 216. A theorem removes the search altogether, which is what the nim-sum does for Nim and fusion does for green Hackenbush.

Only the last changes what is possible in principle. Of the other two, decomposition is much the larger, and it is also the one that needs the theory: memoising needs no mathematics beyond a dictionary, while splitting a board and adding the pieces’ values is licensed by a theorem about disjunctive sums that took a subject to prove.

Why a table cannot find this saving on its own #

The three savings are listed above as three sizes, and it is worth saying why the second is not simply a better version of the first, because a reader who has met memoisation will reasonably ask what decomposition adds that a big enough dictionary does not.

A table keyed on positions stores each position once, and 2,916 is already the count of positions rather than of routes — the route count for that board is far larger. So the table has done its whole job and left 2,916 entries standing. Every one of them is a distinct board and none is a duplicate of another, so no amount of route-sharing removes a single one.

What the 2,916 are is pairs. Each entry is a left-hand configuration beside a right-hand one, and the table is storing $54 \times 54$ answers to a question that has only $54 + 54$ answers in it. The redundancy is real and it is invisible to the key, because the key is the whole board and the whole board is genuinely different in each of the 2,916 cases.

That is the precise sense in which decomposition is a different kind of saving. Memoisation identifies things that are the same; decomposition notices that things which are different do not interact. The first is a fact about arrival — two routes reaching one board — and needs no mathematics beyond a dictionary. The second is a fact about the rules, needs the theorem that values add, and cannot be discovered by any amount of watching a search repeat itself.

It also says where the two savings compose and where they do not. Run both and the cost is the sum of the parts’ position counts, so each half still gets its own route-sharing and the two techniques multiply their benefits. Run only the table and the product stands. Run only the decomposition and each half pays its own route count instead of its position count, which on these boards is another factor of a thousand thrown away.

So the ordering is not a ranking of two versions of one idea. They are answers to two different redundancies that happen to sit in the same search, and a solver wanting either has to ask for it separately.

What a decomposing solver actually does #

Written out, the algorithm is four lines and every one of them is cheap.

1. Split the position into connected components under the adjacency the moves use.
2. Look each component up in the table of values; evaluate the ones that are not there.
3. Add the values.
4. Store the total against the whole position, so that the next arrival is free.

Step one is a flood fill and costs time proportional to the board. Step three is addition of game values, which is building a pair of option lists and costs nothing measurable. All of the expense is in step two, and step two is where the reuse lives: the same 2×3 rectangle appears in an enormous number of positions and is evaluated once for all of them.

The important word in step one is adjacency the moves use, and getting it wrong is the way this goes silently wrong. For Domineering the relation is four-adjacency, because a domino covers two orthogonally adjacent squares — two regions meeting only at a corner are independent and must be counted apart. For a game whose pieces move diagonally the relation is different, and using the wrong one merges components that are really separate, which costs performance, or separates components that are really joined, which produces wrong answers.

The test is cheap enough to run at every node #

There is a temptation to treat decomposition as a preprocessing step — split the board, solve the pieces, done — and it gives up most of the benefit.

A position that has not split yet may split after the next move. Domineering boards do this constantly: a domino placed across the middle of a region leaves two smaller regions with a dead square between them, and from that moment the remaining work has collapsed. A solver that tested for components only at the root would carry the whole undivided board all the way down.

The test costs a flood fill, which is linear in the squares, against a subtree that is exponential in them. So the arithmetic is not close, and the rule is simply to test always. The site’s own figures are built this way: the Amazons generator asks for the regions of every position it draws rather than of the opening only, which is why it can report the value of a mid-game board that has fallen into three pieces without ever evaluating the board as a whole.

When the split is in the value and not in the picture #

The most interesting case is a position that does not decompose on the board at all and decomposes anyway, because a theorem says it does.

Green Hackenbush is the clean example. A tangled graph of green edges has no independent regions — everything is connected to everything, and no move leaves two pieces that cannot affect each other. Yet its value is a single Nim heap, computed by fusing every cycle to a point and running one pass up the tree that remains. The decomposition is real and it is invisible in the drawing: it is a statement about which structural features of the graph the value depends on.

That is worth holding onto because it says where to look for the next saving. Splitting a board is one way for a position to be a sum. Being equal to a sum, by a theorem nobody could have guessed from the picture, is another, and it is the one that turns a hard-looking family into an easy one. Nobody looking at a lattice of twelve green edges would see three independent games in it; the colon principle says the value behaves as though there were.

Where the model stops #

Two limits, and both are the kind that a figure cannot show.

Regions have to be genuinely independent. The blocked board here is independent by construction — a domino needs two adjacent free squares and there are none across the wall. In a real game the test is a property of the rules, not of the picture: two regions that look separate but share a resource, a move count, or a piece that can travel between them are one game drawn to look like two. Amazons is safe because a queen cannot cross a burnt square. A game where a player has a limited number of moves in total would not be, however far apart the pieces sat.

The parts must be small enough to evaluate. Splitting a board into two halves each of which is still out of reach has bought nothing at all. This is the ordinary situation in large Amazons endgames, where the components are small enough for the decomposition to be worth everything, and in mid-game positions where they are not.

There is also the case the whole subject is built around and which deserves naming here: a component may be evaluated once and reused everywhere it appears. A table of small Domineering region values is worth building because the same 2×3 rectangle turns up on thousands of boards, and each time it is worth what it was worth before.

A number worth being uncomfortable about #

The saving is enormous and it does not make the family easy, and conflating those two is the commonest overclaim available here.

Take the 4×5 board that splits into two halves. Undivided it is 2,916 positions; split it is 108. Now double every dimension. A 8×10 board split into two halves of 8×5 is two searches instead of one, and each of those searches is far past what this solver can reach — the halves are individually harder than the whole board was. The saving is a real exponential and the problem is exponential too, so dividing one by the other leaves an exponential.

That is why nothing about decomposition contradicts the hardness result. Generalized Geography is PSPACE-complete, and a Geography position that happened to fall into two independent halves would be cheaper to solve than one that did not — by a factor that grows, and not by enough to matter to a statement about families. Hardness survives every saving that is a ratio, however large the ratio is, and dies only to a saving that changes the shape of the growth.

What decomposition changes is which positions a person can actually settle this afternoon, which is not nothing. Berlekamp’s Go endgame work is the standing demonstration: positions that mattered to real players, out of reach as boards, entirely tractable as sums of a dozen small fights.

Somebody has to find the regions #

Everything above assumes the regions are known, and on a real board nobody labels them.

What that costs to discover is the question this page has been treating as free, and it is not free: the pass runs on every board, including the ones with nothing in them to find, and it visits twenty squares whether it returns one region or four. Finding the parts prices that bet.

Who found it, and what it was for #

The disjunctive sum and the theorem that values add are the founding results of the subject — Sprague and Grundy in the 1930s for impartial games, Conway in the 1970s for the general case — and they were not originally proved to make solvers faster. They were proved because a sum is what a real position is, and a theory that could not say what a sum was worth would have been a theory about positions nobody plays.

The computational reading came afterwards and it changed what people attempted. Go endgames are the standard example: a late Go board is a dozen small independent fights, and Berlekamp’s work applying combinatorial game theory to them is exactly the observation that a product of a dozen searches is out of reach while a sum of a dozen searches is a pleasant afternoon. The theory arrived as mathematics and turned out to be the only affordable way to compute the answer.

That is a pattern worth carrying: the structural result and the algorithm are the same statement read at different angles. Fusion in green Hackenbush is a theorem about graphs, and it is also the fastest known way to evaluate one.

Where the ladder goes next #

decomposition opens here with the saving priced against the other two.

Finding the parts prices the bet that this page treats as free. The flood fill is cheap and it is not conditional: it runs on every board of a size, including every board with nothing to find, and what it buys ranges from four orders of magnitude down to nothing at all. The rule test at every node is therefore a wager, and that rung says what the odds are.

How often a board falls apart supplies the other half of the same wager, and the answer is more encouraging than the shape of the game suggests. Over every position of a 4 × 4 Domineering board a decomposition is present 47 per cent of the time — nought for the first two moves, three fifths through the middle of the game, and nought again at the end when there is nothing left to split. And what one decomposition is worth, averaged over the positions that have one, is a factor of 1.8: much smaller than the 27 the blocked board on this page shows, because a real split is usually lopsided and a lopsided split saves far less than an even one.

Those two numbers together are the honest version of this page’s headline. The saving is a product turning into a sum, it is available on about half the game, and the typical instance of it is worth less than a doubling — which is still worth having at every node, because the test costs a flood fill and the payoff compounds down the tree.

The other direction is the third saving, the one with a ceiling. Identifying a position with its mirror image is not a theorem about the game and it does not decompose anything: it divides the table by at most the size of the symmetry group, which is four here and four on a board of any size whatever.