Rustでつくる詰将棋Solver その後

memo.sugyan.com

の続き。1ヶ月ほど経ってちょこちょこ更新して進化した。

残課題が幾つかあったが、そのうち幾つかは解決した。

探索無限ループ

f:id:sugyan:20211111001858p:plain

上図のような問題で ▲4四飛成 △3二玉 ▲4一竜 △3三玉 ▲4四竜 △3二玉 ... を無限に探索してしまっていた問題。

結局これはプログラム中のhashに格納する値を間違えていたことに起因していたようで、そこを直すことで解決した。また合わせて最適解の選択ロジックを修正していくことでその他の問題で起きていた不具合も解消することが出来た。

Issue: 連続王手の繰り返し · Issue #2 · sugyan/tsumeshogi-solver · GitHub

後手から始まる問題、kifファイル入力

やねうら王公式からクリスマスプレゼントに詰将棋500万問を謹呈 | やねうら王公式サイトの問題を試してみようと思ったら後手番から先手玉を詰ませる問題が半数含まれていて対応が必要だった。これは主に合法手生成の部分を修正することで解決した。

1行ごとにsfen文字列を読んで解を出力していく、といったことも出来るようにした。

ようやく100万問くらい解けそうな感じになってきた pic.twitter.com/9i9SDt73VR
— すぎゃーん💯 (@sugyan) November 26, 2021

500万問すべては試せていないが、各ファイル先頭200問ずつの計1000問くらいは最短ではないが詰みを見つけることは出来た。まだ解けないものもあるようなので一つ一つ調査して原因を潰していきたいところ…

また、kif形式のファイルも読み込んでparseし初期盤面を問題として解かせることが出来るように簡単なparserを書いた。あまりに自由な形式なので完全には対応できないが…

日本将棋連盟のまいにち詰将棋で使われているkifファイルくらいならだいたい正しくparseできるようにはなっていると思う。

f:id:sugyan:20211210152939p:plain

tsumeshogi-solver/kif_converter.rs at 0.2.0 · sugyan/tsumeshogi-solver · GitHub

証明数二重カウント問題

前述の500万問のものを試していて見つかったもの。例えば以下のような問題

f:id:sugyan:20211210001433p:plain

解としては例えば △7九角成 ▲同玉 △5七角 ▲6九玉 △6八銀 ▲5八玉 △6九銀打 の7手詰になる。

これを自作solverでdfpn探索していると △7九角成 ▲5九玉 △6八角 の手順をまず探索していって、これに対しては ▲4八玉 と ▲5八玉 があり、どちらの場合も △5七角成 ▲5九玉 で同じ局面になる。次は △6八馬引 で詰むのだけど、それを探索する前に △6八馬上 ▲4八玉 △5七馬 という筋を探索しようとする。その優先度を決める際に4手目からの ▲4八玉 △5七角成 ▲5九玉 の経路と ▲5八玉 △5七角成 ▲5九玉 の経路の両方から証明数を足し合わせることになり、両者のノードの証明数が交互に過剰に加算されて更新されていってしまい、いつまでも探索が進まないという現象が起きていた。

これに対する解決策として、元の論文では

我々は，各局面に親局面へのポインタを持たせ，場合によっては親局面をたどることで DAG を検出し，証明数の二重カウントを回避した.

-- df-pnアルゴリズムの詰将棋を解くプログラムへの応用

といったad-hocな回避方法が本文中に書かれていた。が、これは該当する実装が末尾の疑似コードには記載されておらず疑似コードを極力忠実に移植した今回の自作solverではそういったことをしていなかった。

1手詰の検出

書かれている通りに親局面へのポインタを持たせるように変更してみるか、、とも思ったが、そもそも上記の問題はまず6手目 ▲5九玉 になった時点で △6八馬 の1手詰を検出できていればその先のループにハマることないよね？と思い各ORノード(攻方手番)で1手詰めの判定を挟んでみることにした。

     // ノード n の展開
     fn mid(&mut self, hash: P::T, phi: U, delta: U, node: Node) -> (U, U) {

         ...

         // 2. 合法手の生成
         let children = self.generate_legal_moves(node);
+        // 攻方の場合のみ 1手詰を探索する
+        if node == Node::Or {
+            let mut mate = false;
+            for &(m, h) in &children {
+                self.make_move(m).expect("failed to make move");
+                let len = self.generate_legal_moves(Node::And).len();
+                self.unmake_move().expect("failed to unmake move");
+                if len == 0 {
+                    self.put_in_hash(h, (INF, 0));
+                    mate = true;
+                } else {
+                    self.put_in_hash(h, (1, len as U));
+                }
+            }
+            if mate {
+                self.put_in_hash(hash, (0, INF));
+                return (0, INF);
+            }
+        }
         if children.is_empty() {
             ...
         }
         // 3. ハッシュによるサイクル回避
         self.put_in_hash(hash, (delta, phi));
         // 4. 多重反復深化
         loop {
            ...
         }
    }

元の実装では、各局面で合法手を生成した後にループしながら証明数・反証数の更新していくので合法手の生成時点ではそれらの子ノードが詰んでいるか否かはループ内で選択されて探索されない限り判明しない。しかしそうすると前述のように「既に詰んでいる子ノードが見えているのに他の子ノードを無駄に探索してしまう」ということが起こる。

ので、攻方手番の場合の子ノード展開時のみ、それらの子ノードが既に詰んでいるかどうか(子ノードからさらに次の子ノードが生成できるかどうか。できないということは詰んでいる、ということになる)の判定を入れてみた。子ノードから生成される合法手数はそのまま証明数になるので、たとえ詰みが見つからなくてもその後のループでの子ノード選択時にも優先して詰みやすいノードを選択できるようになる効果もある、はず。

ただ勿論これはORノードを探索するたびに子ノードのさらに子ノードまで生成を試みることになるので非効率にもなり得る。そのぶん早く詰みを見つけて探索を打ち切ることができる可能性もあるし、単純に余計な合法手生成とハッシュテーブルの記憶領域を消費するだけになる可能性もある。どうなるかは「問題による」。ただ少なくとも前述のような問題はこれによって解けるようにはなるのでアリかな、と思っているがどうなんだろう…。逆にこれによって解けなくなる問題もあるっぽいのでちゃんとDAG検出するとか他の方法をとるべきかもしれない。。

Issue: Cannot solve · Issue #4 · sugyan/tsumeshogi-solver · GitHub

初手に戻るループ

前述のものに近いが、ちょっと違うパターン。下図のような問題が解けなかった。

f:id:sugyan:20211210144912p:plain

正解は ▲1八歩 △同玉 ▲1九歩 △同玉 ▲3九飛 △1八玉 ▲1九香 の7手詰で、5手目の ▲3九飛 に対して持駒の歩も香も合駒として打てない(前に進めない場所には打てない！)ので玉は逃げるしかない、というのが面白い。

それはともかく、探索していると ▲1九香 △1八香 ▲1六飛 △同玉 ▲1八香 △1七飛 ▲同香 △同玉 という手順でまったく同じ局面に戻ってくる。このときこの局面の証明数・反証数がともに ∞-1 という値でハッシュテーブルに保存されているので、ループ内での証明数の最小値と反証数の総和がともに ∞-1 になる。これによっておかしな結果になってしまっているようだったので、反証数の和が ∞-1 以上だった場合は証明数の和を強制的に 0 にすることで解決した。

Issue: Cannot solve · Issue #7 · sugyan/tsumeshogi-solver · GitHub

打ち歩詰めの誤判定

下図のような問題が不詰として判定されてしまっていた。

f:id:sugyan:20211210150309p:plain

正解は ▲2二歩 △1一玉 ▲2三桂 の3手詰なのだけど、この初手 ▲2二歩 が合法手として生成されていなかった。原因を探ってみると、使用していた shogi-rs ライブラリの中で打ち歩詰めの判定に問題があってこの ▲2二歩 に対して玉が1一に逃げられないと判断してしまって打ち歩詰めのためこの歩は打てない、という結果を返してしまっていることが分かった。

修正のコードを提案して取り込んでもらって無事に解決した。

Pull Request: Fix Uchifuzume check by sugyan · Pull Request #41 · nozaq/shogi-rs · GitHub