A region one player owns

An Amazons board breaks into regions as the arrows fly, which is what makes a decomposed board cheap to evaluate, and once a region holds only one player’s amazons nobody else can ever move in it. Such a region is a number: a bank of moves for its owner, worth nothing to the other player, and the natural guess is that it is worth exactly how many free squares it has.

Amazons on one line settled that on a strip — 45,057 positions and no exception — and predicted that a board would be different:

On a strip the “almost” disappears — 45,057 positions and no exception. In two dimensions it does not, because an amazon can be short of room in one direction and not another, and the gap between the count and the value is the next thing to measure.

There is no gap.

The sweep #

Four exhaustive sweeps and one sample, 2,412 regions in all:

• 2 × 3 with one amazon, up to two burnt squares: 92 regions, all exact;
• 3 × 3 with one amazon, up to three burnt: 801, all exact;
• 2 × 3 with two amazons of one colour: 75, all exact;
• 3 × 3 with two amazons of one colour: 1,044, all exact;
• 4 × 4 with one amazon, sampled: 400 regions with two to seven burnt squares, all exact.

Not one region in either dimension is worth anything other than its free-square count. The sweeps include the shapes the prediction was about — L-shaped regions, regions pinched to a single square in the middle, regions where the amazon starts in a corner with the free squares behind a diagonal — and none of them costs a move.

The sample is the part worth defending. A 4 × 4 region takes a full evaluation, so four hundred of them is ten seconds, and an exhaustive sweep of the board is out of reach. But an exception would be one board, and a sample of four hundred is a reasonable instrument for finding one: what it cannot do is prove there is none.

Why, in one clause #

The prediction was that an amazon could be short of room in one direction and not another, and the move rule makes that impossible.

An Amazons move is two steps: the amazon moves like a chess queen, then fires an arrow like a queen from its new square. The square it has just left is empty, and it is one step away, so the arrow may be fired back into it.

That single option is the whole result. A player whose amazon has any free square beside it can step into that square and burn the square behind — spending exactly one free square per move, and leaving the amazon adjacent to whatever remains of the region. So a connected region of $n$ free squares supplies exactly $n$ moves, whatever its shape, and being short of room in one direction costs nothing because the amazon never has to commit to a direction.

It is worth checking the argument against the one case that looks dangerous: an amazon in a corner with the rest of the region behind a diagonal pinch. The amazon steps to the pinch square, shoots back at the corner, and is now on the far side with the rest of the region in front of it — one square spent, nothing lost. The pinch that looked like a constraint is a square like any other.

The strip result and the board result are therefore the same theorem, and the strip was not the special case. What the two dimensions add is more shapes for the argument to survive, and it survives them.

Two amazons, and the crowding that costs nothing #

The natural place for the argument to fail is a region with two amazons of the same colour, where they can block one another — one amazon parked in a corridor the other wants.

It does not fail: 1,119 such regions across the two boards, all exact. The reason is that a blocked amazon is not a lost move. The player has two amazons and needs only one of them to be beside a free square; the region’s supply of moves is the squares, not the amazons, and an amazon that cannot move is simply one the player does not use.

The check that matters here is that the sweep contains crowded regions at all: a 3 × 3 board with two burnt squares and two amazons leaves five free squares for two pieces, which is as cramped as this size allows. Those are in the 1,044 and they are exact like the rest.

That is worth stating because it separates two ideas the word region runs together. A region’s value is about ownership, not about mobility: whoever owns it collects one move per square, however awkwardly their pieces sit in it.

There is a second reading of the two-amazon result that is worth a sentence, because it sounds wrong until it is said carefully. Adding an amazon to a region does not add value. A region of six free squares is worth 6 with one amazon and 6 with two, since the count is of squares and not of pieces. So a player gains nothing by having more amazons in a region they already own — and everything by having one in a region they do not.

When both players are in it #

The contrast is what makes the one-sided result worth having. Take the same boards and put one amazon of each colour in the region: of the 2,088 such positions, 128 are integers and 1,452 are fractions, with 280 switches and 228 nimbers or numbers-plus-star.

The 128 integers among them are worth a glance, since they are the exceptions to the exception: a shared region can still be a bank of moves, and when it is, one side’s amazon has nothing to contest. What separates those 128 from the 1,452 fractions is not measured here and is the obvious question to ask of them.

So the transition is sharp. A region with one owner is an integer — a bank of moves — and a region with two is almost anything else: a fraction, a fight, an infinitesimal. Nothing gradual happens in between, because there is nothing in between: a region either has both players in it or it does not.

That is the reason a decomposed board is so much easier than a whole one. It is not only that the components are smaller; it is that most of them have stopped being games at all, and are counts a player can add up.

What a player does with it #

Two consequences at a board, and the first is the one that makes Amazons playable at all.

A one-sided region needs no thought. Count the empty squares, add the number to the tally, and never look at the region again — no evaluation, no shape, no ordering. That is why a strong Amazons player spends the endgame counting rather than calculating, and it is now exact rather than approximate.

And the whole game is a race to own regions. Since a shared region is a fight and an owned one is a number, that is not a metaphor but what the values say, and the entire strategic content of the middle game is the partition: whoever ends up owning more squares wins, and the arrows are the instrument for deciding who owns what. Cutting the board is therefore not neutral machinery but the game itself, which is the reading this ladder has been building toward.

Why the count is exact and not merely close #

An integer value is a strong claim and it is worth separating from the weaker one it is easily mistaken for. Left has more moves here than Right would make the region positive. Left has $n$ moves and Right has none makes it the integer $n$, which is a statement about every sum the region ever appears in.

The difference is what a fractional or hot value would mean. A region worth $2\\tfrac12$ would be one where the count is not a whole number of moves — where some placement is worth half a tempo because it changes what the other player can do. A region worth $\\{3 \\mid 1\\}$ would be one where the count depends on who moves first. Neither can happen when only one player can move at all: there is nothing for the other player’s presence to modulate, so the recursion runs down a chain and stops, and a chain of $n$ moves for one player and none for the other is the integer $n$ by the number tree’s own definition.

So the exactness is not a numerical coincidence that survived a large sweep; it is the shape of the game tree. The sweep’s job is to check that the shape really is that — that no arrangement of squares and arrows lets an amazon run out of moves before it runs out of squares — and the one clause that guarantees it is the one identified above.

That also says exactly where the result stops. It stops the moment the region contains an amazon of each colour, because then the other player’s moves exist and can change what the first player may do. The boundary is not a size, a shape, or a number of squares; it is a single bit about who is in the region, and everything on one side of that bit is arithmetic while everything on the other is a fight.

What this changes about the ladder #

The rung below’s prediction was reasonable and it was wrong, and the way it was wrong is worth recording.

It reasoned geometrically: two dimensions give an amazon more ways to be constrained, so somewhere a constraint should bite. The rule reasoned differently: a move is a step plus a shot, and the shot can undo the step’s cost of position. The geometry of the region never enters, because the amazon’s own move rule makes every free square equally available in turn.

There is a general form of this worth carrying. A prediction about a game’s values made from the shape of its positions is a prediction that the shape matters, and it can be answered by a clause of the move rule that makes shape irrelevant. This site has met the pattern before — End-Nim is cold everywhere for a one-line reason about who can move rather than for any reason about rows — and it is the same kind of argument at the same level of depth.

Who plays this game, and why the count matters #

Amazons was invented in 1988 by Walter Zamkauskas as a game to play rather than a game to analyse, and it became a standard test problem for game programming almost immediately: large branching factor, no easy heuristic, and an endgame that decomposes.

That last property is why combinatorial game theory got involved. A late Amazons board is a sum of small regions, so a program that can evaluate regions and add values plays the endgame perfectly while a search would still be enumerating. Berlekamp’s Go endgame work is the model, and Amazons is the game where the technique pays off most obviously, because its regions really do become independent — an arrow is permanent, so a board that has split stays split.

What this page adds is the cheapest half of that machinery, made exact. Most late regions are one-sided, and a one-sided region needs no evaluation at all — a count of squares, with no error term, in one dimension and in two.

What this does not say #

Four limits.

The mixed census is one board size. The 2,088 mixed regions are all 3 × 3 with at most two burnt squares, so the 70 per cent is a share on one shape of board and not a general figure.

Boards up to sixteen squares. The exhaustive sweeps are 2 × 3 and 3 × 3, and the 4 × 4 is sampled. Amazons positions are expensive — each region is a full evaluation — and a 5 × 5 sweep is out of reach here.

Nothing here covers regions with amazons of both colours, beyond the count above. The 1,452 fractions are a different subject and are the rung above.

One region at a time. Every position measured is a single region. A board of several is the sum of them, and the sum of integers is an integer, so nothing new happens there; but it is the sum that the theorem is used on, and it is not swept.

The argument is a proof and is not written as one. An amazon may shoot back gives the induction — a region of $n$ free squares has a move leaving one of $n - 1$ — and turning it into a formal induction takes a paragraph nobody has written here. The census is what stands in for it.

And a region with no amazon at all is worth nought, which is the degenerate case and is excluded from every count above. A region with amazons of one colour and no free squares is worth nought too, and is included.

What it cost to check #

Amazons is the most expensive game on this site to evaluate, and the sweep is where that shows.

A 3 × 3 region is a few milliseconds; a 4 × 4 region is tens of milliseconds, because an Amazons move is a queen move followed by a queen shot and the branching factor is the product of the two. The whole census here is about ten seconds — 2,412 regions, four exhaustive sweeps and one sample — which is affordable and is two orders of magnitude short of a 5 × 5 sweep.

That is the reason the sample exists and the reason it is small. A result of the form no exception anywhere is worth the largest population that can be afforded, and here the affordable population runs out at sixteen squares. The argument in the third section is what carries the claim past that, and the census is what makes the argument worth trusting.

The convention, named #

Normal play, Amazons: an amazon moves any distance in any of eight directions through empty squares, then fires an arrow the same way from its new square, and the arrow burns the square it lands on. A player who cannot move loses.

A region is a maximal set of squares connected through non-burnt squares, so two amazons in different regions can never interact again and the board is the sum of its regions.

A region is one-sided when every amazon in it belongs to one player. Its free-square count is the number of empty squares in it — the amazons’ own squares are not counted, since an amazon is standing on its square rather than able to burn it.

Exact means the region’s value, computed by the recursion, is the integer equal to that count.

Where the ladder goes next #

The amazons anchor has four rungs to here: the game, the strip, the one-dimensional census, and now the two-dimensional one.

The rung above takes this page’s own question about the 1,452 fractions and answers it by dissolving it. The fractions that were not there finds that fifty-six of them are fractions. The other 1,396 are hot positions with a fraction buried somewhere inside their options, counted by a regular expression looking for a slash in a printed value — which is a measurement of the printer rather than of the game, and it is the kind of error a count over rendered strings invites.

With the count corrected the question changes shape. The quantity the separation of two amazons sets is not a denominator at all but a temperature, which is a much more natural thing for a distance to set: further apart is a bigger fight.

Room pulls two ways then tries to improve on distance as a predictor of that temperature, with the two obvious refinements — how many squares each amazon can reach, and how many both can. Neither beats distance on its own. Together they beat it by half as much again, and the reason is the finding: they pull opposite ways. Further apart is hotter, and sharing more reachable squares is colder, so either one alone is measuring the sum of two effects with opposite signs and cancelling most of its own signal.

Two neighbours are worth the trip. When a real board falls apart is where the decomposition is measured on played boards, and it is why the one-sided case matters: most regions late in a game are one-sided, and this page says what all of them are worth. And Amazons on one line is the strip this result generalises, where the same count was established and the failure in two dimensions was expected.