強化学習で、強力な「３目並べ」プレイヤーを作る

　この記事は、「強化学習」によって、「３目並べ」の強力なコンピュータプレイヤー（スマホアプリ）の作成をめざした報告です。簡単な問題でも良いので、自ら考え、手法を設計し、実装することは普遍の価値があると思います。

●「３目並べ」で強化学習する背景
　AI囲碁で有名なAlphaGOやAlphaGo Zeroでは、「強化学習」を取り入れているとのことです。強化学習とは、参考文献[1]を引用して、「連続した一連の行動の結果、価値が最大化する（＝報酬が最も多く得られる）行動を自ら学習し、選択していくだけでなく、行動についての評価も自ら更新していくこと」としておきます。

　ここでは、囲碁に比べると非常に単純な「３目並べ」（米国ではTic-Tac-Toeゲーム）で、強いコンピュータプレイヤーを、強化学習で作ります。今さら３目並べ？と思われるかも知れませんが、著名なコンピュータ科学者Donald Michieは、1960年代（約60年前）に、多数のマッチ箱を用いた手作業でこの問題を強化学習させる仕組み[2]を発表しています。また、Donald Knuthも、1958年に、当時の僅か10KBメモリのコンピュータで、Tic-Tac-ToeのLearning Programを書いた[3]とのことです。

●「３目並べ」を強化学習するAndroidアプリ
　これら先人の業績に触発されて、今回、独自に強化学習を設計しました。そして、それをスマホのアプリとして作成（with MIT App Inventor）しました。どんなものかを、まず図１に示します。auto_playモードと、computer-humanモードがあります。いずれのモードでも、「負けた状況に応じてペナルティを科す」という強化学習を行います。それによって、computer playerが段々強くなっていくはずです。

　以下の図２には、両方のモードでの実行画面の例を示します。ここでは、computer playerが先手で"O"を打つことから始めています。強化学習の結果は、後でさらに改善するために、外部記憶に格納したり取り出したりできます。save DBやrestore DBなどのボタンがそれを可能にします。

● 強化学習の方法
　さて、どのように強化学習するのかを簡単に説明します。この「３目並べ」は、先手、後手どちらで始めても、両者がミスしない限り、必ず引き分け（tie）になることが分かっています。ですから、人間を相手にした場合、computer playerは勝つことを目指すのではなく、負けない（引き分けか、運がよければ勝つ）ことを目指します。

　今回のauto_playモードの強化学習では、まず、computerが先手でどこかに"O"を打ちます。それ以降は、相手（"X"）とcomputer player（"O"）は交互に、空いている場所にランダムに打って行きます。そして、computer playerが負けた場合には、その時の局面を記憶して、次回にまた同じ局面になった時に、前回打った場所を避けて打つ確率を高く（打てる選択肢を制限）します。それが強化学習となります。図３は、そのような学習の状況を説明しています。

● 強化学習の性能
　このような強化学習はどの程度の効果を発揮するのでしょうか。それを確かめた一例を図４に示します。上記のようなauto_playモードで、6万回ゲームを行った結果から、1,000ゲーム毎に、computer playerが「負けなかった率」を示しています。最後の方の1,000ゲームにおいては、負けなかった率は、99%に達しています。これをベースに人間と対戦しても、相当に強いと思いますが、もしも負けたら、また強化学習してさらに強くなります！

● MIT App Inventorで作成 
　今回のスマホアプリは、MIT App Inventorで作成しました。強化学習結果の保存と取り出しにはTinyDBを、ボタンの操作には、最近新規に提供された汎用のイベントブロックを利用して、非常に効率的に作成できたと思います。図５に簡単にそれを示します。

参考文献
[1] 強化学習とは？ALPHAGOでも使われている強化学習を丁寧に解説　https://udemy.benesse.co.jp/ai/reinforcement-learning.html
[2] Menace: the Machine Educable Noughts And Crosses Engine, http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/
[3] A guide to building AI apps and artefacts, https://ecraft2learn.github.io/ai/AI-Teacher-Guide/chapter-6.html
[4] http://www.half-real.net/tictactoe/

【補足】

• 図４において、最初の1,000ゲームの学習の結果、computer playerが負けない率がすでに75%近くになっていますが、これは一応納得がいきます。文献[4]によれば、ゲームに決着がつくパタンは全部で255,168あるそうです。このうち、先手（computer player）が負けなかったパタン数は177,264あるとのことです。その比率は約7割になりますので。
• 図４のデータを得るために、auto_playモードを6万ゲーム実行しました。その間、Androidスマホを６時間程度走らせました。途中で中断再開もしました。より高速な学習も可能でしょうが、スマホが過熱発熱しないようにしました！（その後の検討の結果、途中結果を表示しながらでも、もっとスピードアップしても大丈夫なことが分かりました。その場合は、約90分で、図４に相当するデータが得られます。）