直線近傍

投稿者: | 2017-03-26

Bit boardの実装が終わったので禁手判定の実装を進めています。禁手は

  • 長連
  • 四々
  • 三々

の3種類があります。

詳細は別の記事にしますが長連と四々は石のパターン検索で判定できる一方、三々は判定が複雑です。というのも、三の定義が「同色の石を1個加えると達四になるもの」となっており「1個加える」点が禁点かで三か否三かが変わります。つまり、禁点の定義と三の定義は相互に依存しており三々の判定は再帰的にチェックする必要があります。判定の高速化や差分計算をしやすいようにREAL Coreでは三々の判定は

  • 見かけの三々(Semi double three)
  • 三々(double three)

の2つに分けて判定をしています。「見かけの三々」は三になる黒石のパターンが2つ以上存在する状態のことで、「三々」は「見かけの三々」から達四を作る位置が禁点になっていない見かけの三が2つ以上ある状態を指します。本記事での禁手判定は三々判定の前段階である「見かけの三々」を判定することを対象とします。

前置きが長くなりましたが正規局面[math]P[/math]における着手[math]m[/math]が禁手(三々は見かけの三々かどうか)かは盤面全体を調べる必要はなく、着手mを中心とした一定の範囲をチェックすれば十分です。そこで「着手mを中心とした一定の範囲」を表す概念としてREAL Coreでは直線近傍(line neighborhood)を定義しています。

直線近傍

ある着手地点[math]p[/math]を中心としたタテ、ヨコ、ナナメの直線領域を以下で定義します。

ある地点[math]p[/math]から[math]N[/math]路以下の直線領域を「地点[math]p[/math]の長さ[math]N[/math]の直線近傍」と呼ぶ。

例えば[math]N=2[/math]の直線近傍は以下になりイメージ的にも理解しやすい概念だと思います。

直線近傍のデータ構造

各方向で最大15地点あり1地点あたり2bitで表現しているので1方向30bitあれば十分です。REAL Coreでは64bit変数2つで直線近傍を表現するデータ構造になっています。なお、[math]N[/math]が3以下であれば64bit変数1つで4方向分の直線近傍を表現できますが禁手判定等では[math]N[/math]が4以上必要となるため64bit変数2つで表現するようにしています。Bit boardは64bit変数32個で表現しているので直線近傍だとデータ量は1/16になります。

禁手判定では直線近傍でパターン検索をし、特定パターンの出現位置が必要になる(例:見かけの三の達四を作る位置を求める)ため位置計算がしやすいように地点[math]p[/math]に対応する状態を14,15/46,47bit目に設定するようにしています。

直線近傍の実装

Bit boardから直線近傍の取得はBitBoardクラスで実装しており

  template<size_t N>
  void GetLineNeighborhoodStateBit(const MovePosition move, std::array<StateBit, kBoardDirectionNum> * const line_neighborhood_list) const;

直線近傍の管理はLineNeighborhoodクラスで実装しています。

スポンサーリンク

コメントを残す

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

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