[Kaggle] Halite by Two Sigma 17th Solution
KaggleのゲームAIコンペ『Halite by Two Sigma』に、minaminao・yasagure・Johannesの3人でチーム『team-tokai』として参加しました。（チーム名は高校同期であることに由来。） 結果は、銀メダル圏内の17位でした。
チームメンバー全員わりと忙しく「平日23時から1時間だけやる」ルールを基本に少しずつ進めていましたが、良い成果を残せて良かったです。今後、類似のコンペや問題に出会ったときのために考察と解法を残します。
目次§
ゲームの概要§
ゲームは4人対戦です。場にhalite(岩塩)が埋まっているセルがあります。プレイヤーは船を動かしてhaliteを回収でき、ゲーム終了時にhaliteを回収した量に応じてランキングがつけられます。
船はhaliteを消費することで拠点から生成できます。同様に拠点もhaliteを消費することで船からコンバートできます。全プレイヤーはステップごとに、各船に対し「上下左右にどれかに動かす」「居座る」「拠点にコンバートする」の選択を取れ、また、各拠点に対し「船を生成する」「船を生成しない」の選択を取れます。
セルごとにhaliteの量は異なります。船がhaliteのあるマスに移動すると、毎ステップhaliteを25%回収できます。逆に回収されないセルのhaliteは毎ステップ2%増えていきます。船が回収したhaliteは、拠点に持って帰って初めてスコアとして計上されます。また、haliteの所持量が小さい船を、所持量が大きい船に衝突させることで、大きい船を破壊し、そのhaliteを奪える、という攻撃要素もあります。
(引用: https://www.kaggle.com/c/halite/submissions?dialog=episodes-episode-3419247)
以降は、コンペ参加者向けです。
コンペ序盤と方針決定§
アルゴリズムのアプローチは、強化学習を使う/使わないの2種類に分けられます。ゲームによって強化学習に向き不向きがあることは理解していたため、コンペ序盤は強化学習が問題解決として筋が良いのか判断するために、「Haliteゲームの性質理解」と「強化学習が活躍するケースの体系化」に時間を費やしました。
結論として「強化学習に取り組むのは大沼になりそうだ」となり、強化学習は使わない選択を取りました。理由は主に「プレイヤーの行動空間の広さ」と「全体最適を求める難しさ」です。船は数十個まで増やせ、それぞれの船に6つの選択肢(上下左右+居座る+コンバート)があるため、プレイヤーの行動空間は船の数に応じて指数関数的に増加します。例えば、30個の船があると1ステップで6^30の行動パターンがあります。AlphaGoが活躍している囲碁でさえ、ステップごとの選択肢は高々数百しかありません。
この行動空間の広さを解決するために、船ごとに強化学習をするアプローチが妥当だと考えられます。しかし、船ごとの最適は求められるかもしれませんが、全ての船を考慮した全体最適な行動を求めるは難しいため、非強化学習のアプローチを超えるためには相当な努力が必要ではないか、という考えに至りました。
一方で、前回開催されたHaliteコンペ（今回とは少々ルールが異なる）では、強化学習で良い成績を残していたチームも存在していたため、強化学習を完全に捨てることはせず、コンペ中盤以降はチームメンバーであるJohannesが強化学習に張り続ける方針にしました。
解法の概要§
私たちの戦略のポイントは以下の6点です。
- 100ステップ目まではhaliteを積極的に回収する。船を作れるなら作る。
- 101ステップ目から300ステップ目までは相手を積極的に攻撃しhaliteを過度に回収しない。船を作れるなら作る。
- 301ステップ目以降はhaliteを積極的に回収する。船は作らない。
- 「船とターゲットセルの最適マッチング」と「船と次ステップセルの最適マッチング」の2段階のマッチングを最小コストフローで解く。
- 拠点に船を居座らせ、拠点を破壊させない。
- 拠点は面を取るように配置し、陣地の面積を広げる。
100ステップ目まではhaliteを積極的に回収する。船を作れるなら作る。§
船の生成タイミングは、基本的に早ければ早いほうが有利です。例えば、390ステップ目に船を生成するのは悪手です。また、船を200ステップ目に生成するのであれば、199ステップ目に生成したほうが1ステップ分の得です。さらに、後述しますが相手を攻撃するとき船が多いほうが破壊できる確率が上がるため、序盤にhaliteを貯めることは悪手です。まとめると、序盤はHaliteを効率的に回収しつつ、船を多く作るのが重要になります。
上位のbotのほとんどはこの戦略を取っていたように感じます。
101ステップ目から300ステップ目までは相手を積極的に攻撃しhaliteを過度に回収しない。船を作れるなら作る。§
100ステップ目あたりで場のhaliteがほぼ枯渇します。いわゆる共有地の悲劇です。また、船は20個程度になります（各プレイヤーの実力が均衡していれば）。
ここからは、haliteを回収しても雀の涙であるため、相手の船を壊す戦略が有利です。船は500 haliteで生成できるため、船を壊せば攻撃相手は500 haliteほど損することになります。私たちはhaliteを持つ船を最大4つの船で攻撃するようにしました。1つの船で攻撃するよりも複数の船で攻撃するほうが、敵船の行き場を無くせる可能性が高くなるためです。
また、haliteは極力回収しないほうが有利です。haliteを回収すれば相手の攻撃対象になります。拠点から離れたセルで回収してしまうと破壊される確率が高くなります。私たちは、拠点より一定距離離れたセルにあるhaliteの回収を避けました。
回収を避けることには、もう一つの目的「halite量の回復」があります。例えば、500 haliteが埋まっているとき、1ステップで125 halite獲得できますが、20 haliteが埋まっているときは、1ステップで5 haliteしか獲得できません。適度にhaliteを回収することでhaliteの枯渇を防ぎます。
301ステップ目以降はhaliteを積極的に回収する。船は作らない。§
300ステップ目までに、上手く進めば相手の船の数は減っています。また、攻撃していることと、拠点の周囲にhaliteを過度に回収しないことで、場にhaliteが貯まっています。このhaliteを一気に回収します。
船の生成はストップします。船を新規で作っても、その船で500 haliteを回収するのは難しく元が取れないためです。
「船とターゲットセルの最適マッチング」と「船と次ステップセルの最適マッチング」の2段階のマッチングを最小コストフローで解く。§
マッチングは最小コストフロー（最小費用流）問題として定式化して解きました。最小コストフローは、けんちょんさんの記事『実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！』が大変まとまっています。競技プログラミングではお馴染みの数理最適化問題です。
この2段階のアルゴリズムは、船がhaliteを回収する流れを踏まえています。haliteの回収は以下の流れです。
- 場の中でhalite量が多いセル（ターゲットセル）に移動する。
- そのセルに居座りhaliteを回収する。
- 回収したhaliteを拠点に持ち帰る。
船とターゲットセルの最適マッチング§
上記の流れのようにhaliteを回収するのは、ターゲットセルへ到着する数ステップ先を考慮する必要があります。船ごとに各セルへの距離やhalite所持量は異なるため、船とターゲットセルの最適なマッチングは重要です。マッチングにより、
- 複数の船を同じセルへ向かわせる。
- 別の船を向かわせたほうが到着が速い。
- 味方の船を衝突させる。
のような悪手を一括で解決できます。特に後半2つの悪手は、船ごとにループを回してターゲットセルを決定する手法で対処が困難です。
船ごとに各セルの評価を次のように求めます。
- 衝突したときに負ける（halite所持量が小さい）船が居るマスと周囲4マスは移動禁止とし、幅優先探索で各セルごとの最短経路を求める。
- その最短経路を使って各セルに対し「何ステップ居座り、そのセルから最も近い拠点へ帰れば、1ステップの平均獲得halite量が最大化できるか」を求める。ここで、拠点に帰ることも考慮する。
- ノートブック『Optimus Mine Agent』と同じ手法です。
- ただし、このロジックは2つ以上のセルのhaliteを回収することを考慮していないため、改善余地があります。
- 101ステップ目から300ステップ目までは、そのセルに敵船がいる場合、敵船が持つhaliteを評価に加えます。
- その平均獲得halite量を各セルの評価値とする。
この評価値を用いた最小コストフローにより、全体最適な船とターゲットセルの組み合わせが求まります。
船と次ステップセルの最適マッチング§
ターゲットセルを求めたら、船ごとに次に移動するセル（次ステップセル）を求めます。現在居るマスと周囲4マスが対象です。この5マスに対し、目的地まで行くための最短距離を求め、その最短距離が小さいほど評価値を良くします。ただし、衝突して破壊されうる敵船が1ステップで移動可能なマスは、評価を極端に悪くします。
この評価値を用いた最小コストフローにより、全体最適な船と次ステップセルの組み合わせが求まります。フローの辺の張り方上、味方の船同士がぶつかることはありません。
拠点に船を居座らせ、拠点を破壊させない。§
対戦相手の中には拠点を攻撃してくるbotが存在していました。拠点を破壊されると次の2つの理由から大きなダメージになります。
- 拠点を作るには、拠点から船を生成し、船から拠点にコンバートとする必要があり、1000 haliteを消費する必要がある
- 拠点があることを前提に様々なロジックを組んでいる
相手の船も消滅するとはいえ、拠点は破壊されないようにすべきです。私たちは、拠点の上に船を常時配置することで、この問題を解決しました。
拠点は面を取るように配置し、陣地の面積を広げる。§
中盤に各セルのhaliteを貯めるロジックですが、せっかく貯めたhaliteを敵船に回収されたくはありません。面を取るように拠点を配置して陣地を作ることで、その中に敵船を入り込む余地を少なくし、たとえ敵船が陣地内に入りこんでhaliteを回収されたとしても、その敵船を囲い込み破壊しやすくなります。
ソースコード§
最も点数が高かったbotのソースコードです。 https://gist.github.com/minaminao/cbe4a3d514ea9ae924cb5d59181d78cc
おわりに§
他にも細かなアルゴリズムを幾つか実装しましたが、それらは割愛します。コンテスト序盤で最小コストフローを2段階で用いるアルゴリズムを導入しました。このアルゴリズムが他のロジックと組み合わせやすく万能だったのが最後まで効いてきたと思います。強化学習を上手く適用できなかったのが心残りです。次は金メダルを獲りたい。