27 May 2017

    全然強くない

     前作(「進化する三目並べ(Tic-tac-toe Evo)」)と同様の機能のまま「消える三目並べ」(3手前に打った自分の駒が消えるルールの三目並べ)のアプリをリリースしようと思っていたのですが、いざ作成した「消える三目並べ」のアプリをスマホにインストールしてテストしてみるとあまりにもAIが弱い。それに前作の通常の三目並べ版だと学習データが真っさらの状態から300回程度対戦すると先手の時はほぼ必ず真ん中に駒を打つようになり、成長する過程が実感できるのに対して、「消える三目並べ」版だと強くなっていく過程が全然実感できませんでした。自分が「消える三目並べ」というゲームに慣れてきて強くなった所為もあると思いますが…。
     と、いうことでAIの成長を実感できないので前作のように進化する過程を画像で表現する機能はやめて、とりあえずもう少し強くする方法を試行錯誤しました。AIが思ったほど強くならないのは、やはり通常の三目並べの全局面数が6,046ノード(回転・対照形を省くと627ノード)1であるのに対して、「消える三目並べ」では79,210ノード2と2桁以上増える違いは大きかったようです。

    なかなか強くならない原因

     以前「「消える三目並べ」は、学習が速い」という記事で、MIN-MAX法を使った最強プログラムと1,500回程度対戦させると、勝ち負けがほぼ互角になることを書きました。最強のプログラムと互角なので十分強いだろうと思っていたのですが、最強プログラムの方はいつも同じ手を指すようになっていたので私がテストに使った自作の最強プログラムに対してだけ強くなっているだけのことでした:sob:
     ちょっと考えれば分かりそうなものですが、通常の三目並べならそれで上手くいっていたので深く考えてませんでした:cold_sweat:もちろん通常の三目並べのテストで使用した最強プログラムも、いつも同じ手で勝つプログラム(プログラム内で乱数を使用していない)でしたが、通常の三目並べの場合ノード(局面のパターン)の数がたった627ノードだったので、数千回の対戦でほぼすべてのノードに対して何度も学習データが蓄積されていきますが、「消える三目並べ」で数千回対戦してもほとんどのノードの学習データは初期状態のままです。同じノードに対して何度も何度も学習データを蓄積していく必要があるため、例え数千回対戦させたとしても十分ではなさそうです。
     前作(「進化する三目並べ(Tic-tac-toe Evo)」)は、AIの成長過程を楽しんで貰うという意図もあったのですが、「消える三目並べ」では一回の対戦で得られる学習効果が非常に薄いため成長を楽しむのは無理そうだと思い、学習度合いを生物の進化に例えて表示する機能は取りやめることにしました。

    弱すぎるアプリの改善方法

     アプリが弱すぎることの解決策として予め学習済みのデータをアプリの初期データとして同梱してリリースすることにしたのですが、まずテストに使用しているMIN-MAX法を使った最強プログラムに修正を加え、いつも同じ手を指さないように局面の評価値が同じ場合はその都度2分の1の確率で指し手を分散させるようにして学習させることにしました。その状態で勝数の遷移をグラフにしたものが以下です。

     ※範囲をドラッグすれば、グラフを zoom up 出来ます

     赤と黄色のグラフは以前の記事と同じものです。今回同じ評価値なら指し手をランダムに変更するように改良した最強プログラムとの対戦勝率(水色のグラフ)は5,000回対戦後でも30%程度でまだまだ学習が足りないのがわかります。今まで同じ指し手しか選ばない最強プログラムでテストして、勝率5割になったから学習完了した(=強くなった)と勘違いしていたわけです。本来なら最初からこのプログラムでテストするべきでした:cold_sweat:。このプログラムを使って作った学習データをアプリの初期データとしてリリースしようかと思ってます。でも、以前にも書きましたが最強プログラムとの対戦テストは時間が掛るのが辛いところです。このわずか5,000回の対戦データを作成するためにCore i7-2600KのPCを約3日間稼働しっぱなしでした。
     ちなみにグラフにはしませんでしたが、対乱数プログラムとの対戦テストなら対最強プログラムのように時間はかからないので100,000回まで試してみました。すると勝率(赤のグラフ)は9割以上まで伸びました3が、その学習データを使ってアプリにして遊んでみても全然強さを感じさせるものにはなっていませんでした。以前から書いてますが、いくら乱数プログラムとの対戦学習(モンテカルロ法を使った強化学習)を続けても効果は薄そうです。

    その他の方法

     学習させたい機械学習プログラム側の学習データ作成部分だけを使用して最強プログラム同士で対戦させれば、最強プログラムの指し手そのものを学習データに反映させることもできます。これはプログラムが自分で学習するのとは異なり、最強プログラムの手を真似るデータを定跡データとして学習データに反映させていることになります。こうした定跡データを使った方法や、何も学習していない状態から学習プログラム同士で対戦を重ねて学習データを作る方法なども試しましたが、詳しく確認したわけでないですが思ったほど強くなりませんでした。強くなったかどうかをどのように判断してるのかという話もいろいろあるのですが、それほどたいそうな事はしてないのですが話が長くなるのでまた別の機会に書こうと思います。


    1. 「三目並べのゲーム木データを間引く」 

    2. 「消える三目並べ」、思ったより大変」 

    3. 「消える三目並べ」というゲームは先手必勝のゲームなので、先手・後手をランダムに決める条件で勝率9割以上になるというのは、かなりの実力差(乱数で指し手を決めても先手の時は偶然最善手を選び続けて勝つ場合があるため)があると言えると思います。 



    blog comments powered by Disqus