26 February 2019

    常に2段階で先読みする

     3三将棋アプリの「長考モード」と「瞑想モード」では、まず4手読み(depth=3)で候補手を5手に絞って、その5手に関して8手読み(depth=7)をするという仕様になっていますが、候補手を絞る作業は最初の一回だけでした。一度候補手を絞った後はその候補手に関してαβ法で枝刈りをしながら全件探索するというやり方です。この候補手を絞る作業を最初の一回だけではなく、全ての先読みの過程(再帰呼び出しの都度)で行えるようにコードを修正しました。その結果同じ時間でより深く読むことが出来るようになりました。
     候補手を絞って評価値の低い手は意図的に読まない(αβ法の枝刈りとは意味合いが違います)ので、最善手が読み抜けてしまう可能性はありますが、より深く読むことを優先したということです。テストスクリプトの実行時間で比較したところ約30%時間短縮出来ました。

    以前解けなかった問題

     解けなかったというより解ける深さまで読ませるとアプリで実行するには時間がかかり過ぎるので、最善手(おそらく正解)を諦めていた初期配置です。

    上級編の問題の初期配置

     この初期配置は以前の記事(「9マス将棋の本」買ってみました)で紹介した本(9マス将棋の本)に載っていた問題で、3三将棋アプリでは初期配置リストのNo.41番にあるものです。この配置は初手が肝心なのですが、以前の3三将棋アプリでAIに指させてみると一番深く読む「瞑想」モードでも初手1三角と相手の角を取ってしまい先手が勝てません。本に出題されている通り先手が勝つためには初手に2三玉と指さないといけないのですが、Version1.0.7.0からは初手2三玉が指せるようになりました。
     しかし、その後の変化はいろいろあるようでアプリでは後手が勝つケースもあるようです。以前の記事(「9マス将棋の本」買ってみました)で紹介した手順(2三玉、2一玉、1三角、同歩成、同玉、3三角、2三歩、1一角成、3一歩成、同玉、2二角、同馬、同歩、1一歩、2三玉、1二角、3三玉、2一角、同歩成、同玉、3二角、1二玉、3一角、2一歩、2三角)の25手で「先手が勝ち」という手順も以前のバージョンの設定を一時的に深く読む設定にして導いた一例に過ぎません。ちなみに、候補手を絞るという作業を入れずに全件探索で調べてみると43手で先手が勝ちという変化になりました1、奥が深いです。
     この初期配置以外にも今まで間違ってるなぁと思いながらもそのままにしていた初期配置に関して、今回の修正で正解が出せるようになった(と自分が思っている)初期配置があったり、先手勝ち、後手勝ち、千日手の結論は置いといて、この変化は筋悪過ぎるだろうと思う手順が改善されたものもあります。また、逆に深く読めるのはいいけど、全件探索の「弱い」モードなら正解手順を示せるのに、最善手が初期の段階で候補手から漏れてしまい「瞑想」モードだと間違えるという初期配置もあると思います。と言うことで、局面の検討をするときは、まず「弱い」モードで試してから、他のモードを試してみることをお勧めします。
     ちなみに何手先まで読むかを指定するパラメータ(depthの値)が今回の修正で7から9になっています。2手深く読めるようになったということです。

    反復深化について

     以前の記事で特殊な三目並べを例にして、最も単純な評価関数(勝ち、負け、それ以外の3つの値を返す関数)を使って9手読み、10手読み、11手読みと徐々に先読みの手数を伸ばしていって解を求めるやり方について書きました。これが一番単純な反復深化探索だと思いますが、このやり方だと同じ経路を何度も探索しているので重複チェックを組み入れるのが普通だと思います。3三将棋アプリでは、短い手数で読んで候補手リストを作って評価値でソート後、さらに深く読むときに候補手リストに無い手は読まないようにしているのですが、これは重複を避けるというより、見込みがないと思われる手をバッサリと読みから外していますので反復深化探索とは呼ばないのかもしれません。少なくともこの方法で迷路やパズルを解くと解答が得られないことがあるでしょう。その辺りのアルゴリズムの分類についてはよく分かりませんが、どう呼べばいいのか分からなかったので反復深化と表題につけました。2段階深化とでも言うべきでしょうか?
     また、一般的に反復深化探索で迷路やパズル等の問題を解くときは、重複チェックにコストがかかり過ぎて重複チェックを省略した方が速く解けるケースもあるようで、たしかに再帰呼び出しの度に候補手リストを作成する作業も結構コストがかかるやり方なので、3三将棋の変更を試しに5五将棋アプリに適用してもそれほど速度アップの効果はありませんでした。コードの中身は変わったのですが、評価関数を変えたわけではないので指し手もあまり変わりませんでした。再帰の度に候補手リストを作って読む指し手を省略すると言っても、5五将棋アプリでは元々深く読めてない(5手読み)ので、読む手を省略する効果もそれ程ありません23三将棋アプリは8手(depth=7)読んでいたからこそ、指し手の省略の効果が大きく出たのだと思います。
     でも、候補手リストに含める手の数、候補手リスト作成時の読みの深さ、最終的に制限する読みの深さ、全件探索に切り替える手数など、パラメータが増えたので5五将棋アプリ禽将棋アプリにも取り入れて試行錯誤してみようと思ってます。

    検討モード

     アプリの中で設定しているパラメータや読みの深さ、全件探索にするかどうか、評価関数の種類等の設定をユーザが指定出来るようにして、検討モードのようなメニューがあった方がいいかなとも思っていますが、そこまで3三将棋(9マス将棋)の検討を熱心にやりたいというニーズがあるのかどうかが問題です:sweat_smile:


    1. 2三玉、2一玉、1三角、同歩成、同玉、3三角、2三歩、1一角成、3一歩成、同玉、2二角、同馬、同歩、1一角、3一角、3二玉、1二玉、3三玉、1一玉、2三角、2一歩成、3二角成、3一角、3一馬、同と、2二角、2一玉、1三角成、3二と、2三玉、2二角、1二馬、3一玉、1三馬、同角、同玉、1一角、2一歩、3三角成、1二玉、2二と、同歩、同馬まで43手で先手勝ち。全件探索で読んでいると言っても初手から詰みを読んでいるわけではないのでこの手順が正解とは限りません。37手目1一角を打つ時に初めて先手勝ちを読みきっています。 

    2. JavaScriptと言えども5五将棋で3手読みぐらいまでは一瞬で全件探索が完了します。2段階深化の方法だけだとかえって遅くなるので、残り4手(depth=3)からは全件探索に切り替えているという事情があります。5手読み(depth=4)だと今までの「最初に一回だけ候補手リストを作成する方法」と同じ効果しかないわけです。残り何手から切り替えるのが良いのかは今後試行錯誤してみる予定です。 



    blog comments powered by Disqus