Sure, some long cycles have multi-stone captures. Erik
On Thu, Oct 9, 2008 at 4:39 PM, Don Dailey <[EMAIL PROTECTED]> wrote: > 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/ > > _______________________________________________ > 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/
