Given that you are basically looking at a bitmap, here is my implementation
to get all legal moves (according to Brown):
/**
* return <bitmap_t> containing all legal moves for <player>
* move is strictly legal if it connects to a liberty provided by
* - an empty neighbor
* - a connection to a friendly group not in atari
* - a capture of a neighboring enemy group
* considered are only moves that are not one-point (half)-eyes, i.e.,
* - no empty neighbors
* - no enemy neighbors
* - no connection to friendly group in atari
* prohibit simple ko
*
* known issue: disallows some connection moves essential in capture races
*/
bitmap_t board_t::all_legal_moves (unsigned int player) const {
const bitmap_t bm_my_points = points_for_player [player];
const bitmap_t bm_your_points = points_for_player [1^player];
bitmap_t connect = bm_my_points;
connect.clear (atari);
bitmap_t capture = bm_your_points & atari;
bitmap_t strictly_legal = (points_empty | connect | capture).gather();
bitmap_t no_eye = (points_empty | bm_your_points | atari).gather();
bitmap_t legal = points_empty & no_eye & strictly_legal;
legal.clear (ko);
return legal;
}
Where you'll need the helper function gather(), which for 9x9 looks like:
static __m128i _mm_slli_epi128 (__m128i a, int i) {
__m128i r = _mm_srli_epi64 (a, 64-i); // shift right by (64-i)
__m128i l = _mm_slli_epi64 (a, i); // shift left by (i)
r = _mm_move_epi64 (r); // zero upper QWORD
r = _mm_shuffle_epi32 (r, 0x4e); // exchange lower/upper QWORD
return _mm_or_si128 (l, r); // recombine
}
static __m128i _mm_srli_epi128 (__m128i a, int i) {
__m128i l = _mm_slli_epi64 (a, 64-i); // shift left by (64-i)
__m128i r = _mm_srli_epi64 (a, i); // shift right by (i)
l = _mm_shuffle_epi32 (l, 0x4e); // exchange lower/upper QWORD
l = _mm_move_epi64 (l); // zero upper QWORD
return _mm_or_si128 (l, r); // recombine
}
/**
* 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);
}
Here, a bitmap has one extra bit per line to account for the edge of the
board. The whole bitmap fits in one 128-bit variable. Or's and and's are
overloaded in the straightforward way and 'atari' is a maintained bitmap
that denotes all stones in atari. It runs in about 17 clock cycles.
On Wed, Apr 1, 2015 at 9:28 AM, Remco Bloemen <
[email protected]> wrote:
> I just implementation of 'Rule 2/4' [1] and have some observations I
> would like to share.
>
> First, the corner case can be eliminated if we consider four 'virtual'
> stones of the same colour on the diagonals just beyond the board (i.e.
> on coordinates (-1, -1), etc.). With these stones included, the corners,
> edges and centre eyes all need to have at least two diagonals set.
>
> If we have booleans (tl, tr, bl, br) standing for the occupancy of the
> respective diagonals, then rule 2/4 can be expressed by or-ing each pair
> of diagonals:
>
> (tl & tr) | (tl & bl) | (tl & br) | (tr & bl) | (tr & br) | (bl & br)
>
> This has 11 operations. We can simply this using a Karnaugh Map:
>
> bl br
> 00 01 11 10
> 00 0 0 1 0
> 01 0 1 1 1
> tl tr 11 1 1 1 1
> 10 0 1 1 1
>
> We can see that the minterms require at least six components (like
> above) but the maxterms can be done in four groups:
>
> (~tl & ~tr & ~bl) | (~tl & ~bl & ~br) | (~tr & ~bl & ~br) | (~tl & ~tr &
> ~br)
>
> Negating with De Morgan's law gives:
>
> (tl | tr | bl) & (tl | bl | br) & (tr | bl | br) & (tl | tr | br)
>
> Which again has 11 operations, but this time we can eliminate common
> subexpressions:
>
> t = tl | tr
> b = bl | br
> (t | bl) & (tl | b) & (tr | b) & (t | br)
>
> Resulting in only 9 operations, shaving off two.
>
> In actual C++ code that would be:
>
> const BoardMask eyelike = free &
> (player.up() | BoardMask::bottomEdge) &
> (player.down() | BoardMask::topEdge) &
> (player.left() | BoardMask::rightEdge) &
> (player.right() | BoardMask::leftEdge);
> const BoardMask tl = player.right().down().set(BoardPoint::topLeft());
> const BoardMask tr = player.left().down().set(BoardPoint::topRight());
> const BoardMask bl = player.right().up().set(BoardPoint::bottomLeft());
> const BoardMask br = player.left().up().set(BoardPoint::bottomRight());
> const BoardMask t = tl | tr;
> const BoardMask b = bl | br;
> const BoardMask rule24 = (t | bl) & (tl | b) & (tr | b) & (t | br);
> const BoardMask eyes = eyelike & rule24;
>
> where BoardMask is basically a bool[19][19]. The whole thing should
> compile to a small number of SSE instructions: only shifts, ANDs and
> ORs. Notice that the whole board is processed in one go without any
> branching or looping.
>
> [1] http://senseis.xmp.net/?RecognizingAnEye
>
> I'm new here, so feedback, criticism and/or encouragement is much
> appreciated!
>
> — Remco
> _______________________________________________
> Computer-go mailing list
> [email protected]
> http://computer-go.org/mailman/listinfo/computer-go
_______________________________________________
Computer-go mailing list
[email protected]
http://computer-go.org/mailman/listinfo/computer-go
