開発メモ : 新規節点で固定深さの探索を併用するdf-pnアルゴリズム

私が昨日の記事に書いた「短い詰みに対してもほとんど遅くならない詰み探索ルーチン」というのは、Bonanzaの3手詰みを5手詰みに拡張し、中合い探索の省略技法(→ http://d.hatena.ne.jp/LS3600/20100101)を用いて、これをdf-pnの末端ノードに適用し、このとき探索したノード数をもとに証明数と反証数を設定してやるというアイデアでした。

今日、df-pn関係の論文を一通り読もうと思って調べていると↓これを見つけました。

新規節点で固定深さの探索を併用するdf-pnアルゴリズム
http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw05.pdf

節点あたりに必要な時間に関しては深さ優先探索の方が効率の良い実装が可能
である． そこで， 末端で固定深さの探索を行い， 詰む場合はその情報を， 詰まない場合は固定深さの
探索が展開した探索木の証明数と反証数を計算して， df-pn に提供することを行った．

・末端ノードで固定深さの詰め将棋ルーチンを呼び出す
・詰め将棋ルーチンで探索したノード数をdf-pnに提供する

の2点のアイデアが思いっきり車輪の再発明だったようです。軽くショックでした。この論文を読むとこの手法自体には効果があるようで、アイデアの方向性が正しかったことはわかってそれはそれで良かったのですが。