1980/04/01 by David Lichtenstein, Michael Sipser · 183 citations
Computer Science · Mathematics · #Artificial Intelligence in Games #Numerical Methods and Algorithms #Complexity and Algorithms in Graphs #PSPACE #Planar #Mathematics #Set (abstract data type) #Combinatorial game theory #Space (punctuation) #Combinatorics #Polynomial #Computer science #Discrete mathematics #Computational complexity theory #Sequential game #Game theory #Algorithm #Mathematical economics #Computer graphics (images) #Mathematical analysis
paper · pdf · doi:10.1145/322186.322201
published in Journal of the ACM 27(2), 393-401 (Association for Computing Machinery)
openalex publication_date 1980/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/04
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.