ICGA赛

NoGo

Basic Rules.

The NoGo game is similar to Go, in the sense that each player puts a stone on the board alternatively, and stones do not move; but the goal is different: the first player who either suicides or kills a group has lost the game.

Related information

It has been invented by the organizers of the Birs workshop on Combinatorial Game Theory 2011 for being a completely new game; in spite of the syntaxic similarity with Go (notion of group, killing, black and white stones put alternately on the board), it is not (at all) tactically related to Go. NoGo is immediately PSPACE because it is solvable in polynomial time by an alternating Turing machine[6] (the horizon of the game is at most the number of cells as each location is played at most once per game). The NoGo game is difficult to analyze as it does not look like any known game and we don’t see how to simulate any game in NoGo positions. We could not find any proof of PSPACE-completeness.

赛

程序