Access Restriction

Author Lichtenstein, David ♦ Sipser, Michael
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1980
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract It is shown that, given an arbitrary GO position on an $\textit{n}$ × $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1980-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 27
Issue Number 2
Page Count 9
Starting Page 393
Ending Page 401

Open content in new tab

   Open content in new tab
Source: ACM Digital Library