Quite a while back I tried to put together a set of requirements of what needed
to be done to make a minimal implementation of a board and liberty
administration that kept liberties incrementally, including their locations.
This because even though my tactics implementation is very fast, I had found
that my program spent a considerable percentage of its time in the getNlib()
function, which is the routine that loops over the stones to fetch its
liberties.
IIRC, at the time I ended up with an implementation that was a little slower
than what was in GNU-Go but was written in Java. So probably about comparable.
However, using this incremental administration still ended up being a lot
slower than simply using the original tactics module that did the getNlib().
You should be able to find the discussion on the old archive of the mailing
list.
The result is maybe not the one you wanted to hear, that it was a wasted
effort. It's better to use an extremely optimized tactics module and then
reduce its use through 'stone-age', also discussed on this list a while back. I
found that where I could do 20Kps/CPU MCTS with light playouts (including
building the tree) this dropped to 15K using tactics. So the cost, while not
negligible, is very reasonable.
All the code is online somewhere :)
Gotta go, Holland is going to play Uruguay so I need to wake up and shower :)
Mark
On Jul 5, 2010, at 1:07 AM, Petr Baudis wrote:
> 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
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
