Tuesday, August 07, 2007

Super ko

The various different rulesets regarding how to deal with super-ko in the game of go 囲碁 bother me. No-result or replay-game is bothersome because the game might be decided regardless of the outcome of the super ko. In positional super ko, if a different player is to move in the repeated position, the game is guaranteed to become different on the next move. The amount of hidden state theoretically required to implement situational or positional super ko is infeasibly enormous and detracts from the concept that the state of the game should be mostly encoded in the visible board position, not some potentially enormous list of forbidden previous positions.

My radical solution is, simply stated, let the game never end. Practically, a game is scored as follows: When both players agree that they are trapped in a super ko situation that no further progress may be made, the game is scored as the average score of all positions being visited in the super ko. If it is a loop, it is simply the average of all the positions in the loop. Theoretically, the players should always be able to agree on what the loop is (one does not need to play mixed strategies in games of perfect information), but if they cannot agree, Markov-chain Monte Carlo may be used to average over a graph.

As a shortcut, one need only bound the average enough to determine the outcome of the game. The average need not be calculated exactly.

A group left on the board that would normally be marked as dead achieves eternal life as players trapped in a loop never get a chance to kill it off.

The average can conceivably be any arbitrary fractional number, so komi should be an irrational number to avoid a tied score.

No comments :