I had very similar ideas to yours when I started to write CrazyStone. I started with a disjoint-set data structure, and the
hope that I could do all incremental updates locally, without going through long chains. I gave up because of the problem of updating liberties. As you wrote, it seems very difficult to incrementally update liberty counts when chains are merged. So I gave up with the disjoint-set data structure, and I now store a group number for each stone.
It is rather rare that long chains are merged together, so the merging operation can be made very efficient by not exploring the longest chain. I found that not passing through the longest chain is a very big speedup in CrazyStone. But that may depend on your data structure.
David Fotland wrote:
1. I don't know of one. Many Faces keeps a sorted list of liberties and a count of liberties for each chain. When chains are merged, the sorted lists are merged (one pass through both), and the count is updated during the merge. 2. For tactical stability, 4 liberties is enough. When I do tactical look ahead I stop when a chain can be proven to have 4 liberties or more. For semeai, I calculate several liberty-related values, which are estimates of the number of moves it takes to capture a chain with each side to move first. To compare liberties in a semeai you need distinguish between shared (inside) liberties, and outside liberties, and you need to compare the number of eyes in each group. There is a good discussion in "The Second Book of Go".
_______________________________________________ computer-go mailing list computer-go@xxxxxxxxxxxxxxxxx http://www.computer-go.org/mailman/listinfo/computer-go/