01 July 2017

    Project: 「三目並べ」: neural

    消える三目並べの学習効率を上げるには

     前回の記事で現在作成中の「消える三目並べ」(3手前に打った自分の駒が消えるルールの三目並べ)の学習に時間が掛ることを書きましたが、「ゼロから作るDeep Learning」という本1に書いてあるニューラルネットワークのアルゴリズムを適用すれば学習効率が上がるのではないかと思い試すことにしました。ただ「消える三目並べ」のアプリに組み込む前に例のごとく「通常の三目並べ」でどうなるか試してみました。ディープラーニング(多層構造のニューラルネットワーク)を組み入れたわけではなく、指し手を決める「推論」部分は今まで通りで、対戦毎に学習データを更新する「学習」部分をニューラルネットワークに変更したということです。前述の本の中で”simpleNet”クラスとして紹介されているものに当たると思います。
     汎用的なAIライブラリもいろいろあるようですが、既存ライブラリの使い方を覚えるだけでは面白くないので自前(スクラッチ開発)でやってます:smiley:と言っても前述の本に書いてある通りやっただけですが:sweat_smile:

    修正内容

    1. 三目並べの局面データに保持している重みデータ(小石の数)を合計が1.0になるように按分する。
    2. 重みデータを更新する際に勾配法(確率的勾配降下法)を使う(学習率=0.1)

     変更したのは主に上記2点だけです。1.に関しては本に紹介されていたsoftmax関数を使いました。ニューラルネットワークで学習するための準備です。2.に関しては、今までは勝ったら+3、負けたら−1、引き分けなら+1、という報酬&罰を与えていた(重みデータの加減算)わけですが、その数値を使う必要がなくなります。根拠がはっきりしないマジックナンバーが無くなることはいいことでしょう。元々「STATISTICS HACKS」という本にこの数値(勝ち+3、負け−1、引分+1)を使うのがいいと書いてあったからそうしただけなので2以前から気になってました。また今回の修正で、ゲーム序盤の指し手よりゲーム終盤の指し手を重視するというロジックはとりあえず取り外すことにしました。
     2.の修正を行う際には、MIN-MAX法を使った最強プログラムと対戦させて最強プログラムの指し手を教師データとして一手毎に重みを修正するようにすれば、とりあえず学習データを作成することが出来て、後述するグラフデータと同様の結果が得られました。普通はこの学習済みのデータを使えば強いプログラムが完成したということになります。でもこのままだと乱数で指し手を決める弱いプログラムと対戦させた時に勝率が上がりません。弱いプログラムの指し手を教師データとして学習してしまうので、勝率グラフはほぼ5割の横ばい状態になってしまいます(実際に試しました)。どんな対戦相手でも対戦する度に強くなるようにするために、勝った方の指し手を教師データとして重みを更新するように修正しました。簡単に言うと今までは「AI側の指し手を元に勝ったらAIの手番の局面データの重みを加算、負けたら減算」3としていたのを「勝っても負けても勝った方の指し手を教師データとして、勝った方の手番の局面データの重みを勾配法を使って誤差修正する」というやり方に変えたということです。実際に取り組んでみないと分かりづらいかもしれませんが、学習済みデータを作ることと、対戦しながら強くなるプログラムを作ることは少し違うってことです。興味のある方はソースのPlayer.learningメソッドを参照して下さい。
     あと、引き分けの時はどうするかという問題もあったのですが、相手のデータを教師データとして誤差修正するようにしました。学習中のAI側が最強プログラムに対して偶然引き分けに持ち込んだ時でも最強プログラムの指し手を教師データとして学習するようにするためです。

    – 最強プログラムとの対戦結果 –

     上の2つのグラフのうち下側のグラフは以前掲載したグラフと同じ(現在リリース中の「進化する三目並べ(Tic-tac-toe Evo)」と同じ)ものです。上側のニューラルネットワークのグラフは下側のグラフに比べると、一気に学習が進んで引き分け率(対最強プログラムなので勝つことは出来ない)が90%程度に上昇しますが、その後80%〜99%の間を行ったり来たりしています。何度か試しましたがこの傾向は変わらないようで、一様に強くなり続けるというわけにはいかないようです。これが過学習というやつでしょうか?同じプログラム相手に10,000回も学習させる必要はないと言うことでしょう。このグラフを見る限り1,000回程度対戦させれば学習がピークに達するようです。対して従来の方法はニューラルネットワークに比べると学習速度は劣りますが、学習がピークに達した後も安定して指し手を間違えない(負けない手、最善手を選ぶ)ようです。

    – 乱数プログラムとの対戦結果 –

     乱数で指し手を決める弱いプログラム相手でも、今までより対戦回数が少ない段階で勝率が上がっていることがわかります。個人的には重みデータの総量が減ったことが学習速度がアップした大きな要因(過去記事参照)になった気がしてます。

    学習速度アップは歴然

     過学習という問題はあるものの、ニューラルネットワークを採用することでご褒美を上げたり取ったり(足したり引いたり)するより学習速度がアップすることは間違いないようです。でも現在リリース中の「進化する三目並べ(Tic-tac-toe Evo)」「STATISTICS HACKS」に書かれている仕様に合わせて作っていることを謳っているので今のまま変更せずに、次アプリにする予定の「消える三目並べ」に採用してみようと思ってます。試してみたいと思うテーマが次々と出てきてなかなかリリース出来ないのですが、どこかでまず一度リリースしようと思ってます。本当は「5五将棋」アプリを作りたいのですが…:sweat_smile:


    1. ディープラーニングやニューラルネットワークに関する本をいろいろ読みましたが、個人的にはこの本が一番実践に役立つ気がします。 

    2. なぜ勝ちは+3,引き分けは+1,負けは−1がいいのかという根拠は「STATISTICS HACKS」にも明確には書かれていません。 

    3. 今までのやり方だと最強プログラムと対戦した場合には引き分けに持ち込んだ時にしか重みの加算が行われない状態でした(最強プログラムには絶対勝てないので+3を得る機会はない)。 



    blog comments powered by Disqus