df-pnの完璧な実装が公開されていた話

前回オープンソースで公開されてるミクロコスモスの解けるdf-pnの実装がないとか書いちゃったけど、あった。ごめんなさい。

GPS将棋についてた。しかも完璧な実装。（東大の金子先生がほぼ一人で書いたらしい。たぶんdf-pnのバリエーションも実装されてて、全部入れると詰将棋だけで1万行くらいある……）

多分df-pn+というdf-pnを更に効率化したアルゴリズム（末端ノードで固定深さの探索を行って、証明数・反証数の推定値を得る）をベースに、詰将棋ソルバ定番の優越関係・証明駒・GHI検出の完璧なやつ（kishimoto-mueller）・ループ検出・Small TreeGCを全部実装している。まあソースコードは関数名をちらっと見たくらいで、読んでないんで間違ってたらごめんなさい。

ミクロコスモスが5000万ノードの探索で解けるらしい……（脊尾詰のアルゴリズムだと5億ノードくらい探索する？）

詳しくはCiNii 論文 -  新規節点で固定深さの探索を行うdf-pnの拡張←これを読んでね。

ミクロコスモスを解きたい人向け

優越関係・証明駒はやらないと探索ノードが爆発するので必須。優越関係を生かすため、玉方の合駒の応手は玉に近い順にソートして試すこと。

GHI対策はちゃんとやらないと図巧一番すら解けない。長井論文のGHI対策は不備が指摘されているので注意。（詳しくはA solution to the GHI problem for depth-first proof-number search - ScienceDirect←この論文読んでね）最小距離法もダメ。

ミクロコスモスだけを解くぶんにはループ検出・合流検出は必須ではない。ミクロコスモスだと探索時間がせいぜい２倍くらいになるだけっぽい。

固定深さの探索はミクロコスモスを解くだけなら要らない。

GCはほぼ必須。実装によるが5億ノードで20GBくらいはハッシュを使うので、64GBくらいメモリがあれば要らないかも。GCの実装は超簡単なのでやって損はない。

なのはは何でミクロコスモス解けないんだろう？多分GHI対策を最小距離法でやってるせいとかだと思うが。