やねうら王詰将棋エンジンを公開しました

やねうら王のエンジンには、tanuki-詰将棋エンジンがその仲間にいましたが、今回、やねうら王詰将棋エンジンを追加しました。

やねうら王詰将棋エンジンの追加commit : https://github.com/yaneurao/YaneuraOu/commit/9a8f683377070d10ba2e2b07f36f9bcfbb5e2e23

従来の詰将棋エンジンの問題点

・置換表を用いる実装の場合、置換表の衝突により、詰みと不詰を間違うことがあった。
・千日手絡みで詰みを間違うことがあった。

tanuki-詰将棋ルーチンや、これの問題については、Qhapaqさんが研究されているので、以下の記事を読んでいただくとして、ここでは割愛します。

今の詰将棋ルーチンが図巧の1番を解けない話
http://qhapaq.hatenablog.com/entry/2020/07/22/093903

やねうら王搭載の詰将棋ルーチンの改造中継（ver 2）
http://qhapaq.hatenablog.com/entry/2020/07/25/171014

やねうら王搭載の詰将棋ルーチンの千日手対応
http://qhapaq.hatenablog.com/entry/2020/07/26/190856

従来の詰将棋ルーチン自体の問題点

詰将棋ルーチン内で千日手を発見した場合、それは攻め方(攻める側)の連続王手の千日手に他ならないので、反則であり、この指し手は指せません。すなわち、この指し手は、負け扱いにします。

また、同じく、劣等局面の処理があります。これは、盤上の駒は同じ配置で、自分の手駒が相手の手駒に移動している局面を意味します。攻め方がある指し手Mで劣等局面に突入した場合、Mは意味のない指し手だと考えられます。もしこの局面で相手の玉を詰ませられるのであれば、その損した駒を使わずとも詰ませられるということであり、劣等局面に突入せずとも詰みます。つまり、Mは無筋で、Mでは詰まないとして良いのです。

従来の詰将棋ルーチンは、このように、千日手と劣等局面を処理していました。

ところが、詰将棋を解くために与えられた局面以前の指し手が存在する場合はどうでしょうか？

例えば、相手の王様に歩を叩いた(歩を王手になるように打った)とします。相手の王様は逃げました。ここから詰将棋ルーチンが呼び出されたとします。この最初の歩を叩いた手は実は悪い手だった場合、これをごめんなさいと、この歩を成り捨てて、同玉のあと詰むかもしれません。ところが、この歩を成り捨てた局面が劣等局面になってしまうのです。

つまり、劣等局面に突入したからと言って直ちに詰まないとは言えないのです。

この現象は、詰探索開始前からの循環による千日手・劣等局面への突入によって引き起こされます。

私(やねうらお)の結論

この問題についてかねてより取り組んでいたのですが、これは通常の詰将棋ルーチンが扱う問題より、一段階難しい部類の問題であるという結論に達しました。そして、これのため、局面の合流が非常に処理しにくくなります。そこまでの経路によっては劣等局面になったり、ならなかったりするわけですから。そして、劣等局面になった時に、即座に無筋だとは言えなくなるので、合流を扱うとしたら、千日手が一切絡まない部分木であることが証明されている接点(局面)にしか合流を許すべきではないのです。

しかし、これは実装がとても難しくなりますし、合流を取り扱うための計算コストが大きいので、よほど長編で合流を何度もするような詰将棋以外では問題とならないだろうということで、今回、合流を一切処理しないことにしました。

また、置換表を使うのもやめて、調べた局面はすべてメモリに残しておくことにしました。そうすると非常に美しく短いコードでかつ高速な詰将棋ルーチンが書けました。ソースコードのレビューをして、アイデアを色々くださったtanuki-の開発者の野田さんに、この場をお借りして感謝の意を表します。

やねうら王詰将棋ルーチンの特徴

・従来の詰将棋エンジン(例えばtanuki-詰将棋エンジン)の2～3倍のnps(探索速度)。
・合流を処理しないので詰み・不詰を間違うことは(原理上は)存在しない。
・詰将棋ルーチンを呼び出された局面以前の手順まで考慮した実戦の検討に耐えうる詰将棋ルーチン。
・メモリと時間さえ無限にあればどんな問題も原理的には解けることが保証されている。
・エンジン側からは、詰み・不詰(不詰を証明した)、メモリを使い切った、タイムアップの4つの状態が返ってくる。
・解けた時に発見したなかで攻め方はなるべく短く、受け方はなるべく長くなるような詰み手順を返す(攻め方の最短性、受け方の最長性は保証されない)
・扱えるノード(局面)数が32bitで表現できる数(42億)までのものと64bitで表現できる数(実質的に無限)までの実装の二通りを用意。
・歩の不成が絡む問題もきちんと解ける。
・長編で合流が多い問題はメモリの制約や探索ノード数が膨大になることなどから現実的な時間では解けないと思われる。(試してない)

やねうら王の詰探索アルゴリズムについて

df-pnアルゴリズム、実は私、いまだに千日手絡みのところがよく理解できてなくて、「こんなことせんでええやろ…」とか思いながら、dn(disproof number:不詰の証明数),pn(proof number:詰みの証明数)を用いて、最良優先探索かつ、現在のノードから近くて有望な新規接点を探してそこを展開するアルゴリズムを実装しました。

たぶん、これは、df-pnとは呼べない(呼ばない)何か新しいアルゴリズムなのだと思うのですが、これが何というアルゴリズムなのかは、私はその道の研究者ではないので知りません。もしかすると新規性があるのかも知れませんが、論文書いてもおなかふくれないので論文は書きません。

今後の改良

メモリを使い切った時にGC(ガーベジコレクター)でお掃除をする仕組みを導入するかも知れません。

あと、詰探索の並列化がしやすい形で書いてありますので気が向いたら並列化対応版も作るかも知れません。

まとめ

かねてより、不詰を100%証明できる(間違って不詰と返さない)詰将棋ルーチンが検討のために欲しかったので、望み通りのものが完成して嬉しいです。

この詰将棋ルーチンは、ふかうら王にも搭載(内蔵？)される予定です。

Deep Learningの将棋ソフトと言うと、機械学習の難しい理論を駆使して開発しているのだろうと皆さん想像されているかも知れませんが、まずは詰将棋です！詰将棋を強くするのが最強のDeep Learningの将棋ソフトにいま一番必要とされていることなのです。(と勝手に思っている)

先日、このサイトで詰将棋問題を500万問公開しましたが、将棋ソフト開発者の皆さんは、今回のやねうら王の詰将棋ルーチンを参考に、この500万問が1ミリ秒でも速く解ける詰将棋ルーチンを作ってみてくださいね。