Amazons, and when a position becomes a sum

An amazon moves like a chess queen: any distance along a rank, a file or a diagonal, through nothing. Having moved, it shoots an arrow, also like a queen, from the square it landed on. The arrow burns the square it reaches and stays there for the rest of the game. A player who cannot move loses.

Two things follow from those rules and they pull in opposite directions. Every move burns a square, so the board shrinks monotonically, the game is short, and the recursion is grounded. And every move burns a square, so the board fragments — and the fragments stop being one game.

The decomposition arrives during the game #

Every technique in this subject begins from a sum. Values add, so a position that splits into independent parts can be evaluated part by part, and that is the reason an exact analysis of anything is possible.

But a sum is a fact about a position, and most games are set up so that the fact is either true from the start or never true at all. Hackenbush sprigs are separate from the moment they are drawn. A Nim position is a list of heaps. Domineering begins as one region and stays one until the placements happen to cut it, which they rarely do on the boards people analyse.

Amazons is the game where the fragmentation is the substance. A full-size Amazons board begins as one enormous fight, and over the course of the game the arrows partition it into regions of a handful of squares each, none of which can influence any other. The endgame is a sum, and getting to a favourable sum is what the middlegame is about.

That makes Amazons the right game for a point the rest of this site takes for granted: the independence of components is a property that can be created, and creating it is a move.

It also inverts the usual relationship between the theory and the player. Everywhere else the analyst’s job is to notice a decomposition that the position already has. Here a player can bring one about, and a player who cuts the board at a moment favourable to them has converted an intractable fight into an arithmetic problem with a known answer. Whether to do that, and when, is a strategic question the theory poses and does not answer.

The asymmetry is worth stating plainly. Cutting the board is good for whoever is ahead in the resulting sum and bad for the other player, so the decomposition is not neutral machinery — it is a weapon, and both players know it. That is not a situation any of the classical examples in this subject present.

What a region is #

Two squares belong to the same region when a chain of unburnt squares connects them, moving one step at a time in any of the eight directions. An amazon in one region can never influence a square in another: no queen move crosses a burnt square, and no arrow does either.

So the regions found by that walk are genuinely independent games, and their values add. That is not an approximation — it is the additivity theorem applied to a partition the position happens to have.

The contrast between those two figures is the essay. The first has a value that can be written down in one character because it decomposed. The second has a value that runs to a line of nested braces because it did not.

What the solver computed, and how #

The decomposition is checked rather than assumed, and the check is the point of the figure.

The regions are found by a flood fill over unburnt squares. Each region is then turned into a board of its own — the same dimensions, with everything outside the region marked burnt — and evaluated by the ordinary game recursion. The values are added.

Separately, and by a route with nothing in common, the whole board is evaluated by the same recursion without any mention of regions at all.

The generator then compares. In the position at the top of this page, the two regions come out worth $5$ and $-3$, their sum is $2$, and the undivided evaluation of the whole board returns $2$. If those had disagreed the figure would not have drawn, and the site’s gate makes the same comparison before anything is published.

That check has teeth because the two computations really are independent. The region evaluation never sees a full board; the whole-board evaluation never sees a region. They share the site’s evaluator and nothing else, and a bug in the flood fill — a region boundary in the wrong place, a diagonal connection missed — would show up as a mismatch rather than as a plausible wrong answer.

The gate also requires the undivided board to report one region. A flood fill that found phantom boundaries would pass the additivity check trivially, since a single region trivially sums to itself, and requiring the count as well is what closes that hole.

Reading the two values #

The numbers in the first figure repay a moment, because they are unusually interpretable for this subject.

The region holding Left’s amazon is worth $5$. Nothing of Right’s can reach it, so Right has no move there ever, and the value is a count: Left has five moves available in that region and Right has none. A game in which one player can move $n$ times and the other cannot move at all is worth exactly $n$, which is the same fact that makes an integer an integer.

The region holding Right’s amazon is worth $-3$. Same argument, other side, smaller region.

The whole board is worth $5 + (-3) = 2$, and $2$ is positive, so Left wins whoever moves. That is the entire analysis of the position, and it took two flood fills and two counts.

Compare what happens before the cut. The $2 \times 4$ board with both amazons on it is worth

$$\{\,\{4 \mid \{1 \mid 0, \{0\mid0\}\}, 0\}, 3 \;\mid\; \{\{0, \{0\mid0\} \mid -1\}, 0 \mid -4\}, -3\,\}$$

which is a first-player win and is not a number, not a switch, and not anything with a short name. It is what a game looks like when the two players are still interfering with each other, and it is why the regions matter: cutting the board replaced that object with two integers.

The last figure is worth dwelling on because it makes the endgame’s character explicit. After the cut, both regions are numbers, nobody wants to move in a number, and the players are simply obliged to. The game has become a formality being played out, and the value said so several moves earlier.

Why a region one player owns is worth a count #

The claim that an unshared region is worth the number of free squares in it looks like an approximation and is not one, and the argument is worth having here because it is what makes the endgame arithmetic trivial once the cutting is done.

Suppose a region holds one amazon, Left’s, and $n$ free squares besides. Right can never move there, so the region is a game in which only Left has options, and a game only Left can move in is worth the number of moves Left can make in it before running out. So the question is whether Left gets exactly $n$ moves — one per free square — or fewer.

Fewer is what a reader expects, because a move needs two things and not one: somewhere to go and somewhere to shoot. An amazon that walks into a corner with its last arrow unspent looks stranded. It is not, and the reason is a clause of the rules easy to read past: the arrow is shot after the amazon has moved, so the square the amazon just left is empty and legal to burn. Every move therefore burns exactly one square and always has a target, and the amazon can always retreat along the line it came down.

So each move costs the region one free square and no move is ever unavailable while a free square remains. Left gets $n$ moves, the region is worth $n$, and the count is exact rather than close.

That is a small theorem with a large consequence for the game. Once the arrows have cut the board into single-owner regions, every component is an integer, the sum is a subtraction, and the winner is decided by counting squares — which is exactly what an Amazons player does and is usually described as an estimate. It is not an estimate on those positions; it is the value. The estimating begins again only where a region holds amazons of both colours, and that is where the ladder above spends its remaining rungs.

How far the exact evaluation reaches #

Not far, and it is worth being specific because the numbers are startling.

A $3 \times 3$ board with one amazon each takes about a second and produces a value four lines long. A $2 \times 5$ board takes six seconds. A $3 \times 4$ board exhausts the memory available to the interning table before it finishes.

Real Amazons is played on $10 \times 10$ with four amazons a side. The number of positions is beyond any comparison worth making, and no exact evaluation of an opening position exists or will.

What is available instead is exactly the decomposition this essay is about. A late Amazons position is a dozen regions of four or five squares each, every one of which is small enough to evaluate exactly, and the sum of their values settles the game. That is not a heuristic or an approximation; it is an exact answer to the endgame, obtained because the arrows did the partitioning that the analyst could not.

Where the model stops #

The boards here are tiny. Everything drawn is at most fifteen squares with one amazon a side. Real Amazons has four amazons a side and a hundred squares, and nothing here scales.

A region with two amazons in it is still a fight. The decomposition helps when the regions are small, and a region containing amazons of both colours is a partizan game that may be as hard as the whole board was — with a temperature and a mean rather than a count. The useful case is a region owned by one player, whose value is a count of the free squares in it — exactly, as it turns out, and not approximately: the rungs above check it on 45,057 one-dimensional positions and 2,412 two-dimensional ones without an exception.

The independence is exact, and the identification of it is the work. Deciding whether two squares are connected is a flood fill and is easy. Deciding, during play, whether a move that would cut the board is worth what it costs is the actual difficulty of Amazons, and the theory has nothing to say about it — this is the gap between knowing a value and knowing a move, in its most concrete form.

Normal play, and no chance. As everywhere here. The convention matters more in Amazons than in most games because the whole game is about running the opponent out of moves, and reversing the convention would reverse the objective.

What the board picture cannot show #

The figures draw squares, amazons and burnt cells, and there are two things a reader might reasonably expect from them that a board cannot supply.

It cannot show that the regions are independent. The shading asserts a partition; nothing in the drawing proves that no move crosses it. The proof is the flood fill plus the observation that no queen move and no arrow passes through a burnt square, and both live in the code rather than in the picture. A reader looking at two shaded areas is being asked to accept a claim, and the claim’s warrant is the value comparison printed beside it rather than the shading itself.

It cannot show how the position was reached. Amazons positions carry their history in the arrows — every burnt square was somebody’s shot — but the board says nothing about the order, and the order is what a player wanting to reproduce the situation would need. A value is a statement about a position and not about the game that produced it.

There is a third thing, more specific to this game. The drawn boards are three or five squares across, and a reader’s intuition about Amazons is formed on boards of ten. Almost every strategic feature of the real game — the value of central amazons, the technique of walling off territory, the endgame counting — needs more room than these figures have. What the figures show is the mechanism, at the smallest size where the mechanism is visible.

What the game is a demonstration of #

Amazons is worth an essay for a reason that is not about Amazons.

The subject’s central technique requires a decomposition, and the literature usually presents positions that have one. That makes the technique look more generally applicable than it is, and it hides the question of where decompositions come from.

There are three answers and Amazons exhibits the third. Some games are sums by construction — Nim, Hackenbush. Some are never sums and the technique simply does not apply. And some become sums, through play, and in those the decomposition is a resource that a player can work towards or deny.

That third category is where most real games live. Go is the largest example: a Go board late in the game is a set of independent regions, and the whole endgame accounting this site describes was developed for it. Amazons is the same phenomenon with the mechanism made explicit, because in Amazons the walls between regions are burnt squares rather than living stones, and there is no ambiguity about whether the separation has happened.

Who found it, and when #

Amazons was invented by Walter Zamkauskas of Argentina in 1988 and published in the puzzle magazine El Acertijo. It is one of very few genuinely modern abstract games to have entered the combinatorial-game-theory literature, and it did so quickly, because its endgames decompose so cleanly that the theory applies almost without modification.

Elwyn Berlekamp analysed one-dimensional Amazons in the late 1990s and found values that include fractions, stars and hot positions, which is a good sign that the game is not a special case of anything simpler. Subsequent work established that deciding a general Amazons position is hard in the complexity-theoretic sense, which was expected and is the usual fate of games with a board that grows.

The game is also a standard test bed for computer play, and the strong programs use exactly the structure described here: play the middlegame with search and heuristics, and switch to exact combinatorial evaluation once the board has fragmented enough for it to be affordable.

What the players count instead #

An Amazons player handed a position that has split does not evaluate the regions and add. They count territory — every empty square to whichever side reaches it in fewer moves — and the two answers can be compared.

The ladder from here #

This is the base rung of the Amazons anchor, and the five above it take the two halves of the last section — the regions one player owns, and the regions both do — as far as an exact evaluation reaches.

When a real board falls apart is the same decomposition on positions from games people played, with the territory count every program uses measured against what the sum is actually worth.

Amazons on one line shrinks the board until it can be swept completely: every strip from two to ten squares with one amazon a side, 37,886 positions carrying 81 distinct values, and not one of them a fraction — every value is an integer, a switch, a number plus a star, or a bare star. The rule that keeps the fractions out is a single clause of the rules, and taking it away puts 1,196 of them straight back in.

A region one player owns settles the count. The value is exactly the free-square count on every one of the 45,057 positions of that sweep, and the exactness was expected to fail in two dimensions, where an amazon can be short of room along one line and not another. It does not fail: 2,412 two-dimensional regions and no exception, for the same one-clause reason — an amazon may shoot back at the square it has just left, so it never runs out of arrows before it runs out of squares.

The last two rungs are about the hard half. The fractions that were not there goes looking for the fractions among shared regions and finds fifty-six of a claimed 1,452, the rest being hot positions with a fraction buried in their options — and the quantity the two amazons’ separation actually sets is a temperature rather than a denominator. Room pulls two ways then improves on distance as a predictor of that temperature, and finds why nothing simpler worked: the two obvious refinements pull in opposite directions, since further apart is hotter and sharing more reachable squares is colder.

The thing established here is a check rather than a theorem. The regions were found, evaluated separately, and their values added, and the sum was compared against an evaluation that never saw a region. The two agreed, and the figure would not have drawn if they had not.