# «1. Introduction A great deal of effort has been spent in the search for optimal and computationally feasible game strategies. In some cases (e.g., ...»

GO is Polynominal-Space Hard

## DAVID LICHTENSTEIN AND MICHAEL SIPSER

Umversayof Cahforma,Berkeley, Cahforma

ABSTRACT. It ~S shown that, given an arbitrary G O posmon o n an n x n board, the problem of determining the

winner is Pspace hard New techmques are exploited to overcome the dffficulues a n s m g from the planar nature

of board games In parucular, tt ts proved that G O ts Pspace hard by reducing a Pspace-complete set, TQBF, to

a game called generahzed geography, then to a planar version of that game, and finally to GO.

KEY WORDS AND PHRASES computattonal complexity, games, GO, planarlty, Pspac¢ hardness CR CATEGORIES 3 69, 5 25, 5 32

1. Introduction A great deal of effort has been spent in the search for optimal and computationally feasible game strategies. In some cases (e.g., Bridge-it, Nim) such strategies have been found, while in others the search has been unsuccessful. Recently it has become possible to provide compelling evidence that such strategies may not always exist. For example, Even and Tarjan [4] and Schaefer [10] have shown that determining which player has a winning strategy m certain combinatorial games is a polynomial-space-complete problem [9] (See also [l, 3].) Polynomial-space-complete (Pspace-complete) problems are generally thought to be computationally infeasible because they are, in a certain sense, the most difficult to solve of all problems in Pspace (the class of problems solvable with a polynomial amount of memory on a reasonable model of computer), including the well-known class of NP- complete problems [6].

We show that GO, a popular Oriental game with a long history, has a similar property.

That is, given an arbitrary G O position on an n x n board, the problem of determining the winner is Pspace hard. (Pspace-hard problems are at least as difficult as any problem in Pspace.) To our knowledge, this is the first such result for a board game. Board games are by their nature p l a n a r - - a property which frequently complicates completeness proofs. We exploit new techniques developed in [7, 8] to overcome this difficulty.

In practice G O is played on a 19 x 19 board. As such it is a finite game for which a large table containing a winning strategy could, in prinople, be given. Our generalization to an n × n board prevents such a solution while preserving the spirit of the game. We make no further modifications to the rules.

We claim only that G O is Pspace hard rather than Pspace complete because G O is not known to be in Pspace. If there were a polynomial bound on the length of G O games, then the completeness would follow trivially. Whde it happens that actual games seem never to Permissionto copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercialadvantage, the ACM copynght notice and the Utleof the pubhcationand its date appear, and notice is giventhat copyingis by permissionof the Associationfor ComputingMachinery To copy otherwise, or to republish,requires a fee and/or specificpermission.

The work of the first author was supportedby the National Soence Foundationunder Grant MCS 76-17605,the work of the second author was supported by the National ScienceFoundationunder Grant MCS 75-21760-A01 and by an IBM Graduate Fellowship Authors' present addresses D Llchtenstem,Computer ScienceDivision,Departmentof Elecmcal Engmeenng and Computer Science, Umversltyof Cahforma, Berkeley, CA 94720; M Sipser, IBM Research Laboratory, 5600 Cottle Road, San Jose, CA 95913 © 1980ACM 0004-5411/80/0400-0393$00 75

approach 192 moves, we are unable to argue this in general. Finally, we acknowledge that our result has no a priori relevance to the problem of determining an optimal strategy when play begins on an empty board.

2. Quantified Boolean Formulas We will prove that G O is Pspace hard by reducing a Pspace-complete set, TQBF, to the problem of deciding the winner in an arbitrary G O position. The reduction proceeds by a series of steps, first reducing TQBF to a game called generalized geography (Section 3), then to a planar version of that game (Section 4), and fmally to GO (Section 6) Definition 1. The set of quantified Boolean formulas QBF ffi {Q~v~Q2v2... Qnvn.

F(vl, v2..... vn) l Q, ~ {v, 3}, where the v, are Boolean variables and F i s a Boolean formula in conjunctive normal form}.

Definition 2. TQBF is the set o f true formulas in QBF.

TQBF is Pspace complete [9].

THEOREM 1.

3. Generalized Geography Definition 3. Generalized geography (GG) is a game played by two players on the nodes of a directed graph. Play begins when the first player puts a marker on a distinguished node. In subsequent turns, players alternately place a marker on any unmarked node q such that there is a directed arc from the last node played to q. The first player who cannot move loses.

This is a generalization of a commonly played game in which players must name a geographical location not yet mentioned in the game and whose first letter is the same as the last letter of the last place named. The first player to be stumped loses. This instance of geography would be modeled by a graph with as many nodes as there are places.

Directed arcs would go from a node u to all those nodes whose first letters are the same as u's last letter.

representing universally quantified variables), and the other player chooses which path to take through 3-diamonds. After all diamonds have been traversed, the V-player chooses a clause, and the 3-player then chooses a variable from that clause. 3 then wins immediately if the chosen variable satisfies the clause; otherwise, V wins on the next move. It follows easily that 3 wins if;' B is true, and we leave the details to the reader. []

4. Planar Generalized Geography THEOREM 3. Generahzed geography is Pspace complete, even when played on planar graphs.

PROOF. (This proof is due to T. Schaefer and an anonymous referee who simplified the original construction appearing in [8] ) Every G G graph constructed in the previous section can be transformed into an equivalent planar G G graph as follows: Draw the graph in the

**plane, allowing arcs to cross. Pick a point in the graph where two arcs cross:**

0 [] PROPOSITION h 3 has a win in the new graph with the indicated replacement i f f 3 has a win m the original graph.

This proposition can be proved with a simple case analysis, which we omit.

To make the proof of Theorem 3 rigorous, the method of drawing a G G graph in the plane should be specified, and we refer the reader to [7, 8] for an analogous proof.

COROLLARY. GG ts Pspace complete even when played on planar bipartite graphs with maximum degree 3.

PROOF. The proof of this can~accomplished by making trivial modifications to the structures described above. The diamonds representing existential variables are enlarged

**to become:**

The back arcs representing clauses are then attached at v,,2 or ~,,2 (instead of v,,1 or ~,1), allowing the graph to remain bipartite. Nodes of indegree greater than 2 are replaced by

**chains, as below:**

/ / 7 /

5. The Rules of GO GO is played on a board which is a grid of 19 x 19 locations caUedpomts. There are two players, Black and White, for whom the rules are symmetric except that Black moves first.

A player moves by placing a stone of his own color on a vacant point. The moves alternate between players, except that any player may pass at any time. The game terminates when both players pass.

As the game progresses, the stones form clusters called groups. A group is a maximal, uniformly colored set of stones which occupy a connected region of the board A group of stones becomes surrounded if none of them is adjacent to a vacant point. After each black (white) move, all surrounded white (black) groups are removed, followed by all surrounded black (white) groups.

SCORING. At the end of the game all dead stones are removed from the board. A stone is dead if it ultimately can be surrounded, despite any attempts to save it. A vacant point is said to be white territory if it is surrounded on all sides by either white stones or the edge of the board. Black territory is similarly designated. The final score for White is the count of all the white territory minus the number of white stones which have been captured (removed at any time). The black score is slmdarly calculated and the highest scorer wins.

These rules are a subset of the actual rules of GO, though they are adequate for our purposes. The major omission concerns the situauon of KO which has a special rule designed to prevent infinite repetitions of the same position. A complete, concise treatment of all the rules is given in [2].

EYES. An important consequence of the GO rules is that certain configurations of stones cannot be captured. If a configuration surrounds two separated, vacant points, it is said to have two eyes. It then cannot be surrounded because it is impossible for the opponent to fill both eyes simultaneously (see Figure 2).

Frequently, in the course of actual games, a player may have a nearly surrounded group of stones which he is desperately trying to connect to a group having two eyes. At the same time his opponent is trying to cut him off. We exploit such a situation later m our proof.

6. Construction of the GO Position We now encode the constructed planar generalized geography game as a GO position. We refer to the GO players as Black and White and the geography players as the 3-player and the V-player. The GO position to be constructed will have the property that Black has a winning strategy iff the 3-player has a winning strategy.

The overall plan behind the construction is to have a large region of guaranteed whtte territory, together with an even larger white group of stones which is nearly surrounded (see F~gure 3). It is so large that the outcome of the game hinges on its survival; that is, Black will wm lff he can capture it. Whlte's only hope is first to escape through the small breach in the surrounding black stones and then ultimately connect to a group with two eyes This breach, however, leads to a structure which is patterned after the given geography graph. White and Black are then, in effect, forced to play the geography game with each other. (The rows of black stones extending from the left into the white group ensure that White would have no hope of recapturing any of that territory.) Each arc and vertex m the geography graph is represented by a corresponding pipe and junctton in the GO position (see Figure 4). There are essenUally five types of vertices which anse in our geography graphs (see Figure 5). We gwe the corresponding G O junctions for these vertices. Note that in the generalized geography graphs which we construct, the position of a choice vertex 0.e., a vertex with outdegree 1) determines which player

## D. LICHTENSTEIN AND M. SIPSER

398 \ /makes the choice. This necessitates the occasional use of trivial vertices to switch the initiative. In the G O construction the nature of the junction determines which player makes the choice. Thus the trivial vertices become unnecessary and are treated as arcs.

The test vertices are distinguished from the join vertices in that they occur only along the sides of the subgraphs representing variables and in the crossover boxes (see Figure 6).

GO is Polynominal-Space Hard 399

The desired G O position is obtained by joining the appropriate pipes and junctions in a way which embeds the geography graph. The pipe entering the first choice junction (the first diamond) is connected to the breach m Black's wall around the large white group.

White moves first.

400 D. LICHTENSTEIN AND M. SIPSER We now argue that if the players play "correctly," then the ensuing game will mimic a geography game in that the course of play will travel through a sequence of pipes corresponding to a valid sequence of geography arcs. Furthermore, if any player does not play correctly, his opponent will be able to win within a few moves.

Upon entering or leaving any junction it will be White's turn. Inductively, we assume that the large white group is completely surrounded except for the tip of the pipe entering the current juncuon. Let us consider the case where the play is about to enter an (a) junction, corresponding to a choice by the V-player. We assume wlog that he wishes to go left.

PROPOSITION 2. I f White"s first move is not at either point 1 or point 2, then Black can win in two moves.

PROOF. Assume that White does not play at either 1 or 2. Further assume that White does not play at 3. In that case Black plays at 2, forcing White to respond at 1, whereby Black wins at 3. If White had played at 3 initially, then by symmetry Black again has a win. [] PROPOSITION 3. I f Black does not respond at point 2, then White can win in two moves.

PROOF. Suppose White played at 1 and Black failed to play at 2. Then White plays at 2, capturing three black stones. Black cannot now prevent White from connecting to the White group with two eyes, and thus White wins. [] PROPOSITION 4. White must now continue at point 3 or else lose immediately.

PROOF. Clear. [] PROPOSITION 5. Black must respond at point 4 or lose immediately.

PROOF. Clear, using the white group which has two eyes and which is directly above 4. [] Thus if White chooses the left-hand pipe and both players play correctly, the sequence of moves would be: White--l; Black--2; White--3; Black--4. The play now continues as before, down the left-hand pipe. The large white group is again completely surrounded, except for the tip of the left-hand pipe, and it is Whlte's turn to move, fulfilling the induction assumptions. Both the (b) and the (c) junctions can be argued similarly. The (d) junction, corresponding to a selection of a variable to test by Black, is somewhat different and we analyze it here. We show that if the play enters through the right-hand pipe, then Black wins lff the play had previously passed down through the verucal pipe.