Article
2000時間。
これは私がスプラトゥーン2に溶かした時間です。
この時間をデータ分析の勉強に費やしていればと思いますが、
ゲーマーとしてのセンスは思わぬところで役に立つものです。
先日までKaggleにて“Halite by Two Sigma”というゲームAIコンペが開催され、
非常に楽しみながら参戦しておりました。備忘録として以下記します。
[目次]
1. 初のメダル対象シミュレーションコンペ”Halite by Two Sigma”とは？
2. 参加モチベーション：マルチエージェントとゲーム
3. Halite4のルール
4. Haliteコンペのユニークな点
5. 戦い方および参考図書
6. Topプレイヤーのログの分析
7. 工夫(苦労)した点
8. 最終的な戦略と結果
9. 上位陣および1位の解法
1. 初のメダル対象シミュレーションコンペ”Halite by Two Sigma”とは？
Kaggleには、下記4種類のコンペがあります。
・Predictコンペ：もっともスタンダードなコンペ。任意の環境で分析可能。
・Codeコンペ：Kaggleのオンライン環境で分析するコンペ。
・最適化コンペ：数理最適化を行うコンペ。競プロ勢が揃うスピード勝負のもの。
・Simulationコンペ：2019年12月から始まった、ゲームAIを作成しスコアを競うコンペ。
“Halite by Two Sigma”はKaggleにおける2つ目のシミュレーションコンペとなります。
シミュレーションコンペとしては初のメダル対象コンペであり、
1つ目のConnectXというチュートリアルコンペは参加者200人であったのに対し、
Haliteは最終的に1,139人が参加しました。
Haliteは、AIを活用したクォンツ系ヘッジファンドTwo Sigmaが定期的に開催するゲームコンペです。
2017に第一回が開催され、これまで年に1回のペースで開催されてきました。
各回ごとにゲームデザイン・ルールは異なります。
これまでは独自環境での開催で、今回のHalite4が初のKaggleでの開催となります。
Halite 1（2017）
初めての開催。1600人以上の学生・エンジニア・研究者などが参加
Halite 2（2018）
100以上の国から参加。ゲームデザインが独特。(3からはグリッドに戻された)
Halite 3（2019）
20以上のプログラム言語をサポート。上位に機械学習を駆使したbotが出現。
Halite 4（2020）
今回のコンペ。初のKaggleでの開催(これまではオリジナルサイトで開催)
2. 参加モチベーション：マルチエージェントとゲーム
さて、今回のコンペ、近年マルチエージェントに関心があり、
かつゲーマーとして時間を溶かしすぎた私としては
是非チャレンジしたいコンペでした。
マルチエージェントの取り組みとしては、ITmediaに連載中の記事にて、
「満員電車で快適に過ごすための動き方」を物理シミュレーションで解き明かす」、
「休日に会社の同僚と遭遇しないための動き方」を物理シミュレーションとゲーマーの英知で解き明かす」
などを執筆しております。是非ご覧くださいませ。
ゲーマーとしては、スプラトゥーン2で最高ランクであるウデマエXであり、
ゲーム実況チャンネル「ミランドラチャンネル」を運営しております。
エリア、ヤグラに続いて、ホコもXになれました～！自分のチャンネルのホコ動画を相当見返した笑笑 アサリは、、どうしよう、、他ルールと比較するとあまりsocha先生に教えてもらってない笑笑 #Splatoon2 #スプラトゥーン2 #NintendoSwitch pic.twitter.com/UVjZUQ5Q6b
— ミランドラチャンネル (@mirandora_ch) August 18, 2019
上記のような、ここ最近の取り組みの経緯があり、本コンペに参戦しました。
3. Halite4のルール
Halite4は自分のshipを動かして、もっともマップ上のHaliteを集めた人が勝利するゲームです。
shipの動きなどを決めるbotプログラムを作成・投稿して他のプレイヤーのbotと競います（手動では操作できない）。
主なルールは下記となります。
・初期Halite5000からスタート。初期位置は4隅。
・マップ上のHaliteはランダムに配置される。一定時間でマップ上のHaliteは回復。
・毎ターン、1セル分shipを動かせる。
・500Halite消費することでshipをshipyardに変換できる。
・shipyardは500Halite消費することでshipを生産できる。
・shipをマップ上のHaliteに重ねるとその位置のHaliteの25%を取得。
ただしこの時点では、shipのcargo(積荷)扱いで、まだ自分のHaliteに反映されない。
・shipがshipyardに帰還するとそのshipのHaliteを自Haliteとして取得できる。
・shipとshipがセルに重なったら、積荷が少ないほうが勝ち、負けたほうのshipは爆破。
負けたshipの積荷のHaliteを積荷として得ることができる。どちらのshipも同じ積荷の場合、どちらも爆破。
(ちなみにshipの重なり判定は自・敵関係なく行われる)
・自shipと敵shipyardが重なったら、自shipと敵shipyardどちらも爆破。
・shipとshipyardの生成数に上限はない。
自分のHaliteを集めつつ、敵をうまく妨害することが求められる非常に戦略性の高いゲームとなります。
4. Haliteコンペのユニークな点
Haliteコンペ、というよりもKaggleのシミュレーションコンペのユニークな点は3つあります。
・正解がないこと。
通常のKaggleコンペと異なり、正解の予測精度を競うわけではありません（正解がない）。
4人の”対人ゲーム”で他のKagglerが投稿したbotとスコアを競うことになります。
・スコア・順位は常に変動
初期スコア600から開始し、投稿したbotは同スコア帯のbotとランダムに常に対戦し続けます。
おおよその傾向として、1、2位だとスコア獲得、3、4位だとスコア減少、上下幅は対戦相手やresultによります。
・結果をプレビュー・データ取得可
自分だけではなく他の人の対戦履歴を動画でプレビュー可能です。
かつ各対戦は他の人の履歴含めてjsonデータでダウンロード可能です。
5. 戦い方および参考図書
さて、今回このコンペに取り組むにあたって最初に大きな方針を3つ決めました。
これはあくまで私がこうしたというわけで、これが正しいわけではないです。
（※後ほど、1位の方の解法を紹介します。）
・(深層)強化学習を使うかどうか
→使わない。（選択できる手が多く学習が困難？）
・機械学習を使うか、どのように使うか
→積極的に使う。盤面の分析から実際の手の選択まで幅広く使用。
・ゲーマーとしてのセンスの活かし方
→盤面の分け方や細かいルールベースの定石作りに活かす。
以上のことを考えるに至った背景として、コンペ参加中に読み返して参考にした書籍を3つ紹介します。
『AlphaZero 深層学習・強化学習・探索 人工知能プログラミング実践入門』
◯×ゲーム、ミニ将棋はじめ、様々な具体的なゲームを通して、
深層強化学習をPythonコードを用いながら学ぶことができます。
今回、深層強化学習を最終的に使うかどうかはともかく、
一通り勉強してから判断したかったため読了しました。
深層強化学習は用いなかったものの盤面をどのようにデータとして
機械学習にインプットしていくか、非常に参考になりました。
『ゲームAI技術入門』
下記3レイヤーでのAI構造など概念が非常に参考になりました。
– キャラクターAI：自律的な判断、時にチームAIに。
– ナビゲーションAI：自分と敵の位置把握。地点ごとの特徴など。
– メタAI：自分と敵のステータスなどの監視。
上記を別々のレベルのトピックとして解決していくという視点、
つまり、まず全体を把握し、次に周りの味方の役割を付与し、
その中でそれぞれのキャラクター(ship)の動きを決める、などが参考になりました。
『人工知能はどのようにして「名人」を超えたのか？』
最強の将棋AI”ポナンザ”の開発思想が詳細に述べられております。
特に下記が参考になりました。
「探索と評価」
どういう行動を選択できるのかの（時間内での）探索と、
各行動をとったときの評価、をどこまで先読みしてできるかが肝とのことです。
「残存よりも配置の重要性」
将棋はチェスよりも駒の動きが遅いため、盤面のどこかで危機が
起きた時に対応できるかは、駒がどれだけ残存しているかよりも
配置が重要とのこと。
（おそらく今回のHaliteも同様。いかによい配置を維持するか。）
「DNNは使わずロジスティック回帰を中心に使用」
計算時間を重視。十分戦える。（2020年現在はDNNも利用？）
さて、では実際に自分はどのような戦略をとっていったのか、記していきます。
6. Topプレイヤーのログの分析
まずは戦略を立てるにあたりTopプレイヤーのログを収集し、分析していきました。
・序盤のKPI設定
最初に考えたのは、「中盤でほぼ勝敗は決まるのか」ということです。
もしそうなら100step時点のデータから最終順位を予測できるかもしれません。
Topプレイヤーのゲームを1000試合収集して、
100step時点で1位だった人がそのまま1位になった割合は…
54.5%でした。
思っていたよりも低いです。
100step時点で1位であることにあまり固執しなくてもよいのかもしれません。
そこで相対値ではなく、絶対値でKPI作ってみることを考えました。
Topプレイヤーのゲームを1000試合収集して、
30step時点で総resource(ship*500+shipyard*500+halite+cargoの合計)が
8000未満だった人が1位を逃す割合は…
80.3%でした。
こちらはかなり高い数値です。
Map上の状況など関係しますが、とにかくゲーム序盤はこのKPI(総resource8000以上)を目指した行動をとることにしました。
・stepごとにship/shipyardをどれくらい生産するべきか
同様にTopプレイヤーのゲームを1000試合収集して、
各stepごとに自分・敵の状況、Map状況に対してどの程度の数のshipを生産しているかlightGBMで学習させました。
この学習済みモデルを毎stepごとに読み出して上限ship数に応じてship生産数を決めることにしました。
下記が学習に用いていない4つの試合におけるstepごとの実際のTopプレイヤーのship数と、
lightGBMが予測したstepごとの上限ship数の推移です。
試合ごとに毎stepでどれくらいのship数を生産すべきか異なるようですが、
状況に応じて上限ship数を適切に予測できるモデルを作成できました。
・各shipをstepごとに、どの程度shipyardから離れた位置で行動させるか
各shipをどの程度shipyardから離れた位置で行動させるかを決めるために、
Topプレイヤーと自分のshipの移動を可視化しました。
自分のbotはTopプレイヤーと比較すると、離れた位置まで移動するshipが少ないようで、
もう少し増やしても良いかもしれません。
・各shipごとにHaliteをどの程度集めるか。
各shipがどれだけHaliteを集めるかを決めるために、
Topプレイヤーと自分のshipがどれだけHaliteを収集したかを可視化しました。
自分のbotはTopプレイヤーと比較すると、Haliteを持ちすぎかもしれません。
Haliteを集めすぎると他のshipに強奪されるリスクが高まりますので、
もっと早めにshipyardに帰還するようにしたほうが良いかもしれません。
7. 工夫(苦労)した点
Topプレイヤーの分析を通して大まかな動きを決めたあと、
細かな点で工夫(苦労)した点が3つあります。
・自/敵の状況に応じた期待値Halite計算
現在位置から遠いセルのHaliteは敵にとられる可能性が高いので、
現在位置からの距離、および自・敵の状況でHaliteの期待値を調整しました。
期待値Halite = そのセルのHalite * (現在地からの距離による係数) * (そのセル周辺の敵割合)
上記によって、次にshipが向かうべき目的地を現実的なHalite期待値に応じて、
決めることができました。
距離に応じた期待値Halite計算は様々な関数を作成して、
ローカル環境での自分bot vs 自分botで、もっとも強い関数をテストしました。
・状況に応じた敵への攻撃
100step以降、暫定1位の敵をそのままにしておくと逃げ切られるため、
優先的にその敵のshipyardを攻撃するshipを一定数作成しました。
・攻撃的な敵への対処
shipyardごとに閾値を設けて、もし敵がその閾値を超えてshipyard近くに入ってきたら、
そのshipyard周辺の味方の一定数を、敵撃退を最優先にした動きに変更しました。
なお、どれくらいの味方を敵撃退ルールに変更するかはローカル環境で調整しました。
8. 最終的な戦略と結果
stepごとにロジック切り替えることにしました。
序盤・終盤はルールベース、中盤は機械学習モデルで制御しています。
盤面ごとの対応もstep次第で判断しました。
・序盤(1〜50step)
-初期Halite5000を全て消費して、真っ先にshipを9つ作る。
-初期位置から5×5以内のセルで、Halite量がTop10のセルを探索、
それを初期位置から遠い順に各shipの目的地として割り当て。
-敵を倒すことに執着しない。ただしshipyardは守る。
・中盤(50〜350step)
-ship/shipyardの生産、基地からどこまで離れた場所のセルにいくか、
などをlightGBMのモデルで計算
-その他、状況に応じて、攻撃/防御に特化したshipを割り当て。
・終盤(350〜400step)
-残りstepで基地に戻れるかをチェック。戻れるギリギリまでHaliteを収集。
-最終盤ではshipの生産はしない。shipyardの生産も2つまで。
-最終盤では自ship通しで衝突してもいいから基地に戻る。
※自ship通しで衝突するとHaliteが少ないほうのshipに
どちらとものHaliteが集約される。
-敵を倒すことに執着しない。ただしshipyardは守る。
以上による最終結果は…
1139チーム中、83位（Top8%。銅メダル受賞）でした！
正直、途中まで銀メダル圏内におり、最後もかなり惜しいところまでいったので悔しいかぎりですが、
上位陣の解法を読むと、自分が考慮できていなかった点が多くあり、妥当な順位かなと思います。
9. 上位陣および1位の解法
さて、上位陣ですが錚々たるメンバーが出揃ってしておりました。
1位. Tom Van de Wiele さん
Deep Mindのデータサイエンティスト（※現在、Intelecyに転職）
2位. Raine Force さん（會田 翔さん）
バンダイナムコのAIエンジニア
…
9位. Robiland さん（Per von Soostenさん）
ハーバード大学のポスドク
いや、すごい…。
では、1位のTom Von de WieleさんはどのようにHaliteを攻略したのでしょうか。
コンペ終了後、彼の解法を彼自身が解説および全コードを公開しております。
下記、抜粋して紹介します。（私の日本語訳および解釈が間違っていたらすみません…）
まず何よりも気になる点は深層強化学習をメインで使用したのかどうかですが、
深層強化学習はあまりうまくいかず、状況ごとの細かなコンポーネントを
丁寧に積み上げていくことでハイスコアを獲得したようです。意外でした。
彼のコメントにその理由が述べられております。
“DeepMindでの経験から戦略ゲームにおける深層強化学習の力を
目の当たりにした。だからHaliteも良い成果がでると確信していた。
しかし、1か月ほど費やしてもうまくいかず、別のアプローチを試すことにした。
任意の数のship/shipyard、長いゲームスパン(400step)、動的な対戦相手では、
(深層強化学習だけで戦うのは)困難だった。”
結果、細かい状況ごとのコンポーネントを積み上げていくことにしたようです。
例えば一部を紹介すると下記のようなもののようです。（※図は自分なりの解釈）
・Camping strategy
敵のshipyardを邪魔する。最初にリスクを犯さずに敵shipyardに近づく。
そこで敵が積極的に攻撃してくるかを観察。
別のミッションに割り当てられるまで基地の周りを旋回し続ける。
・Opponent ship boxing in
敵の行動を予測できると確認している場合は、
4隻未満の船でも囲い込む。
スコアが近い敵を特に囲い込むようにする。
・Opponent hunting
途中から平和的にHaliteを収集することはあきらめたとのこと（笑）。
Haliteが0の船は、Haliteを持っている敵shipに向かって移動し
敵shipの脱出方向がないように徐々に追い込むルールを設定。
・Rescue missions
自shipが敵に窮地に追い込まれているときは、
近くの自分のHalite0の船が助けに行く。
いかがでしたでしょうか。
さて、現在Kaggleでは3つ目のシミュレーションコンペとして、
“Google Research Football with Manchester City F.C.”という
サッカーAIのコンペが開催中です。
何を隠そう、横浜F・マリノスの大ファンで、
サッカーロシアワールドカップでは現地に観戦に行き、
日本代表戦でテレビで見切れたサッカー好きの私としては、
参戦しないわけにはいかないのではないでしょうか。
秋も深まり肌寒くなってきましたが、
日本代表のユニフォームを引っ張り出して、
次のコンペに向けてタイピングのウォーミングアップを始めたこの頃です。
関連記事:
人気記事:
