GPS将棋(OpenShogiLib)のdf-pnの移植その２（ソース全体像）

GPS将棋(OpenShogiLib)のdf-pnのソースの全体像を調べた。

df-pnアルゴリズムの概要

df-pn（Depth-First Proof-Number Search）とは、将棋の詰将棋問題において「詰むか否か」を効率的に証明するための探索アルゴリズムである。
各局面において証明数（Proof Number）と反証数（Disproof Number）を管理し、局面ごとの評価値に基づいて「最も有望な分岐」を優先的に探索する仕組みである。
実装では、単なる深さ優先探索に加え、以下のような工夫がなされている。

重複局面の再探索回避（DAG構造）
同一局面はハッシュ値（HashKey）により識別され、既に計算済みの結果を再利用することで、再探索を回避している。
証明駒を利用した枝刈り
各局面において、詰み成立に必要な最小限の駒集合（Proof Pieces／Disproof Pieces）を保持し、局面間の優越関係を用いることにより探索枝を削減している。
局面評価の断片的解法
浅い局面では固定深度ソルバ（例：FixedDepthSolverExt）を利用して高速に詰み判定を行う工夫が施されている。

クラス構造と主要コンポーネント

1. DfpnTable

DfpnTableは、既に探索済みの局面の評価結果（DfpnRecord）を保存するためのデータ構造である。
並列探索時には複数のスレッドが共有して利用するため、排他制御（LightMutexなど）やハッシュテーブルの分割（DIVSIZEによる分割）が施されている。

以下は、dfpn.h における DfpnTable の主要部分の定義例である。

class DfpnTable
{
  // 略
  boost::scoped_array<Table> table;
  size_t total_size;
  int dfpn_max_depth;
  size_t growth_limit, gc_threshold;
public:
  DfpnTable(Player attack);
  DfpnTable();
  ~DfpnTable();
  template <Player Attack>
  const DfpnRecord probe(const HashKey& key, PieceStand white) const;
  // ...
  void store(const HashKey& key, DfpnRecord& value, int leaving_thread_id=-1);
  // ガベージコレクション用の関数も実装されている
  bool runGC();
  // 略
};

2. DfpnRecord

DfpnRecordは、各局面の評価情報を保持する構造体である。
証明数・反証数に加え、最善手や詰み成立に必要な駒集合（Proof Pieces／Disproof Pieces）なども記録している。

3. Node および Tree

探索ノード（Node）は、局面状態、生成した候補手、各子局面の評価（DfpnRecord）などをまとめた構造体である。
Treeは探索全体の状態管理を行い、局面の遷移（newVisit() 関数など）や探索深度の管理を担当している。
例えば、dfpn.cc では以下のようにノードの基本情報をまとめている。

struct osl::checkmate::Dfpn::NodeBase
{
  // 入力情報
  HashKey hash_key;
  PathEncoding path;
  ProofDisproof threshold;
  Move moved;
  PieceStand white_stand;
  // 局面評価情報
  DfpnRecord record;
  DfpnPathRecord *path_record;
};

主要な探索関数

1. attack()（攻め側の探索）

攻め側の探索では、まずdf-pn表に保存された局面評価（DfpnRecord）をプローブし、既知であればその結果を利用する。
未探索の場合は、generateCheck() により王手をかける候補手を生成し、各子局面ごとに再帰的に探索を行う。
また、浅い深さでは即時詰み判定（ImmediateCheckmate）や固定深度ソルバを利用して高速に結果を得る工夫がなされている。

例えば、dfpn.cc 内の attack 関数の冒頭部分は以下のようになっている。

template <osl::Player P> 
void osl::checkmate::Dfpn::attack()
{
  // ...
  DfpnRecord& record = tree->node[tree->depth].record;
  // df-pn表から既存の評価をプローブする
  record = table->probe<P>(node.hash_key, node.white_stand);
  // 省略：浅い深さでの即時詰み判定など
  // 候補手生成
  generateCheck<P>(tree->state, node.moves, has_pawn_checkmate);
  // 省略：各子局面の証明数・反証数の評価、再帰探索
  // ...
}

2. defense()（受け側の探索）

受け側の探索では、王手から逃れるための候補手を generateEscape() により生成し、各候補の反証数を評価する。
逃げ道が存在しなければ、その局面は詰んでいると判断される。
また、必要に応じて局面情報を再評価するための full-width 探索も実施している。

最適化テクニックと特殊な高速化戦略

1. DAG（有向非巡回グラフ）による重複除去

同一局面はハッシュ値（HashKey）により識別され、df-pn表に記録されるため、同じ局面の再探索を回避することができる。
これにより探索木の不要な膨張を防いでいる。

2. 証明駒を利用した枝刈り

各局面において詰み成立に必要な最小限の駒集合（Proof Pieces／Disproof Pieces）を保持し、局面間で優越性が認められる場合は、より有望な局面の情報を採用する。
この手法は、実際のコード中でも record.setProofPieces() や record.setDisproofPieces() として実装されている。

3. 断片的解法（浅い深さでの特殊処理）

マクロ CHECKMATE_D2 や CHECKMATE_A3 の定義により、浅い深さでの詰み探索を高速に行うために固定深度ソルバ（FixedDepthSolverExt）を利用している。

4. 循環検出

isLoop() 関数などにより、探索中に同じ局面が再び現れるループを検出し、無限ループに陥らないようにしている。
例えば、局面のパス（PathEncoding）に同一局面が含まれている場合にループと判定する仕組みである。

5. ガベージコレクション（GC）

df-pn表やパステーブル（DfpnPathTable）のサイズが過度に大きくならないよう、不要な局面情報を削除するGC機能が実装されている。
DfpnTable::runGC() 関数などがその例である。

6. 祖父局面のシミュレーションとブロッキングシミュレーション

祖父局面のシミュレーションでは、直前の局面だけでなく、ひとつ前（祖父局面）の情報を利用して局面評価を高速化している。
実装例として、grandParentSimulation() 関数が存在し、局面の局所的な類似性を利用している。
ブロッキングシミュレーションは、合駒（王手を防ぐための駒打ち）に対して、類似局面の情報をまとめて利用することで、不要な探索枝を減らす効果があるのである。

7. 証明オラクルの活用

既知の詰み筋（証明オラクル）の情報をヒントとして利用し、探索初期に有望な手を即座に導出する手法が実装されている。
tryProofMain() 関数では、証明オラクルを基に局面の再評価が行われ、探索を効率化している。

並列探索とメモリ管理

実装は並列探索（マルチスレッド）にも対応しており、各スレッドは共有のdf-pn表（DfpnTable）およびパステーブル（DfpnPathTable）を参照する。
そのため、以下の対策が講じられている。

排他制御
LightMutex や（場合によっては） std::mutex により、複数スレッドによる同時アクセスからデータを保護している。
ハッシュテーブルの分割
df-pn表はDIVSIZEで分割され、各部分に対して個別にロックをかけることで、スレッド間の競合を低減している。
GC機能
探索中に不要な局面情報を削除するGC機能は、メモリ使用量を管理する上で極めて重要である。

例えば、dfpn.cc 内の一部では、以下のようにガベージコレクションが呼び出されている。

if (tree->MaxDepth > EnableGCDepth && thread_id <= 0) {
  try {
    const size_t removed = table->runGC();
    // GCにより削除されたエントリの情報を出力している
  }
  catch (...) { 
    if (parallel_shared)
      parallel_shared->stop_all = true;
    throw;
  }
}

まとめ

以上のように、実装においては以下の点が特徴である。

探索効率向上
各局面における証明数・反証数の管理、df-pn表による既探索局面の再利用、証明駒を用いた枝刈り、断片的解法、祖父局面のシミュレーション、ブロッキングシミュレーション、証明オラクルの活用など、多数の最適化テクニックが凝縮されている。
並列探索とメモリ管理
複数スレッドによる探索を安全かつ効率的に実施するため、df-pn表の分割・排他制御およびガベージコレクション（GC）機能が実装され、これにより大規模な探索局面においても安定した動作を実現している。
将棋固有の特殊処理
王手生成（generateCheck()）および王手回避（generateEscape()）に加え、打歩詰めや不成、合駒処理など、将棋のルールに基づいた特殊な対応も盛り込まれている。

TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。