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/
