Bitboardでのパターン検索

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)