Bitboardでのパターン検索

投稿者: | 2017-03-11

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)

で実装されています。

スポンサーリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください