証明駒の弊害？

詰ルーチンが返す詰め手順を検証したところ、作意より短手数を返す場合がときどきあって、ようやく原因がわかりました。
図は大内延介「実戦詰将棋100題」第98番。


作意は▲14香△21玉…の17手詰めなのに、返ってくる手順は▲14香△13角▲同香…の11手詰め。
ログを追うと▲14香△13角▲同香の局面で持ち駒が角と香になる。


このとき△21玉と逃げた先の局面のハッシュの証明駒にこの局面は香を持っていれば詰み、かつ手順が長いと登録されていて、そちらを選んでしまう。しかし、進んでみると角を持っているので角を使って短手数で詰んでしまう。といったことで、証明駒の関係でおかしくなっているようです。構造上、対策は困難かつ実戦上特に問題ではなさそうなので静観予定(ANDノードなので、詰め手順でも詰んでいることは確認していた)。
この検証をしていく中で証明駒、反証駒の扱いに非効率的なところがあったので、改善できるかも？と期待ｗ

※2011年11月26日公開版「なのは詰め」ではこの詰将棋は解けませんでした。。。orz

 

3手詰めが詰まない？！

謎電さんの双玉詰試験図の右下の問題図を解かせると「不詰」と返ってきて、激指10にやらせても「詰みません」と出るし、頭を抱えてしまいました。
解答手順は引用元の詰将棋おもちゃ箱－加藤徹 全作品No.11aを見て、▲42歩生から3手というのがわかったんですが、今度は自分がその手順で何で詰みなのかがさっぱりわからず、かなり悩んでしまいました。



で、詰問題は玉方持駒残り全部という思い込みがあってそうしていましたが、よくよく問題図を見ると玉方の持駒は歩1枚だけでした。
というわけで、入力した問題図が間違っていた(持駒残り全部としていた)のを歩1枚にしたところ、ちゃんと▲42歩不成から詰ますことができて一安心（無駄合いはありますが）。
しかしながら、問題図を修正しても激指10は「詰みません」と解答していました…。

USI対応してみた

詰ルーチンで行き詰ったので、詰ルーチンだけUSI対応してみました。
面倒かと思いきや、Lesserkai を参考にしたら意外と簡単に出来ました。
なのはは GUI が特徴なので、エンジンの USI 対応は積極的にしないつもりでしたが、将棋所でリーグ戦など出来るようなので対応するメリットはありますね。

ダウンロード(NanohaTsumeUSI111126.zip;213KB)

※ドキュメントに書き忘れましたが、思考時間の制限は内部でノード数の制限にしています。このため、実時間と相関はありますが、指定した時間で終わりません。
また、無制限にしても適当なところで終了します。

最小距離法の限界

なのはの詰ルーチンはdf-pnベースで、基本的に岸本さんの「IS 将棋の詰将棋解答プログラムについて」http://www.is.titech.ac.jp/~kishi/pdf_file/csa.pdf の最小距離法を使っています。
この中の「4. 最小距離法の限界」に書かれている「将棋依存の条件を書き下すことで解決している」というのがなんなのか未だわかりません…。

ただ、問題を解かせている中で異様に時間がかかるものがあり、よくよく確認してみるとこの事例に当てはまっていました。

それは大内延介「実戦詰将棋100題」第95番(17手詰)という問題で、現状だと69.3秒かかっていました。

正解手順は▲11角打▽12玉(22)▲22金打▽13玉(12)▲12金(22)<略>と進むのですが、まず▲11角打▽13玉(22)▲12金打と読んでしまうと、その局面はルートからの最小距離md=3でハッシュに登録します。
その後、正解手順の▲11角打▽12玉(22)▲22金打▽13玉(12)まで来ると次の手の▲12金打とした局面がmd=3で登録されているため異常な子節点の判断となり、その局面のほかの手が反証されない限り展開されなくなってしまい、そこで長時間費やしていました。

適当な対策を入れたところこの問題自体は 9ms で解けるようになり、「これで解決！」と思いきや、他の問題集で解けなくなっている問題が出てきたり、逆にノード数がやたらと増加してしまう問題があったりで、平均的にもパフォーマンスが落ちていました。orz

あちらを立てればこちらが立たず、という感じでなかなかうまくいきません。

しかも、これって2008年11月20日のエントリーでもわからないって言ってるし、進歩ないなー。orz

全力全開で「寿」を解く！

2010年分からGPWの論文がオンラインで読めるようになっているんですね！
ぜんぜん知りませんでした。あぁ、情弱…。

で、GPW2010の長井さんの「長手数の詰将棋を解くプログラムを改善するヒューリスティックス」を見ると、ヒューリスティックスを入れる前でCore i7-860(2.8GHz)で将棋図巧(不詰の第73番を除く全作品)を150秒、ミクロコスモスを124秒で解けるということだそうで…。

PCのスペックは劣るとはいえ、何10分かけても将棋図巧の解けない作品がいくつもあるのは、なんなんだろう？
努力が足りない？？解くのはコンピュータなんだからちゃんと作れば解けるはず！

この際、実戦で役に立たなかろうが、目標が20年近く時代遅れだろうが、関係ない。一念発起して全力全開で「寿」を解くと決めました！(でも、ここで「ミクロコスモス」を解くといわないｗ)

2000年6月号の近代将棋の記事の中でIS将棋は Athlon 800MHz で「寿は2分で解けます」とあるので、目標タイムは2分でｗ