Go and mathematics

The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, an 11th century Chinese scholar, estimated in his Dream Pool Essays that the number of possible board positions is around 10172. In more recent years, research of the game by John H. Conway led to the development of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go). Generalized Go is played on n × n boards, and the computational complexity of determining the winner in a given position of generalized Go depends crucially on the ko rules. Go is “almost” in PSPACE, since in normal play, moves are not reversible, and it is only through capture that there is the possibility of the repeating patterns necessary for a harder complexity. Without ko, Go is PSPACE-hard. This is proved by reducing True Quantified Boolean Formula, which is known to be PSPACE-complete, to generalized geography, to planar generalized geography, to planar generalized geography with maximum degree 3, finally to Go positions. Go with superko is not known to be in PSPACE. Though actual games seem never to last longer than moves, in general it is not known if there were a polynomial bound on the length of Go games. If there were, Go would be PSPACE-complete. As it currently stands, it might be PSPACE-complete, EXPTIME-complete, or even EXPSPACE-complete. Japanese ko rules state that only the basic ko, that is, a move that reverts the board to the situation one move previously, is forbidden. Longer repetitive situations are allowed, thus potentially allowing a game to loop forever, such as the triple ko, where there are three kos at the same time, allowing a cycle of 12 moves. With Japanese ko rules, Go is EXPTIME-complete. The superko rule (also called the positional superko rule) states that a repetition of any board position that has previously occurred is forbidden.