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
