Claus,
I think you have summarized things better than I am going to, but
here
goes anyway:
If the play-outs are uniformly random and you have eye rule, it is
guaranteed to terminate as long as you use simple ko. It might even
be
guaranteed to terminate if you don't, I don't know. Although it's
guaranteed to terminate, it could be arbitrarily long (millions or
billions of moves) but that is not a practical consideration. The
odds
of it not terminating within a couple of hundred moves at 9x9 is
probably extremely low as long as you have eye and simple KO and do
not
allow suicide.
If it's not uniformly random, all bets are off.
If you want to be paranoid, you can limit the number of moves but it's
not necessary. Something like number of empty points times some
constant such as 2 or 3 might be good here.
There are several eye rules used, but I believe the vast majority of
us
use the same one. It is stated like this:
1. An empty point surrounded by friendly stones.
2. If edge, no diagonal enemies allowed.
3. If NOT edge, only 1 diagonal enemy allowed.
Some programs do these things in addition to simple ko, no suicide
allowed and eye rule:
1. Limit the number of moves. (not needed)
2. Stop game if one side has many more stones than the other.
3. Detect superko (a waste of time)
4. Let pass move be one of the random moves tried. (bad)
You asked if people compared the eye rules. This has been discussed
on
this group before and the short answer seems to be that it probably
does
not make too much of a difference if it's reasonably sound. You
might
get different opinions on this.
- Don
On Thu, 2008-10-09 at 13:31 +0100, Claus Reinke wrote:
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/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
