Petr,
2010/7/6 Petr Baudis <[email protected]>
> On Mon, Jul 05, 2010 at 12:10:28PM -0700, René van de Veerdonk wrote:
> > 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.
>
> Hmm, I think what you describe is pretty much the same as the naive
> approach, just with bitmap structures? Or did I misunderstand?
Not so, I believe. A bitmap based function would look something like this:
/**
* return <bitmap_t> containing all capture moves for <player>
* prohibit simple ko
* only consider moves around friendly string at anchor <root>
*
* no checks for validity of <root>, nor status of friendly string at
<root>
*/
bitmap_t board_t::capture_moves (unsigned int player, unsigned int root)
const {
/* 1 */ bitmap_t bm_moves;
/* 2 */ bitmap_t adj_strings = adjacent [root] & points_for_player
[1-player] & atari;
/* 3 */ while (!adj_strings.is_empty ()) {
/* 4 */ const unsigned int i = find_root (adj_strings.lowest_index ());
/* 5 */ adj_strings.clear (string [i]);
/* 6 */ bm_moves = bm_moves | adjacent [i];
/* 7 */ }
/* 8 */ bm_moves = bm_moves & points_empty;
/* 9 */ bm_moves.clear (ko);
/* 0 */ return bm_moves;
}
Line 1: empty bitmap to collect capture moves
Line 2: identifies all enemy stones that are (a) touching the friendly
string in atari,
and (b) are themselves in atari
In this step, these stones could be from multiple enemy strings, and these
strings
are potentially (likely) incomplete, unlike the fragment I posted before.
Therefore,
I start the next loop.
Line 3: For each identified string, do once (and only once)
Line 4: find the anchor point
Line 5: remove all its stones from the 'queue'
Line 6: add its last liberty (and more, but occupied, points) to
<bm_moves>
Line 7: End of loop
Line 8: only empty points are interesting
Line 9: no use for simple ko-point
Line 0: return bitmap with all the capture moves
is_empty (), find_root (), and lowest_index () are small methods/functions
found in
the BitmapGo mockup and each executes in few clock-cycles. You can probably
guess what they do by their names.
Note that the loop only executes if there is a candidate move, and only once
per
candidate move.
The loop you are describing executes once for every stone, checks each of
its
neighbors, and performs additional checks for each enemy stone found. That
should
add up to quite a bit of more work to do. Moreover, there is a lot
of useless and
duplicate work being done.
René
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
