詰将棋アルゴリズムdf-pnのすべて | やねうら王 公式サイト
将棋AIで用いている詰将棋ルーチンにdf-pnというアルゴリズムがある。 これは、proof number(証明数)、disproof number(非証明数)を用いて効率的に探索を行い、その局面が詰むか、詰まないかを判定できるとても強力なアルゴリズムである。 将棋ファンなら『脊尾詰』と言う「ミクロコスモス」(1525手詰)を解く詰将棋専用ソフトについて一度ぐらいは聞いたことぐらいあるだろう。これは、脊尾さんが大学時代に作成されたプログラムである。そこに使われていたのが脊尾さんが考案されたdf-pnというアルゴリズムである。 df-pnに関しては、脊尾さん自身の論文(1998年)があるものの、要点しか書かれておらず、いまのようにGitHubにソースコードがあるわけでもなく、その詳細については長らく謎に包まれたままであった。(この脊尾さんの論文では、証明数のみを用いており、非証明数は陽には出
df-pnの完璧な実装が公開されていた話 - コンピュータ将棋動画勢！
前回オープンソースで公開されてるミクロコスモスの解けるdf-pnの実装がないとか書いちゃったけど、あった。ごめんなさい。 GPS将棋についてた。しかも完璧な実装。（東大の金子先生がほぼ一人で書いたらしい。たぶんdf-pnのバリエーションも実装されてて、全部入れると詰将棋だけで1万行くらいある……） 多分df-pn+というdf-pnを更に効率化したアルゴリズム（末端ノードで固定深さの探索を行って、証明数・反証数の推定値を得る）をベースに、詰将棋ソルバ定番の優越関係・証明駒・GHI検出の完璧なやつ（kishimoto-mueller）・ループ検出・Small TreeGCを全部実装している。まあソースコードは関数名をちらっと見たくらいで、読んでないんで間違ってたらごめんなさい。 ミクロコスモスが5000万ノードの探索で解けるらしい……（脊尾詰のアルゴリズムだと5億ノードくらい探索する？） 詳し
将棋プログラムK1.5の無駄合判定アルゴリズムについて | やねうら王 公式サイト
前回記事で柿木将棋の柿木さんが考案された無駄合判定アルゴリズムとして以下の本を紹介したのですが、この本が絶版になっていて悲鳴のような声を受信したのでフォローしておきます。 コンピュータ将棋―あなたも挑戦してみませんか[サイエンス社 , 1990年 本アルゴリズムは本書籍の第4章で書かれており、この章は柿木さんが執筆を担当しておられます。 本章ではK1.5という柿木さんの作成された将棋プログラムの解説として、無駄合の処理について書かれています。その部分を以下に引用します。 この無駄合判定アルゴリズム自体は、柿木の無駄合判定アルゴリズムとして複数の論文で引用されているのですが、この一次ソースである本書が絶版になっているため、ニュアンスが変わって伝わっていたりして学術的な研究の妨げになっているように思いましたので、上に引用させていただきました。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
