I never used paths. I keep a linked list of each point in the chain, and each stone has the index of the head of the list it is in. The board has an array of 361 list head/tail pointers, and an array of 361 root-indexes.
Merging linked lists is O(1) since I keep a pointer to the last item. Updating the list-head-index requires walking the shorter list. I don’t support undo in the playouts, so there is no need for the extra bookkeeping to support restoring the old state. Yes, I maintain bitmaps in parallel with the other structures, but I only use them for pattern matching. I didn’t add them to the playouts until the playout time was dominated by move generation, not updates. From: computer-go-boun...@dvandva.org [mailto:computer-go-boun...@dvandva.org] On Behalf Of Peter Drake Sent: Saturday, May 24, 2014 11:57 AM To: computer-go@dvandva.org Subject: Re: [Computer-go] Bitwise-parallel surround capture On Sat, May 24, 2014 at 11:29 AM, David Fotland <fotl...@smart-games.com> wrote: No. Many Faces uses union find. I looked through some old literature, including Anders’ thesis. Even though we all used this algorithm it seems he didn’t mention it, probably because it seemed too obvious. Orego currently uses a variation on union-find with eager path compression; each point is given a direct link to the root of its chain at the time of merging. Is there a significant speed advantage to the lazy approach? I do use bitmaps for pattern matching arbitrary shaped patterns up to 8x8. Does this mean that you maintain the bitmaps in parallel with the other structures? -- Peter Drake https://sites.google.com/a/lclark.edu/drake/
_______________________________________________ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
