I agree that the check against two moves back is not necessary. As for the solution, I think it is good enough to prevent the infinite loop at least for the current level of my engine. StoneGrid had relatively often crashes due to superko by running out of stack. But there is no crashes due to the superko since I added the check. It's been almost one year. As for the effect on accuracy or strength, the triple ko is rare. And computer engine generated triple ko most times are non-sense triple ko. Usually in those situations, the winning side can find better moves to secure a win by avoiding the super ko. So I guess it really does not matter how well does the engine handle the superko, more importantly is to prevent a crash when the situation arises.
On Fri, Jul 11, 2008 at 5:24 PM, Jason House <[EMAIL PROTECTED]> wrote: > On Jul 11, 2008, at 4:42 PM, "John Fan" <[EMAIL PROTECTED]> wrote: > > I checked it whenever the current move is ko. And I think I only checked > against the latest 6 (or 8) ancestors. And only check it against the node > with even distance in the tree. And I am passing down the list of pointers, > so the comparison is not that much work. It is only pointer comparison, only > 3 or 4 times of extra pointer comparison on each ko move. > > > Checking against the ancestor two moves back is unnecessary. That will only > find violations of the simple ko rule, which I assume all bot authors avoid > to begin with > > > > When using hash table, you would want to stop the repition as soon as > possible. Since if you wait too many moves, lets say depth 32 into the tree, > the same node could have already appears many times in the path, and the UCT > update would have added too many losses for the same node. > > > I don't like adding losses. The ideal handling would be to split the search > tree. While a split is expensive, complex ko violations are extremely rare. > > > > > > > On Fri, Jul 11, 2008 at 4:15 PM, Peter Drake < <[EMAIL PROTECTED]> > [EMAIL PROTECTED]> wrote: > >> Do you always check it? Would it be faster to hold off on this check until >> you realize that you're in a cycle? >> >> On Jul 11, 2008, at 12:06 PM, John Fan wrote: >> >> I guess you missed my message. >> >> I solved this by comparing the current node with its ancestors in the >> path. On each walking down the tree, I pass the list of nodes in the same >> path. Then I check whether the current node already appear in the path. If >> yes, I assign a loss there. To speed it up, I only check the current node >> against 6 nodes before it. >> >> It is not perfect or accurate solution for the issue, but it solves the >> problem at hand. >> >> >> >> On Fri, Jul 11, 2008 at 12:23 PM, John Fan < <[EMAIL PROTECTED]> >> [EMAIL PROTECTED]> wrote: >> >>> I had the same issue in UCT tree. What I did is to check if the current >>> node is a ko move, then compare it with its latest 6 ancestors. If any match >>> is found, then consider the move is a loss. So it cuts off the infinite >>> loop. >>> >>> >>> On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake < <[EMAIL PROTECTED]> >>> [EMAIL PROTECTED]> wrote: >>> >>>> My sense is that most programs ignore superko except for checking right >>>> before a "real" move (as opposed to a playout move) is played. >>>> >>>> The way out of the infinite loop is to set a maximum number of moves in >>>> a playout; abort the playout if you reach this threshold. >>>> >>>> >>>> On Jul 11, 2008, at 9:03 AM, Jason House wrote: >>>> >>>> I tracked down a rare hang/crash in my bot and I'm curious how others >>>>> handle this. >>>>> >>>>> I use simple ko state as part of my hash lookup, but I don't use super >>>>> ko. I can't store the whole graph history because then there would be no >>>>> transpositions at all. I can't really update legal moves to exclude super >>>>> ko >>>>> because the super ko legality changes based on how a node is reached. >>>>> >>>>> In particular, a deterministic algorithm like UCT can get caught in an >>>>> infinite loop. My random playouts may take a bit longer from super ko, but >>>>> it gets quickly resolved. >>>>> >>>>> Sent from my iPhone >>>>> _______________________________________________ >>>>> computer-go mailing list >>>>> <computer-go@computer-go.org>computer-go@computer-go.org >>>>> <http://www.computer-go.org/mailman/listinfo/computer-go/> >>>>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>>>> >>>> >>>> Peter Drake >>>> >>>> <http://www.lclark.edu/%7Edrake/>http://www.lclark.edu/~drake/<http://www.lclark.edu/%7Edrake/> >>>> >>>> >>>> >>>> >>>> _______________________________________________ >>>> computer-go mailing list >>>> <computer-go@computer-go.org>computer-go@computer-go.org >>>> <http://www.computer-go.org/mailman/listinfo/computer-go/> >>>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>>> >>> >>> >> _______________________________________________ >> computer-go mailing list >> <computer-go@computer-go.org>computer-go@computer-go.org >> <http://www.computer-go.org/mailman/listinfo/computer-go/> >> http://www.computer-go.org/mailman/listinfo/computer-go/ >> >> >> Peter Drake >> <http://www.lclark.edu/%7Edrake/>http://www.lclark.edu/~drake/<http://www.lclark.edu/%7Edrake/> >> >> >> >> >> _______________________________________________ >> computer-go mailing list >> <computer-go@computer-go.org>computer-go@computer-go.org >> <http://www.computer-go.org/mailman/listinfo/computer-go/> >> 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/
