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という柿木さんの作成された将棋プログラムの解説として、無駄合の処理について書かれています。その部分を以下に引用します。 この無駄合判定アルゴリズム自体は、柿木の無駄合判定アルゴリズムとして複数の論文で引用されているのですが、この一次ソースである本書が絶版になっているため、ニュアンスが変わって伝わっていたりして学術的な研究の妨げになっているように思いましたので、上に引用させていただきました。
高速な詰将棋ソルバー『KomoringHeights』v0.4.0を公開した
この表より、探索速度が大幅に向上していることがわかる。v0.2.1と比較して、v0.4.0での解答速度は1.3倍~8.9倍になっている。 このように、v0.4.0では探索性能が大幅に改善されている。以下ではその中から主要な3項目について説明する。 df-pn+ #探索速度の根本的な改善のために、df-pn+アルゴリズム1を導入した。df-pn+アルゴリズムは、初めて訪れた局面の(pn, dn)を一様に(1, 1)で初期化するのではなく、局面の詰みやすさに応じて値を増減させるアルゴリズムである。展開前の局面に対して値に差をつけることにより、より詰みに近い局面を優先して子局面の展開を行うことができる。素朴な発想のヒューリスティックではあるが、局面の詰みやすさをうまく評価できれば探索性能が大きく向上することが知られている。KomoringHeightsのdf-pn+評価関数の設計は、GPS将棋2
Rustでつくる詰将棋Solver - すぎゃーんメモ
ついカッとなって先週からRustで詰将棋ソルバを書き始めてしまい、ようやくdf-pnで何らかの解答を出せるようになったところ。ここからもうちょっと調整していくぞ、、 pic.twitter.com/XM9iPJqocv— すぎゃーん💯 (@sugyan) November 2, 2021 というわけで突然Rustで詰将棋ソルバを作りたくなり、作った。 github.com 現時点ではまだ完成度は低くて6割ほどかな…。 とはいえそこらの素直な詰将棋問題なら普通に解けると思う。 冒頭の画像は看寿賞作品の3手詰「新たなる殺意」を2秒弱で解いたもの。 先行事例 将棋プログラムの多くはC++で書かれていて 最近はRustも増えてきているのかな？ しかし「詰将棋を解く」ことに特化しているものはあまり多くはなさそうだった。 なかでもRustで書かれているものはna2hiroさんによるものくらいしか無さ
詰将棋に対するdf-pnアルゴリズムの解説 | コウモリのちょーおんぱ
長手数の詰将棋の探索に用いられるdf-pnアルゴリズムについて、その概要と実用上の課題を解説する。 概要 #詰め将棋において、各局面の平均着手可能数は5.8手程度と言われている1。単純にこれを全探索することを考えると、\(n\) 手詰を解くためには \(5.8^n\) 局面を調べることになる。例えば、現時点で最長の詰将棋であるミクロコスモス（1525手詰）を解くためにはざっくり \(10^{1164}\) 局面を調べることになってしまう。このように、愚直な全探索では長手数の詰将棋を現実的な時間内で解くことはできないことが分かる。 しかし、ある局面が詰むことを示すだけならここまで膨大な探索は必要ない。例えば以下の局面を考える。 この局面の合法手は63金打、53金打など全部で9通りあるが、この局面が詰みであることを示すためには次の手順だけ探索できていればよい。 この探索結果より、玉方がどのよう
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
