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/
signature.asc
Description: This is a digitally signed message part
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
