On Tue, 15 Feb 2005 11:32:57 +0000, Nick Wedd <nick@xxxxxxxxxxxxxxxxx> wrote:
>
>i.e. is there a deterministic, bounded-time algorithm
>to determine that a board position is "finished"? at
>least the way that i and other players i've played
>with
>play go, it's not clear that there is or might be such
>an algorithm. (two consecutive passes before a game
>is considered over).
There is no such algorithm.
Knowing whether this is all my territory, or whether my opponent's group
inside it has a way to live, is difficult.
Actually this is not correct. Such an algorithm is theoretically very
easy for Chinese rules. Japanese rules are a bit more complex, but
come down to the same thing.
The game is finished when neither player wants to play any longer and
therefore pass. For a computer to implement this is easy, just
continue playing until you can't play a move that doesn't put yourself
in atari. You can speed this up a bit by not playing on points that
are only next to your color either, although in that case you have to
be careful not to put your own stones in danger by filling a critical
liberty of yourself. But to make a successful program you'll have to
do that anyway.
In practice, things are a bit more complicated though, as humans don't
like to play the game out that far.
Indeed, with Chinese/area rules, it is much simpler. Try this, with
Japanese/territory rules: