Go is polynominal-space hard

ABSTRACT. It ~S shown that, given an arbitrary GO posmon on an n x n board, the problem of determining the winner is Pspace hard New techmques are exploited to overcome the dffficulues ansmg from the planar nature of board games In parucular, tt ts proved that GO ts Pspace hard by reducing a Pspace-complete s t, TQBF, to a game called generahzed geography, then to a planar version of that game, and finally to GO