23 November 2016

    「消える三目並べ」の対戦結果

     前回の記事で「消える三目並べ」(3手前に打った自分の駒が消えるルールの三目並べ)の機械学習プログラムと最強プログラム(MIN-MAX法、αβ法を使った11手読みのプログラム)と対戦させて、機械学習プログラムが一回も勝てなかった話をしましたが、どこが悪いかは分かっていたので今回機械学習部分の修正が完了したものと再度対戦させてみました。通常の三目並べより対戦に時間がかかるので最強プログラムの方は100回の対戦を1回として50回戦、乱数プログラムは100回戦の対戦結果です。

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

     黄色の線のグラフを見てください、最初の600回は最強プログラムに対して全く勝てなかったのが、その後100回に数回の割合で機械学習プログラムが勝つようになり、1000回戦目辺りから急速に勝ち星を伸ばして1500回戦後ぐらいからはほぼ互角(勝率5割)の対戦成績が続いています。前回の記事でも言及したように「消える三目並べ」というゲームは先手必勝なのですが、わずか1500回の対戦でそのことを学んだようです。先手・後手はランダムに決めて対戦テストをしていますので、約50%の確率で最強プログラムに勝つことが出来るということは、学習深度がほぼ限界にまで達した(先手の時は勝てる)と言えると思います。ただ、毎回最後まで読み切って先手のときには必ず勝つ「最強プログラム」と違い、「機械学習プログラム」の場合はあくまで最善手を選択する確率が高くなるだけですので、MIN-MAX法を用いた最強プログラムのように「必ず勝つ」とは限りません。だから、グラフの推移も時々5割以上勝つ時はあるものの、5割弱の数値(100回の内50回弱)で推移しているところに特長が出ていると思います。限界に達したというのはあくまでも「勝てば小石の報酬を与えて、負ければ小石を取り上げる」というこのプログラムの作り方についての表現です(小石の報酬については以前の記事を参照してください)。
     以前の記事で「通常の三目並べ」がほぼ限界まで学習が進むのに約一万回の対戦を必要としたのに、「消える三目並べ」の場合はわずか1500回で済んだのは、ゲームの特性の違いが関係していると思います。機械学習プログラムは「通常の三目並べの最強プログラム」と対戦して、最善手を指し続けて引分に持ち込めば報酬を貰えるわけですが、あくまでも引分の分のみの報酬(小石)です。勝利の味を味わうことが無いまま学習を続けます。それに対して「消える三目並べ」は引分がないので、「消える三目並べの最強プログラム」に勝てばより多くの小石の報酬を貰うことが出来るので「通常の三目並べ」に較べてメリハリが効いて学習速度が上がったのではないでしょうか。1

    対戦テスト後の小石の報酬

     |1|2|3|
     |4|5|6|
     |7|8|9|
    

     5000回の最強プログラムとの対戦テスト後に、機械学習プログラムの小石の数(score配列)の中身を確認すると、上記の初期盤面9箇所に対応する値は以下のようになっていました。

      1:0.49880952380952337 2: 0.30714285714285683 3:0.703571428571428
      4:0.49523809523809537 5:0.249981962481963 6: 0.5761904761904751
      7:0.1738095238095236 8:499.9101323384054 9: 0.2321428571428563

     8の位置(辺の位置)がダントツで大きい数字になっています。つまり先手の時に初期盤面で8の位置を選べば勝てることを学習したというわけです2。8と同じく他の辺の位置(2,4,6)にうまく分散して欲しいところですが、仕方がないというか、むしろ4箇所は同じものとして扱うようにプログラムを改変出来ればデータ量も減るのでメリットも大きい(回転、対称型の省略)のですが、実際の局面に展開する時の処理がややこしそうなので今後の課題です。

    乱数プログラムのテスト結果

     上のグラフで乱数プログラムのテストだけ10,000回実施していますが、最強プログラムと同じ5,000回実施しただけでは、強くなっているのかどうか確認できなかったからです。5,000回対戦までのグラフを見てもわかる通り、対最強プログラムの対戦結果グラフのような一見して右肩上がりとわかるほどには勝ち星が増えていません。初期状態からほぼ5割の勝ち星を上げていて、その後も対戦を続けているのに勝ち星が増える気配がないので、こんなはずはないと思いながら10,000に回数を増やしてみたわけです。得られた結果はなんとか勝ち星が漸増していると言っていいグラフ形状になっているのではないでしょうか。グラフには10,000回戦までしか表示していませんが、その後、念のため20,000まで対戦させてみると最後の100回の勝率は7割を超えていたので、学習が進んでいくのは間違いなさそうです。ただ、通常の三目並べでもそうでしたが、弱いプログラムと対戦してもなかなか強くならないということでしょう。
     そもそも一般的に機械学習プログラムを何かの予測やシミュレーションに使う場合、学習に使用するデータを選ばなければならないわけですが、三目並べの機械学習プログラムを学習させるためには、乱数プログラムは役に立たないということでしょう、但しプログラム自体のバグを見つけるためのテストとしては有効だと思います。対戦を重ねる度に勝数が減るようでは、プログラムの何処かにバグが有るということですから。
     ちなみに乱数プログラムとの20,000回対戦後の初期盤面のscore配列は以下の通りでした。

      1:78.74922305652922 2: 3.4935515653936715 3:57.53441829242526
      4:13.591606247023199 5:151.80688472679168 6: 2315.8063733952617
      7:98.0014452573806 8:81.55661501027998 9: 236.37938875004835

     最強プログラムとの対戦後と同様に辺の位置である6の場所が最大値になっていて、先手の時の初手は辺の位置が良いことは学習できているようですが、まだまだ学習が足りないという感じですね。

    その他グラフからわかること

     ゲーム終了までの手数を見てみると、対最強プログラムでは漸増していき、対乱数プログラムでは漸減していく傾向があります。最強プログラムには刃が立たずに短手数で負けてしまっていた機械学習プログラムが、学習が進むに連れて負けずに粘れるようになり徐々にゲーム終了までの手数が増えていくわけです。それに対して乱数プログラムの場合はお互い弱い者同士なので、無意味な手でいたずらに手数だけが増えていたものが、機械学習プログラムが強くなるに連れて手数をかけずに勝負をつけることが出来るようになっていったということが読み取れます。

    Androidアプリにしてみると

     PC上でRuby製プログラムでのテスト結果で強くなる(進化する)ことが確認できたので、「進化する三目並べ(Tic-tac-toe Evo)」の別バージョンとしてandroidアプリとしてリリースしたかったのですが、局面の多分木データファイルが大きすぎて動きが重くなり過ぎる(起動に約1分、ゲーム終了毎に学習データ書き込みに約30秒)ので、Cordovaで作るのはとりあえず止めることにしました。元々Rubyのコードを流用したいと思いCoffeeScript(CoffeeScriptはRubyと言語仕様が似ているので移植が簡単です)に書き換えてCordovaを使ってみたわけですが、今度は何か別の方法を模索しようと思ってます。


    1. 勘違いでした。テストに使用していた最強プログラムは常に同じ勝ち方しかしないようになっていたため、限定された指し手に対して学習が進んでいただけで、全く別の手を指すプログラム相手には弱い状態のままでした。詳しくはこの記事を参照して下さい。 

    2. 「消える三目並べ」は辺の位置に初手を打てば勝てる先手必勝のゲームであることは以前の記事にも書きました。 



    blog comments powered by Disqus