Generalized Amazons is PSPACE­Complete Timothy Furtak1 , Masashi Kiyomi2 , Takeaki Uno3 , Michael Buro4 Department of Computing Science, University of Alberta, Edmonton, Canada. email: { 1 furtak,4mburo}@cs.ualberta.ca 1,4 National Institute of Informatics, Japan. email: 2 masashi@grad.nii.ac.jp, 3 uno@nii.jp 2,3 serve as a testbed for research on selective search and Abstract adversarial planning. Amazons is a perfect information board game with ˇ Like Hex, Go-moku, Tic-Tac-Toe, and Othello, Ama- simple rules and large branching factors. Two play- zons has the property of being monotonically increasing ers alternately move chess queen-like pieces and (each move blocks one square), so the underlying struc- block squares on a 10 × 10 playing field. The ture of the game is a directed acyclic graph, rather than player who makes the last move wins. Ama- a general graph. This eliminates some potentially com- zons endgames usually decompose into indepen- plicating variables for scientific research. Also like Hex, dent subgames. Therefore, the game is a nat- Amazons cannot end in a draw. ural testbed for combinatorial game theory. It was known that determining the winner of simple ˇ Endgames regularly decompose into independent sub- generalized Amazons endgames is NP-equivalent. games (Fig 1). At this stage, combinatorial game theory This paper presents two proofs for the PSPACE- can be applied to vastly reduce the search space, and thus completeness of the generalized version of the full speed up good move selection compared with full-board game. analyses. Hence, Amazons is a suitable test-domain for new ideas in this area. See for instance [Berlekamp, 2000; Muller and Tegos, 2002; Snatzke, 2004]. ¨ 1 Introduction Establishing the computational complexity of various prob- Amazons is a two-person perfect information board game that lems associated with generalized games is also interesting. combines elements of chess and Go. Both players start with For example, proving NP- or PSPACE-hardness is convincing four pieces called amazons which are symmetrically posi- evidence that a problem does not possess a simple solution in tioned at the edges of an otherwise empty 10 × 10 square general (although effective methods may exist for specific in- board. Moves consist of picking an amazon of the player's stances). colour, moving it like a chess queen, and then shooting an Generalizing the standard Amazons game is straight- arrow straight in one of eight directions from the amazon's destination square to an empty square. This square becomes blocked for the remainder of the game and no amazon or ar- abcde fgh i j abcde fgh i j row can pass it. Arrows are not allowed to pass amazons 1 1 either and amazons cannot be captured. Blocking squares is 2 2 mandatory. The game proceeds in turns and the first player 3 3 4 4 without any legal move loses. Fig. 1 shows two typical Ama- 5 5 zons positions. 6 6 The game of Amazons is interesting for AI research for at 7 7 least the following reasons: 8 8 ˇ Compared with other popular games its rule set is sim- 9 9 ple -- and yet, it leads to interesting strategic concepts 10 10 which need to be addressed when designing evaluation Black to move: c7-b7,e10 Endgame position functions [Lieberum, 2005]. Figure 1: Typical Amazons positions. On the left, the black ˇ The number of legal moves in Amazons positions on the amazon at c7 is about to move to b7 and block e10 to prevent standard board is often in the hundreds or even thou- the white amazon at g8 from entering the SW corner area. sands. This puts pressure on sound backward pruning On the right, Black can make 24 unopposed moves, whereas search techniques such as the alpha-beta algorithm, be- White can make only 20, so Black can win regardless of who cause the number of positions to be searched even at is to move. small depths is astronomical. Amazons can therefore forward: we allow arbitrary square-shaped boards (n × n) with at least one and up to n2 amazons. It is known that solv- ing generalized Amazons puzzles (i.e. determining whether in a single-player Amazons game the player can make at least k consecutive moves) is NP-complete and determining the winner of simple generalized Amazons endgames -- in which players do not interact anymore -- is NP-equivalent 2(n2 + 2) + 4 [Buro, 2000]. In what follows, we present two proofs for the PSPACE-hardness of deciding the winner of generalized1 Amazons positions. While the first proof is more intuitive, 2(n2 + 2) + 5 2(n2 + 2) + 9 the second one leads to a stronger results, namely that the problem remains PSPACE-complete even if each player has only one amazon. 2 Hex Reduction In this section we show that determining the winner in Hex Figure 2: The arrangement of rooms relative to each other positions, which is known to be PSPACE-complete, can be and the connecting corridors. There is slack space for arrows reduced to the related Amazons problem. We begin with the in each corridor and at the top and bottom of each room suf- definition of the sets we like to relate to each other: ficient to allow a large number of amazons to pass through. Definition 1: ˇ AMAZONS is a set of succinct encodings of all gen- and one White amazon (Fig. 2,3). These amazons are placed eralized Amazons positions with a winning strategy for across from each other so that each is able to contain the Black (to move). other in one move, and so gain control of the room. Occu- ˇ HEX is a set of succinct encodings of all Hex positions pied tiles on the Hex board are represented by removing the with a winning strategy for Black (to move). opposing piece. In this way the first stage of the transformed game is effectively a game of Hex where players alternately select rooms, blocking the opponent's amazons. Indeed, if Theorem 1: HEX p AMAZONS. any player does not take control of a room when such a move is available then the opposing player may take a room "for Corollary 1: AMAZONS is PSPACE-complete. free," which in Hex (and similarly here) can only help. The rooms are connected by corridors which require a cer- Proof: [Reisch, 1981] shows that HEX is PSPACE-complete tain minimum number of steps to traverse. This traversal time by reducing QBF to HEX. Moreover, AMAZONS for each corridor is chosen such that no adjacent rooms may PSPACE, which is obvious by the existence of a depth-first affect either player from securing a room. Each of the n2 minimax search algorithm that decides the winner of a given rooms may be sealed off from enemy rooms by blocking off Amazons position in space polynomial in the length of its en- the appropriate corridors. As there are at most 6 entrances to coding. Note, that the number of moves in an Amazons game each room and each can be blocked in one move, minimum played on an n × n board is at most n2 . 2 corridor traversal times of 7n2 are sufficient. To force the outcome of the Amazons game to be equiv- Proof of Theorem 1: We describe a function f that maps ar- alent to that of the initial Hex game, White must win if and bitrary code words w into the encoding of an associated Ama- only if he can form a connecting path from top to bottom. zons position with the following properties: This is accomplished by placing an army of n2 + 2 White 1. If w encodes a Hex position, then the first player (Black) amazons at the bottom of the board with a path to all of the in decode(w) has a Hex winning strategy if and only if bottom rooms (Fig. 4). As with adjacent rooms, these ama- the first player in decode(f (w)) (Black) has an Amazons zons are also sufficiently far away that they cannot influence winning strategy. the initial choosing of rooms. 2. Otherwise, f (w) encodes a fixed Amazons position with At the top of the board are 2n2 + 5 strips of open space. a second player (White) winning strategy. The size of these strips is chosen large enough so that each 3. There exists a Turing machine F and a polynomial p is larger than the rest of the board when ignoring the other such that for all w, F started on input w computes f (w) strips. This ensures that the outcome of the game is entirely in at most p(|w|) steps. determined by which player is able to control a majority of the strips. Strips are positioned such that once a White amazon It follows that w HEX f (w) AMAZONS and HEX has captured one, it is unable to capture any others. At the top p AMAZONS. We now describe the transformation f . of each strip is a long path connecting to a single Black ama- From a given n × n Hex position, each of the n2 hex tiles zon (Fig. 5). The path is made long enough so that while the are represented by a rectangular room containing one Black amazon may eventually reach the strip, the number of moves required to do so is greater than that needed by White to cap- 1 We drop "generalized" from now on when the context is clear. path from enemy influence. Since there are no draws in Hex, a winning strategy for the second player is equivalent to pre- venting White from forming such a sequence of rooms. If White can form a connecting path then the one White amazon at the top and the army (of size n2 + 2) at the bottom may be moved one at a time to take control of n2 + 3 strips, a majority allowing White to win the game. If White cannot form a connecting path then the number of strips he may capture is at most n2 + 1: the number of White amazons on the board not counting the army. Black will then eventually be able to take control of the remaining strips with the amazon at the top of each. This gives Black a majority of Figure 3: Sample transformation of a 3 × 3 Hex board. free space allowing him to win. The winner of this game is therefore the same as for the original Hex position. The connecting corridors must allow for the entire army to pass through them. The given structure requires long slack tunnels so that arrows may be fired while moving. These tun- nels must be at least as long as the size of the army, n2 + 2. Not counting the boundary walls, the height of the horizontal corridors then is 2(n2 + 2) + 5, and the diagonal corridors one less. Ensuring that the corridors are long enough to pre- vent room interference is a simple matter of adding additional bends in the path, with each bend increasing the travel time n2 + 2 by 2. Since each corridor only needs to be 7n2 moves long constructing this new board is clearly polynomial. Figure 4: White's army at the bottom of the board. The first Each room is a rectangle with slack tunnels running amazon can block off paths to enemy rooms. through the middle. This tunnel is easily sufficient with al- most twice the space of those in the diagonal corridors. Mov- ing an amazon through a room is straightforward: move to the center column when entering, then move to the exit row, and very long tunnel (~size of lower board) finally into the next corridor. To enter and exit on the same row simply move straight across. The initial amazon in the room may be considered as part of the army or moved out of > rest of board the way to the side. Rooms and corridors may clearly be arranged without con- flict (Fig. 2). The entire transformation takes polynomial time in the size of the original Hex board. The strategy to move the army to the top of the board when a connecting series of rooms exists is then trivial. It is also clearly impossible to do this when a connecting series of rooms does not exist. 2 3 Geography Reduction Figure 5: 2n2 + 5 large strips of space at the top of the board. Here we show a stronger result, namely that even if the num- White has a gatekeeper to prevent enemy rooms from reach- ber of Amazons is bounded by a constant, the problem re- ing them. Black has an amazon at the top of each strip that mains PSPACE-complete. We again start with definitions of will eventually be able to take control of it if White cannot. the sets we consider: Definition 2: ture as many strips as he can. This is the time needed to ˇ AMAZONS-2 is a set of succinct encodings of all decide the control of each room, secure those rooms, and to n × n Amazons positions with exactly one Black and move the army from the bottom of the board to each of the one White amazon and a winning strategy for Black (to strips. A very loose upper bound for this distance is the num- move). ber of free squares in the lower section of the board, every- thing beneath the strips. In this manner Black is eventually ˇ GEOGRAPHY-BP3 is a set of succinct encodings of able to take control of any strips that White cannot. GEOGRAPHY positions -- consisting of a directed bi- If the first player (White) has a winning strategy in the ini- partite planar graph, whose node types are shown in tial Hex position that player may capture a set of rooms such Fig. 7,8,9, and a distinguished start node (Fig. 6) with two leaving edges -- for which the first player has a win- that a path exists from the bottom of the playfield to the top. By blocking all corridors to hostile rooms he may isolate this ning strategy. only once, vertices cannot be marked twice. We force the two amazons to go along the same paths. If one amazon advances toward a path different from the path chosen by the acting Figure 7: Path vertex. player (the player placing the marker) then the amazon will be locked out by the acting player at some gadget. Figure 6: Start vertex. We implement a path, which has a one-square width, as blank squares with surrounding blocked squares, as shown in Fig. 10. We assume an amazon is currently at the left en- trance a and proceeds to the right exit A. At each player's respective turn, the amazon is moved forward and blocks a Figure 8: Branch vertex. Figure 9: Join vertex. square behind it. If the player blocks a square in front of him the amazon becomes trapped. The amazons need to travel at maximum speed, otherwise they will be locked out by the op- Theorem 2: GEOGRAPHY-BP3 p AMAZONS-2. ponent's amazon at some point. In Fig. 10, the amazon needs at least 12 moves to travel from the entrance to the exit. The Corollary 2: AMAZONS-2 and AMAZONS are PSPACE- amazon can also get there in 13 moves. We use gadgets that complete. force the amazons to travel in the minimal numbers of moves Proof: Analog to Proof of Corollary 1. Note that (in this case 12). Thus, amazons have to traverse any straight AMAZONS-2 p AMAZONS. line section of a path in one move. If we want to force an 2 amazon to take several moves, we bend the path an appro- priate number of times as shown in Fig. 10. Moreover, it is Proof of Theorem 2: Geography is a game played by two obvious that we can change the direction a path aims as we players on a given directed graph with a marked start node. like. We now discuss the sub-gadgets shown in Fig. 11 to 14. The players alternately put a marker on any unmarked node from which there exists an edge from the node marked last. Type 1 top speed gadget (Fig. 11). Assume the amazon The first player who cannot move loses. Note that in case for player X (denoted X ) comes to the bottom left entrance, of GEOGRAPHY-BP3, the graph is bipartite and planar with a, and the amazon for player Y (Y ) comes to the bottom right node types that are shown above. The game always ends in entrance, b. This gadget forces Y to come to the entrance as a vertex with two entering edges and one leaving edge at the quickly as possible. That is, if Y comes to the entrance just second visit of that vertex. [Lichtenstein and Sisper, 1980] after X comes to the entrance (we say that they arrive at the show that GEOGRAPHY-BP3 is PSPACE-complete. entrances at the same time in this situation), then X cannot We present a polynomial-time transformation that maps in- trap Y and X should exit this gadget at A, and Y should exit put words -- which are now encodings of planar bipartite at B . If Y comes to this gadget late then X can lock Y out in graphs with a start marker -- into encodings of Amazons po- 3 moves by moving to E , C , then D and blocking F . Thus sitions with two amazons, such that the first player wins the Y should come to the entrance as quickly as possible. If Y geography game if and only if the first player wins the associ- comes to entrance b at the same time X enters, Y can move ated Amazons game. We emulate the Geography game with to F and block D. Thus, Y cannot be trapped. In this case two amazons -- one for each player -- and with blocks that both X and Y can exit this gadget in five moves; X 's exit is fill the board with the necessary structure. The structure has A, Y 's exit is B . Note that if we use two paths to connect this two separate paths for each edge of the given graph. One path gadget to a symmetrical one, we can force both X and Y to (Fig. 10) is for player one and the other path is for player two. move at top speed along those paths. The two amazons simultaneously proceed along the paths as Type 2 top speed gadget (Fig. 12). If X enters this gadget quickly as possible, otherwise one player locks up the other from a and Y enters from b (resp. d and c), the gadget forces player. We construct the structure such that player one win- X to proceed to exit A and Y to proceed to exit B (resp. D ning in generalized geography is equivalent to the amazon of and C ). Otherwise the player being late will be trapped by player one being able to trap the amazon of player two. We the other player. This gadget is somewhat complex, so first embed the given directed graph in the board using a pair of we will simply refer to its functionality. Assume amazon X paths to represent an edge. To embed the vertices we use two comes to the entrance a and amazon Y comes to the entrance gadgets that force the players to proceed along the paths in b (resp. d and c). This gadget forces Y to come to the entrance pairs and in the same direction as the original directed edges. Putting a marker on a vertex in GEOGRAPHY-BP3 cor- responds to the two amazons going from a vertex gadget to A B another vertex gadget. Since each vertex gadget can be used C D A E F a a b Figure 10: Path example. Figure 11: Top speed gadget (type 1). as quickly as possible. If Y 's entrance is b, this is the same as out by X . We can check the other properties analogously. type 1 top speed gadget, and Y should come to b at the same Type 3 top speed gadget (Fig. 13). This gadget is almost time that X enters. If Y 's entrance is d, this gadget forces Y identical to the previous gadget. The only difference is the to come to d at least before X reaches G, or otherwise Y will direction of the right hand side paths which have been mir- be locked out by X . If Y 's entrance is c, then even if Y comes rored. to c at the same time that X enters, X can trap Y . In addition, Cross gadget (Fig. 14). We can cross a path of player X if X enters from b (resp. c) and Y enters from c (resp. b), Y and a path of player Y with this gadget. Assume the entrance should come to c at the same time that X enters. Otherwise for X is a, and the entrance for Y is b. If X and Y come to X can lock Y out. If X 's entrance is a and Y 's entrance is b, the gadget at the same time, X is forced to exit the gadget at X is forced to exit at A and Y is forced to exit at B . Amazons A and Y is forced to exit this gadget at B . Both X and Y can use the gadget twice, once to enter at a and b and once to take five moves in that case. If X comes later, then X will be enter at d and c. At the first use of the gadget they cannot put locked out. If Y comes two moves later than X , then Y will blocks to obstruct the next use of the gadget. be trapped. Similarly, if a player goes to another exit, or tries Now we detail the amazons' sequence of moves in this gad- to obstruct the opponent player, the opponent player can lock get. First we will describe the moves when X 's entrance is the amazon out. In addition, if X comes to the gadget and Y a and Y 's entrance is b and they come to the entrance at the never comes, then if X exits at B , X takes two more moves same time. X moves to N , Y moves to Q; X then moves than if X exits at A. If Y comes to the gadget and X never to G and blocks I , Y moves to O and blocks H . Then they comes, then if Y exits at A, Y takes two more moves than if proceed to their respective exits at top speed. If X blocks a Y exit at B . We can easily check these properties. position other than I , Y can then proceed to other exits. This We now explain the main vertex gadgets corresponding to increases the number of moves available to Y , so X should the four types of vertices in Fig. 6, Fig. 7, Fig. 8 and Fig. 9. not play this way if he wants to win. Thus we can assume that It is easy to emulate a vertex in Fig. 7. We do this with two X blocks I . If Y blocks a position other than H , X can trap paths, one for each player, on which player one needs one Y . Thus Y should block H to prevent being locked out. If more move to travel from entrance to exit than player two X 's entrance is a and Y 's entrance is c and they arrive at the does, effectively reversing which player is next to act. We entrance at the same time, X moves to N and Y moves to R. illustrate gadgets for branching vertices (Fig. 8) and joining X then moves to G and blocks L, Y moves to P and either vertices (Fig. 9) in Fig. 15 and 16, respectively. We can use blocks F (option 1) or blocks any other position (option 2). the gadget in Fig. 15 for the start vertex (Fig. 6), too. We draw In the case of (1), X moves to K and blocks M . In the case paths for amazon X , who is expected to enter this gadget of (2), X moves to J and blocks E . In both cases, Y is locked first, as solid lines and paths for amazon Y as dotted lines. Two amazons always come to the paired entrances at the same time, otherwise an amazon being late will be locked out by A B C D the opponent's amazon at the top speed gadget just after the entrance. E Branch gadget (Fig. 15). This gadget corresponds to a F vertex with an entering edge and two leaving edges (Fig. 8), G H I J K L M from which a player selects one of the leaving edges to fol- N O P low.Since we can adjust the number of moves amazons re- Q R quire along paths by bending these paths arbitrarily, we set a b c d those from X 's entrances to X 's exits and those from Y 's Figure 12: Top speed gadget (type 2). entrances to Y 's exits to be the same length. Because of the cross gadget, X requires two more moves if X wants to take Y 's exit, therefore doing so will result in X being trapped by Y in the type 2 top speed gadget. Thus player X cannot select Y 's path. Y must select the exit in the same direction that X did, otherwise Y is locked out at the type 2 top speed gadget. Note that if X slows down inside the gadget Y can lock X Figure 13: Top speed gadget (type 3). B A a b Figure 14: Cross gadget. Figure 15: Branch gadget. also drawn in a constant size, even if it includes a cross gad- get. Thus, each grid point is drawn in a board of a constant size, and the size of the Amazons game board is bounded by a polynomial in the size of the input planar graph. To com- plete the transformation function definition with respect to the three properties stated in the previous proof, input words that do not encode valid graphs are mapped into a fixed Ama- zons position with two opposing amazons, Black to move and White to win. From the above explanations, it is clear that the run-time of the entire transformation is polynomial in the in- put length. 2 4 Conclusion We have presented two reductions which imply that determin- ing the winner of generalized Amazons positions is PSPACE- Figure 16: Join gadget. complete. The Hex reduction is appealing because it directly relates two board game complexities. The Geography reduc- out in the cross gadget or any of the top speed gadgets. In tion, however, leads to a stronger result, because the transfor- addition, we can use this gadget for the start vertex (Fig. 6). mation only generates Amazons positions with two opposing We place Black and White amazons at the entrance so that the amazons, whereas in the Hex reduction, the number of gener- Black amazon would enter the gadget first. The size of this ated amazons cannot be bounded above by a constant. gadget is clearly independent of the input size. As this paper was being finished we discovered that Robert Join gadget (Fig. 16). This gadget corresponds to a vertex Hearn had simultaneously derived similar results [Hearn, with two entering edges and a leaving edge (Fig. 9). Ama- 2005]. His reduction shows that generalized Amazons with zons come to this gadget at the left or right entrance. If it is an unbounded number of amazons is PSPACE-complete. the amazons' first visit to this gadget, the gadget forces the amazons to exit at the top center. If one player changes his Acknowledgments way and advances to the entrance not used, the opponent's We thank Darse Billings and Robert Hearn for their valuable amazon can trap him in a type 2 top speed gadget in front of feedback on a draft paper. Financial support was provided the entrance. At the second visit, the amazons cannot exit the by the Natural Sciences and Engineering Research Council gadget, because they can use the left exit of the last top speed of Canada (NSERC). gadget only once. Thus, after they pass the first top speed gadget, they have to play Amazons only in the gadget. In this case, Y will win by entering the region denoted by the gray References ball, which has larger space than that of the rest of this gad- [Berlekamp, 2000] E. Berlekamp. Sums of n × 2 amazons. In get, and closing the entrance to the ball. Y only has to wait Institute of Mathematics, Statistics Lecture Notes ­ Monograph till X fills up the rest of the gadget and becomes locked out by Series 35, pages 1­34. Springer, 2000. himself. This situation corresponds to that in GEOGRAPHY- [Buro, 2000] M. Buro. Simple amazons endgames and their con- BP3 where it is player X 's turn and the adjacent vertices are nection to hamilton circuits in cubic subgrid graphs. In Comput- already marked. The size of this gadget is also independent ers and Games Conference, pages 250­261. Springer, 2000. of the input size. [Hearn, 2005] R.A. Hearn. Amazons is PSPACE­complete. Using the gadgets described above we can transform any http://arxiv.org/abs/cs.CC/0502013, 2005. bipartite planar graph -- as described in the definition of [Kant, 1996] G. Kant. Drawing planar graphs using the canonical GEOGRAPHY-BP3 -- into an Amazons position such that ordering. Algorithmica, 16(1):4­32, 1996. the player to move wins the Geography game if and only if [Lichtenstein and Sisper, 1980] D. Lichtenstein and M. Sisper. Go the first player wins the Amazons game. First we embed the is polynomial­space hard. J. of the ACM, 27:393­401, 1980. given graph into a grid, taking space polynomially bounded by the input graph's size using a linear time orthogonal graph [Lieberum, 2005] J. Lieberum. An evaluation function for the game drawing algorithm (e.g. [Kant, 1996]). Then we replace each of amazons. Theoretical Computer Science, accepted, 2005. grid point which corresponds to a vertex or an edge with a [Muller and Tegos, 2002] M. Muller and T. Tegos. Experiments in ¨ ¨ vertex gadget or a path gadget respectively. Each vertex is computer amazons. In R. Nowakowski, editor, More Games of incident to leaving edges and entering edges at some direc- No Chance, pages 243­260. Cambridge University Press, 2002. tions: north, south, west, and east. We can set the entrances [Reisch, 1981] S. Reisch. Hex ist PSPACE­vollstandig. Acta In- ¨ and exits of the vertex gadgets equal to the directions of these formatica, 15:167­191, 1981. edges by surrounding them with path gadgets. Further, we [Snatzke, 2004] R.G. Snatzke. Exhaustive search of databases in sometimes have to use the cross gadget to connect exits to the application of Combinatorial Game Theory to the game [of] the right entrances in the next gadget. Vertex gadgets and amazons. Ph.D. thesis, University of Augsburg, Germany, 2004. the path gadgets surrounding them are drawn in a board of constant size. An edge corresponding to a grid point can be