Go
Description: This ancient game is played by placing stones on a 19*19 board. When a group of stones of one color is completely surrounded by stones of the other color, the surrounded group is removed from the board. The object is to control empty squares by surrounding them; after both players are unwilling to continue play, these squares are counted and the scores adjusted by the numbers of stones that had been removed.
Status: This is a finite game, but can be generalized to n*n boards. Even without ko (special rules related to repetition of positions) the game is PSPACE-hard; with ko (Japanese rules) it is EXPTIME-complete. It is apparently still open whether Chinese or US rules Go is EXPTIME-complete. Even certain "simple" endgames in which the go board has been decomposed into many small independent regions of play are PSPACE-hard.
References:
* GJ 257 [GP11]. * D. Lichtenstein and M. Sipser, Go is polynomial-space hard, J. ACM 27 (1980) 393-401. * J. M. Robson, The complexity of Go, Proc. IFIP (1983) 413-417. * J. M. Robson. Combinatorial games with exponential space complete decision problems. Proc. Mathematical Foundations of Computer Science, Springer-Verlag, LNCS 176, 1984, pp. 498-506. * E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. * D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000. * M. Crâşmaru and J. Tromp, Ladders are PSPACE-complete, Proc. 2nd Int. Conf. Computers and Games, Springer-Verlag, 2000, pp. 241-249.