Tic-tac-toe Evo

    「Tic-tac-toe Evo」について

     今まで「進化する三目並べ(Tic-tac-toe Evo)」として公開していたアプリをGoogle Playがアプリ公開の要件を強化するのに伴ってリニューアルしました。新機能も追加しデータの互換性もない1ので新しい別アプリとして公開しています。
     モンテカルロ法を使った強化学習によって対戦する毎に強くなります。対局終了時に「勝てばそれまでの指し手に加点、負ければ減点」することによって学習していきます。プログラム内でやっていることは「Statistics Hacks」という統計学の本で紹介されていた強化学習の内容とほぼ同じです2
     旧アプリは近々削除する予定です。

    ※ 進化の過程について

     三目並べプログラムの学習度合いによって「ピロリ菌」から「人」まで、学習度合いをいろんな生物に例えて画像を表示しています。「系統樹」「進化」等をキーワードにしてネットで調べながら自分なりに選んだ生物の画像を表示しています。必ずしも人類の進化の過程を正しく表現しているわけではありません。「僕たちの祖先をめぐる15億年の旅」というサイトを参考にさせていただきました。

    旧アプリとの違い、追加機能

    • 二ヶ国語対応(日本語、英語)
    • 今までの画像による進化度合いの表現に加えて重みデータを数値で視覚化
    • 自己対戦機能追加

    使い方

     先手は×、後手は○で縦、横、斜めに三目並べたら勝ちです。AIと対戦した場合、対戦終了毎に学習データを更新し、AIが徐々に強くなっていきます。最初の内は簡単に勝てますが、徐々に勝てなくなるでしょう。

    先手・後手:

     先手・後手それぞれAIが選択できます。AI同士の対戦では一瞬で勝負が付きますので、対局画面下の<<,<,>,>>マークをタップしてゲーム終了後に手順を確認出来ます。

    先手・後手

    AIの対戦成績:

    AIの対戦成績

    重みデータ表示:

     ゲーム中でもゲーム終了後でも画面左上のチェックマークアイコンをタップすると現在の局面での重みデータを表示します。5秒経つと消えるのでもっと長く表示したい場合はチェックマークアイコンを複数回タップしてください。

    重みデータ確認

     重みデータは既に駒が置かれているマス目は_______で、それ以外のマス目は合計が1になる値で表示します。初期状態では均等に重みが割り振られていますが、学習が進むにつれてこの値が変動し、マス目の値/合計値(=1)の確率でAIが指し手を選択します。一番大きな値の箇所を選択するのが最善だとAIが学習しているということです。

    学習データの初期化:

     アイコンを長押しして表示される「アプリ情報」メニューから「データを消去」を選べば、Androidの機能を使って学習データの初期化が出来ます。

    データの初期化

    「進化の度合い」の数値(%)について:

     すべての局面データから「あと一手でラインが揃う局面」を検索して「どれぐらいの確率で相手が三目揃うのを防ぐか(期待値)」を計算して「進化の度合い」としてアプリに表示しています。100%にはなりません、学習の進捗度合いを表す一つの目安と考えてください。

    進化度合い

    過去のイラスト表示

     スワイプ操作で過去に表示されていた画像を再度表示できます。画像の上に指をおいて左または上にスワイプすると「戻る」右または下にスワイプすると「進む」です。
     過去の画像が見れるだけで、この先どんな動物に進化するのかは見ることは出来ません。「人」まで進化したらすべて見ることが出来ます。「人」の先はどうなるのか、それはやってみてからのお楽しみということにしておきます。

    スワイプで画像の移動

    学習過程を観察

    例1:

    初期状態1

     インストール直後でAIとの対戦をしていない初期状態ではすべての空いているマス目の重みが合計1になるように割り当てられています。上の図では0.1111 * 9 = 1.0(切り捨てて表示)

    初期状態2

     一手進んだ上の図では0.1250 * 8 = 1.0。AIは次の手を数値の確率で選びます。学習が進んで表示上0.000001.00000になることがありますが、小数点以下6桁目を四捨五入して表示していますので内部の数値は01にはなりません。0.00000と表示されていてもそのマス目を選ぶ可能性がありますし、1.00000と表示されていてもそのマス目以外の箇所を選ぶこともあります。

    例2:

    ゲーム例1

     インストール直後の初期状態から上記のようにゲームが進行した後に<<マークで初手の局面に戻して画面左上のチェックマークをタップすると、以下のように真ん中のマス目の重みが増加しています。初手に真ん中を選んだ先手(×)が勝ったので真ん中を選んだ手が良い手だったと判断し報酬を得ました(重みが増加)。

    ゲーム例1、初手

     二手目の局面でチェックマークをタップすると以下のように右上のマス目の値(重みデータ)が減少しています。後手(○)はこの局面で右上を選んで負けたので罰を与えられました(重みが減少)。こういう作業を繰り返すことでどの局面でどの手が最善かを学習していきます。

    ゲーム例1、二手目

     このようにゲーム終了後に勝った方の手を良い手、負けた方の手を悪い手と判断し、全ての局面の重みデータを修正していくことで学習し、徐々に強くなっていきます(モンテカルロ法による強化学習)。

    例3:

    ゲーム例2

     上の局面では次に後手(○)が中央下部分を選ばなければ負けてしまいますが、重みデータは0.52858となっていて約53%の確率でしか選ばない状態です。学習が進むにつれてこの値が1.00000に近づいていきます。

    AIの学習の進捗(進化の進捗)例

     おおよそ3,000回ぐらいの対戦をすると学習が完了(「人」にまで進化)します。

    自己対戦のみ:

     下のグラフはAIの自己対戦機能を使って10,000回対戦した場合のゲーム結果(勝ち・負け・引き分け)の推移を表しています。

     三目並べはお互いに最善手を選ぶと引き分けになりますので、AIの学習が進めば進むほど引き分けの割合が高くなります。自己対戦のみだと現れにくい局面が生じて、若干学習が遅くなります。

    最強プログラムとの対戦(≈人間との対戦):

     下のグラフはこのアプリとは別の方法で作成した絶対負けない最強プログラム(人間との対戦に近いと思われます)との対戦経過です。

     最強プログラムとの対戦なのでアプリ側が勝つことはないのですが、学習が進むにつれて引き分けに持ち込む可能性が高くなっていきます(間違った手を選ばなくなる)。自己対戦だけの時より若干速く学習が進むようです。
     出来るだけ考えられるすべての手順を使ってAIに対して厳しく勝ち続けることが進化を速めます。


    1. データの互換性がないのはCoffeeScript1.xxからCoffeeScript2に変えたことによるものです。 

    2. この本に関する内容はここここここなど、ブログ内で散らばっていますので興味のある方はご参照ください。Rubyのソースも公開していますが、アプリ内でやっていることは本の内容に沿って作ったシンプルな加減算による強化学習です。