When a real board falls apart

Amazons is played on a 10 × 10 board with four queens a side. A move slides a queen like a chess queen and then fires an arrow from where she lands, which burns that square for good. A player unable to move loses.

It was invented in 1988 to be played, has competitive tournaments and computer olympiads, and is nowhere near being solved. What makes it worth an essay here is what happens to it late in a game.

The board cuts itself up #

Every move burns a square. After enough of them the burnt squares form barriers, and the board falls into regions that no queen can cross.

From that moment the position is a disjunctive sum, and this is the cleanest example on the site of a decomposition that is arrived at by the play rather than assumed by an author.

Nothing about the rules mentions regions. What happens is that arrows accumulate, and a set of burnt squares that separates the board is a barrier because a queen’s move is a straight line through empty squares. The decomposition is a consequence of play, and its arrival is the moment the whole apparatus of this site becomes applicable to a game that had been beyond it.

The moment of decomposition is a fact about the position #

It is worth pausing on how unusual this is among the games this site studies.

In Domineering a board falls into regions when blocked squares happen to separate it, and the essays that use it choose boards with a wall in them. In Nim the components are handed over as separate heaps from the start. In Hackenbush the components are whatever the picture was drawn as. Every one of those decompositions is a modelling decision made by whoever set the position up.

Amazons decomposes because two players, each trying to win, burnt squares until it did. Neither of them was trying to produce a disjunctive sum. The sum is a consequence of competent play, in the same way that a Dots and Boxes endgame becomes a multiset of chains because both players avoid the alternative.

That gives the theory an unusual entry point into a real game: it is inapplicable for most of the game, becomes applicable at a moment nobody chose, and from then on is exactly the right tool. Recognising that the moment has arrived is a skill, and it is not one the theory itself provides.

What players and programs count #

Once a position has split, an Amazons player does not evaluate each region and add up game values. They count territory.

The standard version, and the one every Amazons program computes: every empty square goes to whichever side can reach it in the fewer queen-moves, and ties go to nobody. The difference between the two counts is how far ahead somebody is.

That is a genuine heuristic, in wide use, and it is the one worth measuring the theory against — a straw heuristic would prove nothing.

Over every 3 × 3 position with three squares burnt that has already split — 180 of them, out of 2,520 enumerated — the count and the value agree on 148. Thirty-two disagreements out of 180 is not a bad heuristic; it is a good one being wrong about one position in six.

Every disagreement is a switch #

The disagreements are not scattered. They all have the same shape, and the shape is the essay’s point.

In every one of the thirty-two, the computed value is a switch — a position both players want to move in, whose value is not a number at all. The count returns a number of squares. The position is not worth a number of anything.

So the failure is not that the count is imprecise. It is that the count answers a question with a number and the position’s answer is a pair — what it becomes if Left moves and what it becomes if Right moves — and no single number represents that.

A count of one square in Left’s favour and a value of {1 | −1} are describing the same position, and they disagree because one of them has thrown away the fact that the square is contested.

What “not a number” means operationally is that the comparison has a fourth answer. A switch set against nought comes back confused — neither greater, less, nor equal — and that verdict is one a numerical estimate has no room for. A count of squares can say ahead, behind or level; it cannot say whoever moves.

Reading one disagreement #

The smallest of the disagreements is worth reading in full, because it makes the abstract claim concrete.

Two regions, four squares burnt, one queen in each region. The queen-distance count gives one empty square to Left, none to Right and two to nobody, so the count says Left is one ahead. The computed value is {1 | −1}: if Left moves the position is worth 1, if Right moves it is worth −1, and the position itself is worth neither.

The outcome class is N — whoever moves wins — and the count has no way to express that. It said “Left ahead by one”, which in outcome terms is a claim that Left wins whoever moves, and that is false.

The error is not in the arithmetic. The count is right that Left will get one square if nobody interferes; what it cannot represent is that Right moving first takes the square instead. A number describes a settled position and this one is not settled.

That is the difference between a mean and a value. The count is computing something like the mean — where the position lands if the contested squares are split evenly — and the mean of {1 | −1} is indeed 0, or one square in nobody’s favour once the arithmetic is done properly. What the mean throws away is what is at stake, which here is the whole of the answer.

Why the count is right so often #

The interesting half of the measurement is not the thirty-two. It is the 148.

A heuristic that agrees with an exact evaluation five times in six is doing real work, and it is worth saying why. Most split positions are settled: each region belongs decisively to one side, nobody has a move into the other’s territory, and the value of the whole is an integer — the number of spare moves one player has over the other. An integer is exactly what a count of squares is good at.

The count fails precisely where the theory earns its keep — on the contested regions, where whoever moves first changes the answer. Those are a minority of positions and they are the ones that decide games, which is the ordinary situation for a heuristic and the ordinary reason to want an exact method for the hard cases.

There is a second reason the agreement rate is as high as it is, and it is a property of the sample rather than of the count. A 3 × 3 board with three squares burnt leaves six free squares between two queens, which is a very small endgame; most of its split positions have one queen shut in a corner with nothing to contest. Bigger regions have more contested squares and more of the values that are not numbers, so the honest expectation is that the count does worse as the regions grow — up to the point where the regions are too large to evaluate at all, which is where the count is the only thing available.

That is the shape of the whole trade, and it is uncomfortable: the heuristic is most reliable exactly where the exact method is cheapest, and least reliable exactly where the exact method has become impossible.

The trend is already in the two rows #

The expectation that the count does worse as the regions grow is offered above as a prediction, and the essay has two measurements that bear on it and does not put them together.

Three squares burnt: 148 agreements of 180, which is 82%. Six free squares between the queens.

Four squares burnt: 448 of 480, which is 93%. Five free squares.

Burning a square makes the free regions smaller, and the agreement rate went up by eleven points. That is the predicted trend seen from the other end: fewer contested squares, fewer positions that are worth a switch, more positions the count gets exactly right.

Two points do not make a curve and the direction is the informative part. It says the 82% figure at the head of this essay is not a property of Amazons; it is a property of six free squares, and the number a reader should carry away is that the rate moves with the size of what is left rather than with the game.

And it sharpens the uncomfortable trade. The count is best where the board is nearly finished — where an exact evaluation is trivial — and the two rows measure the rate improving as the position becomes less worth having an opinion about.

The error is exactly the temperature #

Every disagreement being a switch is more than a pattern in a sample. It says what the count is computing and what it is missing, in the vocabulary the rest of this site uses.

A count of territory is an estimate of the mean: where the position settles if the contested squares are split as they should be. What it has no column for is what is at stake — how much moving first in a region is worth — and that quantity is the temperature.

So the count is right on a region exactly when the region’s temperature is zero, and a region of temperature zero is a region worth a number. Every one of the 148 agreements is a position whose regions are all cold; every one of the thirty-two failures has a hot region in it. That is not a rule of thumb about when to trust the count — it is a characterisation.

Which means the count’s failures are predictable in kind and, more usefully, detectable in advance. A program need not evaluate a region to suspect it: a region is contested when both queens can reach a common empty square, and that is a reachability test on a graph, not a game evaluation. Any region failing it is cold and the count is exact there; any region passing it is one where the count is reporting a mean and the position may not have one.

That turns “the count is wrong one time in six” into something a program can act on. It cannot fix the estimate — fixing it means computing the value, which is the expensive thing — but it can say which regions the estimate is untrustworthy about, which is the difference between a number and a number with an error bar attached.

And it explains why territory counting works as well as it does in a real game rather than in this census. Late Amazons positions are mostly sealed rooms with one side’s queens in them, and a sealed room has nothing to contest; the contested regions are few and are the ones strong players spend their time on. The heuristic and the human attention are pointed at complementary halves of the board, which is the ordinary way an approximation earns its place — not by being right everywhere, but by being right everywhere nobody is looking.

What the theory offers instead #

Given a split position, the theory’s answer is: evaluate each region, add the values, read the outcome.

That saving is what makes exact Amazons endgame analysis feasible at all, and it is the reason serious Amazons programs do compute game values for small regions rather than counting squares in them. The count survives as the evaluation of the whole board while the regions are still large; the values take over when they are small enough.

The general shape #

Strip the Amazons out and the finding is one this field keeps producing.

A practical evaluation of a game position is a number. The theory’s answer is a game, which is a richer object: it is a pair of things the position becomes, recursively, and it collapses to a number only when the position is settled.

So a numerical heuristic is exactly right on the settled positions, and structurally unable to be right on the contested ones. It is not a matter of tuning: no refinement of a count of squares will ever produce {1 | −1}, because {1 | −1} is not a quantity.

That is the same finding as the counting rule in a pawn ending, where a count of spare moves has two answers and the game has four outcome classes; and the same as the long-chain rule in Dots and Boxes, which is a parity and fails exactly where the parity stops being the whole story. Three games, three folk heuristics, one reason.

The operation that separates the two kinds of position is the difference game: comparing a position with a number means playing their difference and asking who wins, and a settled position gives a definite answer where a contested one comes back confused. That is the formal statement of this is not worth a number, and it is a search rather than a reading.

What the theory offers in exchange for the extra complexity is that its answers compose. Two counts added together give a count that may be wrong about the sum even when both were right about the parts; two values added together give the value of the sum, always. That is the whole argument for the disjunctive sum and Amazons is where a real game supplies the components.

What the picture cannot show #

The boards here are 3 × 3 with three or four squares burnt, and Amazons is played on a hundred squares with four queens a side.

That gap is not a matter of a factor or two. The 3 × 3 census enumerates 2,520 positions and solves the 180 of them that have split; a 10 × 10 Amazons endgame with four queens a side has regions that are individually past exhaustive evaluation, which is why the real programs compute values for small regions and heuristics for large ones.

So the honest statement of what is measured is: on positions small enough to evaluate exactly, the territory count is right about five times in six, and its failures are all of one kind. Whether the same ratio holds on a real board is not something these figures can say — but the kind of failure is structural rather than accidental, and it would be surprising if it changed.

The second thing not shown is which regions are worth what. Every figure here reports the value of the whole position; the interesting quantity for a player is the value of each region separately, so that the hottest can be chosen. That is a per-region table rather than a per-position one, and it belongs to the rung above this.

Fifteen values, and what they are #

The 180 split positions carry fifteen distinct values between them, and running an eye down the list is a compact summary of the whole essay.

Most are integers: −3 through 3, the settled positions where one side simply has more moves. A few are switches of small size — {1 | −1}, {2 | 0}, {0 | −2} — which are the contested ones. And a handful are stranger: {2 | −1, {1 | −1}} is a position where Right’s best reply is itself a switch, so the contest has a contest inside it.

That last sentence is as compact as the finding gets. The count reports what is at stake as though it were what the position is worth, and on a settled position those coincide, and on a contested one they are different numbers about different things.

The nested switch is worth a note too, because it is the case a two-number summary cannot even approximate. A position whose options are themselves contested has a whole thermograph rather than a mean and a width, and reading one off is what the temperature field is for.

The convention, named #

Amazons is normal play: a player with no move loses. That is why everything on this site applies to it directly, and it is worth noticing that this is not typical of the games in this field.

Dots and Boxes is scored. Go is scored. Chess ends by checkmate. Amazons was invented in 1988, by which time the last-move convention was thoroughly established as the one under which a game has a theory — and whether that influenced the design is not something this site can know. What is true is that Amazons is the game in this field that the theory fits without adjustment, and that it is also the most recently invented.

Where the ladder goes next #

amazons has two rungs now: what a board is worth, and the question its players ask.

The rung above is the one the last section named. A split Amazons position is a sum, its regions have values, and choosing where to move is choosing a component — so the natural next essay is the one that computes a temperature per region and compares the resulting move order with the one a territory count gives. That is the same experiment big is not the same as hot runs on abstract switches, run on a game people play for trophies.