詰み判定処理導入でレスポンス改善

     今回は前回の記事で紹介したもう一つの方法、詰み判定処理を導入したやり方(前回の記事の「方法1」)で試した結果について書いてみます。既存のアプリ(3三将棋5五将棋7七将棋禽将棋)は全て相手玉を取れば勝ちという簡潔な評価関数(「方法2」)を使っていて特別な詰み判定処理を行っていなかったのですが、今回チェスアプリで二つの方法を試してなかなか有用だということがわかったので、今後7七将棋禽将棋にも採用しようと思っています。詰み判定処理を使うと何が良いかというと、一つは全体的に読みの深さを浅く出来る(玉、キングを取るところまで読む必要がない)ことで、テストスクリプト内の読みの深さのパラメータを全て一手少ない値にしても、同じテスト結果が得られるなんてことが起こります。もう一つの利点は局面の評価をする際に細かく制御出来る点です。

    詰み判定(ゲーム終了判定)処理とは

     以前の記事でも少し触れましたが、現状詰み判定処理を行なわずにどうやって詰みかどうか(ゲームが終了かどうか)を判定しているかと言うと、先後の手番を入れ替えて一手先読みを行い最善手を選んでも玉が取られてしまう状態であればゲーム終了と判断しているわけです。一手先読みして判断するので、玉一枚になって敵駒に囲まれて持ち駒もなくなり全く指し手がない時(詰みではない時)でも、ゲームが終了したかどうかを判定出来るので色々なゲーム終了の条件をチェックする必要がないので便利です。前々回の記事で例に挙げた局面のように、角の筋に玉が入っていて間にある駒を動かせないケースでも、動かした後に一手先読みすれば玉が取られることが分かるので特別な判定処理を用意しなくても、ゲーム終了したかどうかが判断出来ます。
     詰み判定処理とは、一手先読みをするのではなく手番と駒の利きと王手が掛かっているかなどの情報を使って現時点の局面の状態だけをみて詰みかどうか(ゲーム終了かどうか)を判定する処理のことを言っています。相手玉に王手をかけている局面でも、すでに自分の玉に王手がかかっていたら「王手放置」、前々回の記事の例のように動かせる駒はあるけど動かすと角の利きに入っているから動かしたら「負け」等、いろんなケースに対応しなければいけないので煩雑な処理になります。

    詰み判定導入で局面に依って読みの深さが変わる

     例えば評価関数内でこういう条件が成立すれば王手放置で先手の勝ちと結論が出たとします、結論が出たらすぐに評価関数からreturnするのですが、そうじゃない場合(if〜else文のelseの場合)には新たに読みの深さを指定して先読みを継続するという形になります。評価値を計算する計算式は同じでも、局面評価のタイミングの違いによって指し手が変わるようです。今までは何手先まで読むと指定すれば全局面を一律に評価して効率的な枝刈りはαβ法に任せていた1わけですが、評価関数内で詰み判定(終了判定)することでより細かく制御できます。巷の将棋ソフトで「局面に依って読みの深さを変える」という機能を耳にしたことはあるのですが、こういうことなのかもしれません。詰み判定処理を導入することで、図らずも局面に依って読みの深さが変わる仕様になりました。
     言葉で説明しても違いがよく伝わらないと思うので、いずれ安定したら3三将棋アプリ同様に何らかの形(CLI版だけとか)で公開したいと思います。

    前回の問題で指し手が変わった

    例1:Bf6のステイルメイトを避ける

    (クリックで画像拡大)

    テスト1

     評価方法を変えたらステイルメイトに対応しているはずなのに、ステイルメイトになる手(Bf6)を選んでしまいました。
     調べてみるとこれは前々回の記事のようにステイルメイトの局面を勝ちの局面と誤って評価したわけではなく、ステイルメイト(引き分け)にした方が先手にとって良いと判断したようです。前回の記事でステイルメイトの場合はDraw(評価値=0)を返すようにしたわけですが、この局面は評価値0よりも先手(White)にとって悪い局面で、引き分けにした方がいいと判断されたようです。評価値を計算する数式は変更していないのですが、評価関数に詰み判定を導入した(前回記事の「方法1」)ことで指し手が変わりました。
     ところでステイルメイトの局面の評価値は一体どのように計算すればいいのでしょうか?打ち歩詰めの評価値は「打ち歩詰めをした方が負け」相手玉を詰めたら勝ちの将棋だけど「打ち歩詰め」の場合は相手玉を詰めた方が負けという分かり易いルールなので、局面の静的評価値に−1を掛けて評価を真逆にしました。しかしステイルメイトの場合はステイルメイトの局面にした方が負けというわけではないので−1を掛けるのはやり過ぎだと思います。単純に引き分けだから0がいいだろうと思ってそうしたのですが、多くの場合ステイルメイトは劣勢な側が何とか引き分けに持ち込んで負けを逃れる類のものなので、優勢な側は出来ればステイルメイトを避けたいはずです。かと言ってステイルメイトでいきなり負けになるわけでもないので−1を掛けるのではなく、−0.7を掛けることにしました。
     すると以下のようにまた指し手が変わりました。 (クリックで画像拡大)

    テスト2

     ナイト(♘)をe6に移動(Ne6)として見事にステイルメイトを避けました。前回の記事の指し手(Nf7)より良い手のような気がします。
     あと、実行時間が大幅に短縮されているところも見逃せないところです4277ms -> 70ms
     ちなみに前回の記事の「方法2」でもステイルメイトの局面に-0.7を掛ける処理に変更したところ、今回と同じ手(Ne6)を指すようになりました。-0.7という数値が妥当かどうかは不明ですし、評価値自体に問題があるのかもしれませんが、取り敢えずこのやり方にしました。

    例2:c8=Qのステイルメイトを避ける

    (クリックで画像拡大)

    テスト3

     前回記事の例題2では、ステイルメイトの局面の評価値を0にしても-0.7を掛けても同じ指し手(c8=B)でした。例題1と違い、先手(White)が圧倒的に有利(詰み=チェックメイトがある局面)なので当然こうなるべきでしょう。

    2種類の評価関数の比較

     方法1(詰み判定処理有り)と方法2(玉を取るまで読む)では、上記の例以外にもいろいろ指し手の違いが出てきます。既存のアプリで採用している「方法2」の方が以前の記事で紹介したように詰みを読むことに関しては正確だと思いますが、いくら正確に読んでいると言っても、実際のアプリではレスポンス改善のために候補手を削っていますので最善手を逃しているケースも多いと思います。7七将棋アプリ禽将棋アプリでは時間短縮のために全ての指し手の20%も読んでいないと思います。結局時間との兼ね合いで妥協せざるを得ないのなら「方法1」のやり方に移行してもいいだろうと考えています。
     また、以前の記事で「駒の働き(モビリティ)」について書いたことがありますが、詰み判定処理をする際に王手(チェック)が掛かっているか、相手の駒の利きに入っているかなどを検証する必要が出てくるのですが、その処理を評価値計算の処理に流用して、より複雑な評価値計算を効果的に出来るのも「方法1」の有用な点です。
     あと、このブログでは「何手先まで先読みするかを指定するパラメータを5にすると3手詰めが解ける」、「1手詰めの詰将棋を解くには、先読みの深さ(depth)に3を指定しなければいけない」と書いてきましたが、「方法1」のやり方を採用することによって先読みの深さと詰み手数が同じになって3手詰めの詰将棋を解く為には先読みの深さ(depth)に同じ値の3を指定すればいいようになります。


    1. 全局面を一律に評価していると言っても、評価値順にソートして評価値の低い手は読まない等の独自の枝刈り処理は行っています。