Game of the Amazons

The Game of the Amazons
abcdefghij
10a10b10c10d10 black queene10f10g10 black queenh10i10j1010
9a9b9c9d9e9f9g9h9i9j99
8a8b8c8d8e8f8g8h8i8j88
7a7 black queenb7c7d7e7f7g7h7i7j7 black queen7
6a6b6c6d6e6f6g6h6i6j66
5a5b5c5d5e5f5g5h5i5j55
4a4 white queenb4c4d4e4f4g4h4i4j4 white queen4
3a3b3c3d3e3f3g3h3i3j33
2a2b2c2d2e2f2g2h2i2j22
1a1b1c1d1 white queene1f1g1 white queenh1i1j11
abcdefghij
The starting position in The Game of the Amazons
Players 2
Setup time 20 seconds
Playing time 30-60 minutes
Random chance None
Skill(s) required Tactics, strategy, position

The Game of the Amazons (in Spanish, El Juego de las Amazonas; often called Amazons for short) is a two-player abstract strategy game invented in 1988 by Walter Zamkauskas of Argentina.[1] It is a member of the territorial game family, a distant relative of Go and chess. El Juego de las Amazonas (The Game of the Amazons) is a trademark of Ediciones de Mente.

The Game of the Amazons is played on a 10x10 chessboard (or an international checkerboard). Some players prefer to use a monochromatic board. The two players are White and Black; each player has four amazons (not to be confused with the amazon fairy chess piece), which start on the board in the configuration shown at right. A supply of markers (checkers, poker chips, etc.) is also required.

Rules

White moves first, and the players alternate moves thereafter. Each move consists of two parts. First, one moves one of one's 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.

abcdefghij
10a10b10c10d10 black queene10f10g10 black queenh10i10j1010
9a9b9c9d9e9f9g9 black circleh9i9j99
8a8b8c8d8e8f8g8h8i8j88
7a7 black queenb7c7d7e7f7g7h7i7j7 black queen7
6a6b6c6d6 white queene6f6g6h6i6j66
5a5b5c5d5e5f5g5h5i5j55
4a4 white queenb4c4d4e4f4g4h4i4j4 white queen4
3a3b3c3d3e3f3g3h3i3j33
2a2b2c2d2e2f2g2h2i2j22
1a1b1c1d1e1f1g1 white queenh1i1j11
abcdefghij
The diagram shows a possible first move by white: d1-d6/g9, i.e. amazon moved from d1 to d6 and fired arrow to g9.

Territory and scoring

abcdefghij
10a10 black circleb10c10d10 black queene10 black circlef10g10h10 black circlei10j1010
9a9b9 black circlec9 black circled9 black circlee9f9 black circleg9h9i9 black circlej99
8a8 black circleb8 black circlec8 white queend8 black circlee8 black circlef8 black circleg8 black circleh8 black circlei8 black circlej8 black circle8
7a7b7c7 black circled7 black circlee7 black circlef7 white queeng7h7i7 black circlej7 white queen7
6a6b6c6 black circled6e6 black circlef6 black circleg6 black circleh6 black circlei6 black circlej6 black circle6
5a5b5 black circlec5 black circled5 black circlee5 black queenf5 black circleg5h5 black circlei5j55
4a4b4 black circlec4 black circled4e4f4 black circleg4 black circleh4i4j44
3a3 black circleb3 black circlec3d3 black circlee3 black circlef3 black circleg3 black circleh3 black circlei3j33
2a2 black circleb2 black circlec2d2 black circlee2 white queenf2 black circleg2 black circleh2i2j22
1a1b1c1 black circled1 black queene1 black circlef1 black circleg1 black queenh1i1j1 black circle1
abcdefghij
A completed Amazons game. White has just moved f1-e2/f1. White now has 8 moves left, while Black has 31.

The strategy of the game is based on using arrows (as well as one's four amazons) to block the movement of the opponent's amazons and gradually wall off territory, trying to trap the opponents in smaller regions and gain larger areas for oneself. Each move reduces the available playing area, and eventually each amazon finds itself in a territory blocked off from all other amazons. The amazon can then move about its territory firing arrows until it no longer has any room to move. Since it would be tedious to actually play out all these moves, in practice the game usually ends when all of the amazons are in separate territories. The player with the largest amount of territory will be able to win, as the opponent will have to fill in her own territory more quickly.

Scores are sometimes used for tie-breaking purposes in Amazons tournaments. When scoring, it is important to note that although the number of moves remaining to a player is usually equal to the number of empty squares in the territories occupied by that player's amazons, it is nonetheless possible to have defective territories in which there are fewer moves left than there are empty squares. The simplest such territory is three squares of the same colour, not in a straight line, with the amazon in the middle (for example, a1+b2+c1 with the amazon at b2).

History

El Juego de las Amazonas was first published in Spanish in the Argentine puzzle magazine El Acertijo in December 1992. An approved English translation written by Michael Keller appeared in World Game Review in January 1994.[1] Other game publications also published the rules, and the game gathered a small but devoted following. The Internet spread the game more widely.

Michael Keller wrote the first known computer version of the game in VAX Fortran in 1994,[2] and an updated version with graphics in Visual Basic in 1995.[1][2] There are Amazons tournaments at the Computer Olympiad, a series of computer-versus-computer competitions.

Computational complexity

Usually, in the endgame, the board is partitioned into separate "royal chambers", with queens inside each chamber. We define simple Amazons endgames to be endgames where each chamber has at most one queen. Determining who wins in a simple Amazons endgame is NP-hard.[3] This is proved by reducing it to finding the Hamiltonian path of a cubic subgraph of the square grid graph.

Generalized Amazons (that is, determining the winner of a game of Amazons played on a n x n grid, started from an arbitrary configuration) is PSPACE-complete.[4][5] This can be proved in two ways.

The first is by reducing a generalized Hex position, which is known to be PSPACE-complete,[6] into an Amazons position.

The second is by reducing a certain kind of generalized geography called GEOGRAPHY-BP3, which is PSPACE-complete, to an Amazons position. This Amazons position uses only one black queen and one white queen, thus showing that generalized Amazons is PSPACE-complete even if only one queen on each side is allowed.

References

  1. 1 2 3 Pegg, Ed (1999), Amazons, retrieved 2014-10-19.
  2. 1 2 Keller, Michael, El Juego de las Amazonas (The Game of the Amazons), retrieved 2014-10-26.
  3. ↑ Buro, Michael (2000), "Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs" (PDF), Conference on Computers and Games, doi:10.1007/3-540-45579-5_17.
  4. ↑ Furtak, Timothy; Kiyomi, Masashi; Uno, Takeaki; Buro, Michael (2005), "Generalized Amazons is PSPACE-complete" (PDF), IJCAI.
  5. ↑ Hearn, Robert A. (February 2, 2005), Amazons is PSPACE-complete, arXiv:cs.CC/0502013 Freely accessible.
  6. ↑ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Informatica (15): 167–191.

Additional reading

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.