Hi again, with yet another question:-)
Could someone please summarize the state-of-the art wrt the various ways
of limiting random playouts, and the their consequences?
There are several variations on the "don't fill your own eyes" (dfyoe) approach,
but the way this approach is often described tends to confuse me (eg, when
someone seems to claim that there is exactly one correct way of implementing
this, or when someone seems to claim that this guarantees termination, or when
the resulting biases are not even mentioned, let alone discussed or compared
against biases in alternative implementations, etc.).
I'll try to summarize my current understanding, in the hope that others will
fill in the missing pieces or point out misunderstandings:
- the only thing that guarantees termination of random playouts (with or
without dfyoe) is the positional superko rule: no whole-board repetitions
allowed. Waiting for this to kick in without taking other measures is not
an option: it takes too long and the results don't tell us much about the
value of the initial position.
- dfyoe variations share some motivations:
- reduce the likelihood of unnaturally long playouts (but not to zero)
- try to avoid disastrous endgame-situation mistakes that random playouts
are otherwise prone to make (and that eliminate the value of playouts)
- try to be simple (efficiently implementable), with low (but non-zero)
probability of introducing errors (filling in when not filling in would
be
better, or vice versa)
- aim to steer playouts to easily counted terminal positions that bear a
quantifiable relationship to the estimated value of the initial position
(perhaps a more suggestive name would be "random legal fill-ins"?)
- some variations of dfyoe have been reported (are there others?):
[Bruegmann; Monte Carlo Go] (Gobble):
The computer only passes if either no legal move is available or all
legal moves reduce the eye space of one of its groups from two to
one. The (over-) simplification lies in the definition of an eye, which
is defined to be a field whose direct neighbors are all of the same
color and whose diagonal neighbors contain no more than 1 stone
of the opposite color (0 for border and corner fields). The reader
may convince himself that this definition of an eye is correct for
most situations, excluding sekis.
.. the rule is necessary for technical reasons, and even though (if
passing was implemented) the program could figure out the rule by
itself, that would be very inefficient ..
[Bouzy,Helmstetter; Monte-Carlo Go Developments] (Olga/Oleg)
Without this rule, the random player would never make living groups
and the games would never end. There are different ways to define
"eyes" as precisely as possible with domain-dependent knowledge
such as Fotland (2002) and Chen and Chen (1999). Our definitions
are designed to be integrated into a random Go-playing program;
they are simple and fast but not correct in some cases.
In OLGA, an eye is an empty intersection surrounded by stones of
one colour with two liberties or more.
In OLEG, an eye is an empty intersection surrounded by stones
belonging to the same string.
The upside of both definitions is the speed of the programs.
OLEG's definition is simpler and faster than OLGA's. Both
approaches have the downside of being wrong in some cases.
OLEG's definition is very restrictive: OLEG's eyes are actual
true eyes but it may fill an actual eye surrounded by more than
one string. Besides, OLGA has a fuzzy and optimistic definition:
it never fills an actual eye but, to connect its stones surrounding
an OLGA's eye, OLGA always expects one adjacent stone to
be put into atari.
Gobble's definition seems to be the one used in recent discussions here.
Has anyone compared the different eye definitions, without other changes?
Or looked for systematic (exploitable) errors (erroneous fill-ins, erroneous
inability to fill in)? What about the remaining unrealistic and overlong games
(filling large parts of the board without making eyes, then killing all and
repeat with small variations)? What about that claim that "the program
could figure out the rule by itself"?
Comments/pointers appreciated (especially if there was a discussion
that limited the options to Gobble's definition, as recent threads seemed
to suggest).
Claus
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
