自己対戦でも強くなるのか？

    coffeescript tictactoe android javascript ruby

    自己対戦でも強くなるはず、なって欲しい…

    　以前「統計の基本と世界を測るテクニック」という本に書かれていた方法（加減算を使った強化学習）で作った三目並べプログラムを「ゼロから作るDeep-Learning-Pythonで学ぶディープラーニングの理論と実装」に書かれていた方法（勾配法を使った誤差修正）に置き換えて比較した記事を書きましたが、この時は学習部分を書き換えただけで、学習データから指し手を決める部分（推論部分）は両方同じものを使いました。そして、MIN-MAX法（+αβ法）で作成した最強の三目並べプログラム（絶対負けない）にほぼ100%引き分けるようになるという学習効果が出たので良しとしました。今回は、自己対戦での学習です。
    　同じプログラムで自己対戦を進めてみると、学習の経過を観察している限りはうまくいっているように見えるのですが、ある程度進んだところからお互いに示し合わせたような手順で引き分けに持ち込むようになり、学習が進まなくなりました。何が不足していたのか書いていきます。

    学習データを使って指し手を決める部分

    　以前の記事はRubyで試したのですが、進化する三目並べ（Tic-tac-toe Evo）アプリも同じコードです。アプリの方でやっている、指し手を決める部分（学習データの重みを元に確率的に指し手を決める推論部分）のコードは以下のようになっています。

        idx=(score) ->
        ret = null
        index = ((Math.random() * score.reduce (t, s) -> t + s) * 10) / 10.0
        start = 0
        for v, i in score
            continue unless v
            start += v
            if start > index
                ret = i
                break
        return ret

    　[94, 32, 137, 98, 160, 95, 98, 84, 97]のように格納されている学習データ（score配列）の合計値を最大とした乱数を生成して、配列要素の値の確率で指し手を選択します。この配列の場合、三目並べの９マスの中の真ん中の部分（=160）が一番選ばれる確率が高くなります。要素の値が大きなものほど選ばれる確率が高くなるようにしていて、このアルゴリズムにはルーレット選択（roulette wheel selection）という名前もついているそうです。
    　一方、勾配法を使って誤差修正した学習データ（重みデータ）の方は、こんな感じ（[0.4318351809286462, -0.136178370499291, -0.09351127010637855, 0.1634164478516657, 0.24849662017899993, 0.6657091635199834, -0.0935112701066006, -0.05211347023271268, -0.13414303387244214]）になっていて合計が１になるように正規化されています。合計が１になるのだから上のコードの配列の値を合計している部分（score.reduce (t, s) -> t + s）は不要なので取り去ったのですが、自己対戦で学習させる場合はここに問題がありそうです。重みデータに負数が含まれていますので、上のコードだと負数の場所が選ばれることはありません。選ばれることがなかったとしても、それが学習の結果だからいいと思っていたのですが、自己対戦で学習を進める場合は選ばれることがない手が多いと学習する機会がありません。

    アプリに自己対戦機能をつけてみると

    　このアプリ（Tic-tac-toe Evo）はCoffeeScript1.xxで作成していたのですが、CoffeeScript2で仕様が変わって今までのコードがトランスパイル出来なくなって放置していたのです1が、久しぶりに更新しようとして、ついでに自己対戦機能もつけてみてテストしたところ前述の問題に気づきました。
    　自己対戦させてみると、５００回程度の対戦で学習が進まなくなる（手順の変化がほとんどなくなる）のです。以前の記事にも書いたように、MIN-MAX法（+αβ法）で作成した最強の三目並べプログラムと対戦させた時はだいたい6,000回ぐらいの対戦が必要でしたのでおかしいと気付きました。自分で対戦してみても確かに弱いです。ＡＩが自己対戦で学習する場合、指し手を選択する部分にランダム性（無作為性）がなくなると、ゲーム木内で学習が進まないノードが多くなるからです。
    　そこで指し手を決める部分を以下のように修正しました。

        normal=(score) ->
        min = score.reduce (t,s) -> if (t < s && t?) then t else s
        max = score.reduce (t,s) -> if (t > s && t?) then t else s
        if min < 0
            return score.map (o) -> if o? then (o - min) / (max - min) else null
        else
            return score

    idx=(score) ->
        ret = null
        dest = normal.call @, score
        sum = dest.reduce (t, s) -> t + s
        index = Math.random() * sum
        start = 0
        for v, i in dest
            continue unless v
            start += v
            if start > index
                ret = i
                break
        return ret

    　学習データに負数が含まれている場合は０〜１の正の値に正規化し直して、指し手をルーレット選択で決めます。こうすれば学習データ生成部分（勾配法で重みを修正していく部分）を弄らなくて済みます。
    　念のために書いておきますが現在リリースしているアプリは勾配法を使っていない（加減算による重み修正）ので、重みが負数になることがないため問題はありません。リニューアルする前に気がついてよかったです。

    修正したコードで学習

    　指し手を決める部分を修正した後に自己対戦で学習を進めたところ以下のグラフのような推移になりました。学習が進めば引き分けが多くなっていくはずですが、ＡＩ同士の対戦なので勝った方が正しい手を選択したとか負けた方が間違ってるとは言えませんので、このグラフだと学習が進んでいるのかどうかよく分かりません。

    グラフ１

    　最強プログラムと対戦させると以下のようになりました。学習の進み具合に関しては、以前の記事で紹介した最強プログラムとの対戦結果より結果が悪くなっています（当たり前？）。以前の記事で紹介した最強プログラムとの対戦経過のグラフは6,000回以上対戦した後はほぼ負けなくなりましたが、今回（以下のグラフ）はそれ以降も結構指し手を間違えて負けてます。重みデータが負数であっても選択されるようになったからです。

    グラフ２

    試しに

    　新しいアプリではＡＩ対ＡＩの自己対戦時だけ学習フェーズと看做して修正後の指し手選択機能（正の値に再正規化してルーレット選択）を使い、人との対戦時には修正前の方法（学習データからそのままルーレット選択）で指し手を決めるようにしようかと思い、自己対戦で10,000回対戦（学習）させて(=グラフ１と同じことをやって)、その学習データを使ってMIN-MAX法（+αβ法）で作成した最強の三目並べプログラムと対戦させた結果が以下のグラフです。

    グラフ３

    　最強プログラムと対戦しながら、学習データの更新もしてます。約1,000回対戦後ぐらいから最強プログラムに対応して１００％間違えずに引き分けに持ち込んでいます2。

    結局

    　でも、現在のアプリ（Tic-tac-toe Evo）は「ピロリ菌から人間」に進化するのが目的だったんですけど、重みの変化も表示出来るようにしてリニューアルするつもりなので、一度学習した重みが人と対戦する時だけ全く修正されなくなる（負数の重みの箇所は選択されない）のはおかしいので、結局リニューアル版アプリでは人と対戦する場合でも、修正後の指し手選択機能（正の値に再正規化してルーレット選択）を使うことにしました3。

    　学習率（0.03）をもっと上げればもう少し学習速度が上がることを確認していますが、前回の記事との比較のために同じ値にしています。

    一つの疑問

    　ＡＩの自己対戦で学習させた後の初期盤面のデータを見ると、このようになっていて
    [-1.8925330868577688, 1.8008319403253112, -1.897081206496631, 1.8408789986060665, 1.7986873436156023, 1.6117949761265158, -1.869006677797431, 1.5211261154141682, -1.914698484728805]
    　９マスの真ん中の値が一番大きな値にはなっていません。何回か試しましたが毎回こんな感じです。最強プログラムと対戦させると初手は真ん中が最善手だと学習するのですが、自己対戦だとそうならなくて良いのでしょうか？
    　以下のように二手目の局面に関しては全て真ん中の重みが一番大きな値になっています。

    # verify.rbの出力

 |X|2|3|
 |4|5|6|
 |7|8|9|
[nil, -0.6426669303657259, -0.6367678042990683, -0.6383926721743185, 5.4310677151704265, -0.6327334824829767, -0.6424836060305146, -0.616752627068463, -0.6212705675723019]
       
 |1|X|3|
 |4|5|6|
 |7|8|9|
[-0.16631190866539602, nil, 1.538412046081448, -0.7372359877317052, 3.3482333802093187, -0.7691023601009714, -0.7318887423947653, -0.7247859552613936, -0.7573204566228662]
       
 |1|2|X|
 |4|5|6|
 |7|8|9|
[nil, -0.6426669303657259, -0.6367678042990683, -0.6383926721743185, 5.4310677151704265, -0.6327334824829767, -0.6424836060305146, -0.616752627068463, -0.6212705675723019]
       
 |1|2|3|
 |X|5|6|
 |7|8|9|
[-0.16631190866539602, nil, 1.538412046081448, -0.7372359877317052, 3.3482333802093187, -0.7691023601009714, -0.7318887423947653, -0.7247859552613936, -0.7573204566228662]
       
 |1|2|3|
 |4|X|6|
 |7|8|9|
[0.5849222179777929, 0.010018189953422851, 0.12908711346909785, 0.004284212528851583, nil, 0.04368794916876073, 0.1295710912817576, 0.07700222026718873, 0.02142701999881247]
       
 |1|2|3|
 |4|5|X|
 |7|8|9|
[-0.16631190866539602, nil, 1.538412046081448, -0.7372359877317052, 3.3482333802093187, -0.7691023601009714, -0.7318887423947653, -0.7247859552613936, -0.7573204566228662]
       
 |1|2|3|
 |4|5|6|
 |X|8|9|
[nil, -0.6426669303657259, -0.6367678042990683, -0.6383926721743185, 5.4310677151704265, -0.6327334824829767, -0.6424836060305146, -0.616752627068463, -0.6212705675723019]
       
 |1|2|3|
 |4|5|6|
 |7|X|9|
[-0.16631190866539602, nil, 1.538412046081448, -0.7372359877317052, 3.3482333802093187, -0.7691023601009714, -0.7318887423947653, -0.7247859552613936, -0.7573204566228662]
       
 |1|2|3|
 |4|5|6|
 |7|8|X|
[nil, -0.6426669303657259, -0.6367678042990683, -0.6383926721743185, 5.4310677151704265, -0.6327334824829767, -0.6424836060305146, -0.616752627068463, -0.6212705675723019]

    　二手目に関しては空いていれば必ず真ん中を選ぶのが最善だと学習したということです。
    　昔の記事に書きましたが三目並べでは初手にどこを選んでも引き分けになります。先手・後手お互い最善手を選べば引き分けになるのですから、真ん中が最善手とは言えないという正しい結論を導いているように思えるのですが、一方で初手に真ん中を選ぶことはラインが揃う期待値がもっとも高い？と思っていたので、どう解釈すべきなのでしょうか。一般的に機械学習では最も期待値が高い手を選ぶようになるはずですが、三目並べの場合は規模が小さいので完全読み切りと同じ結論を得ることが出来たと言えるのかもしれません4。
    　また、αβ法を使った三目並べプログラム（の指し手）という教師（データ）を使って学習するより、自己対戦で学習したデータの方が正しいという見方も出来そうです。プロ棋士の指し手を学習した将棋ＡＩより自己対戦で学んだAlphaZeroの方が強い状況と似ていますね5。

    サンプルコード

    　公開しているRubyのコード（neural branch）は、必要に応じて、必要な箇所をコメントにしたりアンコメントしたりしないといけない形になっていて分かりにくいと思いますが、興味があれば今回の作業を再現出来ます。

    将棋ＡＩに適用すると

    　この三目並べアプリと全く同じ作り方で将棋ＡＩも出来そうな気もするのですが、三目並べのようにゲーム木内の全ノードを保持するわけにはいかないので、少なくとも新たな局面が現れる度に動的に局面データを生成していく必要がありそうです6。それでも膨大なリソースが必要になりそうなので、とりあえず本将棋ではなく５五将棋で、尚且つ三目並べのようにゲーム終局を確認してから報酬か罰を与える（ロールアウト、プレイアウト）のではなく、ある程度優劣がはっきりしたところで打ち切って評価する形にすれば可能かもしれないと考えています。AlphaZeroもそんな感じ？で作られているようです（「強化学習入門 Part3 － AlphaGoZeroでも重要な技術要素！ モンテカルロ木探索の入門 －」）。
    　自己対戦で強くなるのであれば、優秀な教師データを作ることに注力するより開発効率は良さそうです。

    1. CoffeeScriptはオブジェクト指向言語のように記述出来るのですが、クラスベースのオブジェクト指向言語になりきっていないJavaScriptにトランスパイルするには無理があるようで、Arrayクラスを継承した独自クラスを使っていた部分の振る舞いが、CoffeeScript2になって変わりました。その辺の技術的なことは別の記事に書くかもしれません。 ↩

    2. 何回か試してみると、1,000回目ぐらいから１００％にならずにずっと９９％ぐらいで推移することもあるのですが、１００％になる時との違いが何に起因するものかよく分かりません。 ↩

    3. 公開しているRubyのコード（neural branch）は先手か後手の一方でしか学習データを更新していませんが、実際のアプリではＡＩ同士の対戦時に先手・後手双方で学習データを更新しますので、このグラフよりかは学習効率は上がります。 ↩

    4. αβ法を使った最強三目並べプログラムとの対戦だけだと、たとえ同じ評価値の時に乱数で指し手を選択するようにしているとしてもランダム性が足りないのかもしれません。 ↩

    5. こういう書き方をするとＡＩ万能なＡＩ信者のように受け取られるかもしれませんが、個人的には将棋ＡＩは勝つことを目的にしているので勝ち易い手を選ぶ（入玉指向だったり、ポイントを積み重ねる将棋）だけで、本当の最善手は今のＡＩが選ぶのとは別の経路にあるかもしれない（短手数の必勝手順が存在するとか…）、もしそうなら面白いなぁなんて考えてます、相入玉か千日手が本命かなとも思いますが…。細かなポイントを積み重ねる柔道より一本を取る柔道の方が見ていて面白いので、間違いがあっても人間の将棋の方が楽しめます。ＡＩの指し手も年々変化するわけですから、ＡＩの手が最善手とは言えないのは確かでしょう。 ↩

    6. 三目並べアプリも昔のバージョンは動的にゲーム木を生成するやり方でした。 ↩