ゲームの自動プレイAIに関する妄想

別に上手くなくていいので普通プレイができるAIがあるとTAS制作が色々捗るんだろうなぁと思ったりしてます(まぁ、それが難しいんでしょうけど)。AIだけで人間が作ったTASを超えるのは(ゲームにもよるでしょうが)難しいんじゃないかなと思いますが、逆にテクニックなりバグなりを探す際に自動プレイAIがあると非常に便利そうです。

基本的にバグ探しは数をこなしてナンボだと思いますが、大量に数をこなせるほどプレイヤー人口が多いゲームって全体から見ると少ないんですよね。マイナータイトルは真面目に調べると大抵変な挙動とかバグが新たに見つかりますし。なのでAIでプレイ記録を大量に蓄積するだけでも色々と新しい発見はあるのではないかと思ったりしてます(データだけあっても見るべきところを探すのが大変なので、異常検知システムみたいなものと組み合わせる必要がありそうですが)。

OpenAI GymのFrozenLakeをQ学習で解く

前回はFrozenLakeを自前のアルゴリズムで解いてみました。今回はQ学習をやってみようと思います。

その前に、前回変な結論を出してたので訂正しておきます。前回8x8が通らなかったのは明らかに試行回数不足だと思います。1エピソードあたりの成功報酬が1なので、平均報酬はそのまま勝率を表すことになりますが、通算勝率が 0.88 なら100回中99回勝つ確率は 0.00004 程度なので、10000回では明らかに試行回数が足りないです。実際に1000000回試行したものを提出したら約10万回で通りました(ついでに初手だけ修正)。通算勝率がもう少し悪くてもこれだけ試行すれば通るはずなので、この問題に関してはいい所取り100回より通算勝率を見る方がいいかも?

また、提出前に要求水準を満たしているか調べる方法がないのかと思ってモニタのソースを読んだりしたのですが、よくわからなかったので自前で通算/いい所取り平均報酬を計算するスクリプトを書きました。使い方はモニタが出力したjsonを食わせるだけです。

今回はOpenAI Gymの本来の趣旨通りに強化学習で解いてみることにします。学習法はとりあえずQ学習にします(今のところこれくらいしか知りません)。

前提として、学習ができるためにはある程度の成功体験が必要ということがあります。学習中は何らかの方策に従って探索を行いますが、その探索でゴールに辿り着ける確率があまりに低いと学習が進みにくいと考えられます。簡単な基準として4x4, 8x8それぞれに対し完全なランダムプレイを100000エピソード行い、平均報酬を調べてみました:

環境	平均報酬
4x4	0.014
8x8	0.002

どちらもかなり低い値なので、学習中もゴールに辿り着きやすくなるように方策を工夫するか、もしくは単純に学習回数を増やすなどの対処が必要かもしれないと考えられます。

本題のQ学習に入ります。理論的なことは私より詳しい方がたくさんネット上に資料を上げてくれているので省略しますが、学習の大まかな流れは以下のようになると思います:

• 行動価値関数 Q(s,a) を任意に初期化(テーブルとして保持)
• 以下を一定エピソード数繰り返す:
  • 状態 state を初期化
  • 以下を一定ステップ数繰り返す(ここではターン制限まで):
    • 何らかの方策により行動 act を決定
    • act を実行し、次状態 state_next, 報酬 reward を得る
    • Q(state,act) := (1-alpha) * Q(state,act) + alpha * (reward + gamma * max_a(Q(state_next,a)))
    • state := state_next
    • state が終端状態なら break

少し難しい問題になると状態空間が大きかったりして Q(s,a) をテーブルで持つことが不可能になって関数近似…とかいう話になるようですが、この問題では状態数16, 行動数4なのでそのままテーブルで持てます(というか、この問題を選んだ理由がそれだったりします)。

ここで alpha は学習率、gamma は割引率です。割引率は Q(s,a) が発散するのを防ぐとともに、同じ報酬なら遠い未来より近い未来のものを優先するといった効果をもたらすようです。

学習中の行動は「何らかの方策」により決定されるとしていますが、Q学習ではこの方策は任意ということみたいです。要は状態と行動の全ての組み合わせを網羅できるような方策であれば十分学習を繰り返せば Q(s,a) は正しく収束するということです。

実装ですが、とりあえずシンプルにしたいので「何らかの方策」はランダムプレイでやってみることにします。前述の通りこれだとなかなか成功しないので学習が遅くなりそうですが、そこは回数でカバーすることにします。

パラメータはとりあえず alpha=0.1, gamma=0.99 としました。多少実験はしましたがほとんど野生の勘で決めてます。一応学習自体はできてるっぽいのであまり深く考えない方向で。

以上の設定で10⁶回学習後に10⁶回テストしたところ4x4は問題なく解けました(スクリプト添付)。

同じ設定で8x8も10⁶回学習後に10⁶回テストしてみましたが、通算勝率 0.85, いい所取り100エピソードの平均勝率 0.98 でわずかに足りませんでした。通算勝率 0.85 だと100回中99回勝てる確率は 0.0000015 程度なので、確かに10⁶回のテストでは通らない可能性もあります。そこで同じ設定で学習回数を10⁷に増やしてみましたが、なぜか通算勝率 0.82, いい所取り 0.97 と成績が落ちてしまいました。原因はよくわかりませんが、ブレるということはまだ収束しきっていないのかもしれません。

学習率や割引率をいじったりしてみましたがほとんど成績が落ちるだけだったので、やはり学習時の探索がランダムプレイなせいで成功体験が少ないのが問題なのかと考えました。ということで、学習中にもQ関数を使って行動を決定するようにして、ある程度の探索を保証するためにε-greedy法(確率εでQ関数を無視してランダム選択を行う)を使うようにしてみました。

alpha=0.1, gamma=0.99, epsilon=0.1 で10⁶回学習後に10⁶回テストしてみたところ、一応8x8も解けました(スクリプト添付)。通算勝率は 0.864 で、自前のアルゴリズムに比べると少し劣るのでまだ改善の余地はあるのかもしれませんが、とりあえず通ったのでよしとしておきます。

OpenAI Gym を触ってみる

OpenAI Gymなる強化学習用プラットフォームを触ってみました(参考: PyConJPのプレゼンテーション)。

インストール自体はpip install gymで一発です(Atariゲームなどを扱いたい場合はpip install gym[atari]のようにサブパッケージをインストールする必要があるようです)。一応ドキュメントで使い方は説明されていますが、若干戸惑う点があったので随時補足します。

Atariゲームなど色々面白そうな環境がありますが、とりあえずFrozenLake(4x4, 8x8)というのが初心者向けっぽいので、これを試してみました。

ルールは非常に単純で、固定配置のマップ上でスタートから穴に落ちずにゴールに辿り着くだけです。成功時1点、失敗時0点の報酬が得られます。マップ上の記号の意味は以下の通り:

記号	意味
S	スタート
F	床
H	穴
G	ゴール

ただしスタート地点を含む全ての床は凍っているため、必ずしも指定した方向に動いてくれるとは限りません。また、説明文には書かれていませんが実はターン制限があるため、あまりターンをかけすぎると報酬が得られなくなります。

OpenAI Gymはあくまで強化学習用という位置付けなので、この問題も強化学習によって解くことが期待されているようです。そのためか、環境における状態や行動の値の意味(例えば0が左への移動に相当するなど)も明示されてはいません。しかし入門ということで今回はそれも調べた上で色々試してみようと思います。

環境の状態空間および行動空間は以下のようにして調べられます:

>>> env = gym.make("FrozenLake-v0")
>>> env.observation_space
Discrete(16)
>>> env.action_space
Discrete(4)

Discrete(n)は {0, 1, ..., n-1} を表します。よって、ここでは状態空間が0から15までの16通り、行動空間が0から3までの4通りとなります。大体察しがついていると思いますが、状態はマス目のインデックス、行動は4通りの移動方向を表しています。またenv.render()を呼ぶと直前に指定した移動方向も含めて表示してくれるので、これを見れば値と移動方向の関係もわかります(0:L, 1:D, 2:R, 3:U)。参考までに4x4版をインタラクティブに遊べるスクリプトを置いておきます。

少し人手でプレイしてみるとわかりますが、指定した方向に動いてくれないことが多いです。法則がわかるまでは穴に落ちまくると思います。

ここで身も蓋もないですがソースコードを見て法則を調べてみます。すると:

if is_slippery:
    for b in [(a-1)%4, a, (a+1)%4]:
        newrow, newcol = inc(row, col, b)
        # ...
        li.append((1.0/3.0, newstate, rew, done))

というコード(is_slipperyは常に真)があるので、4を法として指定した方向の±1へずれる可能性があり、3方向とも確率は1/3であることがわかります(流し読みなので違ったらスミマセン)。言い換えると、指定方向から±90度ずれる可能性はありますが、180度ずれることはありません。つまり「行く方向は指定できないが、行かない方向は指定できる」ということになります(行きたくない方向の逆を指定すればよい)。

これを踏まえて4x4版のマップ配置を見てみます:

SFFF
FHFH
FFFH
HFFG

隣接する穴が1つだけなら必ず回避できるので、これなら割と高確率でクリアできそうです。ただし隣接する穴が2つ以上になると死ぬ可能性があるので、ターン制限を考えなくても100%クリアするのは無理と思われます。隣接する穴が2つ以上あるマスを「危険マス」と呼ぶことにします(ここでは0-basedで座標 (2,1) がそれにあたります)。

この程度であれば人力で解く(各マスでの最適解を求める)のも難しくなさそうなので、とりあえずそれを書いてみます。穴に落ちるのを回避することと、開幕は危険マスを避けるため下に進むことに注意して各マスでの最適解を書き出してみると:

LUUU
L_L_
UDL_
_RD_

こんな感じでしょうか(厳密に最適かどうかは自信ありませんが)。これをそのまま実装して提出してみたところ、とりあえず要求水準(いい所取り100エピソードで平均報酬0.78以上)はクリアしているようです*1。

ここでターン制限について注意しておきます。問題文にはターン制限の説明がありませんが、モニタで提出用データを記録する際はターン制限を超過すると失敗とみなされます(提出したスクリプトではターン制限を考慮していないため、モニタなしの方が成績が良くなります)。ターン制限は環境ごとに異なり、以下のようにして調べられます:

>>> env.spec.timestep_limit
100

4x4版と8x8版でも制限ターンが異なるので、必ず上記のように取得する必要があるようです。

次は8x8版(制限ターン200)を考えてみます。マップはこのようになっています:

SFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

見た感じ、ターン制限を考えなければ右上からまっすぐ下へ進むルートで100%クリアできそうです。そこで適当に実装したものを提出してみましたが、これだとターン制限なしなら100%クリアできるものの、ターン制限ありだと微妙に足りないようです(いい所取り100エピソードで平均報酬0.99以上が必要だが、0.97止まり)。

他の人の結果を見ると(学習込みではありますが)クリアまでに短くても10000エピソード以上かかっているので、単純に試行回数不足というのも考えられますが、それだけではなさそうです。ターン制限を考慮した上でアルゴリズムを変えると成績が結構変わります。例えば開幕から右上に到達するまでずっと上を指定し、右上に到達したらずっと右を指定する、という方法でもターン制限がなければ100%クリアできますが、ターン制限を考慮すると10000エピソードでの平均報酬が0.71程度しか出なくなります(提出したものでは 0.88 程度)。

8x8版は解が自明とは言いがたいようなので、次回はQ学習による解法を試してみたいと思います。

*1:AIでもなんでもないので、こういうのを提出していいのかどうかはよくわかりませんが

エミュレータのフレーム境界

FCEUXではフレーム境界がline240(post-render)となっていますが、この理由がよくわかりませんでした。しかし考えてみると、入力更新タイミングとしてはここが適切なのではないかと思いました。

NESゲームの入力処理はNMIルーチン(line241で呼び出される)内で行われるのが一般的なので、line240で入力更新を行えば確実に入力が読み取られる可能性が高いと考えられます(それならline241開始前に入力更新でもよい、とは言えそうですが)。これが他のタイミング、例えばline0(描画開始ライン)だったとすると、NMIルーチンの処理にかかる時間によっては入力更新と入力処理の順序が入れ替わったり、最悪入力処理の途中で入力を更新してしまう事態も考えられます。実際、自作のNESエミュレータでもフレーム境界をline0からline240に変えただけでFCEUXのムービーがsyncするケースがありました。

他の理由もあるのかもしれませんが、とりあえず入力処理を考えただけでもフレーム境界はNMIの直前あたりに設定するのが無難そうですね。

SMB1などのムービーがsyncした

まだgithubには反映されてませんが、手元のブランチで主にPPUをFCEUXと一致させる作業中です。とりあえず以下のムービーはsyncするようになりました:

• HappyLee's NES Super Mario Bros "warped" in 04:57.31
• t3h Icy's NES Urban Champion in 00:26.97
• アストロロボSASA testrun

なお、現在github上で最新のgit @141eb20では上記のいずれもsyncしません。SMB1は途中までsyncしますが、4-1でパックンフラワーに当たってしまいます。

コアのライブラリ化は一応完了し、pythonから利用することもできるようになったので、その分ムービー機能は楽に付けられました。コア以外の機能は基本的にpythonで書く方向でいこうと思っています。なんでもかんでもC++で書いてるとハゲそうになるので…。

pysdl2でオーディオ再生(コールバック方式)

以前SDL2でのコールバック方式オーディオ再生について書きましたが、同様のコードをpysdl2で試してみました(全コードを置いておきます)。

スレッド間のやりとりには標準のqueue.Queueを使っていますが、これが最適かどうかはよくわかりません。

動かしてみると一応まともに鳴っているように思われますが、少し気になるところもあります。pythonにはGIL(Global Interpreter Lock)があり、C++版と違ってメインスレッドとオーディオスレッドの並列動作が不可能なため、負荷が高くなったり環境が変わったりしたとき正常に再生できるかどうかはやや怪しい気がします。また、SDL_Delay()を省略して出力を/dev/nullに捨ててみると音が止まる現象が確認されています。*1

今書いているNESエミュレータは後々コア部分のみをライブラリ化してpythonから利用できるようにしたいと考えていて、そのために特定の映像/音声ライブラリには依存しない作りにしてあったのですが、オーディオ再生に関しては何かしら補助的なインターフェースを加えてC++側で行えるようにした方が無難かもしれないと考えています。

そういえばpygameにはコールバック方式のオーディオ再生機能はなかった気がしますが、この辺が理由なんですかね…?

*1:sys.setswitchinterval(0.001)を行うと止まらなくなりますが、Ctrl-Cは受け付けられません。

一応APU実装完了

どうにか全チャネルがそれなりに鳴ってくれるようになりました(DMCは以前作ったPCM再生ROMでテストしましたが、本来の使い方であるDelta PCMについてはまだテストしてません)。ただ、ほとんどFCEUXのパクリなので理解度は半分以下です。

NesDevWikiの記述通りになってない部分も多々ありますが、正直あのWikiの内容を全部実装するのはきつそうです。BizHawkはそういう方向で頑張ってるみたいですが、CPU命令がマイクロコード単位に分割されていたりして私にはちょっと手に負えない感じです。

とりあえずテストROMなどを活用してちまちまとFCEUX互換に近づけていく予定です。PPUは相当いいかげんなのでまずはそれから着手しようかと思っています。