Amazons

Description

Two players (Black and White) move amazons on a $n \times n$ board. White moves first, and the players alternate moves thereafter. Each move consists of two parts. First, a player moves one of their own amazons one or more empty squares in a straight line (orthogonally or diagonally), exactly as a queen moves in chess; it may not cross or enter a square occupied by an amazon of either color or an arrow. Second, after moving, the amazon shoots an arrow from its landing square to another square, using another queenlike move. This arrow may travel in any orthogonal or diagonal direction (even backwards along the same path the amazon just traveled, into or across the starting square if desired). An arrow, like an amazon, cannot cross or enter a square where another arrow has landed or an amazon of either color stands. The square where the arrow lands is marked to show that it can no longer be used. The last player to be able to make a move wins. Draws are impossible.

An instance consists of $n$ and of the starting configuration of amazons and arrows.

The classical game corresponds to $n=10$, black amazons on a7, d10, g10, j7, white amazons on a4, d1, g1, j4, and no arrows.

Computational complexity

PSPACE-complete via a reductions from Hex [1], from a variant of Geography [1], or from Formula Game [2].

Endgames in which pieces of opposing colors are separated from each other are NP-hard [2] [3].

References

[1] T. Furtak, M. Kiyomi, T. Uno, M. Buro, “Generalized Amazons is PSPACE–Complete”, in IJCAI 2005.

[2] R. A. Hearn, “Amazons is PSPACE-complete”, arXiv preprint, 2005.

[3] M. Buro, “Simple Amazons Endgames and Their Connection to Hamilton Circuits in Cubic Subgrid Graphs”, in CG 2000.

Game of the Amazons on Wikipedia

@misc{cog:amazons,
    author = "{CoG contributors}",
    title  = "{Amazons --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/amazons/",
    note   = "[Online; accessed 2024-04-13]"
}