思考の本棚

機械学習のことや読んだ本の感想を整理するところ

LuxAIコンペの振り返り

f:id:kutohonn:20211211190917p:plain

はじめに

12/6に終了したLuxAI Challengeコンペの振り返り記事です。 最終結果は12/21に出る予定で現在の順位は37位です。 この記事ではコンペの概要と私の取り組みをまとめたいと思います。

Lux AI | Kaggle

ゲームの概要

LuxはゲームAIコンペティション用に立ち上げられたオリジナルゲームです。公式サイトは以下で、複雑な戦略性と魅力的なデザインが特徴のゲームでした。今回のkaggleでのコンペがLux AI Challenge Season1という立ち位置であるため今後もkaggle上で行われる可能性がありそうです。 www.lux-ai.org

ルール

ゲームルールはかなり複雑なのですが要約するとポイントは以下の3つです。

  1. プレイヤーはマップ上のUnitやCitytileを操作して資源を集めたり新たなUnit, Citytileを生み出す
  2. 昼と夜のターンが今後に現れ、夜のターンに十分な資源を持っていないUnitやCityは消滅する
  3. 最後に残っているCitytile数が大きいチームが勝ち

実際にプレイしている様子はこちらなどで確認できます。
https://www.kaggle.com/c/lux-ai-2021/leaderboard?dialog=episodes-episode-34126914

行動対象

前述したようにこのゲームではUnitとCitytileと呼ばれるものを行動させてゲームを進めていきます。

Unit

Unitがメインで操作する対象になります。資源の近くに移動することで資源を獲得したりこのゲームの目的であるCitytileを建設したりします。デザインがかわいいですね。

https://www.lux-ai.org/static/media/workers.b6dad2ed.svg

Action 説明
Center Move 現在の位置に止まる(何もしない)
North Move 北へ動く
West Move 西へ動く
South Move 南へ動く
East Move 東へ動く
Build City Cityを建設する
Transfer 保有資源を隣のUnitへ渡す
Pillage セルを壊す

TransferやPillageは利用するとより多様な戦略をとることができますが今回説明する内容の中ではあまり出てこないので無視していただいても構いません。またUnitにはCart(荷車)という種類もあるのですがこちらも同じ理由でこの記事では説明は省略します。

Citytile

Citytileの行動はUnitの数を増やしたり上位資源を獲得するためのポイントを貯めたりで、行動の選択肢は少なめです。

https://www.lux-ai.org/static/media/cityinfo.74901bf7.svg

Action 説明
Build Unit Unitを1体生み出す
Research 上位資源を採取するために必要な研究ポイントを貯める

補足するとマップ上に存在する資源にはwood, coal, uraniumの3種類があります。 uraniumなどの上位資源の方がを採取した時の利益が多いが、それらを採取するためにはresearch pointを貯める必要があるため、そのResearch ActionをCitytileが担っています。

資源 資源名 資源名
f:id:kutohonn:20211212112530p:plain wood 初めから採取可能
f:id:kutohonn:20211212112545p:plain coal research point > 50で採取可能。woodより資源効率が良い。
f:id:kutohonn:20211212113319p:plain uranium research point > 200で採取可能。coalより資源効率が良い。

このコンペの難しいところ

①複雑なルール
ここまで情報をかなり絞ってルールついて説明してきましたがそれでもルールが複雑であることがわかると思います。 このゲームを複雑にしている要因として以下のようなポイントがあります。

  • cooldownの概念
    f:id:kutohonn:20211214123755p:plain

UnitやCitytileは毎ターン行動ができるわけではなく行動後はcooldownのためにしばらく何もできないターンが存在します。 これによりどの行動をどのタイミングでするかというところに戦略性が生まれてきます。また行動可能な時にあえて何もしない選択を取り行動を温存するという戦略も考えられます。

  • 夜の概念
    f:id:kutohonn:20211214123805p:plain

前述の通り、このゲームでは昼と夜のターンが交互に現れ、夜のターンになると資源を十分に持っていないUnitやCitytileは消えてしまいます。 これを避けるためにマップ上の資源を相手のチームよりも効率的に採取することが重要となります。ただし資源効率の良いcoalやuraniumを採取するためにはResearch Actionをしないと採取自体が不可能であるため、Unit, Citytileを増やし資源を採取することとResearchのバランスをうまく取る必要があります。よく取られていた戦略として、序盤は消滅するのを前提に大量にUnitやCitytileを生み出してResearchを行うことで上位資源を早いターンで採取できるようにする戦略が多かった印象です。

②マルチエージェント
こちらがこのコンペを複雑にしている大きな要因だと思います。このコンペはターンによって操作するUnit・Citytileの数が大きく変動します。初めのターンではUnitは1体しかいませんが、ゲーム中盤になると多い時では50体ものUnitを操作する必要がありました。このように行動対象が複数かつ可変であることで以下のような点が課題となりました。

  • 探索空間が膨大
    強化学習や探索系のアルゴリズム(ex; モンテカルロ木探索)を行う際にはゲーム状態の探索を行う必要がありますが、Unit・Citytileが複数存在しそれぞれの行動によってゲームの状況は変化するので探索空間が非常に大きくなってしまいます。

  • 推論時間がかかる
    このコンペでは模倣学習(教師あり学習)や強化学習などのモデルによる推論によって行動を決定するアプローチをとっていた方が多いと思うのですが、自チームのUnit・Citytileの行動を全て1つずつ推論するとそれだけ推論に時間を要してしまいます。

  • 自チームの協力行動
    複数のUnit・Citytileを一度に操作できるということは、Unit同士が協力して行動することでより良い戦略が生まれそうです。そのためには自チームの他のUnitがどう動くのかというところも含めて戦略を立てる必要があり、これが重要な点であったのではないかと考えています。

取り組み

私はこのコンペで強化学習アプローチをとることを参加前から決めていました。理由は以下の3つです。
①これまでkaggleで行われたゲームAIコンペの多くで強化学習が上位解法となっている
②昨年度参加したfootballコンペで学んだ強化学習の知見を活かしたい
③技術的に面白い

前回参加したfootballコンペでは以下の学びを得ました。

  • 強化学習は学習効率が悪くまともなagentを作るのに多大な時間&コストを要する
  • 過学習を避けるために複数の敵と対戦させる必要がある  
  • 報酬は極力シンプルに

特に1つ目の学習コストが高いという点はかなりネックな部分で、それなりに複雑なゲームで強化学習を用いて一からagentを作ろうとすると、数十~数百のcpuを用意して数十時間~数日対戦させる必要があります。そうなるとコストが高いだけでなく、試行錯誤も容易ではないことから一から強化学習を行うのは厳しいと判断しました。そこで以下の方針を取りました。

  • 模倣学習でそれなりに良いAgentの行動を学習しそれをpretrained modelとして強化学習を実施する
  • うまく学習が進む特徴量やモデルのアーキテクチャを模倣学習で試行錯誤する

模倣学習とはエキスパートのゲームログ(今回の場合kaggle上での各チームの対戦ログ)を用いてその行動を模倣する教師あり学習のことです。模倣学習も過去コンペで用いられる有効なアプローチであったためこれを使ってそれなりに良い行動方策を事前学習した後に強化学習を行うことで学習コストを大幅に下げることができると考えました。また模倣学習で学習がうまくいく特徴量やモデルアーキテクチャはそのまま強化学習でも有用だと考え、模倣学習時にこれらの試行錯誤を行うようにしました。

模倣学習の取り組み

模倣学習ではコンペ序盤にsazumaさんという方が模倣学習のnotebookを公開してくれました。

f:id:kutohonn:20211214084936p:plain この手法は行動が比較的シンプルに決定できるCItytileの方はルールベースで決定し、Unitの方はゲームの状態と対象Unitの状態を19chのマップとして特徴量化し、特に重要な行動である4方向のMove行動とBuild City行動に絞って模倣学習を行うというものでした。この手法は非常によく働いており公開当初は銀圏の上位に食い込むほどのものでした。そこで私もこのモデルをベースに模倣学習を実施していました。

しかしこの手法には課題もありました。1つは学習・推論の時間がかかるという点です。このモデルではインプットに行動を決定したい対象のユニットの状態を表すチャネルを特徴量として与え、アウトプットとして対象ユニットの行動を返すように分類モデルを作成しているため、Unitの数だけ学習・推論を行う必要がありました。またUnitを独立して扱っているので協働した行動の学習が難しいというのも考えられます。

上記のような課題を解決する方法としてコンペ終了の1ヶ月ほど前にnosoundによるUNetを用いた模倣学習アプローチががdiscussionで共有されました。

https://i.imgur.com/hzjwYNA.png

このアプローチは元々Unit単位で行なっていた模倣学習をUNetを用いたセグメンテーションタスクのような形で解くことでMap単位で全てのUnitをまとめて学習・推論を行えるという非常に画期的なものでした。コードは公開されなかったもののdisucssionやコメントで丁寧に情報共有されていたことから私もこのアプローチに切り替えることにしました。 また共有されている情報や過去コンペの会報なども参考にし、UNetモデルに以下の工夫を加えました。

  • データサンプリング
    ゲームの説明で述べたようにこのゲームではcooldownという概念があり、行動後はしばらく行動できないターンが存在するため、「何も行動しない」という選択を学習することも重要でした。この何もしない行動はUnitのCenter Actionに該当するのですが、Center Actionは対戦ログには明示的に記録されていないケースが多かったため、ラベルを自分で作成する必要がありました。またラベルを自分で作成してもそのまま学習しようとするとCenter Actionのサンプルサイズは他のラベルの3-10倍以上あり、データが不均衡になるという問題がありました。そこでCenter Actionを他のラベルのサンプルサイズの平均値と同じになるようにアンダーサンプリングすることで対処しました。 もう一つターンごとに行動させるUnitの数に偏りがあり、それも問題になる可能性があったためターンごとのデータ数の偏りを減らすために、各ターン最大4つのUnitの行動のみを学習するようにサンプリングを行いました。

  • 移動行動の階層化
    こちらはUNetの情報を公開してくれたnosoundが共有してくれたTipsで、 上記の模倣学習で扱っているような特徴量マップとモデルの場合、4つのMove Actionを1つのMove Actionとして階層的に計算することができるというものです。 https://i.imgur.com/LiDvWQr.png 特徴量マップを90度回転させればNorth ActionはWest Actionとみなすことができることを利用し、 推論対象が元々Center Action, 4 Move Action, Build City Actionの6つであった場合、4Move Actionの代わりにNorth Actionのみを定義し、モデルに入力する特徴量マップを90度ずつ4回、回転させて4つのbatchとして入力しoutputを算出します。こうすると3ch × 4 のoutputが取得でき、4つのCenter Actionと4つのBuild Actionはoutputの平均をとることで、最終的に本来欲しかった6つの行動のoutputが取得できるというものです。 このTipsは非常に効果的で50くらいのスコアアップを達成できました。実装がやや面倒ではありますが離散的な移動行動を持つ他のシミュレーションコンペでも有用なアプローチだと思います。

  • TTA
    Hangry Geeseの4th place solutionではTTAとしてflip系を追加することでロバスト性を高めスコアが向上したという説明があったことから追加しました。スコアの向上はあまり確認されなかったのですが、マイナスの影響は少ないと判断しとりあえず追加しておくことにしました。

以上が模倣学習の私の取り組みです。この模倣学習モデルをもとに強化学習に取り組みました。が最終的なベストAgentは上記の模倣学習アプローチとなりました。

強化学習の取り組み

前述のように模倣学習モデルを事前学習モデルとして扱い、強化学習を実施しました。 強化学習フレームワークであるStable baslines3を今回は使用し、アルゴリズムにはPPOを選択しました。 使用した計算資源は手元のローカルマシンです。(GPU: RTX3080×1, メモリ64GB,cpu数=24) 本来強化学習で強いAgentを作ろうとするとこのようなスペックでは特にcpuが不足なのですが、模倣学習である程度事前学習を行なっているのでこのスペックでも十分に戦えるのではと考えました。 主な取り組みは以下です。

  • ハイパラチューニング
    模倣学習を事前学習モデルとして強化学習を行うとこれまでの行動を忘れたかのように急激に弱くなる現象が起きました。 そこで方策が大きく変更されないようにこちらで紹介しているPostを参考に、PPOのハイパラを変更しました。これにより序盤で行動がおかしくなる現象に対処しました。これはシンプルなモデルではよく働いたのですがUNetモデルで強化学習をするとハイパラを調整しても学習がうまくいかない現象が起きました。この原因はよくわかっていません。 brown: デフォルトパラメータ(bad)
    red: clip_range=0.1 / targe_kl=0.003(good)

https://user-images.githubusercontent.com/43205304/145128065-206d6eb4-6029-4bb0-9db4-c22b4c304156.png

  • 複数の対戦相手の作成
    過去の強化学習コンペから単一の対戦相手だと過学習することがわかっていたので、複数の上位チームのデータによる模倣学習Agentとself-play(自己対戦)を以下の配分で学習することにしました。
割合 対戦相手
0.25 self-play (現在のモデル)
0.15 self-play (過去のモデルからランダムサンプリング)
0.2 1stチームの模倣学習v1 (LB score is 1550)
0.2 1stチームの模倣学習v2 (LB score is 1450)
0.2 2ndチームの模倣学習 (LB score is 1450)
  • 推論の高速化
    前回の強化学習コンペから対戦回数を増やすことが強いAgentを作るために大事だと考えました。対戦相手として模倣学習やself-playのAgentを使っていたのですが、通常のpytorchモデルだと推論に時間がかかり時間あたりの対戦回数が少ない問題がありました。そこで今回はonnxruntimeを使用して対戦相手の推論を高速化しました。

  • 学習するパラメータの制限
    事前学習モデルである程度モデルの学習ができていることから全てのパラメータを学習するのは非効率だと考え、policy network(模倣学習で学習したnetwork)の最終層とvalue network(状態価値を評価するnetwork)のみを学習するようにしました。

  • シンプルな報酬設計
    報酬は今回の目的である最終的に残ったCitytile数を報酬とする方法と勝敗を報酬とする方法を軸に実験を行いました。 この方法の場合ゲームが終了するまで報酬を得ることができないので各ターンごとに得ることのできる即時報酬(例えば現在のターンのCitytile数)を用いることもできるのですが、即時報酬はAgentの行動を誘導する補助的なものであり、ある程度強くなったAgentには逆にノイズになる可能性もありました。今回の場合は模倣学習である程度良い方策がすでに得られていたので補助的な即時報酬は不要と考え上記のようなシンプルな報酬を使用することにしました。

上記のような取り組みを行ったのですが、最終的には強化学習を適用していない模倣学習モデルがベストAgentとなりました。強化学習にはかなり時間をかけて取り組んだのでこの結果はとても悔しかったです。

感想

強化学習自体は最終的にはうまくいかなかったのですが、時間をかけて取り組むことで強化学習に対する理解はかなり深まったと思います。 今度面白そうなゲームAIのコンペが来たらまた参加したいと思います。

私の解法

www.kaggle.com

https://user-images.githubusercontent.com/43205304/145222404-2365af22-0a25-4505-b2d4-25d84f3c9ad1.png