Combinatorial Game Theory
who wins, and by how much
Particular games

Amazons, and when a position becomes a sum

Every technique on this site starts from a position already broken into independent parts. Amazons does not begin that way — the board is one fight until the arrows cut it, and the moment of cutting is something the play produces rather than the analyst assumes.
16 min read 7 figures The sum is the objectThe theory runs outThe value is computable

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.

Amazons, after the arrows have cut the board in 2An amazon moves like a queen and then shoots an arrow, also like a queen, which burns the square it lands on. Late in a game the burnt squares cut the board into regions no amazon can cross — and from that moment the position is a sum of independent games, which is the shape the whole theory was built for, arrived at by the play rather than assumed.worth 2, outcome La burnt square is crossed out; the shading separates the regionsthe regions, evaluated aloneregion 1 — 5region 2 — -3their sum is 2which is what the whole board is worththe regions were found by walking the board, evaluated separately, and their values added — the equality is checked, not claimed
Fig. 1 A position in which the arrows have cut the board in two. The shaded region holds Right’s amazon and nothing else; the unshaded one holds Left’s. Each region was evaluated alone and their values added, and the sum was compared with the value of the whole board.

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.

Amazons, still one fightAn amazon moves like a queen and then shoots an arrow, also like a queen, which burns the square it lands on. Late in a game the burnt squares cut the board into regions no amazon can cross — and from that moment the position is a sum of independent games, which is the shape the whole theory was built for, arrived at by the play rather than assumed.worth {{4 | {1 | 0, {0 | 0}}, 0}, 3 | {{0, {0 | 0} | -1}, 0 | -4}, -3}, outcome Na burnt square is crossed out; the shading separates the regionsone region — no arrow hascut the board yet, so there isnothing to add upuntil the board is cut, the whole position has to be evaluated at once, which is why the real game is out of reach
Fig. 2 The same game before any arrow has cut anything. One region, both amazons in it, and every move by either player affects what the other can do. Until the board is cut, the whole position has to be evaluated at once — which is why the real game is out of reach.

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 55 and −3-3, their sum is 22, and the undivided evaluation of the whole board returns 22. If those had disagreed the figure would not have drawn, and the site’s gate makes the same comparison on every build.

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 recursion in lib/cgt.js 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 55. 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 nn times and the other cannot move at all is worth exactly nn, which is the same fact that makes an integer an integer.

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

The whole board is worth 5+(−3)=25 + (-3) = 2, and 22 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×42 \times 4 board with both amazons on it is worth

{ {4∣{1∣0,{0∣0}},0},3  ∣  {{0,{0∣0}∣−1},0∣−4},−3 }\{\,\{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.

Which part to move inA sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least.5 + -3worth 2, outcome LLeft to movemove inleavingthe whole position becomesverdict541winsexactly one of the 1 moves wins, and it is in 5each verdict is the outcome of the whole position after the move, computed rather than judged
Fig. 3 The decomposed position as a sum, with every move Left has in it listed. Both components are numbers, so every move loses ground — which is the arithmetic form of the fact that once the board is cut, nothing remains but to spend the moves.

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.

How far the exact evaluation reaches

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

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

Real Amazons is played on 10×1010 \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.

Which questions are answerableThe theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space.the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint
Fig. 4 The general shape of the wall. Exact evaluation reaches a few dozen moves and stops, and the games people play are far beyond it. Amazons is unusual only in how quickly the wall arrives — three squares by four is already past it.

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 essentially a count of the moves available in it.

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.

A position is the sum of its partsFour separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable.2+-2+1/2+−1/2=0outcome Peach sprig is a separate game; a move is a move in one of themthe total was computed by adding the games, not the labels
Fig. 5 The shape an Amazons endgame reduces to. Independent components, each with its own value, added. Everything the theory does well happens after a position looks like this, and the interest of Amazons is that it does not start out looking like this.

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.

Amazons, still one fightAn amazon moves like a queen and then shoots an arrow, also like a queen, which burns the square it lands on. Late in a game the burnt squares cut the board into regions no amazon can cross — and from that moment the position is a sum of independent games, which is the shape the whole theory was built for, arrived at by the play rather than assumed.worth {{5 | {2 | −1/4}, {{1 | 1} | {1/2 | 0}, 0}} | {{1/4 | -2}, {{0 | −1/2}, 0 | {-1 | -1}} | -5}}, outcome Na burnt square is crossed out; the shading separates the regionsone region — no arrow hascut the board yet, so there isnothing to add upuntil the board is cut, the whole position has to be evaluated at once, which is why the real game is out of reach
Fig. 6 The smallest board on which the game has any content at all: one amazon a side, three squares by three, and a value that already runs to two lines of nested braces. Nine squares, and the exact answer is longer than the description of the position.

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.

Domineering on 2 by 3Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. The two players see different games on the same board, which is what partizan means — and the value that results is not a number.the boardworth 2 | −1/2outcome N{2 | −1/2}Left plays verticallyRight plays horizontally
Fig. 7 A game where the fragmentation is incidental. Domineering placements can cut a board in two, and on small boards they usually do not — so the game is analysed as one region, and its values come out of a single recursion rather than out of a sum.

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.

The ladder from here

This is the base rung of the Amazons anchor.

Later rungs: one-dimensional Amazons and its values, which are computable and surprisingly rich. The regions owned by one player, and why their values are almost but not quite a count of squares. The moment of separation as a strategic goal, and what a player gives up to achieve it. The complexity result and what it does and does not rule out. And the practical hybrid used by playing programs, which is a real answer to the question of what to do when exact evaluation is out of reach.

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.

Where this goes next

2+-1+1/4+∗={5/4 | 5/4}outcome Leach sprig is a separate game; a move is a move in one of themthe total was computed by adding the games, not the labels The sum is the object Real positions come apart into independent regions, and a move happens in exactly one of them. That operation — the disjunctive sum — is what the whole theory is built to survive, and it is the reason values exist at all. ↑ + ∗worth ↑∗, outcome NLeft to movemove inleavingthe whole position becomesverdict↑0∗loses∗0↑winsexactly one of the 2 moves wins, and it is in ∗each verdict is the outcome of the whole position after the move, computed rather than judged Which part to move in The value of a sum is the sum of the values. The move in a sum is not the move in any part, and there is no rule that reads it off the values — in the smallest interesting example, the only winning move is in the component worth nothing. the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint How hard is it Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.