打ち歩詰め判定メソッド

　以前「打ち歩詰めについて」という記事で打ち歩詰め判定メソッドのことを書いて、結局それだけではうまくいかず、ＡＩが打ち歩詰めの手を返してきた時は次善手に置き換えて打ち歩詰めを回避したことを書きました。あの記事を読んだ人はそれでいいのか？と疑問を感じた人がいるかもしれません。中途半端な打ち歩詰め判定メソッドを使っているということは、先読みの最中に打ち歩詰めの手も読んでいるわけです。それには目を瞑るとしても、局面の先読みメソッド（ＡＩ）が打ち歩の王手を返してきた場合に、それが打ち歩詰めの反則手かどうかを確認するために呼び出し元のGUIプログラム側でもう一度先読みメソッドで二手読みをして、打ち歩詰めになっていたら次善手に置き換えるという手法はなんとも泥臭い。幸いなことに打ち歩詰めに関しては一局面に一手しか存在しないためＡＩが返してきた次善手もまた打ち歩詰めだったなんてことはあり得ないので、次善手に置き換えるという方法でも実害はないのですが、コードが煩雑になるのと二手読み分の処理が重複しているのが気になっていました。
　ということで頑張ってＡＩが打ち歩詰めの指し手を返してこないように修正したので、どうやって打ち歩詰めの手を返してこないようにしているか現状を書いておきます。

そもそもＡＩに「打ち歩詰め」させてはいけないのか？

　前段の「それには目を瞑るとしても」という文に「瞑っちゃダメだろ」とツッコミ入れた方いると思います。そういう人に聞いていただきたいのですが、私も３三将棋アプリを作り始めた頃は、事前に反則となる手は指さないようにしなければいけないと思って作り始めました。「二歩」という反則手と同じく「打ち歩詰め」も事前にチェックして、その手を指させないようにしなければいけないと思って作っていたのです¹が、ある時デバッグの最中にＡＩが自玉に掛けられている王手を無視して相手玉に王手をかけている局面があることに気づいて、「そう言えば王手放置の対策は何もしてなかったなぁ、これはまずいんじゃないか？」と思ってすぐに王手放置チェックを組み入れたのですが、王手放置をさせないようにしたＡＩは単に遅くなっただけで強さは変わりませんでした（自前のテストケースでの確認）。局面の先読みをする過程で王手放置を許したとしても、その次の一手で王が取られるので静的評価は負けの評価（先手は最小値、後手は最大値）になります。だから、特に何もしなくてもＡＩ側が王手放置の指し手を選択して返してくることはありません。つまり局面を読み進める際にわざわざ駒の利きをチェックして王手放置させないようにしても、コスト（一手毎に駒の利き情報を更新するコスト）に見合った効果はないということだと思います²。ということで３三将棋アプリのＡＩでは、二歩は事前に指させないようにチェックしています（コストが軽微なので）が、王手放置対策は特にしていません。もちろんユーザー側の指し手に関しては二歩も王手放置もチェックしています。
　では「打ち歩詰め」に関してはどうでしょうか、「王手放置」は一手分読めば負けとわかりますが「打ち歩詰め」は二手分読まないと反則だと判定出来ない³のでちょっと事情が違ってきます。でも「二歩」も「王手放置」も「打ち歩詰め」も事前に反則手を指させないようにする方法（事前チェック）と反則手を指した場合に負けの評価を与える方法（事後チェック）の二つのやり方があるということです。どちらのチェック方法を採っても同じ結果が得られるわけですから、大事なのは実行速度を上げるためにどこにコストをかけるかということです。
　この好きに指させて事後に評価するという考え方は、アプリを機械学習型のＡＩに変えるときにも大事なことだと思います。

打ち歩詰め判定メソッドは使わないようにしてみた

　前回の記事で打ち歩詰め判定をするために必要な条件を３つ程列挙しましたが、一番簡単な定義は「打ち歩による王手で詰んだらそれが打ち歩詰め」ってことです。この「詰んだら」の「だら」が曲者で、詰んでるかどうかをソフトで判定するのが面倒なわけですが、とりあえず前回の記事で書いたような、こう言う条件を満たしたら打ち歩詰めになるという条件を細かく列挙するのは止めて、「打ち歩による王手で詰んだらそれが打ち歩詰め」という判定方法でまずは実現してみました。
　先手用のPlayerオブジェクトと後手用のPlayerオブジェクトを生成して、同じPlayer.thinkメソッドを再帰呼び出し（相互再帰）してゲーム木を辿っていくのですが、その本流ともいうべき局面のツリー構造（木構造）を辿っていく過程で「打ち歩による王手」が現れたら別経路の支流に寄り道してまた本流に戻るというやり方です。図にすると以下のような感じです（クリックで拡大）。

　上の図は四角（□）の箱が一局面分、実線が先読みの本流、破線が打ち歩詰めチェックのためだけの支流で、四手目まで先読みをする場合を表しています。打ち歩による王手の場合だけ、その手が打ち歩詰めにならないか二手読みをして事前チェックするという方法です。このやり方で中途半端な打ち歩詰め判定メソッドを使う必要はなくなり、GUI側で指し手を置き換える必要もなくなり、コードもスッキリしたのですが、図を見ても明らかなように読む局面の数が増えてしまいます。打ち歩詰め判定のためだけに打ち歩の王手の時は毎回二手読みをするというのはかなりのコストです。手元でtime mocha test/と打ってテストスクリプトを走らせてみたところ案の定今までより遅くなっていました。今までは最終的にＡＩが返して来た指し手に対して、打ち歩の王手の場合には打ち歩詰めになっていないかどうか一回だけ問い合わせていたのに対して、このやり方だと毎回二手読みして打ち歩詰めの確認をしているわけですから遅くなって当然です。それに３三将棋だからいいものの、これが本将棋や５五将棋ならさらに遅くなるでしょう。
　打ち歩詰めチェックのためだけに支流に分岐して先読みをするのではなく、打ち歩による王手が指されたことを次のノードに引数で渡すなりして、本流の流れの中でチェックすべきですが、すべての打ち歩詰めのケースに対応するのは大変そうです⁴。打ち歩詰めチェックを組み込んだために効果的な打ち歩による王手を指せなくなっては元も子もありませんし。

事前チェックと事後チェックの折衷案

　ということで最終的には、中途半端な打ち歩詰め判定メソッドで事前チェックを行い、さらに不足しているチェックを先読みの本流で事後チェックするという方法を採りました。
　まず、以前の記事で紹介した打ち歩詰め判定メソッドでやっていることは以下の内容でした。

1. 打ち歩（持ち駒の歩）による王手かどうか、そうでなければfalseを返す。
2. 打たれた歩を玉以外の味方の駒で取ることが出来るかどうか、出来ればfalseを返す。
3. 打たれた歩に相手の駒の利きがあるかどうか（玉で取ることができない）を見て、取ることが出来るか、または他の場所に玉が逃げることが出来ればfalseを返す。
4. 上記の条件を満たさなければtrueを返す（＝打ち歩詰め）。

　これらのチェックはそのまま使用して、このチェックでは不十分なケース（ここでは「特殊な打ち歩詰め」と言っておきます）については先読みの過程で事後チェック（負けの評価値付与）するという方法です。具体的には1.の条件は先読みの過程で行うことにし、打ち歩による王手の場合はその駒の情報を先読みメソッドの引数に渡して、下層のノードに伝えます。そこで王手された打ち歩を玉以外の駒で取った場合に少なくとも、もう一手先まで読みを進めて自玉が取られる状況なら打ち歩詰めだったということで自分が勝ち（打ち歩による王手を掛けた方が負け）という評価値をセットします。
　以下の局面は以前の記事で紹介した判定に失敗する「特殊な打ち歩詰め」のケースですが、

　この局面で先手が１二歩と打った場合に後手は玉以外の味方の駒（飛車）で同飛と取れるから打ち歩詰めではないと誤った判断をしてしまうのを防止するために、王手で打たれた歩を玉以外の駒（玉で取る場合はチェック済み）で取った場合には、その時点で呼び出す先読みメソッドの戻り値が最大値あるいは最小値だった場合（勝負がついた場合）には−１を掛けて値を反転させる（打ち歩の王手を掛けた方が負け）というやり方です。打ち歩による王手なら不完全な打ち歩詰め判定メソッドでチェックして、そこで打ち歩詰めと判定されればその手は指さない（事前チェック）、打ち歩詰めでないと判定されてもその手を指した直後（次の階層を読む時）に打ち歩詰めだとわかったら（先読みメソッドの戻り値が最大値か最小値なら）負けの評価値を与える（事後チェック）ということです。
　図にすると以下のような感じです（クリックで拡大）。

　先読みの支流に分岐して戻ってくるという無駄な読みが無いため、先ほどの図より読む局面の数が減ったのは明らかです。注意しないといけないのは、局面の先読みをする場合に何手先まで読むかの制限値を指定するのですが、図のように四手目まで読むと指定したとしても四手目で打ち歩による王手が指された場合には制限値を無視して少なくとも二手先（打ち歩を取った後にプラス一手）まで読むようにすることです。これでようやく従来のやり方より実行速度を速くすることが出来、GUI側で打ち歩詰めの再チェックをすることもなくなったので、僅かですがレスポンスも改善しました（Version1.0.0.8）。
　今回の修正のために歩の手筋だけのテストコードをmochaでたくさん書きましたが、こういった混みいったリファクタリング作業はTDD（テスト駆動開発）じゃないとやってられないですね

一手詰めを解くためには三手読みが必要

　このブログの記事でよく◯◯手読みという表現を使いますが、読みの深さと詰み手数は違うので念のため書いておきます。自分のアプリだけでなく有名どころの将棋ソフトも多分事情は同じだと思います⁵が、こういう条件とこういう条件を満たせば詰みと判定するより、先手あるいは後手の一方に王将が二つある状態になればゲーム終了（＝詰み）と判定していることが多いと思います⁶。だから詰みの局面からさらに二手分先読みをしないとＡＩには詰んだかどうか判断できません。
　ということで一手詰めの詰将棋を解くには三手読みが必要で、三手詰の詰将棋を解くには五手読みが必要です。私のブログの記事やアプリの説明で「◯◯手読みしてます」と表現している場合、◯◯手詰めの詰将棋が解けるというわけではないので誤解のないようにお願いします。