はじめに一般の詰将棋などの問題設定について説明します。
局面をノードとし、指し手を有向エッジとする木（ゲーム木）があるとします。プレイヤーは「攻め」と「受け」の２人とします。葉ノード（詰将棋の場合は、即詰みor王手をかけられない局面のこと）にはbool値が書かれていて、攻めの勝ちならtrue、受けの勝ちならfalseだとします。内部ノードの値は葉から根に向かって以下のように再帰的に求められます：
- 攻めの手番の場合、子ノードのどれかがtrueならそのノードはtrueである。すべての子ノードがfalseならそのノードはfalseである。
- 受けの手番の場合、子ノードのどれかがfalseならそのノードはfalseである。すべての子ノードがtrueならそのノードはtrueである。
前者をORノード、後者をANDノードと呼ぶこともあります。ミニマックス法におけるmaxノード/minノードの特殊例と見ることができます。
何手詰めなのか事前にわからないとしますと、反復深化深さ優先探索を行うのが普通です。つまり、最大深さDを設定して深さ優先探索し、根からの距離Dの内部ノードにたどり着いた場合は0.5みたいな値を返すことにして、（true=1,false=0でミニマックス探索して）求まった根ノードの値が0.5だったらDを増やして再探索するわけです。df-pnやその亜種では最大深さの代わりに証明数・反証数というのを閾値として用い、内部で再帰的に反復深化深さ優先探索をします。
文献
アルゴリズムの詳細な説明をここに書くのはだるいので、自分への備忘録も兼ねて文献を紹介するにとどめておきます。
GAME-TREE SEARCH USING PROOF NUMBERS THE FIRST TWENTY YEARS
https://dke.maastrichtuniversity.nl/m.winands/documents/ICGA2012PNS.pdf
本当に良いレビュー論文です。2012年という公開時期も良い感じです。
関連トピック
その1: positionとstateの違い
将棋には千日手というルールがあります。同一局面が４回出現したとき、片方が連続して王手をかけ続けているなら王手をかけている側が負けで、さもなくば引き分けになるやつです。このルール設定は「どの局面がどの順番で何回出たか」をプレイヤーが全部覚えていること(perfect recall)を暗に仮定しています。そのため、局面という単語に曖昧さが生じています。
- 《局面 / position》：駒の配置と手番のこと。スナップショット的なイメージ
- 《棋譜 / history》：開始局面から現在までのpositionの移り変わりの履歴
- 《局面 / state》：position + history
みたいな混同がされています。「同一『局面』(←position)が４回出現した『とき』(←state)」みたいな。千日手が絡む詰将棋を正しく解くためには、positionが同じでもhistoryが異なるようなstateは本来は区別して扱う必要があります。positionとstateの区別が曖昧なせいでサイクル問題とかGHI(Graph History Interaction)問題とか呼ばれる問題が出てきます。でも区別すると計算が重くなるじゃんとか色々ありますが、オセロに千日手は無いので今回は無視します。
その2: 2重カウント
オセロには千日手はありませんが、positionが同じでhistoryが異なるstateは無数にあります。transposition tableでこれらを同一視することで探索量を著しく削減できます。しかしこのせいで証明数の二重カウント問題という問題が重く発生します。これに対応するため、df-pnの式をいじったWPNS(weak proof number search)という手法が提案されています。上記のレビュー論文で詳しく言及されています。
その3: 振動問題
これも上記のレビュー論文で詳しく言及されていますが、同じくらい有望な手が複数あったとき、「その手の先の展開をちょっと読みに行って戻ってきてもう片方の手に行く」というのを繰り返し、行きつ戻りつのオーバーヘッドが大きくなる問題です。 trickという対策があります。
その4: データセットの偏り
90年代からゼロ年代にかけての詰将棋ソフト界隈では、「人間が作った詰将棋問題の全てを計算機で解きたい」というのをグランドチャレンジと見ていたようで、江戸時代のスゴい問題集が全部解けたとかそういうのが偉業として語られています。しかしそれはある種の偏りを帯びたデータセットです。そもそも長手数の詰将棋問題を人間が手で作れたという点からして、それはゲーム木として見たときに"メチャクチャ細長い"はずです。なぜならそうでないと手動で検算できないからです。（df-pnをはじめとする）あの界隈の凝った手法たちは、そういうメチャクチャ細長いケースにoverfitしている可能性があるという点は心に留めておくべきです。実際の対局中に出現する長手数の詰み手順が効率的に発見できなくてもがっかりしないようにしましょう。
実装
「完全読みの結果がある値を超えるか否か」という問いにtrue/falseで答えさせるようにして、解の二分探索をする感じで実装しました。長いのでGitHubにあげました。とりあえず単一のcppファイルだけでコンパイルできて動くように書いてあります。
https://github.com/eukaryo/algorithm-study/blob/master/DFPN_single_file.cpp
実装されていない重要テクニックは2つで、終盤は普通のNull Window Searchで読むやつと、ハッシュテーブルを使い切ったときに賢くガベコレするやつです。
