Kaggle Haliteを強化学習で解こうとした話

本記事は 強化学習苦手の会 Advent Calendar 2020 - Adventar 8日目の記事とするべく、コンペ終了後に書いた記事に追記しました。

7日目の記事(Kaggleの強化学習コンペがグダグダだった話 - Qiita)への返歌みたいなものになります。

雑感

  • 強化学習でどこまで行けるんだろう、ということで勝敗に拘らず強化学習を試してみましたが、何も考えないと思っていたより厳しいなぁという印象でした。

    • 「岩塩のあるところまで行く」→ まぁまぁ簡単にできる
    • 「岩塩のあるところまで行って、スタート地点まで戻ってくる」→ 工夫しないと厳しい
    • 「岩塩のあるところまで行って、スタート地点まで戻ってくるのを複数の船で協調する」→ さらに厳しい

  • 結局、カリキュラムラーニングじみたことをやって、「岩塩のあるところまで行って、スタート地点まで戻ってくるのを複数の船で協調する」までは出来ました。
    ただ、ルールベースならそこまで難しくないことではありますね。

  • AlphaStarやOpenAI Fiveはもっと難しい問題を解いているわけで、彼らと同じリソースをつぎ込めば上位には来れたのだとは思います。 そこの差が、どこまでリソースの差で、どこまでが手法の差なのか。私は強化学習苦手なので、当たり前のことを見落としていることはありえます。

  • 典型的な強化学習の課題設定は単独のAgentの行動をコントロールするものが多いようですが、この問題は複数の船の行動をコントロールするというのも難しいポイントで、ライブラリをそのまま突っ込むことができません。私はPFRLを改造しましたが、結構時間と精神力を持っていかれました。

  • コンペで強化学習を使え、とは言っていなかったように思います。

  • コンペとしては良コンペだと思いました


    （kaggle-environmentsのコードは解読が大変だったので、不満はありますが・・笑）

  • 1位の人のソリューション
    https://www.kaggle.com/c/halite/discussion/183543
    手法の概要からソースコードまで付けてくれて、言うこと無い有り難いシェアだと思います。
    印象的なのは手数の多さと、良くこの量のコードをバグらせずに書き続けられるなという感じですね。



（以下は9月に書いた記事です）

KaggleのHalite by Two Sigmaを強化学習で解こうとして、1か月ほど頑張っていました。

www.kaggle.com

@higeponさんと@Seed57_cashさんとチームを組んで、情報共有しながらやっていました。

最終Submissionはこのような感じです。複数の船でHaliteを集めて基地に搬入する、というところまではできましたが、他のプレイヤーに勝てるAIにするには、ここから何個か超えなくてはいけない壁があるようには思います。

予想どおりでしたが、強化学習で動きを学ばせるのはかなり大変ですね。 ルールベースだと簡単な動きも、何も工夫をしない強化学習だと一晩回してもまだしょっぱい動きだったり、なかなか厳しいものだなと。

取り組んだことを記述して行きます。一応念のため、以下にはご注意下さい。

  • 単純なミスをしていて、本来できるはずのことができていない可能性はあります
  • 強化学習のプロがやると一瞬で悩んでいた問題を解決したりするかもしれません

1. Haliteのルール

ルールは以下の日本語概要が分かりやすいです。
https://www.kaggle.com/iicyan/japanese-halite-introduction

さらに要約すると、

  • 盤面は21x21、4人対戦
  • 各プレイヤーはターンごとに行動を同時に指示する
  • 指示の対象は、それぞれの船（待機・上下左右移動・基地への変換）と基地（待機・船の生産）
  • 最初に各プレイヤーは船を１隻保持している。盤面にはHalite（岩塩）が配置されている。
  • 基地はコストを払って船を生産できる。船は基地に変換できる。
  • 各Haliteは時間経過とともに上限まで徐々に増加する
  • 船がHaliteの上で待機することによりその25%を船に貯め込む（Collect）
  • 船が基地に到着することで、溜め込んだHaliteをそのプレイヤーが取得する（Deposit）
  • 船同士が衝突したとき、最もHaliteが少ない船が勝ち、その他の船からHaliteを奪い取り船に貯める
  • 400ターン終了時に最も多くHaliteを最も保持している人の勝ち

2. 全体的な方針

2-1. ライブラリの利用

やってみると痛感するのですが、強化学習は至るところにバグを埋め込むポイントがあり、スクラッチで書くのはリスクがあります。 また、新しめの手法を気軽に試しやすいことを考えて、ライブラリを使うことにしました。

今回使ったのはpfrlですが、以下のような利点があったように思います。

  • コードが読みやすい
  • さまざまなアルゴリズムに対応している
  • PyTorchベース
  • 並列で環境を動かせるため、効率的に学習できる
  • 経過時間やスコアなどのを容易にログ出力できたり、TensorBoardに対応している

github.com

他にもOpenAI Stable Baselineなど、いくつか強化学習用のライブラリがあります。

github.com

2-2. タスクの解釈

このタスクでは、船の生産や船から基地への変換は考えないことにするとしても、複数の船の行動を選択する必要があり、ここが悩ましいポイントです。 よく強化学習の対象にされるAtariのゲームでは選択肢から行動を選ぶだけですし、このように複数の対象の行動を選択するというタスクの例はあまり見つけられませんでした。
（MADDPGという手法など、そのような研究はあるようです  https://github.com/openai/maddpg）
結局、それぞれの船ベースで報酬が最大となるように行動を選択するタスクと解釈して、まずは進めることにしました。

なお、先行してこのコンペに上位で強化学習をしていた参加者がいて、その方のアプローチも参考にしました。 https://www.kaggle.com/c/halite/discussion/169623#948042

また、StarCraftをプレイするAlphaStar、Dota2をプレイするOpenAI Fiveも複数の対象の行動を選択する点は近いように思います。 （大規模すぎて良く分かりませんが・・・）OpenAI FiveではTeam Playという要素により対象間の連携を反映しているようです。

（参考）
https://note.com/npaka/n/nb719e603b4aa
https://note.com/npaka/n/n16ac9b6004bd

3. １隻でHaliteを集めることを学習させる

まずは「1隻、1プレイヤー、30ターンで最も多くHaliteをCollectする」タスクを学ばせました。

DQNで、雑なネットワークを元に作ってみたところ、これすら上手く学習できないのには驚きました。一晩回したり、Rainbowを試してみてもまだ微妙な動きでした。
試しにアルゴリズムをPPOに変えてみたところ、上手く行き、数分程度で良い動きを学ぶことができたため、以下はPPOメインで進めています。
（本当は動かした時間やステップを記述すべきなのですが、コードも試行錯誤していた段階なのでデータを捨ててしまっている・・）

4. １隻でHaliteをDepositすることを学習させる

次に、「1隻、1プレイヤー、30ターンで最も多くHaliteをDepositする」タスクを学ばせます。 これが厳しかったです。

Depositするには、HaliteをCollectしたあと、基地に戻る必要があります。 強化学習のエージェントには盤面と行動に対する報酬のみが渡され、何も分からないまま動き、報酬を得て学びが進んでいくわけですが、 Depositによって報酬が得られることを学ぶには、Haliteを集め「偶然」基地に辿り着く必要があります。 しかし、ランダムに進んでも簡単には辿り着かないため、報酬が疎に与えられることになります。

うまく学習できず局所解にはまっているようで、上下運動のみを繰り返すことしかしなかったり、基地の周りをぐるぐる回るAIが発生しました。 また、まずはCollectを学んでそのうちDepositも学んでほしい、という意図でCollectにも報酬を与えましたが、高くしすぎるとDepositを学ぶことをあきらめてCollectばかりするようになりました。

PPOのパラメータのチューニングやその他の工夫を試しましたが、結局明確に効いたのは以下の２つでした。

  • アップデートまでに集めるエピソード数を増やす
    PPOで方策をアップデートするまでの間隔を増やしていくと徐々に良くなりました。ただ、学習の進みは当然遅くなります。

  • モデルのネットワーク構造に行動の性質を取り入れる（@Seed57_cashさんの貢献）
    盤面と対応させたCNNから、対象が中心になるように盤面をスライドさせた（np.rollを用いた）のちに、上下左右の移動位置のセルの値を抜き出し、層を通して行動選択のSoftMax関数に通すようにしました。
    行動と盤面の関係性が明示的にモデルに伝えられるためか、これによりかなり動きが自然になりました。

納得行く動きを得るには1000万ステップ、10時間程度学習させる必要がありましたが、これでDepositまで学べるようになりました。

5.  複数隻でHaliteをDepositすることを学習させる

5-1. 複数の行動対象への対応

そして、「複数隻、1プレイヤー、30ターンで最も多くHaliteをDepositする」タスクを学ばせます。

ライブラリ内の処理では、一つの環境の遷移に対して一つの行動・報酬が対応しますが、ライブラリを改造し、遷移に対して複数の船による行動・報酬が対応するようにして進めました。
報酬の処理も気をつける必要があり、今回のルールだとHaliteが少ない船は味方から奪った方が得になってしまいます。 それを抑止するよう、味方から奪ったHaliteはペナルティにするなどの調整を行いました。

ただ、「Depositするためには基地に戻らなくてはいけない」と「基地の近くは密になって衝突しやすい」がコンフリクトする要素であり、 最初から学習させようとしてもあまり上手く進まなかったため、下記のカリキュラム学習を適用しました。

5-2. カリキュラム学習

強化学習でカリキュラム学習という手法について聞くものの、実際にはどうやるんだ、という気持ちです。 結局、以下の順に学習を進めていきました。これが正しい方法かは分からないのですが、少なくとも学習時間は節約できて便利ですね。

  • 「1隻、1プレイヤー、30ターンで最も多くHaliteをDepositする」タスク
  • 「1隻、4プレイヤー、30ターンで最も多くHaliteをDepositする」タスク
  • 「複数隻、4プレイヤー、30ターンで最も多くHaliteをDepositする」タスク 
  • 「複数隻、4プレイヤー、100ターンで最も多くHaliteをDepositする」タスク 
  • 「複数隻、4プレイヤー、400ターンで最も多くHaliteをDepositする」タスク 

6. 提出

基地が船を生産するかどうか、また船を基地に変換する動きも強化学習させて判断させたかったのですが、 時間的な都合もありここまでで、Kaggleへの提出をします。

@higeponさんのNotebookが参考になります。
https://www.kaggle.com/c/halite/discussion/164005

ポイントは以下のような感じ：

  • 強化学習エージェントの行動選択の部分のみ抽出し、提出するファイルをsticky_tapeで一つの.pyファイルにまとめる
  • モデルはbase64でエンコードして、文字列として提出ファイル内に保存する
  • 出力するファイルの制限は100MBとかなり余裕があり、大きなモデルもサブミットできるようです。
    （なお、今回の作成したモデルのサイズは100kB程度でした）
        https://www.kaggle.com/c/halite/discussion/161588
  • Kaggle Dockerに入っていないライブラリは手で依存部分を貼り付けるなどする必要があります。学習でなく推論部分のみなので、それほど大変ではありませんでしたが。

7.  有望なアプローチの考察

今回はそこまでたどり着けませんでしたが、こんなことできないかなーと考察していたものです。

良いアルゴリズムの利用

  • 今回はPPOを使用しましたが、もっと探索効率の良いアルゴリズム・工夫はありそう
  • 私が試したときはDQN/RainbowはPPOに対して劣っていたが、本当にそうなのかどうか
  • PPOはon-policyのアルゴリズムで、ヒューリスティクスとの統合を考えたときにはoff-policyのアルゴリズムの方が自由にできそう？
  • このタスクでは難しそうですが、AlphaZeroやモンテカルロ木探索が使えればその方が良さそう

ヒューリスティクスとの統合など

何らかの形でヒューリスティクスと統合できれば、効率的な学習ができそうです。

  • Abstract Action
    「上下左右に動く」を選択対象の行動にするのではなく、「最も近くの基地に帰る」「最も近くの敵に近づく」といった戦術の単位を行動とする手法です。この考え方がハマるタスクであれば、効果がありそうです。
  • 盤面のモデルの活用
    今回のタスクでは、盤面がどのように遷移するかのモデルが明確に分かっていますが、単純に強化学習を行う場合は、報酬だけが与えられせっかく分かっている盤面のモデルが使われません。
    例えば、次の盤面を予想するタスクを追加で解かせる、といったアプローチはありそうです。（既にそういった手法は誰かが考えていそうですが。Muzeroなどもこの発展といえる？）　　 　
  • 大まかな戦略はルールベースで作り、個別の動きは強化学習で学ばせる
    本当は戦略についても学んでほしいところですが、なかなかに厳しいので、そこを妥協したアプローチです

模倣学習

他のプレイヤーの対戦データも落とせたので、模倣学習を上手くできれば上位に入れる可能性はあるのではないかと思います。 最初から学習させるより学習時間も節約できるでしょうし、対戦相手が手に入ると下記のリーグトレーニングなどを節約でき、効果的です。 GAIL（Generative Adversarial Imitation Learning）といった手法が有名なようです。

Fictitious Self-Play, リーグトレーニング

いわゆる「じゃんけん環境」では、自己対戦を繰り返しても戦略がぐるぐる回ってしまう可能性があります。
そのため、AlphaStarでは、Fictitious Self-Playや他のプレイヤーの弱点を突くことを主目的とするプレイヤーを作る、といったアプローチが使われていたようです。

tadaoyamaoka.hatenablog.com

8.  （参考）強化学習の計算時間

強化学習では学習のステップ・エピソードをたくさん回したいのですが、計算時間は主に以下から構成されます。

  • 環境の更新などのCPU処理
  • 行動選択の推論のGPU処理
  • モデルの学習のGPU処理

CPUやGPUの使用率を見るほか、環境を並列にして回してみる、行動選択をランダムに差し替える、モデルの学習をスキップする、とするとボトルネックの箇所が把握できます。

今回のタスクでの計算時間は以下のようになりました。
（PCはi9-9900K 8コア、GeForce 2080Ti。強化学習の環境は8並列で計算した。）

  • 1隻・1プレイヤーで、環境をCythonで高速化すると10000ステップが4秒。（学習のGPU処理がほとんど）
  • 1隻・1プレイヤーで、環境を高速化していないと10000ステップが20秒。
  • 5隻・4プレイヤーで、環境を高速化していないと10000ステップが200秒。（環境の更新などのCPU処理がほとんど）