I changed my search from one tree per search thread to a shared (lock-
free) tree among all threads. Back with dedicated trees, I would set a
visited flag as I walked the tree. With a shared tree are there any
clever ways to detect cycles / super ko?
Here are the two ideas I'm thinking of:
1. An array of visited flags, and each thread uses a unique index into
the array.
2. Track the last n search tree nodes visited and check against that
list with every in-tree move.
Option #1 has a larger memory footprint and will not catch positional
super ko.
Option #2 may be slow and is not guaranteed to solve all cycles.
A variation on #2 is to store a node's depth (at initial creation).
Only when the depth does not increase, check the list for repeats.
This loses positional super ko detection.
What do others do?
Sent from my iPhone
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/