07 September 2019

    学習速度を上げたい

     前回の記事の続きです。自己対戦で大体10,000回ぐらい対戦して学習させると、ほぼ負けないようになることがわかりました。この記事によると三目並べで10,000回の自己対戦回数というのは特に遅いというわけでもなくこれぐらいは必要みたいです。とすると現在リリースしている三目並べアプリは「人間」まで進化するためには大体3,000回ぐらいの対戦が必要なのですが、難しい数式を使わずに足し算、引き算だけで強化学習しているにも関わらずなかなか健闘していると思います1
     もともと強化学習に関する好奇心から作ったアプリですが、今後将棋アプリに応用するためにももう少し学習効率をアップしたいと思いながら、リニューアル予定の三目並べアプリをちまちまテストしながら学習効率を上げるために試したことを書いてみます。

    学習時間の多くは学習する必要のない局面に費やされている

     三目並べアプリをポチポチとやっていると、徐々にAIが強くなっていくのは感じるのですが、極短手数で負けることがあることに気付きます。先手で相手の手など気にせずに横一直線、縦一直線にラインを揃えに行くとAIはリーチを防ごうとせずに最短手数(5手)で負けることが結構あります。どうやらゲーム木の内の末端に近いノードの局面(手数が長くなる)の学習ばかり先に進んで、ゲーム木内の上の方のノード(短い手数で現れる局面)はなかなか学習が進みません。
     例えば以下のような局面では次に先手(×)にラインを揃えられるの防ぐために、後手(○)は真ん中下部を選ぶしかありません。

    局面1: 序盤画面1

     しかし、AIを自己対戦させると地道に全ての局面を学習していきます。

    局面2: 序盤画面2

     そして、仮に上図のように後手(○)が左上を選択した時に、まだ学習が十分でないAI(先手×)が下段真ん中を選ばずに後手(○)が最終的に勝ったりすると、後手が報酬を受け取って「局面1」で左上を選んだのが良い手だったと学習してしまいます。こういうことが何回も繰り返されているわけです。ただ、「局面2」のようにあと一手で勝てる局面では、下段真ん中に打ちさえすればその時点でゲーム終了して勝ち点3の報酬を貰えるので、比較的早い段階で学習できるようです。問題は「局面1」の段階で相手のラインが揃うのを防ぐ手がなかなか学習出来ないことで、「局面1」で下段真ん中を選ばなかった後の展開も非常に多岐に渡りますし、後手が偶々下段真ん中を選んだとしてもそのあとの展開で後手が負けたりすると、結局下段真ん中に打った手が悪い手だったと学習してしまい、それを修正するのにまた多くの対戦を必要とし学習効率が非常に悪くなります2

    実戦には現れない局面を先に学習している

     下の図は前回の記事のプログラムを自己対戦で500局程度対戦させた後の「局面1」と「局面2」での重みデータを表示しているものですが、

    重みデータ画面

     局面2では下段真ん中が0.6815と一番大きな値となっていて、最善手だと学習していることがわかりますが、局面1の学習データは値がバラついていて、まだどこが選ばれるかわからない、学習が十分に進んでいない状況です。「局面2」のようにあと一手で勝ちという局面に関しては比較的早い段階で最善手を学習するのですが、その前の段階で間違えるために非常に無駄な学習を続けることになります。「局面1」で最善手を選べれば「局面2」とそれ以後の局面はお互いに最善手を選ぶ実戦では現れない局面で、学習しなくていいとは言いませんが、後回しにしたいところです3
     「局面1」は将棋で言えば王手を掛けられている状態で、将棋なら玉を逃げるか合い駒するか王手をかけている相手の駒を取るかいろいろ選択肢がありますが、三目並べだと相手のラインが揃うのを防ぐ手一択です。こういう絶対手が存在する局面の重みデータだけあらかじめ大きな値に書き換えるのも一つの方法かもしれません。
     特定の局面の重みデータを恣意的に操作するのは将棋AIで言えば定跡データを利用することに一見似ていますが、将棋で言う定跡は主に序盤で使われるもので、絶対正しいとは言い切れないものですし頻繁に変わります4。それに対してここで言っているケースは、その一手を選ばなければ負けると言う絶対手が存在する局面のことを言っているので定跡とは違い、終盤に生じる限定手に当たります。三目並べでは三手後の局面がすでに終盤なんですね。絶対に正しいとは言い切れない定跡データを使うケースとは違い、絶対正しい手だけを対象にするのであれば重みデータを恣意的に操作してもいいのでは?と考えました。

    一手の読みを入れる

     三目並べアプリと同じモンテカルロ法を使っているAlphaZeroでも一部で先読みを行なっている(参照)と聞いて、最初どういうことだ?と思ったのですが、ゲーム木をプログラム内に保持しているわけですから、子ノードを辿っていくことが先読みに繋がります。先読みといっても、MIN-MAX法(αβ法)等を使って先読みするわけではなくツリー構造のノードを辿る処理をしているのだと想像します。←実際どうやっているかは知りません。
     先ほどの例で言えば、「局面1」から一手進んだ「局面2」は「局面1」の子ノードにあるので、そのデータを参照すれば一手先を読んでいることになります。「局面2」には既に学習が進んだ重みデータがあるわけですから、「局面1」で指し手を決める時にその子ノードを参照して、その子ノードで保持している重みデータの最大値が十分に大きな値(> 0.9)であればその手を優先して採用するようにして見ました。上の図で言えば、「局面1」で左上のマス目を選択したとしても、一度子ノードである「局面2」の重みデータを参照してその最大値(0.6815)が格納されている下段真ん中に変更するというやり方です(上の図の例では、最大値がまだ0.6815> 0.9という条件を満たさないので置き換えません)。子ノードの最大値が相手のラインが揃うのを防ぐ手であるのか、自分のラインが揃う手であるのか分かりませんが、先手または後手の手番におけるその局面での最善手であることを示しているのですから、その値が他のマス目に比べて著しく大きな値であれば十分に学習済みの局面と考えて指し手を変更するという方法です。ある局面から先の局面が全て現局面の子ノードにぶら下がっているわけではないので、このやり方を厳密にやろうとすると親ノードから辿る必要があるのですが、とりあえず学習速度を上げるための効果を試したかっただけなので、現在参照中の局面データ(ノード)にぶら下がっている子ノードだけを調べる方法で、前回記事と同様に10,000回の自己対戦をして見ました。

    グラフ1

    まずまずの結果

     前回記事のグラフ1と比較していただければ明白ですが、効果はあるみたいですが重みデータを恣意的に変更することで何か悪影響があるかもしれません。まだよく検証していません。
     この方法を将棋AIに当てはめることを考えてみましたが、三目並べと違って将棋の場合は詰めろを受ける方法も複数存在することが多いので「この一手」じゃないと負けてしまうという絶対手が存在する局面っていうのはあまり無さそうなので、将棋の場合は候補手を絞るために先読みを使うのがいいかもしれません。将棋AIを作る前に取り敢えず三目並べで色々試しているのですが、試してみたいアイデアや疑問がいっぱい出てきて、学習型の将棋AIの作成がなかなか進みません:sweat_smile:


    1. 但し「人間」にまで進化した後も5%ぐらいはAIが負けて(間違った手を選ぶ)しまいます。詳しい仕様は「統計の基本と世界を測るテクニック」という本に書かれています。 

    2. 三目並べの場合は局面と手番が同じなら最善手はいつも同じなので、間違った学習が他の局面の学習結果に波及するわけではないですが、学習が完了するまでの対戦回数が増える要因ではあります。 

    3. お互いに最善手を選ぶことを前提にしているわけではなく、全てのノードの学習を進めることを前提に作っているので、学習しなくていいとは言い切れないのですが、最初から全ての変化(ノード)を扱うつもりがない場合や、扱うことが出来ない将棋プログラムなどを作る場合は「学習しなくていい局面」と言い切れると思います。 

    4. たとえ最新の将棋AIで導き出した定跡手順と言えども、序盤の定跡手順と言うものは、そのソフト独自の評価関数で導き出したと言うだけで絶対正しいとは言えません。将棋において絶対手と言えるのは、終盤の「この手以外詰まされるという手」になると思います。 



    blog comments powered by Disqus