19 March 2017

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

     以前の記事の最後に「消える三目並べ」(3手前に打った自分の駒が消えるルールの三目並べ)の機械学習を使ったAndroidアプリを作ってみたけど、データが大きすぎて実用に堪えなかった話を書きました。いろいろ解決策を模索した結果、とりあえずデータが大きくなり過ぎる問題は解決しそうですがその話は改めて書くとして、今回はその新しく作ってみた機械学習プログラムのテストを兼ねて実施した学習度合いの進捗テストについてまた書いてみます。
     前回は先手と後手をランダムに決めてソフト同士の対戦をしたのですが、「消える三目並べ」というゲームの特性上、先手の時は最善手を選び続けると必ず勝つはずなのでその違いがわかるように先手の時と後手の時を分けてデータを取りました。前回の時はデータを取った後で気づいて後悔していたのでちょうどいい機会が出来ました。
     前回同様100回の対戦を1回戦として対最強プログラムは50回戦(=5,000回)、対乱数プログラムは100回戦(=10,000回)の対戦結果です。

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

    対最強プログラム

     機械学習プログラムが先手で最強プログラムと対戦した黄色のグラフを見ると、600回程度の対戦までは一度も勝てなかったのにその後急激に勝数を伸ばして先手なら必ず勝てることを学習した様子がよくわかります。この結果は前回と同じですが、前回の記事では、先手・後手をランダムに決めていたので勝率が約50%にまでしか伸びませんでしたが、今回は先手番限定のテストなので100%にまで勝率を伸ばしています。勝率100%まで行ってから90数%に何度か勝率を落としていますが、これは確率による指し手の選択をしている以上仕方がありません。MIN-MAX法で11手先までの全局面を完全に読み切って常に最善手を選ぶ最強プログラムに対して、機械学習プログラムの方は経験(モンテカルロ法による強化学習)から最善手を選ぶ確率を上げているだけなのでこうなります。将棋や囲碁のように今のコンピュータでは全局面探索出来ないゲームに関して、機械学習が重宝されているのも頷けます。
     今度は後手の時のグラフ(水色のグラフ)を見ると、最強プログラムに一度も勝てないままグラフでは見難いのですが0のまま横一直線のグラフになっています。先手必勝のゲームで後手番を持って最強プログラムと対戦しているわけですから一勝も出来ないのは当然の結果です。これはテストに使用している最強プログラムにバグがない(先手番では必ず勝つ)ということでもあるので安心しました:smile:あと、先手必勝のゲームをアプリにして楽しいのか?という問題もあるのですが、先手必勝と言っても11手読みが必要なので人間ではなかなか難しいのではないかと思います。「どうぶつしょうぎ」も後手必勝のゲームだそうですが、人間が遊ぶ分にはそれなりに楽しめるのではないかと思ってます。自分が試している感じではとても先手番になったからと言って必ず勝てるとは思えない「消える三目並べ」ですが、それを極めるのも楽しみ方の一つかもしれません。
     ところで、後手必勝らしい「どうぶつしょうぎ」で、「自分が後手なら必ず勝てる」と言い切れる人ってどれ位いるのでしょうか?興味があります:smile:

    対乱数プログラム

     次に対乱数プログラムにおける勝率の推移を見てみると、先手番(赤色のグラフ)の方が明らかに後手番(緑色のグラフ)より速く学習が進んでいます(勝率の上がり方が速い)。これは機械学習プログラム自身が「消える三目並べ」というゲームの特徴を見出したと表現していいのでしょうか:question:「どうやらこのゲームは先手の方が勝ち易いぞ」ということをAI自身が発見したと:confused:
     機械学習プログラムが最強プログラムと対戦して、勝てるはずの先手の時に勝つことを学んでいくのはなんとなく分かるというか、最強プログラムという先生に教わっていくのだから強くなるのだろうと理解できます1。でも先生でもない単にサイコロを振るように決めた手を選択する乱数プログラムと対戦させて、先手と後手で傾向の違いが出るというのがちょっと意外でした。「何を言ってるんだ、乱数を使うからモンテカルロ法による強化学習だろ」と言われるのかもしれませんが、先手と後手で学習度合いに違いが出るのであれば、もしかしてこれを将棋に応用したら将棋というゲームが先手必勝か、後手必勝か分かるのではないか:flushed:と思ったわけです。将棋版の機械学習プログラムとランダムに指し手を決める将棋プログラムを用意して対戦させてみればいいだけです。そして先手の時の方が後手の時より勝率の上がり方が速ければ将棋は先手必勝のゲームと推測出来るように思えます。将棋で起こりうるすべてのパターンを確認しなくても、何万回か対戦させれば傾向がわかるのではないか?と。でもよく考えてみると将棋の場合はランダムに指し手を決めて対戦させてみてもゲームがなかなか終わってくれないので、囲碁やオセロのようにマス目が埋まれば必ず終わるゲームと違って難しいのでしょう:disappointed:おそらく2。「消える三目並べ」もマス目が埋まれば終了する類いのゲームと違う(長い対戦では20手以上続きます)ので将棋と事情は同じなのですが、「消える三目並べ」程度の局面数ならなんとかなるということでしょう。最強プログラムで使用している先読みと評価関数を使ったやり方も機械学習を使ったやり方も、将棋というゲームの完全解析(先手or後手必勝定跡の発見等)は指数爆発(組合せ爆発)の壁があるので難しいという事情は同じだということでしょう。
     ただ、今回のテスト結果を見てもわかる通り、ソフトを学習させる場合にはヘボ将棋の棋譜(対乱数プログラム)を使うより、プロ棋士の棋譜(最強プログラム)を使うほうが速く学習するのは間違い無さそうです。


    1. たとえ理屈は分かって無くても結果が得られるところが機械学習プログラムの良いところです。 

    2. ゲームの終盤近くになった時に、ゲーム終了までをモンテカルロ法で読み切って指し手を選択するというプレイアウトと言う手法がありますが、マス目が全て埋まったら必ず終了する囲碁と違って将棋の場合は効果を上げることが難しいのだと思います。 



    blog comments powered by Disqus