Re: [computer-go] Mathematically sound rules for determining when thegame is over

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

David wrote:
> I've been trying to figure out a good set of rules for unequivocally
> determining when a game is over. Ssince mutual passing only works
> when both players agree on the score, what happens if they never
> agree, regardless of how far the game progresses? If the rules of go
> are to be logically sound there must be a way to determine the score
> from the rules of the game when it has been fully played out.

You have two different issues here. One is to get the players to stop
playing at all, the other is to determine the score when they have
decided to stop.

The first issue can in principle be solved by superko, although this
won't be practical if the players are sufficiently clueless. It does
help e.g. if their major problem is that they insist on capturing kos
but never want to fill them. It's not much help if they repeatedly
fill in their own eyes and the opponent captures big chunks of stones.

The second issue is mainly a question of determining the status of all
stones. There are at least four possible approaches:
1. Theoretical analysis (Japanese style).
2. Agreement.
3. Analysis of unconditional status.
4. All stones remaining on the board are considered alive
   (Tromp-Taylor style).

For automated play between clueless programs the first two
alternatives are impractical. Number four is simplest to implement but
also the third alternative can be done objectively.

> What I've come up with is: (I'm assuming chinese rules with super-ko
> rule.) * The game is over when neither black nor white have any valid
> moves except moves that put one of its own groups into atari. *

In my opionion you're on the wrong track. Instead of modifying the
rules to force the game to end, you should modify the program(s) to
reach that goal. That can of course be done by adding a limitation
like the one suggested above in the move generation algorithm. The
critical difference is that when playing against another (more
clueful) program, that program will not be restricted by any
artificial limitations.

> When the game is over your score is the number of stones of your
> colour on the board and the number of empty intersections surrounded
> on all sides by stones of your colour.

This is exactly how Tromp-Taylor rules do, alternative four above.

> This seems to work; when all groups have only two one-stone eyes or
> are in seki the game is over and the score is easy to determine. But
> are there any problems or inconsistensies with the standard rules that
> I'm missing?

Others have already pointed out that this doesn't suffice to
distinguish between seki and a dead group with nakade stones inside.
Another problem is that it doesn't stop the players from filling in
the second last eye of a group and get captured as long as there's
some other valid move left on the board. Thus the game could still go
on almost forever. Completely disallowing putting own stones in atari
would of course radically change the game.

A more useful and still very simple restriction on the move generation
(besides ko and possibly suicide restrictions stipulated by the rules)
is the following:

Moves are disallowed if they don't capture any opponent stone and
would be suicide for the opponent.

The key point is that this stops filling in own one-point proper eyes.
In particular an unconditionally alive string (Benson style) will
never be sacrificed. If applied to an otherwise random player it will
no longer be terminally suicidal except that it sooner or later will
dissolve any seki it has managed to get into. The main tactical
weakness of this restriction is that it won't let a program (however
clueful it otherwise is) protect the tail in a position like this:

+---------+
|.XXX.X.X.|
|XOOOXXXXX|
|XX.OOOOOO|
|OOOO.O...|
+---------+

/Gunnar
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go