On 7/20/07, Peter Drake <[EMAIL PROTECTED]> wrote:
On Jul 20, 2007, at 7:23 AM, Jason House wrote: Thanks for the documentation. I have a few questions. Looking at only the four neighbors to detect eye-like points seems like it could leave many false eyes and allow captures of dangling chains. Is there any mechanism to avoid this problem in the play of the bot? It does also look at the diagonals; see Board.isEyelike(). I'll note this in the next version of the document.
I lost a game in the most recent tournament from a buggy alternative to isEyelike. I believe that it may be a bug that affects many, but I'm not really sure... That makes me especially interested in seeing how others do it and the trades they accepted for it. The documentation implies that you're not using a disjoint set for chain id
tracking. I thought this was one of the large speed gains in libego. > I'm using the same data structure as Lew. Each stone knows its chain ID number, which can be used to look up it pseudoliberty count. I'll hazard a guess that this is faster than traveling up a disjoint set tree, even with path compression.
I thought he was using the disjoint set! I'll recheck. Well written disjoint sets average out to nearly O(1) operations for everything. Merging chains together with a chain ID approach can be O(#stones) and then O(1) for everything else. Disjoint sets don't walk the tree for every lookup... the tree is flattened with each lookup.
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/