# GO Is Polynomial-Space Hard

@article{Lichtenstein1980GOIP, title={GO Is Polynomial-Space Hard}, author={David Lichtenstein and Michael Sipser}, journal={J. ACM}, year={1980}, volume={27}, pages={393-401} }

It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is proved that GO is Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and finally to GO.

#### 159 Citations

The Othello game on an n*n board is PSPACE-complete

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1994

Abstract Given an arbitrary position of the Othello game played on an n × n board, the problem of determining the winner is shown to be PSPACE-complete. It can be reduced from generalized geography… Expand

Phutball is PSPACE-hard

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2010

It is shown that, given an arbitrary position of stones on the board, it is a PSPACE-hard problem to determine whether the specified player can win the game, regardless of the opponent's choices made during the game. Expand

Go Endgames Are PSPACE-Hard

- Computer Science
- 2002

Using techniques from combinatorial game theory, it is proved that the Go endgame is PSPACE-hard. Expand

A PSPACE-complete Graph Nim

- Mathematics, Computer Science
- ArXiv
- 2011

The application of graphs can be used as a form of game sum with any games, not only Nim, and it is shown how to construct PSPACE-complete versions with nim heaps *1 and *2. Expand

Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N

- Computer Science
- ICALP
- 1981

It is proved that a natural generalization of chess to an n×n board is complete in exponential time. This implies that there exist chess-positions on an n×n chess-board for which the problem of… Expand

Ladders Are PSPACE-Complete

- Mathematics, Computer Science
- Computers and Games
- 2000

This reduction closely follows that of Lichtenstein and Sipser, who first showed PSPACE-hardness of Go by letting the outcome of a game depend on the capture of a large group of stones. Expand

Complexity of Path-Forming Games

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1993

This work considers the problem to determine whether, for a given game instance, there is a winning strategy for the first player, and shows GENERALIZED GEOGRAPHY and some other PSPACE-complete problems to be linear-time-solvable on graphs with constant bounded treewidth. Expand

PSPACE-hardness of some combinatorial games

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 1987

Abstract PSPACE-hardness of four families of win-lose-draw games' played on a digraph with blocking, capture, or annihilation rules is proved. Special cases of three of the families are shown to be… Expand

Computing a Perfect Strategy for n x n Chess Requires Time Exponential in n

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 1981

Abstract It is proved that a natural generalization of chess to an n × n board is complete in exponential time. This implies that there exist chess positions on an n × n chessboard for which the… Expand

Rikudo is NP-complete

- Computer Science
- ArXiv
- 2021

It is proved that the Rikudo game is complete for NP, even if the puzzle has no hole, when all odd numbers are placed, whereas it is still NP-hard when all numbers of the form 3k + 1 are placed. Expand

#### References

SHOWING 1-10 OF 10 REFERENCES

A Combinatorial Problem Which Is Complete in Polynomial Space

- Mathematics, Computer Science
- JACM
- 1976

It is shown that determining who wins such a game if each player plays perfectly is very hard; this result suggests that the theory of combinational games is difficult. Expand

GO is pspace hard

- Computer Science
- 19th Annual Symposium on Foundations of Computer Science (sfcs 1978)
- 1978

A great deal of effort has been spent in the search for optimal and computationally feasible game strategies, but recently it has become possible to provide compelling evidence that such strategies may not always exist. Expand

The complexity of checkers on an N × N board

- Computer Science
- 19th Annual Symposium on Foundations of Computer Science (sfcs 1978)
- 1978

Under certain reasonable assumptions about the "drawing rule" in force, the problem of whether a specified player can force a win against best play by his opponent is shown to be PSPACE-hard. Expand

On the Complexity of Some Two-Person Perfect-Information Games

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1978

Abstract We present a number of two-person games, based on simple combinatorial ideas, for which the problem of deciding whether the first player can win is complete in polynomial space. This… Expand

Word problems requiring exponential time(Preliminary Report)

- Computer Science
- STOC
- 1973

A number of similar decidable word problems from automata theory and logic whose inherent computational complexity can be precisely characterized in terms of time or space requirements on deterministic or nondeterministic Turing machines are considered. Expand

Electronics Res Lab

- Electronics Res Lab
- 1978

Axioms for GO SIGART Newsletter (ACM), 51 (April 1975), p 13 3 CHANDRA, A K, AND STOC~EYER

- L J Alternation 17th Annual IEEE Syrup Found Comptr Scl,
- 1973

To appear 2 BLOCK, H C Axioms for GO SIGART

- Alternation 17th Annual IEEE Syrup Found Comptr Scl
- 1973

requmng exponential time Preliminary Report Proc 5th Annual ACM Symp Theory Comptg

- requmng exponential time Preliminary Report Proc 5th Annual ACM Symp Theory Comptg
- 1973