1.はじめに
春休みの自由研究ということで、かねがねやりたいと思いつつも時間がないとかなんとかゴニョゴニョ言っていた「ボードゲームを遊んでくれるAI」に取り組んでみました。とりあえず一区切りつくところまで来たので途中経過の報告みたいな感じです。コードはそのうちGitHubに上げる予定です。
オセロや将棋を機械学習で強くした人工知能にやらせるというのは非常に魅力的で、割とそういうこともやりたいなぁと思って情報系に進んでみたものの、講義でやるのは理論寄りな話や泥臭い作業(人工的な設定のモンテカルロ木探索やありえんめんどい自動微分の実装など)ばかりで、自分からはかなり遠くのものに感じられてちょっとウ〜ンとなっていました。
そこで、せっかく長期休みなのだから自分で何かしらこういうのを作ってみよう、ということで取り組んでみたのがこれになります。題材とするボードゲームは"Kalah"(カラハ)です。Kalahはマンカラというゲームの亜種みたいなものです。
マンカラ - Wikipedia
カラハ - BGAうぃき - atwiki(アットウィキ)
ただ機械学習なんも分からんの状態からいきなり人工知能を作りましょう、も無理な話なので、とりあえず目標を細かく分けてみることにしました。以下がそれになります。
大目標:ボードゲームを作り、対戦相手として実際にプレイする思考ルーチンを機械学習で作る
・中目標A:コマンドライン上でKalahを遊ぶプログラムを作成
・中目標B:ゲームのUIを作成
・中目標C:エージェント(人工知能)を作成
現時点でエージェントの作成まで(中途半端ですが)終了したので、そこまでに何をしたかを記録として残しておきます。あと私は本を買っても全く読まない悪癖があるので、今回は本なしでインターネット全頼りでやってみることにしました。
2.やったことのあらまし
(1日あたりだいたい6~7hくらいです)
2-1.~GUI作成
・Kalahをコマンドライン上で対戦する環境を作成(1日)
・Tkinterを使ってKalahを遊べるGUIを作成(2日)
2-2.DQNでエージェント作成
・資料集め、tensorflowなんも分からんくて大泣き(2日)
・tensorflowに慣れるために、DQNで3*3の超絶シンプルな迷路を解くエージェント作成(2日)
・Kalahをコマンドライン上で遊んでくれるエージェント作成(2日)
3.やったこと
※実装は全てPython3です。
3-1.Kalahアプリ制作
なにはともあれまずはKalahのボードとか作らないと人工知能もクソもないので、とりあえずコマンドライン上でKalahを遊べるようにしました。以下のサイトを参考にしましたが、Classはふわっとした理解なのでちょっと心配です。
Python初心者は練習問題としてリバーシ(オセロ)を実装するべき - 勇気ある加藤の猛り
そしてプレイできるようになったはいいものの、自分が先手しか選べなかったり、なによりコマンドラインの味気ない背景でしか動かせないのも寂しいなあと思ったので、TkinterというPythonのライブラリを使ってGUIを作ってみることにしました。以下に(主に)参考にしたリンクを挙げておきます。
Pythonで「マインスイーパー」を開発 | だえうホームページ
tkinterを使ってはさみ将棋の将棋盤を作る - Qiita
できたものがこちらです(ここにGIFを貼る)
こうやってGUIを作るのは初めてなので慣れないこともあり、素人目に見てもかなりお粗末な感じのUIができましたが、それでもちゃんと動くものを作れた時はちょっとした達成感がありました。この時点ではCPUは合法手をランダムに打つだけのダメダメCPUです。
あと、開発環境はmacbook proなのですが、Tkinterを普通に使うと強制終了してしまうのでセーフモードで走らせていました。これどうにかならんかな......
コードは以下になります
warehouse/kalah_play_on_gui.py at main · Syuko4omi/warehouse · GitHub
3-2.tensorflowの導入
さて、いよいよKalahの対戦相手になってくれるAIを作ろうというモチベーションも湧いてきたわけですが、機械学習をフルスクラッチするのは無理! 勾配を手作業で出すのはもう勘弁して! ということでライブラリにお任せするために、機械学習の分野では有名らしい(流石に何も知らん自分でも名前くらいは聞いたことがある)tensorflowを導入することにしました。退屈なことはPythonにやらせよう。Pythonすまん。
ウチのMBP君はtensorflow未対応だったので、これを機に入れてみました。AnacondaでPythonを使っていたので以下のリンクの知恵で救われました。
Python3 TensorFlow for Mac 環境構築 - Qiita
Anaconda PromptでのTensorFlowの導入に苦戦した話 - Qiita
3-3.DQNについてちょっと勉強
ボードゲームをプレイする思考ルーチンにも色々種類があると思います。n手先読みをするミニマックス法やネガマックス法、それこそ前述したモンテカルロ木探索等あると思いますが、そういう探索系アルゴリズムは結構授業でやったし正直しんどい実装が多かったので、学習する環境を整えて後は機械が自分でお勉強してねと丸投げする、いわゆる強化学習を実装してみることにしました。
概念的なこと(具体的に何をやっているのかの説明や、アルゴリズムに関すること)は以下のページを読んだり動画を見たりして理解したりしなかったりしました。
ゼロからDeepまで学ぶ強化学習 - Qiita
DQNの生い立ち + Deep Q-NetworkをChainerで書いた - Qiita
【Pythonで再現】DeepMindのDQNアルゴリズムを再現してみた | ブログ一覧 | DATUM STUDIO株式会社
全力で人工知能に対決を挑んでみた(理論編) - ニコニコ動画
強化学習の基本的な考え方 - Qiita
https://book.mynavi.jp/manatee/detail/id=89691
高校数学で理解・実装するニューラルネットワーク - Qiita
https://book.mynavi.jp/manatee/detail/id=76390
ただコード見てても何も分からん......という感じで、1日粘ってみても自力で実装もできそうにない気配だったので、とても簡単なモデルで機械学習の練習をしてみることにしました。
3-4.DQNで3*3のシンプルな迷路を解く(チュートリアル)
次のページは、実際に実装した問題設定になります。DQNの説明も分かりやすかったので本当に助かりました。
DQN(Deep Q Network)を理解したので、Gopherくんの図を使って説明 - Qiita
要は3*3の正方形(9マス)の左下をスタートとして、上下左右の移動をして右上のゴールを目指すことを機械学習させよう、という内容です。1行2列の入力xを現在位置、上下左右の移動の価値を数値的に表現する1行4列の出力yをy = Wx+bとして、Wとbを学習することでxを入力したら適切なyを返すようにしましょうねというのが本旨になります。
例えば真ん中のマスにいるなら、目指すべきゴールは右上に存在するので、yの成分のうち右、もしくは上の移動を表す要素の価値が高くなり、左や下の移動に対する価値が低くなるようにしたい、という話です。
隠れ層なし(つまり入力xに重みWが掛けられ、バイアスbが足されるだけで出力yになる)の最も単純なモデルで1500回の移動を学習をさせてみたところ、結果は以下のようになりました。
Q値のリスト、マス目、 最もQ値の高い移動方向が各列に表示されています。Q値は簡単に言えば行動の価値を表しています。Q値のリストはそれぞれ右、左、下、上に移動する際のQ値を表示してあります。マス目を表す[0,0]は左上(上から数えて0行、左から数えて0列)、[2,2]は右下を表しています。
例えば[2,1]のマス目はスタートから一歩右に進んだマス目なのですが、そのマスで最もQ値が高いのは上方向への移動になっています。上に移動すると[1,1]のマス目になりますが、Q値最大の移動方向は上です。上に移動した[1,0]では右に移動するのが最も良いと出ているので、無事ゴールにたどり着けます。全体的に見ても上、もしくは右方向への移動が良さそうだと学習ができているので、うまくいっていそうな気配がします。
[[0.69636935 -0.30203688 -0.3140987 -0.0802336 ]] [0, 0] right [[1.77409495 0.32050276 0.25299944 1.6524037 ]] [0, 1] right [[2.85182055 0.9430424 0.82009758 3.385041 ]] [0, 2] up [[1.53447878 0.71656002 0.5865594 1.1624039 ]] [1, 0] right [[2.61220438 1.33909966 1.15365754 2.8950412 ]] [1, 1] up [[3.68992998 1.9616393 1.72075568 4.6276785 ]] [1, 2] up [[2.37258821 1.73515692 1.4872175 2.4050414 ]] [2, 0] up [[3.45031381 2.35769656 2.05431564 4.1376787 ]] [2, 1] up [[4.52803941 2.9802362 2.62141378 5.870316 ]] [2, 2] up
1500回の移動やしそんな時間かからへんやろ〜とか思っていたら余裕で二時間かかってひっくり返りました。tensorflowの演算が明らかに遅いのでもっと良いスペックのパソンココが欲しくなりました。
初めてtensorflowを使ってみて引っかかったところなどを以下にあげておきます。
・tensorflowのVariableを実行時に初期化しないと怒られが発生する(セーブした変数の情報をロードする際はこの限りではないです)
サルでもわかるtensorflow:基本的な変数の扱い方 - Qiita
・隠れ層がある場合、重みを全部1で初期化すると重みが全く変化しない(ことがある)。重みの初期化関連の情報でこういう言及を見たことがないのですが、なにか原因があったりするんでしょうか。そのうち調べてみるつもりです。
・experience replay、報酬のclipping、重みの反映を後回しにする等は実装しましたが、これが無いと本当に上手くいかないかどうかは検証していないので分かりません。
・最適化アルゴリズムは最急降下法を使いました。Adamの方がいいぞ(Adamおじさん)という声はちらほらあったのですがなぜかAdamは実行の時点で引っかかってしまいました。
参考にしたページを挙げておきます。以下の四つはかなり参考になりました。
NNの仕組み↓
ニューラルネットワークの基礎 — ディープラーニング入門:Chainer チュートリアル
tensorflowを使った機械学習のシンプルなやつ↓
TensorFlowのチュートリアルのチュートリアル - Qiita
TensorFlowを使ってシンプルなニューラルネットワークモデルを作ってみる - 株式会社ロカラボ
同じように迷路を解いていた例(問題設定は別)↓
DQNで自作迷路を解く - Qiita
実装したコードは以下になります
warehouse/meiro_nn at main · Syuko4omi/warehouse · GitHub
3-5.Kalahを遊ぶエージェントの作成
オセロでやってた方のページ(参考にしました)↓
Keras+DQNでリバーシのAI書く - Qiita
四目並べ(まだ読んでないけど面白そうなのでそのうち読みます)↓
kaggleで強化学習をやってみた - 機械学習 Memo φ(・ω・ )
いよいよエージェントの作成ですが、迷路の学習と本質的には同じです。とりあえず何も考えずに、自己対局によって生成した10000局面(およそ250試合)について学習を回しました。
Kalahはだいたい1ゲーム40手以内に決着が着くので、80手を終えるごとにニューラルネットワークの重みを更新することにしました。最序盤では40手ごとに更新でええか〜とか思っていたのですが、40手だと先手ばかり勝ったりして後手の勝つパターンが学習できていなかったので急遽こうなりました。言い忘れていましたが、このゲームは先手がかなり有利です。
マシンスペック的なアレなのかコードを書くのがヘタクソで思わぬ副作用が生じているのか何なのかよくわからないんですが、学習がありえん遅くて丸一日回していても10000局面(40手/1試合くらいなので250試合くらい?)しか学習できなかったというのが正直なところです.....。
最後に対ランダムで10000試合行わせました。先手勝率: 3642/5000(72.84%)、後手勝率: 4201/5000(84.02%)となりました。
ただ勾配の係数(optimizerの刻み幅的なアレ)が0.01とか小さすぎて実際は途中から学習が進んでいなかったようで、4000局面(約100試合)見た時点でも既に先手勝率: 3658/5000(73.16%)、後手勝率: 4115/5000(82.3%)となっていたので、あまり良い学習ができていなかったと思います。ちなみに自分も戦ってみましたが、先手後手いずれもこちらの勝ちだったので強さ的にはまだまだだと思います。
それでも自己対局しただけでもそこそこランダムには勝ち越せるようになっていたので、実装の方向性は間違っていなかったような気がします。ズブの素人に負けるAIはカッコ悪いので、後編ではバチバチに強く育てたものを作りたいです。あと作ったGUIと組み合わせてアプリ上で対戦できるようにもしたい。
後編へ続く