詰将棋に対するdf-pnアルゴリズムの解説

長手数の詰将棋の探索に用いられるdf-pnアルゴリズムについて、その概要と実用上の課題を解説する。

概要

#

詰め将棋において、各局面の平均着手可能数は5.8手程度と言われている¹。単純にこれを全探索することを考えると、\(n\) 手詰を解くためには \(5.8^n\) 局面を調べることになる。例えば、現時点で最長の詰将棋であるミクロコスモス（1525手詰）を解くためにはざっくり \(10^{1164}\) 局面を調べることになってしまう。このように、愚直な全探索では長手数の詰将棋を現実的な時間内で解くことはできないことが分かる。

しかし、ある局面が詰むことを示すだけならここまで膨大な探索は必要ない。例えば以下の局面を考える。

この局面の合法手は63金打、53金打など全部で9通りあるが、この局面が詰みであることを示すためには次の手順だけ探索できていればよい。

* 53金打
  * 41玉42金打　まで
  * 51玉52金打　まで
  * 61玉62金打　まで

この探索結果より、玉方がどのように逃げても3手で詰むことが示せている。このような、ある局面が詰み（または不詰）だと証明するための局面の探索木のことを「証明木（または反証木）」という。df-pnアルゴリズムではできるだけ詰み（不詰）に近そうな局面から調べることで証明木（反証木）を構成していく。そうすることで、詰め将棋のように「詰みに近い局面もだいたい詰み」という性質を満たす問題であれば効率的に探索を行うことができる²。

以下ではdf-pnアルゴリズムの具体的な探索方法を例を交えながら説明していく。

証明数と反証数

#

df-pnアルゴリズムでは、各局面でpn/dn (proof number/disproof number)というパラメータを持つ。pn/dnは探索が進むと変化する値で、それぞれ、詰みを示すために探索すべき局面数／不詰を示すために探索すべき局面数を表している。直感的には \(\mathrm{pn}\) が小さい局面ほどより詰みに近く、\(\mathrm{dn}\) が小さい局面ほど不詰に近いとイメージしてもよい。詰み局面では \((\mathrm{pn}, \mathrm{dn})=(0, \infty)\)、不詰の局面では \((\mathrm{pn}, \mathrm{dn})=(\infty, 0)\) となる³。

言い換えると、df-pnアルゴリズムの世界では、与えられた局面の \(\mathrm{pn}, \mathrm{dn}\) を更新しながら探索を進めて \((\mathrm{pn}, \mathrm{dn})=(0, \infty)\) （詰み）と \((\mathrm{pn}, \mathrm{dn})=(\infty, 0)\) （不詰）のいずれであるかを明らかにする行為に帰着されるのである⁴。

詰み／不詰がまだ確定していない局面では、\((\mathrm{pn}, \mathrm{dn})\) は次のように計算する。以下では、局面 \(n\) の証明数／反証数をそれぞれ \(\mathrm{pn}_{(n)}, \mathrm{dn}_{(n)}\) とする。また、局面 \(n\) から手 \(m\) で一手動かした後の局面を \(n_m\) と表記する。また、以下で現れる \(\min_m\) や \(\sum_m\) は局面 \(n\) のすべての合法手に対する min, sum を表すとする。

攻め方（OrNode）

#

\((\mathrm{pn}, \mathrm{dn})\) は次のように計算する。

• $$\mathrm{pn}_{(n)}=\min_{m} \ \mathrm{pn}_{(n_m)}$$
• $$\mathrm{dn}_{(n)} = \sum_{m} \ \mathrm{dn}_{(n_m)}$$

ただし、末端局面（子局面を展開していない局面）では \((\mathrm{pn}_{(n)}, \mathrm{dn}_{(n)}) = (1, 1)\) である。

受け方（AndNode）

#

\((\mathrm{pn}, \mathrm{dn})\) は次のように計算する。

• $$\mathrm{pn}_{(n)} = \sum_{m} \ \mathrm{pn}_{(n_m)}$$
• $$\mathrm{dn}_{(n)}=\min_{m} \ \mathrm{dn}_{(n_m)}$$

ただし、末端局面（子局面を展開していない局面）では \((\mathrm{pn}_{(n)}, \mathrm{dn}_{(n)}) = (1, 1)\) である。

探索方法

#

df-pnアルゴリズムでは探索開始局面の証明（ \((\mathrm{pn}, \mathrm{dn})=(0, \infty)\) ）または反証（ \((\mathrm{pn}, \mathrm{dn})=(\infty, 0)\) ）が示されるまでの間、OrNodeでは\(\mathrm{pn}\)が最小の局面を、AndNodeでは\(\mathrm{dn}\)が最小の局面を選んで探索を進める。

例を挙げて説明する。

探索途中で図のようになっている状況を考える。この瞬間にOrNodeではpn最小の子局面、AndNodeではdn最小の子局面というルール通りに節点をたどっていくと、最善応手列（PV）はA1->B2->C4->D1であることがわかる。よって次に展開すべき局面はD1となる。

D1を展開すると以下のようになったとする。

D1の子にE5, E6, E7という未証明局面があるため、D1のpnが3に変化した。これに伴い、A1, B2, C4のpnも更新される。更新後の探索木ではPVがA1->B1->C1に変化しているため、次に展開すべき局面はC1となる⁵。

このように、PVを順々に更新しながらその時点で最も証明（反証）しやすい局面を選択的に読むことがdf-pnアルゴリズムの特徴である。ぱっと見でめんどくさそうなD2は後回しにして、より詰みやすそうなD1やB1を先に探索することで高速に詰みを見つけられるイメージである。

特徴

#

よい点

#

df-pnアルゴリズムは一般的には以下のような利点が知られている。

• 闇雲な全探索と比べて圧倒的に高速に詰み・不詰を見つけられる
• ハッシュ（置換表）の恩恵を受けやすい
• 深さ優先探索だが最良優先探索に近い順序で探索できる
  • メモリ消費を抑えながら良さげ風なノードから順に探索できる

df-pnアルゴリズムの発表から20年以上が経過しているが、2021年現在のところ長手数の詰将棋を解く最も効率的なアルゴリズムとして認知されている。

よくない点（実装が難しい点）

#

一方で、df-pnアルゴリズムは以下のような難点が存在する。

• 得られた証明木（反証木）が最良（最短）手順とは限らない
• 探索順序が探索性能に大きく影響する
• 探索局面の合流に関連する処理が非自明
  • 局面のループ（GHI問題）⁶
  • 分岐の合流（証明数の二重カウント問題）⁷

特に、最後の探索局面の合流が厄介な問題として常につきまとう。細心の注意を払わないと詰／不詰の判定を誤ったり、無限ループに陥ったりする可能性がある。

この合流問題については、df-pnを詰将棋へ適用した元論文⁸に解決方法が記載されているが、現在のコンピュータ将棋開発者の中には懐疑的な意見を持つ人が一定数いる⁹。局面ループの対処方法については、上記論文記載の方法以外にもやねうらお氏提案の方法¹⁰やtanuki-詰めのように探索を延長して頑張る方法¹¹、DLShogiのようにdepth違いの局面を区別する方法¹²が知られている。また、分岐の合流に関しては証明数・反証数の計算方法を変えて過度に数字が大きくならないようにする方法¹³が知られている。

拡張

#

やねうら王の詰将棋ルーチンでは証明数／反証数の概念を拡張している。新規探索節点の \(\mathrm{pn}, \mathrm{dn}\) を \((1, 1)\) の固定値を使うのではなく、詰みやすそうな局面ではpnが小さく、詰みにくそうな局面ではdnが小さくなるようにヒューリスティックに値を増減させている。このようにすることで、depthの違う局面の比較を行うことができ、pnとdnを方策と見立てた最良優先探索に落とすことができる。

まとめ

#

長手数の詰将棋を短時間で解くためのdf-pnアルゴリズムの概要について解説した。多くのケースで探索局面数を大幅に減らすことができるが、理論と実装の間にはそこそこギャップがあることが感じ取れていただければ幸いである。

次回は詰将棋探索特有のテクニックである証明駒／反証駒について解説する。