A wall an amazon can walk through

Three essays below this one, a board falls into pieces and the pieces are added. The board falls apart is the picture: block out a column of a Domineering board and no domino can span the gap, so the position is the sum of what is left on either side. Finding the parts is the procedure that locates the pieces. How often a board falls apart is the census — over every position of a 4 × 4 Domineering board, forty-seven per cent are in more than one piece, and the saving that buys is the difference between a product and a sum.

All three are about a game where the walls arrive by accident. A Domineering board decomposes because dominoes happen to have been placed in a line, and the line can be broken open again on the next move — not by removing a domino, which is impossible, but because a region can shrink until it holds no domino at all and stops being a summand of anything. Amazons is supposed to be the answer to that. An amazon moves like a queen and then shoots an arrow like a queen, and the square the arrow lands on is burnt for the rest of the game. Nothing removes it. So the walls in Amazons are permanent by construction, and a board that has fallen into pieces should be in pieces for good.

That is a claim with a number attached to it, and the number is easy to get: walk every position reachable from a small opening, count the regions at each one, and count the moves that make the count go down. If the claim holds, the second number is nought.

It is not nought. It is 51,742.

This essay is the account of that number: what is producing it, why the argument above fails, which of the two things it could indict turns out to be guilty, and what believing the wrong one would have cost. The short answer is that the game is innocent and the instrument is not, and the instrument is the one three essays below this one hand the reader as though it were part of the subject rather than part of a particular game.

What the arrows are supposed to promise #

The argument for permanence is short enough to state in one line and it is the reason this rung was worth writing. Every move adds exactly one burnt square and removes none. Burnt squares are the walls. Walls that only ever accumulate can only ever cut a region into smaller pieces; they cannot join two pieces that are already apart. So the partition of the board into regions refines as the game goes on, and refinement is one-way.

The only leak in that argument is the amazons themselves, who move. A square that held an amazon at one moment is empty at the next, and a square that was empty now holds her. But an amazon standing on a square does not wall it off — she is inside her region rather than at its edge, and any sensible region rule walks straight through her. So her moving about changes nothing that connectivity depends on, and the argument survives.

Which is exactly the argument the measurement refutes. Something in it is false, and finding out what is the only interesting thing this essay does. Everything after here is the search for the false step and the bill for having believed it.

The rule that came from the other game #

The walk above is over a 3 × 4 board with two amazons, one for each player, starting on the top row. That is small — 127,583 distinct positions across 2,300,392 moves — and it is small on purpose, because everything here has to be checked exhaustively rather than sampled.

The first column of the figure counts a position as being in pieces when it holds more than one region with an amazon in it, and it finds the regions by flood fill from square to square across shared edges: up, down, left, right. That is the rule finding the parts uses, and it is the right rule there, because a domino covers two squares that share an edge. Two squares that touch only at a corner cannot both be under one domino, so a diagonal touch is not a connection and the fill is correct to ignore it.

It is not the right rule here, and the second column is the same walk with corner neighbours counted as well. The two disagree from the moment anything decomposes at all: at three moves played, the edge rule reports 1,140 positions in pieces out of 13,330 and the corner rule reports 114 — one tenth as many. By the end of the game the edge rule says three quarters of positions are in pieces and the corner rule says just over half. Across the whole walk it is 34.95 per cent against 13.21.

Both columns climb rather than falling back, and that much is genuinely a fact about Amazons rather than about the rule. Domineering’s decomposition rate rises through the middlegame and collapses at the end, because the last few moves fill in the regions and the board runs out of places a domino fits. Amazons has no such collapse: the arrows keep cutting, an amazon on her own square is still a region, and the position stays in pieces right up to the last move anybody can make.

The shape of the walk is worth a note, because it is what makes an exhaustive answer affordable at all. Positions are visited once and remembered, not once per path, so the 127,583 in the figure is a count of distinct boards rather than of nodes in a tree — the tree is very much larger, and the difference is the whole of why the count of moves is 2,300,392 rather than 127,582. Each of those moves is examined at the position it leaves from, which is what allows a question about transitions rather than about states: not how many boards are in pieces but how many moves change that. The first question a census answers and the second one it cannot.

Two amazons rather than four is also deliberate, and it is the one place the small board might be misleading. With two, a region either has an amazon in it or has none, and the count of live regions is a count of pieces of a game. With four, a region can hold two amazons of the same colour, and a rule that counts regions is no longer counting summands in quite the same way. Nothing measured here depends on which of those it is — the mechanism below is about a single amazon crossing a single corner — but the shares would move, and a reader who wants the 13 per cent to be a fact about the real game should read it as a fact about this board.

One step, and the board is whole again #

A number that says two rules disagree is not yet an argument that one of them is wrong. What settles it is a single move.

The amazon at the bottom of the left-hand board is boxed in by arrows on three sides and the edge of the board on the fourth — as far as an edge-neighbour flood fill is concerned, she is alone in a region of one square, and the board is in two pieces. She then steps one square diagonally and is standing in the other region.

This is the false step in the argument, and it is not in the part about arrows. It is in the words any sensible region rule. An amazon moves as a queen, which is to say along eight lines and not four. Two squares that touch at a corner are one move apart for her, however thoroughly the squares between them are burnt. A rule that walks only across shared edges is not describing the game’s geometry; it is describing a domino’s.

The measurement makes that claim precisely rather than by analogy. Every one of the 51,742 moves that lowers the edge rule’s region count is checked, at the moment it is counted, to be a step whose two ends lie in different edge-rule regions — and to be diagonal. If a single one of them were a straight step, or a step within one region, the walk would refuse to return a result at all and say so, because then the mechanism named here would not be the whole of the story. All 51,742 are diagonal crossings. There is no residue.

So the regions were never wrong to be permanent. The rule finding them was drawing walls where there were none, and the game was walking through them.

It is worth being clear about which of two very different errors this is. It is not an off-by-one, or a flood fill that leaks, or a boundary case at the edge of the board — all of which would show up as a handful of exceptions and would be caught by anybody who looked at a few of them. It is a systematic disagreement between the object being measured and the definition being applied to it, and its signature is that it is perfectly consistent. The rule always thinks those two squares are in different regions. The game always thinks they are one step apart. Nothing in the walk is unreliable; the walk is answering a question about a different game, exactly and every time.

Which rule keeps the promise #

With the mechanism identified, the original claim can be asked again of the rule that matches the movement.

Nought and nought. Under the corner rule, no move in the entire walk lowers the number of regions holding an amazon, and no move lowers the number of regions at all. The claim this rung was written to test is true, exactly as stated, and the arrows do keep the promise the opening argument said they would.

The second nought is worth a sentence of its own, because it is not implied by the first. A region could stop existing rather than stop being live: if a region were a single empty square and an arrow landed on it, the region would vanish and the total count would drop without any amazon having gone anywhere. Under the edge rule that happens 77,336 times. Under the corner rule it happens never, and the reason is the same geometry read the other way — an arrow can only land where a queen can reach, and anywhere she can reach is in her own region. A region she cannot reach cannot be filled in.

Domineering has no such protection, which is the asymmetry how often a board falls apart measured without naming. There, a region of two squares in an L is a summand, and one domino later it is a single square holding nothing. The region has not been rejoined to anything; it has simply stopped being a game. Amazons cannot do that either, because a lone amazon on a burnt-out square is still a position, with a value, and it is still worth nought or worth something rather than ceasing to exist.

How much of the saving was never there #

Two rules, one of which cuts along lines the game ignores. The next question is how much of the difference is a decomposition reported where there is none.

The disagreement is one-sided, and it has to be. Adding corner neighbours can only merge regions, never split them, so every corner-rule region is a union of edge-rule regions. A position in pieces under the corner rule is therefore in pieces under the edge rule too, and the count of positions decomposing under the corner rule alone must be nought. It is, and the walk refuses to return anything if it is not — a check on the arithmetic rather than on the game, but a check that has somewhere to fail.

What is left is 27,736 positions, which is 62 per cent of every decomposition the edge rule finds. Nearly two out of three are boards where the two halves the rule has identified are one fight that an amazon can cross in a single move.

That is where the essays below this one would stop, because a count is a count. But a decomposition is not a fact anybody wants for its own sake. It is a licence — the licence to evaluate two pieces separately and add the answers, which is the whole reason the sum is the object and the reason the search saving is exponential rather than incremental. So the honest way to price the error is to exercise the licence and see what comes out.

What it costs to add the wrong parts #

Two hundred and twenty-one of three hundred is not a rounding error and it is not a subtle one. The sums are wrong most of the time they are taken, and 193 of them are wrong in the way that matters to anyone playing: the outcome class changes. A solver that trusted the edge rule would be told, on nearly two thirds of the boards where the rule fires, that a different player wins.

The first row shows the error at its plainest. The whole position is {2 | 0, {1 | −1}} — a switch, hot, a fight, and whoever moves first wins it. Cut it along the diagonal the amazon can step across, evaluate the two supposed halves, and add: the answer is 1, a number, cold, a comfortable win for Left with nothing left to play for. Every property that matters has been destroyed. The temperature has gone, the fight has gone, and what is returned is a confident statement about a position that does not exist.

Three rows further down the same table are positions where the edge rule’s sum is right anyway. Seventy-nine of the three hundred are, and they are not a defence of the rule — they are the ordinary behaviour of a wrong method that sometimes lands on the right answer, in a game where a great many small positions are worth nought. A licence that is void two times in three is void.

There is a second measurement hidden in the gap between the two counts, and it is the more useful of the pair. Two hundred and twenty-one values are wrong and 193 outcomes are; so twenty-eight of the wrong values still name the right winner. A wrong value cannot be corrected by luck, but an outcome is a much coarser reading of a value, and two different games can easily agree about who wins while disagreeing about everything else. That is the failure mode a solver is least likely to notice, because the answer it acts on looks right on the positions somebody checks by hand, and the value it has cached is wrong for every sum that position is ever put into afterwards. The comparison is made both ways here for exactly that reason: a check that only asked about outcomes would have reported the rule as wrong 64 per cent of the time instead of 74, and would have called twenty-eight broken evaluations correct.

The construction being priced is the honest one, too, rather than a straw version of it. Each supposed region is turned into a board of its own with everything outside it burnt — the same construction the site’s working figures use — and evaluated as a full Amazons position. Nothing is approximated and no shortcut stands in for the sum. The only thing that differs from the working version is which squares were called adjacent.

The rule the machinery already used #

There is a coda to this, and it is the reason the error above is a hazard for a reader rather than a live defect on this site.

The generator that draws Amazons positions on this site has always used the corner rule, and it has always carried an assertion: find the regions, evaluate each one alone, add the values, and compare with the value of the position evaluated whole. If the two differ, the figure does not draw. That assertion has run on every Amazons decomposition figure published here — a board that is a sum of its regions, when the regions add, independence is a claim — and it has never once fired.

Which is the point of writing assertions that can fail. The corner rule was not chosen here after an investigation; it was chosen because it is what the game’s movement obviously is, and the assertion is what has been quietly confirming that choice for as long as the figures have existed. Had the edge rule been used instead, the very first published figure would have refused to draw, with a message naming two values that did not match. The error this essay measures is one the site could not have shipped.

That is a narrow escape rather than a design. The rule is easy to get wrong precisely because the neighbouring essays get it right for a different game, and a reader who has just followed the Domineering argument down three rungs has been handed a flood fill that is correct in every one of them and wrong in this one. The transferable lesson is not use eight directions in Amazons. It is that a decomposition is a claim about which moves exist, and the only safe way to cut a board is along the game’s own moves — so a region rule should be derived from the move generator, not from the shape of the pieces.

The assertion is also the reason this essay could be written at all, in a form that is easy to miss. Every claim above about the mechanism is checked at the moment it is counted rather than inspected afterwards: that every lost region is a diagonal step, that the corner rule loses none, that no position decomposes under the corner rule alone, that the two rules’ region sets nest the way a refinement must. Any one of those failing stops the walk with a sentence naming what did not hold. That is not a courtesy to the reader. It is the only thing standing between fifty-one thousand moves undo a decomposition, and here is why and fifty-one thousand moves undo a decomposition, and here is a plausible story about why — which are the same essay to read and different pieces of work entirely.

Against the game it was supposed to beat #

The rung this essay was written for expected Amazons to decompose more often than Domineering, and permanently. Half of that is right.

Under the corner rule, 13 per cent of Amazons positions are in more than one piece, against Domineering’s 47. Amazons decomposes considerably less often, and the reason is the geometry again: a queen’s eight directions make a board hard to cut, and it takes a great many arrows before two amazons genuinely cannot see one another. The edge rule’s 35 per cent is the number that looks like the expected answer, and it is the wrong number.

What Amazons does have, and Domineering does not, is permanence. Domineering’s region count falls 6,648 times over its own 5,700 positions — never by rejoining two regions, which is impossible there too, but by a region shrinking below the two squares a domino needs. Amazons under the corner rule loses a region nought times, by either mechanism. So the rung’s premise survives in the form that mattered and dies in the form that was measured: the cut cannot be undone, and there are fewer cuts than anybody expected.

Set the two boards side by side and nothing distinguishes them to the eye. Both are a board with squares removed; both fall into what look like two independent halves; both invite the same product-against-a-sum argument that a product against a sum sets out. The difference is entirely in the move generator, which is not drawn, and which is the only thing that decides whether the two halves are independent. Independence is a claim, and it is a claim about moves rather than about squares — which is why how wrong a nearly independent split is is a question with an answer rather than a contradiction in terms.

The practical residue for anyone building a solver is one line. When which part to move in becomes the question, and the answer depends on the parts being parts, derive the partition from the game’s own moves: two squares are adjacent when some legal move takes a piece from one to the other. For Domineering that gives edges. For Amazons it gives corners as well. And for the next game it gives whatever it gives, which is the only reason to write it that way instead of copying the flood fill from the essay before.