Amazons on one line

An amazon moves like a chess queen and then shoots an arrow, also like a chess queen, and the square the arrow lands on is burnt for the rest of the game. On a board one square high, “like a queen” collapses to “along the row”. Every diagonal and every file has been taken away, an amazon slides left or right through empty squares and shoots left or right through empty squares, and a whole position is a string: L..x.R is a strip of six squares with Left’s amazon at one end, Right’s at the other, and one square already burnt.

That is a small enough object to hold in the head, and it is not a toy. The base essay on Amazons is about the moment the arrows cut a board into regions and the position becomes a sum. A strip does the same thing, in a game a reader can read aloud, and it produces values from four different classes before the board is ten squares long.

The family the strip is built on #

The simplest strip is two amazons and a gap. Left’s amazon at the left end, Right’s at the right end, g empty squares between them, so the strip is g + 2 squares long. The values run 0, ∗, {1 | −1}, {2 | −2}, {3 | −3}, {4 | −4}, and the pattern is {g−1 | −(g−1)}.

Every member of that family is symmetric under exchanging the players, so its mean value is 0. Every member from g = 2 on is a switch: two options, one good for each player, and a gap between where the position lands under each. And the temperature — how much a player should be willing to pay for the privilege of moving here rather than elsewhere — is half that gap, which is exactly g − 1.

So a strip of a dozen empty squares between two amazons is worth nothing on average and eleven points to whoever moves in it first. The mean value says the position is balanced and the temperature says it is the most urgent thing on any board it sits on, and both are true at once. That is a partizan game in its plainest form — Left’s amazon and Right’s are different pieces, so the two players never have the same move available, and a switch is what that difference looks like when both of them want the same squares.

The mechanism is a race that the arrow decides. Left’s amazon wants to advance into the gap and then shoot behind Right, walling Right into a short region; Right wants the same in reverse. Whoever moves first takes most of the gap, and the amount taken grows with the gap by exactly one square per square. Reading the thermograph of any member gives the same shape: two straight walls, meeting once, with nothing bending on the way up.

A lone amazon is worth a count #

Take the opponent off the strip entirely and the arithmetic becomes arithmetic.

A lone amazon is worth the number of empty squares in its own region. Left with three empty squares to move about in is worth 3, because Left has exactly three moves there and Right has none, and a game where one player can move n times and the other cannot move at all is the integer n.

The reason is the burning. Every move burns exactly one square, and on a strip an amazon can always reach any unburnt square in its region in one slide, so the number of moves available is fixed before anybody plays. There is no way to waste a move and no way to gain one.

The claim was checked rather than asserted. Every strip of up to twelve squares carrying one amazon and any pattern of burnt cells was generated and evaluated by the ordinary game recursion, and the value compared against the count — Σ n · 2ⁿ⁻¹ for n = 1 to 12, which is 45,057 positions, with no exception.

The word region in that claim is doing real work, and the census is where it shows. The strip .xL has one empty square on it and is worth 0, not 1, because the empty square is on the far side of a burnt one and no queen move crosses a burn. A statement of the rule that said “empty squares on the strip” would have 45,057 chances to be wrong and would take several of them.

One burnt square is worth a whole move, and the reason is a sum #

Put the two amazons back and add a single burnt square, and the value swings by a full move depending on where it goes.

L.R is ∗ — the smallest nimber, a first-player win with nothing in it, confused with zero rather than equal to it. Burn the middle square of L.x.R and the position is 0, a second-player win. Slide the burn one place left to Lx.R and it is −1; one place right to L.xR and it is +1.

Those last four numbers are not four separate facts. They are one fact, and it is the fact the whole subject is built on: the strip has fallen into a disjunctive sum. A burnt square is a wall, no move crosses it, and the strip on either side is a game of its own.

• L.x.R is L. plus .R, worth 1 + (−1) = 0.
• Lx.R is L plus .R, worth 0 + (−1) = −1.
• L.xR is L. plus R, worth 1 + 0 = 1.
• L.x..R is 1 + (−2) = −1, and L..x.R is 2 + (−1) = 1.

Each of those sums is the count rule from the previous section applied twice and added, and each was checked against an evaluation of the whole strip that never mentioned a region at all.

That is the surprise worth pausing on. The disjunctive sum is the operation the theory was built around, and it is normally supplied by the way a game is set up — Nim is a list of heaps, Hackenbush is a picture of separate sprigs. Here it arrives in the middle of a game on a board one square wide, produced by the players, in a game invented in 1988 by somebody with no interest in the theory. The decomposition is not an assumption about the position; it is a thing the arrows did.

What the solver computed, and how #

A strip is small enough that the claim “several classes of value” can be settled by exhaustive search rather than by a handful of examples.

The census enumerates every string of length n over the alphabet .LRx containing exactly one L and exactly one R — that is n(n−1) placements of the two amazons times 2ⁿ⁻² patterns of burning on the remaining squares. Summed from n = 2 to n = 10 that is 37,886 positions, and every one was evaluated by the same recursion the rest of this site runs on: build the move list, evaluate the options, reduce to canonical form, intern the result. The class of each position is then read off the canonical form’s name, and every name is an equality the solver proved rather than a shape somebody recognised.

The four classes carry 17, 49, 14 and 1 distinct values respectively, which adds to the 81. The single value in the last class is ∗ itself: not one strip in the census is worth ∗2 or any higher nimber, which is a sharper statement than “stars occur” and is the kind of thing an exhaustive search is for.

The headline is the absence. Not one of the 37,886 is worth a fraction. Every value on a strip is a whole number, a whole number with a star on it, a bare star, or a switch between whole numbers — and a claim about an absence is one that a census can support and no collection of examples can. Thirty-seven thousand positions and no half is evidence; six positions and no half is a drawing.

That absence is also the thing the arrow turns out to be responsible for, which is the next section and is not what anybody would guess.

What the arrow does #

The arrow is what makes a strip a partizan fight with a temperature rather than a dull race along a corridor. Without it, an amazon shuffling along a row does nothing but pass the move, and the natural experiment — take the arrow away and see what breaks — is not available at all: with no burning, an amazon can slide left and right for ever, the game never ends, it is loopy, and the recursion this site runs, in which every game is a finite tree, has no answer for it. That is a genuine limit rather than an omission.

What can be done is subtler and better. Keep the burn and take away the aim: the arrow is forced onto the square the amazon has just vacated. Same queen’s move, same one square burnt per move, same guaranteed termination — one freedom fewer, and nothing else changed.

Run that against the whole census and the expected story is half right. Forcing the arrow does flatten the game: 81 distinct values become 63, and 1,540 more positions collapse into the integers. The number-plus-star class nearly empties, from 2,164 positions to 216.

And then the half nobody would guess. Forcing the arrow creates 1,196 positions worth a fraction, in a game whose real rule never produces one. Taking a freedom away did not shrink the range of values in kind; it produced a class the free game cannot reach. The two rules disagree on 9,648 of the 37,886 positions — a quarter of them — and among the disagreements are .L.R, worth 1∗ with the shot and 1/2 with it forced, and L.R., worth −1∗ and −1/2.

The mechanism is that the shot is what keeps the game’s values whole. With a free arrow, a player who has taken a region can seal it with one burn, and what is left on each side is a count of moves. With the arrow forced backwards, sealing costs something and half-moves survive into the value — which is exactly the shape a rule word makes on Col and Snort, where changing whom a move damages turns a game of counting into a game of grabbing. Here changing where the arrow lands turns a game of grabbing into a game with fractions in it.

Where the search stops #

Everything above is a measurement, and each one has an edge worth naming.

The gap family is observed, not proved. The recursion evaluates the strip with a gap up to n = 17, worth {14 | −14}, in 20.3 seconds; at n = 18 it exhausts the game registry after 48 seconds and returns nothing. So {g−1 | −(g−1)} is a regularity over sixteen members of the family and no more. It is the kind of pattern that usually is a theorem, and this site has not proved it.

The census reaches ten squares. The class counts are claims about strips of ten squares or fewer, and eleven was not run. The whole census of 37,886 positions takes 0.7 seconds — 1.0 seconds with the forced-arrow census computed beside it — which is worth setting against the eighteen-square strip that cannot be done at all. The cost is in the empty squares, not in the length: a heavily burnt strip of ten squares is a handful of moves, and an unburnt one of eighteen is a tree nothing here can hold.

One amazon a side, and one dimension. Nothing here is a claim about the real game on a 10×10 board with four amazons each, and nothing here is a claim about a strip with two amazons a side. That second restriction matters more than it looks: the literature on one-dimensional Amazons reports fractional values, and this census finds none. The two are not in conflict, because the fractions live outside the box the census draws — and the two obvious places outside it are longer strips and more amazons.

And a temperature is only as good as the graph it came from. The thermograph routine saturates: asked for a graph up to t = 8 it will report a temperature of 8 for a position whose temperature is 11. Every temperature quoted on this page was recomputed with the ceiling at 24 or 32, and a caption quoting a temperature from a low ceiling would be quietly wrong in exactly the direction that looks reasonable.

Who found it, and when #

Amazons was invented by Walter Zamkauskas of Argentina in 1988 and published in the puzzle magazine El Acertijo, which makes it one of very few modern abstract games to have entered this subject’s literature — and it entered fast, because its endgames decompose so cleanly that the theory applies almost unmodified.

The one-dimensional game is where people actually computed. Elwyn Berlekamp took up strips and 2×n boards in the late 1990s, and Martin Müller and Theodore Tegos published an exhaustive search of 1×n Amazons in the early 2000s, for the reason this essay exists: it is the largest fragment of the game that can be finished rather than sampled. The full game went the other way — two independent proofs in 2005 established that deciding a general Amazons position is PSPACE-complete, which was expected and is the usual fate of a game whose board grows.

So the strip is not a simplification somebody invented to make an essay work. It is the case the subject settled on when it wanted numbers, and the reason is visible in the timings above: ten squares of it are a second’s work and eighteen are out of reach.

What the picture cannot show #

The figures on this page draw squares, amazons and crossed-out burns, and there are three things a reader might reasonably want from them that no drawing supplies.

A census has no picture. The strongest sentence here — not one of 37,886 positions is worth a fraction — is a fact about a set, and the figure that carries it is a table of counts. Which strips are hot, and where in the strip the switches live, is structure the totals cannot display, and drawing all 2,582 switches would be a wall of dashes.

A strip cannot show what a second dimension costs. The gap family’s values fit on one line each. Give the same squares another row and the value stops being writable.

And a board cannot show that its regions are independent. The shading in the three-region figure asserts a decomposition; nothing drawn proves that no move crosses it. The proof is that no queen move and no arrow passes a burnt square, and the warrant a reader is offered is not the shading but the comparison printed beside it — the sum of the parts against an evaluation that never saw a part. If those disagreed the figure would not draw at all.

The convention, named #

Normal play throughout: a player who cannot move loses. In Amazons that convention is not a detail, because the entire game is the manufacture of positions in which the opponent has run out of room. Under misère play the objective reverses, and a strip worth a comfortable +3 — three moves in hand, and nothing else on the board — becomes a position its owner is desperate to be rid of. None of the values on this page survives the change.

Three rule conventions decide the rest. A move is a slide and then a shot, and both are compulsory: an amazon must move at least one square, and having moved it must shoot. The arrow may land on the square just vacated, which is legal because that square is empty by then — the forced-arrow variant above is what happens when that legal option becomes the only one. And a burnt square is permanent, which is what makes the strip shrink monotonically, the game finite, and the recursion grounded — take the burning away and the game is loopy, with no value in the sense used anywhere on this page.

The last convention is the one that makes the count rule exact: exactly one square is burnt per move. That is why a lone amazon’s value is a count and not a range — the number of moves in a region is settled before play, so nobody can spend a move to gain one, which is the normal reason a number is a number and the reason nobody wants to move in one.

Where the ladder goes next #

This is the third rung of the Amazons anchor, and it settles on a strip a question the base rung left open on a board.

Regions owned by one player, and why their values are almost a count of squares. 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.

The moment of separation as a goal. Cutting the board helps whoever is ahead in the resulting disjunctive sum, so the decomposition is a weapon rather than neutral machinery. On a strip that is a one-parameter decision — where to put the wall — and the six-position sequence above shows it is worth a whole move. What a player should pay for it is the question of which part to move in turned inside out.

Two amazons a side. The census restriction that hides the fractions, and the smallest change that would find them — a strip carrying two partizan fights rather than one.

The complexity result, and what it does not rule out. PSPACE-completeness is a statement about the general problem and says nothing about strips of ten squares, which is why the census exists.

And the hybrid a real playing program uses: search and heuristics through the middlegame, exact combinatorial evaluation once the arrows have cut the board into regions small enough to afford. The programs switch at roughly the size the figures on this page are drawn at, which is the most practical thing a one-square-high board has to say about a game played on a hundred squares.