Go Endgames Are PSPACE-Hard
David Wolfe · 2002
. In a Go endgame, each local area of play has a polynomial size canonical game tree and is insulated from all other local areas by live stones. Using techniques from combinatorial game theory, we prove that the Go endgame is PSPACE-hard. 1. Introduction Go is an ancient game which has been played for several millennia throughout Asia. Although playable rules are relatively simple (tournament rules can include many technicalities), the game is strategically very challenging. Go is replacing Chess as the pure strategy game of choice to serve as a test-bed for artificial intelligence ideas [9] [7] [6]. Go was proved PSPACE-hard by Lichtenstein and Sipser [8], and was later proved EXPTIME-complete (Japanese rules) by Robson [12]. More recently, Crâşmaru and Tromp [5] proved that Go positions called ladders are PSPACE-complete. Yedwab conjectured that the Go endgame is hard [14]. The endgame occurs when each local area of play has a polynomial size canonical game tree and is insulated from all other local areas by live stones. A combinatorial game theorist will recognize this as a sum of simple local positions. Morris succeeded in proving that sums of small local game trees are PSPACE-complete [11]. Yedwab restricted the games to be of depth 2 [14], and Moews showed that sums of games with only three branches are NP-hard [10] [1, p. 109]. (Each of Moew's games is of the form {a || b | c} where a , b and c are integers.) Since Yedwab's and Moews’ Go-like game trees depend upon scores which are exponential in magnitude (yet polynomial in the number of bits of the scores), they did not translate to polynomial sized Go positions. Berlekamp and Wolfe show how to analyze certain one-point Go endgames [1], Some of these endgame positions have values which are linearly related to dyadic rationals of the form. Since these endgame positions are polynomial in size in the number of bits of the numerator and denominator of x, their techniques can be combined with those of Yedwab and Moews to prove that the Go endgame is PSPACE-hard. Robson observed that in Japanese rules (where repetitions of a recent position are forbidden), Go is easily seen to be in EXPTIME. However, he conjectures that according to Chinese rules (where any previous position is forbidden), Go is EXPSPACE-complete [13]. This paper fails to resolve his conjecture, but the techniques may be applicable.