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.
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. On Fri, Jul 11, 2008 at 4:15 PM, Peter Drake <[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]> 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]> 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 >>>> [email protected] >>>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>>> >>> >>> Peter Drake >>> http://www.lclark.edu/~drake/ <http://www.lclark.edu/%7Edrake/> >>> >>> >>> >>> >>> _______________________________________________ >>> computer-go mailing list >>> [email protected] >>> http://www.computer-go.org/mailman/listinfo/computer-go/ >>> >> >> > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > Peter Drake > http://www.lclark.edu/~drake/ <http://www.lclark.edu/%7Edrake/> > > > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
