#概要
「20言っちゃダメゲーム」の最適解を、30分程度で深層強化学習を用いて、自動的に編み出すプログラムを書きました。負けたい人は、githubから試してください。chainerRLのDouble-DQNを使いました。
#成果物
プログラムはgithubに置きました。
. env/bin/activate
python3 main.py --load result_100000 # 僕が学習させた最適解AIと戦いたいだけの場合
python3 main.py --learn yes # 一から学習させる場合
#導入
今までの日本語ブログでの深層強化学習の例題は、最適解が非自明であり、入門として適切なものがなかったように思えます。例として、3目並べの例や、PFNのexampleのgymのありました。これらには、入門者にとっては2つの問題点があります。
- 最適解が非自明であり、正しく動いているという確信が持てない
- gym, trainerなど高次機能から入門すると、環境を自分で構築する場合のコーディング方法がわからない（chainer系は高次機能から入門させたがる傾向がある気がするが、僕は作ってる感があるのでボトムアップが好き）
環境を自分で構築して、かつ最適解とエージェントの比較ができるような簡単な例として、「20言っちゃダメゲーム」を考えます。このゲームは、AさんBさんによる2人ゲームです。始め共有フィールドに数0が存在します。手番はAさんから始まり、手番では以下の操作を繰り返します。
- 数に1, 2, 3のどれかを足す
- 数が20以上になったら、足した人が負ける。そうでなければ手番交代
この問題はNIMと呼ばれる問題クラスに当たり、最適解が具体的に求まります。具体的には先手必勝で、先手は$i = 3(mod 4)$を目標にし続けることで、必ず$19$を相手に押し付けることができます。一方、$i=3(mod 4)$からスタートすると必敗なので、この状態からのアクションは何を選んでも最適解を保持します。
本ブログでは、強化学習によってNIMによる最適解を再現することを目的として、学習プログラムを作ります。
#方法
##状態・行動・報酬系
状態$n$は、「自分の番の初めに、フィールドに$n (0 \le n \le 20)$が出ている」と定義します。
行動$a$は、「状態$s$の時に、数を$a (1 \le a \le 3)$出す」と定義します。
報酬$r$は、少しだけトリッキーに設定しています。行動$a$の結果、$20$を超えたら報酬$r=-1$とします。超えなければ$0$です。しかし、これだけだと2人対戦ゲームの勝者への報酬が設定できていません。したがって、「$20$を超える手を打った1手前の状態$n_{prev}$」に対して報酬$r=1$を追加で与えることとします。これは要するに「その手で詰ませたっぽければ報酬を与える」ということです。
（これだと$n=19$で、報酬が$0$だったり$-1$だったりと一貫しませんが、まあ収束が遅くなるくらいだろうのでいいでしょう）
状態は$1$次元、報酬$r \in {0,-1,1}$, 行動$a$は$3$次元です。
行動が$1$次元だと直感的には思いますが、行動が$3$次元なのは、あとで最も妥当なものを選択するようにネットワークを構築するからです。
##ネットワーク構成
state(1)-81-LLeRU-81-LLeRU-action(3)-DiscreteActionValueのDNNを構築します。
action(3)はその後DiscreteActionValue関数によって$1$つの行動が選択されます。（DiscreteActionValue関数ってなんでしょう？？クロスエントロピーみたいなやつでしょうか。）
また、報酬系は負を含むので、Leaky ReLUを使います。
##その他
最適化にはAdam($\epsilon=0.01$)を使用します。
ExplorerはEpsilonGreedyを用います。$50000$ステップで$\epsilon=1 \rightarrow 0.1$とします。
Experience Replayは$10^6$のバッファサイズを用意します。
Target updateの頻度は100ステップに1回とします。
#実装
chainerRLを用いて実装しました。プログラムはgithubにあります。
3目並べのプログラムをベースにしました。リンク先のプログラムでは、環境クラスがchainerRL quickstartに書いてあるgymの形式に則っていないので、reset関数とstep関数を実装するように修正しました。
実装上何故や、と思ったこととしては、actionが生のint型（0 or 1 or 2）だったことです。1次元のnp.arrayだと思っていました。DescreteActionValueさん、きちんとこれBackpropできるのか。
agentの状態行動は自明ですが、状態観測はどうあるべきでしょうか。$n=10$で$a=3$を行った時、状態観測は$n=13$で良いでしょうか。これはダメで、「自分の手番の時の」状態観測でなければならないので、$n=13$から更に相手が何か行動を起こした後の値を状態観測としなければなりません。
agent_p1, 2を別々にしています。なぜかというと、これは予想でしかないのですが、act_and_train関数への報酬がobs, rewardしかないのが鍵だと思っています。and_train系の関数は、おそらくリプレイバッファに(state_prev, state, reward, action)を貯めています。state_prevはagent内のメンバ変数を副作用で変更することで得ていると予想しています。
#結果
強化学習の結果得られた戦略を示します。以下は、左側の数字がフィールドに出ている数で、右側が何を足すべきかのリストです。きちんと最適解が得られていますね。
0 3
1 2
2 1
3 1
4 3
5 2
6 1
7 1
8 3
9 2
10 1
11 3
12 3
13 2
14 1
15 1
16 3
17 2
18 1
19 1
20 1
人間と対戦してみます。AI先手としてプログラムを書いているので、人間は絶対に負けます。
学習$30分$、$100000$ステップ行いました。$80000$ステップくらいで最適解を得ました。
#今後
スーパーパラメータを振って、どれくらい学習速度が変わるのかの実験をしてみたいです…と言う人が多そうですが、僕は別にぶっちゃけどっっっっでもいいです。主に興味があるのは、別に手法に対しての優位性・スーパーパラメータへのロバストネスをどのように評価するのでしょうか？ということです。WGANの論文でそんなのを見た記憶があるけれど…。
lossとかaverage Qとかってどういう指標になるのでしょうか？あんまり何か見てても嬉しいことがないように思うのですが。
リプレイバッファに行動を貯めていないように見えるんですが、これでいいんですか？
2人対戦ゲームで、今回の実装のように「勝った時に+1, 負けた最後の手に-1」とするのは一般的でしょうか？少なくとも、負けた最後の手は報酬0と報酬-1が混在してよくなさそうです。どのように実装するのが普通でしょうか？
今回は禁止手がないゲームを実装しました。一方、禁止手があるゲームでは、ルール違反に対して-1の報酬を与えるなどの実装方法が考えられます。しかし、ルール違反を制限しながら強化学習することができれば、無駄にルールを学ぶ必要がなくなるので、学習が高速化すると思います。どのように実装すればよいのでしょうか？
途中から学習をやり直す方法ってどうすればよいでしょうか？ステップ数も一緒にsaveしなければならないと思います。
また、今回は状態離散1次元、出力離散3次元でした。今後は、状態が多次元、出力が連続、描画あり、学習中ハイパーパラメータ調整などを行いたいです。
複数プロセッサやGPGPUってどうやって設定するのでしょうか？
#まとめ
入門者に適したタスクであるNIMの最適解発見について、これを深層強化学習で$30$分程度で見つけるプログラムを実装しました。
この程度の勉強を終えた後に疑問に思うことを列挙したので、これを元により良いチュートリアルができればと祈ります。この記事が後の初学者の糧となることを期待します。