🦆

強化学習コンペ「Hungry Geese」を振り返る

2021/12/30に公開

機械学習

はじめに

2021年の春から夏にかけてkaggleで開催されていた「Hungry Geese」という強化学習コンペに参加して最終21位（銀メダル）でした。もともと自分は大学で三年間強化学習や模倣学習の研究をしていたのですが、強化学習コンペは初めての参加でした。本記事は、そんな自分がコンペをどのように進めたのかであったり感想やツラミについて、今更ながらまとめています。技術的なことは深く触れていないので、軽く読み流すぐらいの感じで読んでいただければと思います。

Hungry Geeseとは

https://www.kaggle.com/c/hungry-geese

Hungry Geeseは対戦形式のゲームAI作成コンペです。7x11マスのスネークゲームにおいて、コンペ参加者はゲームAIエージェントを作成、提出しレート戦で競い順位を決めます。HungryGeeseは２００ターンのあいだ動き回るガチョウが餌(food)を食べることで体を伸ばし、最後まで最長で生き残ることを目的とするゲームです。ガチョウの頭が敵味方関係なく体に衝突するか、４０ターンごとに発生する空腹判定時に長さが１だと死亡します。そのため、各プレーヤは敵の体に囲まれないようにしながら、フィールドにランダムで発生するfoodを集めるように動きます。

Hungry Geeseを強化学習問題としてみた場合、完全観測離散状態行動空間における４プレイヤーのマルチエージェント環境です。エージェントの行動に対するダイナミクスは決定的ですが、foodが出現する場所についてはランダム性があります。また、相手エージェントを環境の一部として捉えるのであれば、相手方策がレート環境での方策分布からランダムに選ばれるとして考えることもできます。

コンペ記録

以下では、時系列で自分がどのようにコンペを進めて行ったのかについて述べます。

HandyRL期

HungyGeeseコンペは比較的初期の段階から HandyRLというライブラリを適用したノートブックが公開され、非常に良い成績を収めていました。また、LBでも１位はHandyRLチーム独走している状態でした。
https://github.com/DeNA/HandyRL

実際に結果を出しているチームということで、とりあえずHandyRLの実装を読むところから始めました。アプローチとしてはシンプルな分散off-policy深層強化学習でした。Hungry Geeseへ適用したノートブックでの手法の特徴的な点としては、状態表現がトーラス（左端からさらに左に行くと右端に到達する２Dゲームによくある空間）をCNNで表せるように工夫されている点があります。CNNは、マスの近さを特徴として表現しやすいので、この工夫は非常に有効だと思われます。また、マルチエージェント環境としての学習方法としては、自分と同じ方策を持つエージェントで戦わせるself-playによって行われていました。

HandyRLのその時点で公開されているコードを一式読んで以下の問題点がありそうだと考えました。

胴体の状態表現が場所によらず一定
試合終了残りステップや４０ターン毎の空白判定までのステップ数が状態表現に含まれない
自分と同じ方策のみと戦い続けるため、方策更新が滞ったり変な局所解に落ちそう

問題点1については、既存のモデルでは胴体があるマスを全て0,１の離散値で表現しているという問題です。採用されている手法はMDPを前提とする手法なので、現在状態を一意に表すような状態表現をすることは非常に重要です。尻尾に近いほど、近いステップ数の後にその空間が空く（通れるようになる）ということからも、頭から尻尾までの順番は重要だと考えられます。そのため、頭から尻尾にかけて値を1から0に連続値で表現するようにしました。離散状態空間を連続にする点については、状態の組み合わせが大きくなるように感じますが、ニューラルネットを使って状態表現を獲得する時点で、問題にはならないと考えられます。

問題点２のステップ数は、特に終盤において、行動戦略に大きな影響を与える情報だと思われます。これについては、CNNのチャンネル方向に１次元増やして組み込むという方式を取りました。これについては、１位のHandyRLチームも似たようなことをしていたようです。

問題点3の学習時の対戦相手については、starcraft AIで使用されたalpha starのような複雑な方法も考えられますが、実装リソースや計算資源的な限りもあるため、過去のエージェントもランダムに混ぜるシンプルな方式を取りました。

運よく好成績が出て調子に乗る

以上の改良を加えたモデルを自宅PCで学習させました。gen8のi5+gpuで100epoch毎に１０時間ほどかかっていたようで、ちょっと絶望してました。しかし、一週間ほどかけて学習し、サブミットしたところ一時的に9位まで到達しました。
この程度の改善だとすぐ抜かれるだろうとは思いつつも、金圏に入ったのは初めてだったのでちょっと気合が入ります。これは計算機力あればいけるかもしれない、と思いGCPでの学習環境とオフラインでのモデル評価ができるような環境の構築を始めました。

虚無る

モデル評価を実装し始めて問題が発覚しました。

相当数戦わせても、勝利数などのばらつきが出る（運的な要素が大きい）
モデル毎の相性などもあり、簡単に順位がつけれない

このような問題から、自分の持つ計算資源や実装コスト的にまともに評価するのはほぼ不可能だと結論が出ました。このような、簡易的な指標しかないまま、中途半端に結果を出してしまったモデルを小さく変更しては、submitして、だめだなぁ、みたいな日々が続いて作業も滞りました。
振り返ってみると、まともな評価指標なしに小さな調整を繰り返しているのは無意味な時間だったと思います。

残り１ヶ月ほどで気合を入れ直す

しばらくサボっていたもののの、ある程度順位はキープしており、残り１ヶ月の時点で気合を入れ直します。学習させた我が子の対戦動画を見ていると見ていると、どうにも明らかに正しくない手がたくさんあリました。上位勢の子はやはり堅実な行動をとっていおり、順位としてはそれほど離れていないものの、大きな壁があるように感じました。
少なくとも終盤においては、先を見据えた行動を探索した方が確実な手を打てます。そこで、囲碁AIで有名なAlphaZeroのようなモンテカルロ木探索(MCTS)ベースの方法を取り入れ始めます。

AlphaGoを代表とするMCTSベースの手法は、現在の手番からの各行動についての価値を、盤面をシミュレーションしながら推定する手法です。MTCS系は今までほとんど触れてこなかったのですが、以下のサイトが理論と実装をわかりやすく解説されているので非常に参考になりました。また、実装については１０位の方が当時公開していたnotebookを参考にしました。

囲碁とhungyGeeseの大きな違いは以下の２点です。

プレイヤーがターン制ではなく同時行動
food出現場所がランダム（ダイナミクスが決定的でない）

ターン制でない点については、木の分岐のタイミングを変えるだけで対応できます。
問題となるのはfood出現場所がランダムという点です。状態遷移にランダム性を伴う場合の木探索をする場合、厳密にはそれぞれ分岐して価値を算出しなければなりません。しかし、7x11マスといえど、そのパターンは十分に大きく、愚直にこの価値を導出しようとすると非常に多くの計算量が必要となり、十分先の手まで探索を行うことができません。
この問題に対しては、foodの出現する位置についてのパターンの上限を絞るようにしました。
これによって深さの平均値が増加しつつも、foodの出現を考慮したものが実現できるました。

メインの変更点としては以上で、これをGCPで学習できるようにしたり、他の案を実装しようとしてうまくいかなかったり、MCTSの探索速度を上げようと思ったりとごちゃごちゃやっていたらタイムリミットを迎えました。

結果

提出後の評価対戦期間である１週間は我が子を見守るのみで、なかなかに楽しい時間でした。結果としては21位/875teams に終わりました。そこそこいい成績のようにも感じますが、提出したモデルの行動を見ているとやはり不完全な部分も多く、上位勢には敵わないと感じました。個人的に足りていないと思うのは以下の点です。

推論時の探索の高速化（実装力）
MTCSへの適切な理解
オフラインでの適切な評価指標
学習を高速でたくさん回すための実装力

強化学習コンペのツラミ

HungryGeeseはポップなビジュアルのゲームで、他の参加者とレート形式で戦うという、とても楽しいコンペでした。しかしながら、他のコンペと比較して強化学習コンペ特有のつらみもあったと感じました。

自分が感じた他のコンペと異なる強化学習コンペ特有の大変さは以下の二つ間と思います。

計算＆実装リソース
モデル評価

リソースがツライ

強化学習は他のML系以上に実装にかかるコストが大きいと思います。強化学習コンペでは以下のようにやることがたくさんあり、デバッグ作業も大変です。

コンペに合わせたデータ処理
RLアルゴリズムの構築
評価のための実装

そのため、公開されているnotebookやライブラリをうまく使うことはとても重要だと思いますし、公開していただいている方々には頭が上がりません。

計算リソースが多く必要であることはよく言われます。7x11マスの離散空間でも、マルチエージェントやfood出現のランダム性などの要素もあり、学習にはかなり計算量を要します。初期のベースラインを作成する段階でも、自分のサーバレベルではある程度の学習に一週間程度かかりました。通常の機械学習と異なり、強化学習では環境をいくつも並列して動かすためのCPUパワーがものをいうのも特徴です。
そもそも強化学習は全探索では解けないような問題を、ある程度ヒューリスティックに現実的な計算量で解きたいというものでもあるので、計算リソースがかかるのは当然ともいえます。強化学習研究も、この学習にかかる時間を短縮するために分散学習やoff-policy化など様々な手法が提案されています。その意味で、限られた計算リソースでどう戦うのか、というのも強化学習コンペの１つの勝負ポイントとも言えるのかもしれません。

モデル評価がツライ

学習したモデルを手元で評価するというのは、コンペや研究において必要事項であり、コンペ上位陣ほど信頼できる評価方法を手元で構築しているイメージがあります。しかし、HundyRLのような対戦形式のコンペでは、相性や運要素などが非常に大きく多様な対戦相手を用意して多数対戦を行う必要がありました。多様なエージェントを手元で作成するには大きなコストがかかり、実際に戦わせることにも時間がかかる、ランダム性もあり回数を重ねる必要があるなど様々な要因から手元でまともに評価するのがかなり厳しかったです。後半の方では諦めて、とりあえずsubmitして比べる、というようなことしかできておらず同じモデルを２回投げた場合にLBでの成績もかなりばらつきがあるような状態でした。

このように、対戦形式のコンペではモデルの評価がかなり難しいと感じましたし、まともに手元で評価できているチームもそう多くなかったのではないかと感じます。その意味ではモデル評価をきちんとできれば、より適切なモデル改善ができて、より良い順位に行けたのだろうと思います。
おそらくこのような順位付けやレート付けについて掘り下げれば１つの大きな分野なのだろうと思います。自分が普段からやっているゲームのレートはどうなってるかなど、時間があればより掘り下げてみたいと思いました。

まとめ

振り返ってみると、途中で結構いい結果が出たり、単純に我が子が戦う姿を眺めたりと楽しいコンペでした。初めはただの計算機ゲーなんじゃないかとか思っていましたが、個人のリソースでなんとかなる程度（？）の状態行動空間のサイズであったり、方策勾配法ベースやMTCSベースの手法やその組み合わせが有効だったり、それらが直接適応するには工夫が必要だったり、強さの評価が難しかったりと、考えるべきことや学びが多くあるコンペでした。強化学習は修士課程まで研究していましたが、実際に問題が与えられて、その環境でちゃんと動くモデルを作るというのはまた別の難しさがあると思いましたし、こういう過程を経てまた研究テーマが生まれたりするのだろうとも思いました。また機会と気合があれば参加したいと思います。

強化学習のコンペについては、きょうへいさんという方がサッカーコンペとLux AIコンペを経験した上で概観や取り組み方が詳しくまとめられていますので、こちらの記事もおすすめです。