Hi!
Does anyone have a tip on an efficient data structure for finding out
and keeping up information about neighboring groups of each group? It
seems that it is really essential for MonteCarlo tactics when considering
atari defense moves to also consider capturing of any neighboring groups
in atari. However, I always struggled with implementing this lookup
efficiently, so I wonder how do others go about it.
The default method used by Pachi (and it seems Fuego too) is
absolutely naive - every time I am looking at how to save a group in
atari, I go over all stones in the group, for each go over all its
neighbors, and if it's a different group in atari, I add the capture
move to my queue. Of course, this is pretty slow and moreover, now that
I need to keep my features incrementally, completely unfeasible.
I had a look at how GNUGo tackles the problem - it simply keeps an
unsorted list of neighboring groups in a statically-sized array for each
group. However, this has probably horrible cache behavior (the arrays
have to be huge, just in case) and it is fairly expensive to then
maintain these arrays.
Thanks for any ideas,
--
Petr "Pasky" Baudis
The true meaning of life is to plant a tree under whose shade
you will never sit.
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
