Hi Petr,
In my BitmapGo mockup I have created a function to find all capture moves:
/**
* return <bitmap_t> containing all capture moves for <player>
* prohibit simple ko
*/
bitmap_t board_t::capture_moves (unsigned int player) const {
/* 1 */ bitmap_t bm_moves = points_for_player [1-player] & atari;
/* 2 */ bm_moves = bm_moves.gather () & points_empty;
/* 3 */ bm_moves.clear (ko);
/* 4 */ return bm_moves;
}
Line 1: find all enemy stones currently in atari
Line 2: find their last liberty (i.e, empty point adjacent to enemy group in
atari)
Line 3: exclude simple ko-capture
Line 4: return all candidate moves as a bitmap
Requires maintaining bitmaps for all stones for each color (white, black,
empty),
and all groups in atari (white/black). And the ko-location if you wish.
The call to <gather ()> is relatively expensive (4x shift + 3x or):
/**
* each bit gathers set values from adjacent neighbors
* note: spills into edge-points
*/
const bitmap_t bitmap_t::gather () const {
__m128i r = _mm_slli_epi128 (board, BM_LINE);
__m128i t1 = _mm_slli_epi128 (board, 1);
r = _mm_or_si128 (t1, r);
__m128i t2 = _mm_srli_epi128 (board, 1);
r = _mm_or_si128 (t2, r);
__m128i t3 = _mm_srli_epi128 (board, BM_LINE);
r = _mm_or_si128 (t3, r);
return bitmap_t (r);
}
If you are interested to capture groups adjacent to your ataried group
only, you
would have to modify it a little. I would likely implement it as a check for
each
neighboring enemy ataried group sequentially in a loop. Each loop should be
simpler than this function (no gather ()), and execute only once or twice.
I have not yet incorporated this function in my default playouts, and have
not
yet tested it for speed.
BitmapGo maintains bitmaps for all stones in each group, and their direct
adjacencies (potentially including my own stones). I find these very useful
for
these type of questions. BitmapGo is capable of ~90-100 kpps per thread for
9x9
and ~10 kpps in 19x19 from an empty board, to give you an idea of
efficiency.
These are uniformly random playouts preventing only simple ko and suicide.
René
On Mon, Jul 5, 2010 at 4:07 AM, Petr Baudis <[email protected]> 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
