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は相当いいかげんなのでまずはそれから着手しようかと思っています。
SDL2のオーディオ再生
NESエミュレータはどうにか三角波がまともに鳴るようになりました。どうもSDL_QueueAudio()を使っていたのが良くなかったようで、従来のコールバック方式にしたら改善しました。そこで一応コールバック方式での再生について書いてみます(知識ゼロから調べたので誤っていたりもっといい方法があるかもしれません)。
まず正弦波を再生するコードを貼っておきます(boost, SDL2が必要。SDL1は不可)。引数でSDL側のバッファサイズを指定するようになっています。*1
概念的には単純で、以下の処理を行っているだけです:
- SDL側のオーディオスレッドで呼び出されるコールバック関数を登録する
- メインスレッドで波形データを作る
- オーディオスレッドは定期的にコールバックを呼び出し、波形データを消費して実際の再生を行う
しかし実際は波形データを蓄えるバッファのunderflow(読み出し時のデータ不足), overflow(書き込み時の容量オーバー)という問題があります。これらが発生した場合は以下のように対処します:
- underflowによりコールバックがデータを読めない場合、残りは無音を再生する
- overflowによりメインスレッドがデータを書けない場合、残りのデータを捨てる
ところでこれはマルチスレッド処理になるため、バッファへのアクセスをどう制御するかという問題が生じます(当初コールバック方式を避けていたのはこれを考えるのが面倒だったからです)。この手のバッファはリングバッファで実装するのが定番みたいですが、複数スレッドからの読み書きがあっても正しく動くように書けるかというと怪しい感じでした。
そこでFCEUXとbjneのソースを見てみましたが、どちらも特にその辺りは意識していないように見えました。FCEUXは一応volatile変数を使っていましたが、これだけでは多分不十分と思われます。でもどちらもそんなに破綻してる感じはしないんですけどね…。
調べてみると、今回のように生産者と消費者が1:1のケースを"single-producer single-consumer"と呼び、このための専用のキューの実装が既にあるようです。探した範囲ではboost::lockfree::spsc_queue, cameron314/readerwriterqueueが良さそうな感じでした(どちらもlock-free)。今回はユーザが多そうなboostの実装を使うことにしました。
spsc_queueには初期サイズを与える必要があります(サイズ固定)。理論上は1Fの全サンプル分だけのサイズがあれば足りるはずですが、それだとSDL側のバッファサイズと一致しないのと、コールバックの呼び出し間隔やFPSがブレるためにunderflow/overflowが生じます。いろいろ実験してみましたが、サンプリングレート44.1KHz, 60FPS弱であれば8F分のサイズを用意してやれば足りるようです。キューサイズが大きくて困ることは別にないのでもう少し余裕を見てもいいと思います。
考え方としては、とにかくunderflowだけは起こらないようにキューサイズを大きく取り、メインスレッドは最低限のFPSを維持して書き込みが追いつかない事態を避ける、ということになるのかなと思います。overflowするときというのは要するにメインスレッドの処理が速すぎるわけで、これはウェイト処理を改善すれば容易に対処可能ですし、最悪でも倍速っぽい音になるだけです(NESエミュレータでSDL_Delay()を省略して実験済み)。
ちなみにSDL_QueueAudio()を使っていたときはどうやってもunderflowが起こる感じでした(ノンウェイトで書き込んでもデータがあるはずなのに音がブツ切れになる)。ソースを読んでないので詳細はよくわかりませんが…。
