RE: [computer-go] Keep lists of stones in a group?
4. Keep a singly linked list of stones for each group and keep an additional pointer for each group to the last element of the list. This is what I do in Many Faces. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Isaac Deutsch Sent: Saturday, July 11, 2009 7:48 AM To: computer-go Subject: [computer-go] Keep lists of stones in a group? Hello, I'm thinking about wether it's better to keep a list of stones for each group in the board state or not. I'm keeping a linked list of liberties like Lukasz suggested and it is useful in many cases, but the only case that access to all stones in a group is handy is when removing it. I'm already keeping track of group membership for each stone with union-find. This is needed for the liberty management. There are 3 options I can think of: 1. Keep a doubly linked list for each group. Takes about 1.5 KB ram for 19x19. Stone insertion is O(1), merging is O(1). 2. Keep a simple linked list. Takes about 700B ram. Stone insertion is O(1), but merging is O(min(n,m)) where n,m are the sizes of the groups being merged. 3. Don't keep lists at all. No merging or insertion, takes no ram. In all 3 cases, removing a group takes O(n), n being the size of the group. Option 3 might be a bit slower there because a stack has to be used to perform DFS on the group, also option 3 takes additional memory for the stack. Over all, which do you think is the fastest? All options seem to take about the same amount of effort to maintain. Regards, Isaac p.s. Sorry if this is a double post, I couldn't verify that the message was sent to the mailing list the first time. ___ 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/
RE: [computer-go] Keep lists of stones in a group?
On Sat, 2009-07-11 at 08:57 -0700, David Fotland wrote: 4. Keep a singly linked list of stones for each group and keep an additional pointer for each group to the last element of the list. This is what I do in Many Faces. 5) Use a bitmap. This costs a bit more memory (if one bitmap is allocated per stone), but may have a better locality of reference. Also, there are fewer corner cases wrt cyclic/ empty linked lists, etc. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Keep lists of stones in a group?
Isn't 4. similar to doubly linked lists? You have to keep almost as many pointers as there are points on the board at most. How do you effectively store the pointers to only use as few as possible? I don't see how 5) is good for removing groups. Are there other uses for the bitmaps? Am 11.07.2009 um 18:27 schrieb Moi de Quoi: On Sat, 2009-07-11 at 08:57 -0700, David Fotland wrote: 4. Keep a singly linked list of stones for each group and keep an additional pointer for each group to the last element of the list. This is what I do in Many Faces. 5) Use a bitmap. This costs a bit more memory (if one bitmap is allocated per stone), but may have a better locality of reference. Also, there are fewer corner cases wrt cyclic/ empty linked lists, etc. AvK ___ 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/
RE: [computer-go] Keep lists of stones in a group?
Yes, 4 is very similar to doubly linked lists in memory size. I think it's a little faster. To save memory, I don't use pointers. I use 2-byte indexes into arrays. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Isaac Deutsch Sent: Saturday, July 11, 2009 9:46 AM To: computer-go Subject: Re: [computer-go] Keep lists of stones in a group? Isn't 4. similar to doubly linked lists? You have to keep almost as many pointers as there are points on the board at most. How do you effectively store the pointers to only use as few as possible? I don't see how 5) is good for removing groups. Are there other uses for the bitmaps? Am 11.07.2009 um 18:27 schrieb Moi de Quoi: On Sat, 2009-07-11 at 08:57 -0700, David Fotland wrote: 4. Keep a singly linked list of stones for each group and keep an additional pointer for each group to the last element of the list. This is what I do in Many Faces. 5) Use a bitmap. This costs a bit more memory (if one bitmap is allocated per stone), but may have a better locality of reference. Also, there are fewer corner cases wrt cyclic/ empty linked lists, etc. AvK ___ 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/
