You might be right. I have a liberal game length limit on my play-outs so I didn't notice this.
Another game limiting rule could be something based on counting the number of consecutive 1 stone captures and terminating once this goes beyond some reasonable limit such as 10. Would infinite games still be possible with this rule? - Don On Thu, 2008-10-09 at 10:25 -0400, Jason House wrote: > You are incorrect that the following heuristics in random games lead > to finite game length: > * no eye filling > * no suicide > * no simple ko violations > > Consider two eyeless chains with 3 ko's connecting them... Two taken > by black and it's white's move. Filling the one ko it has is suicide. > It must take a ko. On black's turn, it can't fill a ko due to suicide > and must take a ko. The cycle repeats infinitely. > > Yes, this is a real bug found in a real CGOS game... I opted for the > game length limit so my bot could remain online 24/7 > > Sent from my iPhone > > On Oct 9, 2008, at 9:15 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > > > 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/ > _______________________________________________ > 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/
