詰将棋アルゴリズム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という柿木さんの作成された将棋プログラムの解説として、無駄合の処理について書かれています。その部分を以下に引用します。 この無駄合判定アルゴリズム自体は、柿木の無駄合判定アルゴリズムとして複数の論文で引用されているのですが、この一次ソースである本書が絶版になっているため、ニュアンスが変わって伝わっていたりして学術的な研究の妨げになっているように思いましたので、上に引用させていただきました。
詰将棋の無駄合の定義について(長文) | やねうら王 公式サイト
詰将棋ルーチンを書いていると詰将棋の無駄合のルールがとてもややこしいことに気づきます。本当にややこしいので、無駄合を考慮する詰将棋ルーチンはプログラマーなら誰も書きたがらないことが多く、一部の開発者以外この問題と正面から向き合おうともしていません。 それでたまたまツイッターで見かけた3手詰めの次の問題です。 無駄合ありなら手順としては、27銀、36合、同香、35合、同香、25玉、36馬までの7手詰めです。(作意はおそらく27銀、25玉、43馬まで。) さて、この時の36合、35合を本当に無駄合と言えるのかについてです。 詰将棋の初心者に向けた説明 王手に対して「合駒」ができるということは遠方駒(飛車、角、香のこと)による王様から2升以上離れた升からの王手です。 また、両王手の場合は「合駒」はできません。ゆえに無駄合は両王手の時には出てきません。 いま王手する遠方駒を飛車とします。飛車で王手
難解作品が解ける詰め将棋エンジン KomoringHeights v0.5.0 を公開した
合流検出の実装はかなり複雑だ。詰将棋探索では探索中の局面を置換表（メモリ）に保存する必要があるのだが、合流検出のためにはこれを増やす必要がある。具体的には、v0.4.1 では 1 局面あたりの置換表エントリサイズは 32 byte であったのに対し、v0.5.0 では親局面のポインタ（12 byte）と合流フラグ（8 byte）を追加で持たせているため、サイズが 56 byte（1.5倍）に膨れ上がっている2。 さらに、合流検出のアルゴリズム自体もそれほど単純ではない。合流の可能性がある局面を見つけるたびに、再帰的に局面をさかのぼって合流検出のフラグを立てに行く必要がある。1回の計算量は大したことがないが、長時間探索する場合は無視できない計算量になりうる。 これらの理由から、合流検出を実装したことでNPS（単位時間あたりの探索局面数）がかなり低下する……はずだった。しかし、置換表のデータ構
詰将棋探索における簡易的な二重カウント対策
#証明数／反証数の二重カウント問題を回避するためには、局面グラフの合流を検出ができなければならない。 合流を検出するためには、以下の追加情報のいずれかを置換表に保存する必要がある。 直前手親局面の置換表エントリへのポインタこれらの情報があれば、次回以降に同じ局面に到達したときに局面の合流を検出することができる。なお、直前手だけでは取った駒がわからないので、厳密な合流検出のためには親局面へのポインタも必ず必要になる。 局面の合流検出 長井歩, and 今井浩. “df-pn アルゴリズムの詰将棋を解くプログラムへの応用.” 情報処理学会論文誌 43.6 (2002): 1769-1777. Fig. 3 探索中に局面の合流を見つけたとき、探索経路および置換表に書かれた親局面をたどり、それらの手順が分岐した局面を特定する。このようにして、二重カウント問題が発生しそうな分岐局面を特定すること
コンピュータ向け超難解詰将棋作品集 - 詰将棋メモ
［２０２２年６月９日最終更新］ 脊尾詰でミクロコスモスが解け、長井詰でほとんどの長編が解けてしまってから、詰将棋プログラムの研究は新たな展開がほとんどない。そこで、コンピュータに挑戦！ということで、コンピュータ向けのベンチマークとして超難解詰将棋作品集を作ってみようと思いついた。１０作ぐらい揃えたいので超難解作をご存知の方はコメントやトラックバック、またはおもちゃ箱掲示板で教えてください。また、これらの作品がコンピュータで解けた場合は、プログラム、環境（ＣＰＵやメモリ設定）、時間をレポートしていただければ、随時掲載したいと思います。 作品集はこちら（現在１３作品） ===> コンピュータ向け超難解詰将棋作品集 関連情報（詰将棋メモ）： コンピュータで詰将棋 コンピュータ詰将棋の課題 コンピュータによる詰将棋創作 関連情報（おもちゃ箱）： 将棋ソフト・コンピュータ将棋 超長編作品のプロ
やねうら王公式からクリスマスプレゼントに詰将棋500万問を謹呈 | やねうら王 公式サイト
開発者の皆さん。詰将棋ルーチンをせっかく作っても、そのベンチマークの方法に悩んでいませんか？詰将棋問題集を手打ち入力なんていまどきナンセンスです。 やねうら王公式が、詰将棋問題にお困りの開発者さんたちに、ドドーンっと500万問プレゼントしちゃいます！ アンケートの結果は？ クリスマスプレゼントにやねうら王公式から欲しいもののアンケートを取ったところ、半数ぐらいの人から、「そんなに解けねぇよ！ヽ(`Д´)ﾉｳﾜｧｧﾝ!!」でしたが、逆に言えば残り半数の人は欲しいということですよね？ 3手詰め、5手詰め、7手詰めに加えて、さらに、9手詰め、11手詰めがそれぞれ100万問ずつSFEN形式で収録されています。 https://drive.google.com/file/d/1nJbFFaQeOx3gFafiVIR_oDIcG8iCOHf4/view?usp=sharing ここに収録されている5手
高速な詰将棋アルゴリズムを完全に理解したい（ver2） - コンピュータ将棋 Qhapaq
Qhapaq アドベント将棋記事7日目 ※：連載記事ですが前回までの記事をmergeした記事になりますので過去作は読まなくても大丈夫です。 今の詰将棋アルゴリズムで最強と言われているハッシュテーブル+df-pn探索による詰将棋アルゴリズムの完全理解を目指していきます。今回はproof numberやハッシュテーブルなどの探索で用いられる単語の意味を説明します。 参考文献： memo.sugyan.com 【proof numberとは】 proof numberとは平たく言えば詰将棋専用の盤面評価値みたいなものです。通常の盤面評価値と違って、詰み証明のための評価値(pn)と不詰証明のための評価値(dn)があります。pn、dnは「この局面の詰み/不詰を証明する為に調べなければならない局面の数」であり、値が小さいほど詰み/不詰に近いという扱いになります。そして、詰み /不詰が証明された局面につ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
