Bitboard
連珠では四連、禁手や四ノビする手の列挙など特定の石のパターン検索を頻繁に行います。
REAL Coreでは盤面の石の状態を次の2bitで表現しており
- 盤外(00)
- 黒石(01)
- 白石(10)
- 空点(11)
64bit変数の配列(Bitboardと呼びます)で保持しています。
例えば
++●○+●┨
という石の並びはBitBoardでは
1111 0110 1101 1100
という形で保持されています。
REAL CoreではBitboard上の特定の石のパターン(例:OBBBBOなど)検索をビット演算で実装しています。
黒石/白石/空点bit列
まず黒石/白石/空点がある位置に1が立ったbit列は状態定義からBitboardの値をbとして以下で求めることができます。
- 黒石bit([math]b_B[/math])
(~b >> 1) & b & upper_mask
- 白石bit([math]b_W[/math])
(b >> 1) & ~b & upper_mask
- 空点bit([math]b_O[/math])
(b >> 1) & b & upper_mask
なお、各位置(2bit)の下位にビットが立ち、上位bitは任意の値が入るのでupper_maskとANDをとって0クリアしています。
例えば先ほどの
++●○+●┨
1111 0110 1101 1100
という例では
[math]b_B=[/math]0000 0100 0001 0000
[math]b_W=[/math]0000 0001 0000 0000
[math]b_O=[/math]0101 0000 0100 0100
が得られます。
パターン検索
黒石/白石/空点bit列を使って石のパターンを検索することができます。
連続する[math]n[/math]個の石
長連チェック(BBBBBB)のように連続する同じ石のパターン検索は以下の演算で行えます。
b_B & (b_B >> 2) & (b_B >> 4) & (b_B >> 6) & (b_B >> 8) & (b_B >> 10)
実際、
[math]b_B=[/math]0101 0101 0101 0000
というbit列は上の演算を行うと
0000 0000 0001 0000
となり連続する6個の黒石bitの右端に1が立つbit列が得られます。このbit列からパターンの存在の有無やパターンの位置を知ることができます。
同じような考え方で[math]n[/math]個の連続する石のパターンはn個のシフトした値とのANDをとることで検索することができ、REAL CoreではBitSearch-inl.hで
template<std::size_t N> inline const BitBoard GetConsectiveStoneBit(const BitBoard stone_bit);
で実装されています。
n個の石と1個の空点([BnO1][WnO1]パターン)
四ノビする手の生成などで連続する5つの領域に白石4つと空点1つのパターンを検索することがあります。このパターンを[W4O1]と表記し、一般に連続するn+m個の領域に白石がn個、空点がm個入るパターンを[WnOm]と表記します。黒石についても同様です。
[W4O1]のパターンは以下の5つのbit列を算出することで検索できます。
b_O & (b_W >> 2) & (b_W >> 4) & (b_W >> 6) & (b_W >> 8) b_W & (b_O >> 2) & (b_W >> 4) & (b_W >> 6) & (b_W >> 8) b_W & (b_W >> 2) & (b_O >> 4) & (b_W >> 6) & (b_W >> 8) b_W & (b_W >> 2) & (b_W >> 4) & (b_O >> 6) & (b_W >> 8) b_W & (b_W >> 2) & (b_W >> 4) & (b_W >> 6) & (b_O >> 8)
上から順にWWWWO, WWWOW, WWOWW, WOWWW, OWWWWのパターン検索に対応しています。
同じように[BnO1][WnO1]のパターンは[math](n+1)[/math]個のbit列を算出することで検索することができ、
template<std::size_t N> inline void GetStoneWithOneOpenBit(const BitBoard stone_bit, const BitBoard open_bit, std::array<BitBoard, N> * const pattern_bit_list)
で実装されています。
ピンバック: ビットが立つ位置の列挙アルゴリズム | 連珠プログラム開発ブログ