df-pnアルゴリズムを用いた詰将棋Solverによる最善解・余詰の導出 - すぎゃーんメモ

以前書いた、詰将棋問題生成の続き。 memo.sugyan.com 逆算による詰将棋の問題生成の方法自体は悪くないとして (バグによって有り得ない局面が出来上がったりしてしまったりもしたけど)、正しく詰将棋問題として成立するものが出来上がっているかどうかを検証するためのSolverが必要不可欠であり、これのパフォーマンスが生成のパフォーマンスにも影響してくる、というようなことを書いた。 実際、前回の記事のときに実装したSolverでは 総当たり的に探索するのは3〜5手が限界 詰将棋のルールに則る動きに限定しても、有り得る局面は指数関数的に増加する 合駒が絡む問題に対して正しく解が導けないことがある 先の展開まで読まないと無駄な合駒かどうかの判定ができない といった問題があった。 df-pnアルゴリズムによる探索 2002年の論文「df-pn アルゴリズムの詰将棋を解くプログラムへの応用」が

[wrss]

dfpnでGHI問題(graph history interaction problem)どう対処してるのか、上手い方法があったら知りたいなー。トランスポジションテーブルを利用する頻度減らしたり合流を考えなければ回避できるけど、高速化の点からは不利だし…

[Nyoho]

これは面白そう

[tadashi_shimizu]

ニッチだ。これ、完成したら、自動で詰め将棋を出題するサービスとかができあがってしまう。

[tkmc]

[アルゴリズム]

[shiyakeita]

めっちゃガチやん

[razokulover]

もう研究だ…。凄すぎる