学習速度を上げたい

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

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

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

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

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

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

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

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

一手の読みを入れる

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

グラフ１

まずまずの結果

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