Petr,
To throw some numbers at this, I implemented this (at least something close
to this) in BitmapGo
and ran some benchmarks. Here are my initial numbers:
no atari-escape:
benchmarking playouts
[game] = 26213 cc, [moves] = 110.929
[game] = 88.8889 kpps, [moves] = 111.089
benchmarking board functions (calls/clock cycles)
[legal] 111/36, [pick] 111/59, [play] 106/145, [score] 56, [win] 0.4228
"global response" atari-escape:
benchmarking playouts
[game] = 25654 cc, [moves] = 106.072
[game] = 90.1408 kpps, [moves] = 106.085
benchmarking board functions (calls/clock cycles)
[legal] 105/52, [pick] 105/60, [play] 101/141, [score] 53, [win] 0.3893
"local response" atari-escape:
benchmarking playouts
[game] = 28114 cc, [moves] = 112.974
[game] = 83.1169 kpps, [moves] = 112.885
benchmarking board functions (calls/clock cycles)
[legal] 112/60, [pick] 112/65, [play] 108/138, [score] 56, [win] 0.4407
The logic in "legal" is:
1 -- if (new-atari) then select capture-move
2 -- if (new-atari and no move selected) then select extension-move
3 -- if (no move selected) then select random move
Where "no atari-escape" means purely uniform random playouts. "global
response" means that
once a move puts an enemy group in atari, first capture moves are considered
across the whole
board, followed by any extension move (providing at least two liberties to
the string in atari), and
finally a uniform random move is chosen. "local response" only considers
these to save strings
that have been put in atari by the last move. The move selection is
performed from a bitmap with
move candidates, which is not very efficient for small numbers of move
candidates. The local
responses could just as well store the move candidates in a vector and chose
from that much
more efficiently, buying back some of the overhead. I did not yet separate
out which calls are
made how often and what is their individual cost. Finding legal moves
obviously becomes more
expensive 36 (no) --> 52 (global) --> 60 (local) cc/call, because more work
needs to be done.
So, the additional cost of looking up capture and/or extension moves slows
the playouts by
perhaps 10% or so. How does this compare your implementation? There is also
changes in
the average length of the playout that confounds this conclusion, so make
your own conclusions.
My guess is that maintaining selected bitmaps incrementally is not very
costly and may benefit
your tactical questions, even if you don't use them for play logic.
René
On Tue, Jul 6, 2010 at 10:03 AM, René van de Veerdonk <
[email protected]> wrote:
> 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
