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文字列を読んで 解を出力していく、といったことも出来るようにした。

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

残課題

とりあえずここまでの変更・修正でバージョン 0.2 としてTagを切っておいた。

GitHub - sugyan/tsumeshogi-solver at 0.2.0

試しに日本将棋連盟まいにち詰将棋 の2020年の問題366問を解かせてみたところ、かなり時間かかるものはあったが一応すべてに対して最短の正解ではないにしろ詰みを見つけることは出来ていた。

未着手の課題としては以下。

  • まだ解けていない問題が幾つか発見されているので、可能な限り修正していきたいところ
  • sfen形式ではない、棋譜表記の文字列で回答を出力したい
  • 最短最善解を導出できるように、は勿論していきたい
    • まずは深さ上限を指定しての探索から実装することになる、か
  • パフォーマンスの問題はまだあるので可能であれば高速化は試みたい
  • 長手数の問題はどのレベルなら解けるのか、または残り何手の状態なら現実的な時間で解けるのか、など知っておきたい
  • WASM buildしてWebアプリ上で動かしたい