19 September 2016

    進化する三目並べ 進化する三目並べ Ruby版のソース

    「進化する三目並べ(Tic-tac-toe Evo)」について

     「進化する三目並べ(Tic-tac-toe Evo)」は、「Statistics Hacks」という統計学の本に紹介されていた強化学習の内容に興味を持った私が自作したRubyのPC用のプログラム(githubに公開している)を、せっかく作ったのだからスマホアプリにして公開してみようと考えて、CoffeeScript(JavaScript)に書き換えてCordovaを使ってスマホアプリに作り変えたものです。
     詳しくは「算数で作る機械学習プログラム」というタイトルから始まる一連の記事を読んでいただきたいのですが、ここではスマホアプリに関する内容に限定して特有の機能などについて補足していきたいと思います。プログラミングに興味の有る方はソースコード(github)も見て下さい。
     アプリにもこの記事のリンクを追加していますので、サポートページとして使っていくつもりです。

    ※ 進化の過程について

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

    タッチエフェクト機能追加(ver1.3.6)

     タッチ操作にアプリの反応が遅れているだけなのかタッチ操作が効かなかったのかの区別が付きにくい時があるので、少しでもイライラを無くすために、タッチしたマス目が白っぽくフェードアウトしていく視覚効果を付加しました。

    タッチエフェクト(バージョン1.3.6以降) タッチエフェクト

    手番表示機能追加(ver1.3.6)

     アプリで×が先手と決めていることもあって、盤面を見れば次の手番は×か◯かは一目瞭然なので表示していなかったのですが、次にリリース予定の「消える三目並べ」(×3個、◯3個の局面が長々と続くため局面を見ただけでは次の手番がわからない)に備えて表示するようにしました。

    手番表示(バージョン1.3.6以降) 手番表示

    Twitter投稿機能追加(ver1.3.5)

     SNS機能追加のプラグイン(cordova-plugin-x-socialsharing)を組み込みTwitter投稿を可能にしました。プラグインの機能自体はメールへの画像添付やBlueToothでの画像送信も出来るようですがすべての機能を試したわけでもなく、端末によっては使用できない可能性もあります。

    Twitter投稿ボタン追加
    (バージョン1.3.5以降)
    Twitterボタンスクリーンショット

    学習速度の向上(ver1.3.0)

     詳しくはこの記事に書きましたが、学習速度を改善しました。今までのものは、なかなか進化しなくてすぐに飽きてしまった人もいると思いますが、これでかなり改善されたのではないかと思います。但し、学習データの互換性がなくなったので、1.3.0以前のバージョンをお使いの方は、申し訳ありませんが今まで学習した(進化した)分が初期化され、一から(ピロリ菌から)やり直しになってしまいます。でも進化の速度はかなり速くなったので、旧バージョンをそのまま使うより新バージョンに乗り換えたほうがすぐに進化が追いつくと思います。

    ウナギに進化するまで約2,000回対戦
    (1.3.0以前のバージョン)
    旧バージョンスクリーンショット

    約600回の対戦でウナギに進化
    (バージョン1.3.0以降)
    新バージョンスクリーンショット

     あと、今までの一手毎にゲーム木を生成するバージョンはdynamicブランチに移動し、今回のバージョンをmachinelearningブランチにしています。

    過去のイラスト表示(ver1.2.2)

     現時点での学習状況(進化の度合い)をイラストで表現しているわけですが、過去に表示されていたせっかくのかわいいイラストを見ることが出来ないのはもったいないと思ったので、スワイプ操作で過去に表示されていた画像を再度表示できるようにしました。画像の上に指をおいて左または上にスワイプすると「戻る」右または下にスワイプすると「進む」です。
     あくまで過去の画像が見れるだけで、この先どんな動物に進化するのかは今まで通り見ることは出来ません。「人」まで進化したらすべて見ることが出来ます。「人」の先はどうなるのか、それはやってみてからのお楽しみということにしておきます。

    デリケートなカテゴリに分類される広告をブロック(ver1.2.2)

     アプリ説明欄に「お子様と進化を競ってみては」なんて書いておきながら、広告の種類に関して無頓着でした。デフォルトでブロックされている「制限付きのカテゴリ」に加えて、下図のように「デリケートなカテゴリ」もブロック設定しましたのでお子様にも安心して遊んでいただけると思います。

    アプリの広告設定

    アプリの更新について

     Google Playからインストールした場合は、Google Playアプリのメニューから「マイアプリ&ゲーム」を選んで「更新」のリンクをタップすれば今までの学習データを引き継いだまま更新できます。Amazon App Storeからインストールした場合は、Amazonから送られてくる更新通知を待って更新してください。旧バージョンを削除してから最新バージョンをインストールすることは可能ですが、そうすると対戦成績や学習データが初期化されてしまいますので気をつけてください。

    イラストのアニメーション機能追加(ver1.1.8)

     TexturePackerを使用して画像をスプライトシート化しました。この件に関してはどんな作業が必要だったか近々別の記事を書くつもりです。絵心があればもう少し凝ったアニメーションを付加したかったのですが、今後収益化出来そうならどなたか絵師さんに発注するかもしれません。

    大画面端末(タブレット)対応(ver1.1.8)

     タブレット端末を持っていないのでiosシミュレータで確認しているだけですが、おそらく大きな端末でも違和感なく使えると思います。今にして思えば、リリース時からやっておくべき作業だったと思いますが、自分がタブレット機を持っていないのと、学習機能のアルゴリズムがちゃんと動作しているかばかり気にしていてすっかり頭から抜け落ちていました。

    スプラッシュ画像追加(ver1.1.8)

     スプラッシュ画面は要らないと思っていたのですが、せっかくCordova使って開発しているので一応ios対応しておこうと思い、iosシミュレータで起動時に表示されるCordovaアイコンを消そうと調べながらいろいろ作業していたら勝手に付加されました。

    github上のソースと違う点(ver1.0.3)

    1. アプリの学習効率
    2. 学習度合い(進化の度合い)を表す指標の追加
    3. 全局面のツリー構造生成の仕方
    4. データの読込・保存

    1.アプリの学習効率について

     このアプリの「進化」とは、学習の進捗度合いのことです。学習レベルを表すのに人類の進化に例えれば面白いかなと考えて「進化する三目並べ」としたしだいです。  今まで数回に渡って強化学習について学習効果のグラフの記事を書きましたが、この記事で紹介した「線形関数を使って、終盤の手ほど重要視する」やり方をアプリに採用しています。リリース直前に行った最強プログラムと乱数を使ったプログラムとの対戦テストの結果は以下です(1,000回の対戦を1回として100回の対戦、合計100,000回)。

    回 \ 対戦相手  最強プログラム    乱数プログラム  
      1回戦  0勝540敗460分 481勝383敗136分
      2回戦  0勝424敗576分 518勝352敗130分
      3回戦  0勝318敗682分 567勝315敗118分
      4回戦  0勝270敗730分 574勝310敗116分
      5回戦  0勝191敗809分 618勝261敗121分
      6回戦  0勝136敗864分 617勝271敗112分
      7回戦  0勝120敗880分 637勝242敗121分
      8回戦  0勝118敗882分 677勝217敗106分
      9回戦  0勝 99敗901分 663勝219敗118分
     10回戦  0勝 74敗926分 664勝240敗96分
     11回戦  0勝 60敗940分 708勝181敗111分
     12回戦  0勝 40敗960分 693勝209敗98分
     13回戦  0勝 33敗967分 685勝209敗106分
     14回戦  0勝 34敗966分 685勝200敗115分
     15回戦  0勝 24敗976分 717勝190敗93分
     16回戦  0勝 21敗979分 697勝182敗121分
     17回戦  0勝 20敗980分 731勝164敗105分
     18回戦  0勝 13敗987分 750勝159敗91分
     19回戦  0勝 14敗986分 732勝163敗105分
     20回戦  0勝 15敗985分 747勝144敗109分
     21回戦  0勝 15敗985分 725勝178敗97分
     22回戦  0勝 11敗989分 732勝177敗91分
     23回戦  0勝 17敗983分 734勝168敗98分
     24回戦  0勝  7敗993分 766勝148敗86分
     25回戦  0勝  9敗991分 751勝150敗99分
     26回戦  0勝 15敗985分 761勝149敗90分
     27回戦  0勝 12敗988分 740勝158敗102分
     28回戦  0勝  8敗992分 763勝143敗94分
     29回戦  0勝 11敗989分 743勝153敗104分
     30回戦  0勝 13敗987分 767勝142敗91分
     31回戦  0勝  8敗992分 748勝149敗103分
     32回戦  0勝  5敗995分 762勝136敗102分
     33回戦  0勝 23敗977分 775勝137敗88分
     34回戦  0勝  4敗996分 760勝146敗94分
     35回戦  0勝 13敗987分 753勝141敗106分
     36回戦  0勝  7敗993分 803勝116敗81分
     37回戦  0勝  7敗993分 768勝124敗108分
     38回戦  0勝  6敗994分 771勝147敗82分
     39回戦  0勝  3敗997分 789勝114敗97分
     40回戦  0勝  6敗994分 792勝127敗81分
     41回戦  0勝  4敗996分 768勝132敗100分
     42回戦  0勝  8敗992分 785勝119敗96分
     43回戦  0勝  4敗996分 790勝118敗92分
     44回戦  0勝 13敗987分 794勝121敗85分
     45回戦  0勝  2敗998分 792勝116敗92分
     46回戦  0勝  5敗995分 791勝127敗82分
     47回戦  0勝  6敗994分 777勝124敗99分
     48回戦  0勝  2敗998分 801勝112敗87分
     49回戦  0勝  6敗994分 805勝105敗90分
     50回戦  0勝  6敗984分 766勝153敗81分
       :  : :
     91回戦  0勝  4敗996分 831勝98敗71分
     92回戦  0勝  4敗996分 821勝82敗97分
     93回戦  0勝  3敗997分 838勝86敗76分
     94回戦  0勝  5敗995分 821勝106敗73分
     95回戦  0勝  1敗999分 824勝96敗80分
     96回戦  0勝  2敗998分 820勝107敗73分
     97回戦  0勝  0敗1000分 818勝88敗94分
     98回戦  0勝  2敗998分 832勝94敗74分
     99回戦  0勝  4敗996分 832勝99敗69分
    100回戦  0勝  1敗999分 797勝102敗101分

     上の表の通り、最強プログラム(バックトラック法でゲーム終了まで読み切るので負けることがない)と対戦させたほうが学習効率がいいのは一目瞭然(「強い人と対戦するほど進化が速い」とアプリ紹介欄に書いているのはこのことです)ですが、大まかに言って90%負けない(=100敗を切る)ようになるまでに9,000回、99%負けない(負け数が一桁になる)ようになるまでに24,000回程度の対戦が必要になることが上記テスト結果からわかります。ただ、テストで使用した最強プログラムは常に最善手を選ぶ(最短手数で勝つ)わけではないですし、内部で乱数を使用していないのでいつも同じ手しか選ばないので、人間が対戦すると実際にはもう少し速く学習が進む余地はあると思っています。だから正直なところ実際にどれ位の速度で学習(進化)するのか自分でもわかっていません。

    2.アプリの「進化の度合い」の数値(%)について

     Androidアプリにするに当たって学習効果をどのようにユーザーに伝えようかと考えたのですが、今までブログでやっていたグラフ表示だけでは面白くない。また、上記のような対戦成績はどの程度学習が進んだかの指標には使えません。人間がわざと負けてアプリの勝率が上がれば「進化した」なんて言えるわけありませんし、対戦する人間が強くても、乱数プログラムのように弱くても、対戦回数を重ねるだけで学習が進むからこそ人工知能(AI)と言えるわけですから。  そこで最初は現時点で保持しているすべての局面データからすべてのリーチ1が掛かっている局面を検索して「どれぐらいの確率で勝ちを逃さないか」を計算したのですが、それよりも「どれぐらいの確率で相手が揃うのを防ぐか」を計算した値のほうが上記の対戦成績と似た推移を示したのでその値を「進化の度合い」としてアプリに表示しています。これは人間同士の対局でも同じで、まずは相手が三目揃うのを防ぐ手を優先すると思うので学習度合い(進化度合い)を示す指標としては割りと妥当じゃないかと思ってます。

    進化度合い

    3.局面のツリーデータ生成について

     githubのRubyのソースでは起動時にすべての局面のデータ(多分木データ)を生成しますが、Cordovaアプリ(ハイブリッドアプリ)ではブラウザ(WebViewというブラウザーコンポーネント)上で動くのでネイティブアプリに比べて動作が遅いので、起動時にすべての局面を生成すると2分ぐらい掛かってしまいます。だから初めての起動時は初期局面のみ生成し、未知の局面が現れる度にそのノードに紐づく子ノードを動的に生成するようにしています。

    4.データの読込・保存・初期化

     ツリーデータの保存・読込はlocalStorage.setItemとlocalStorage.getItemを使っています。データベースは使っていません。  アイコンを長押しして表示される「アプリ情報」メニューから「データを消去」を選べば、Androidの機能を使って対戦成績と学習データの初期化が出来ます。

    データの初期化

     あと、もともとRubyのコンソールアプリを元にしているため画面出力に関わるメソッドがgithubのソースとは別物になってます。


    1. あと一手で勝ちになる局面 



    blog comments powered by Disqus