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]> 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
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Peter Drake
http://www.lclark.edu/~drake/
_______________________________________________
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/
Peter Drake
http://www.lclark.edu/~drake/
_______________________________________________
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/
