AI Sports Challenge 2021 参加記
コンテスト概要
CoderOneのAI Sports Challenge 2021というコンテストに参加しました。
ゲームの雰囲気は以下の決勝イベントの配信を参照↓
このイベントはMongoDBやGitLabといった強い企業がスポンサーについており、賞金総額が5000AUドル（約４２万円）と高額なことが特徴。
CoderOneはオーストラリアの企業なので、日本から参加する場合は時差が少ないのが良いです。
コンテストのルール
使用するプログラミング言語は自由、DockerのLinuxコンテナ上で実行できるものなら何でも良い。
サーバーとのやりとりはHTTPS通信で行う。PythonとTypeScriptのサンプルは提供される。
予選はダブルラウンドロビン総当り形式、決勝はダブルエリミネーショントーナメント形式。
予選までに他の参加者のボットと対戦する機会は２回あり、それぞれScrim1、Scrim2と呼ばれている。そのとき提出している最新のボットでラウンドロビン形式の対戦が実行され、対戦結果のリプレイと標準エラー出力がもらえる。
対戦結果のリプレイはCoderOneのサイトにアップロードして再生でき、１手ずつの確認もできる。
ゲーム本体のコードは公開されない。
最初の３日の間はゲームのルールが変更されることがある。
上位８位まで賞金あり。
ゲームのルール
・1vs1の同時着手のターン制ボンバーマン。
・ブロックはHP1のWoodブロック、HP3のOreブロック、HP無限のハードブロックの３種類がある。
・ブロックを壊してもアイテムは出現しない
・初期ステータスはボム３、火力３（火力は直径で表す。つまり火力３の半径は１マス）
・設置した爆弾が爆発しても所持爆弾数は回復しない。
・ボムアップと火力アップは画面上にランダムに出現する
1) ボムアップを取得することで所持爆弾数が１回復する
2) 火力アップを取得することで火力の直径が２上昇する
・爆弾はリモコンボムであり、任意のターンに爆破できる。40ターン経過すると自動で爆発する
・爆風は10ターン残る
・ダメージを受けると５ターン無敵状態になる
・行動は移動 or 爆弾設置 or 爆弾を１つ爆破
・２人のキャラクターが同じセルを専有することはできない。
・同じターンに移動先がかぶった場合、先に出力したほうが先に行動する。
1) 移動先がかぶっている場合、先に移動したほうだけが移動できる
2) 相手が移動していなくなった座標に、後から移動したほうは移動できる
・1800ターンが経過すると画面端から火で埋まっていく（この記事ではこれを『終焉ファイアー』と呼ぶことにする）。これに当たると、爆風に当たったときと同様に１ダメージを受け、５ターン無敵になる。
・爆風はアイテムや爆弾を貫通しない。人は貫通する。
・１ターンの思考時間は100ms
・思考時間中に何も出力がなかった場合、そのターンは何もしない。
参加日記
コンテスト開始まで
2021年１月、Twitterを見ていると@CoderOneHQからフォローが来ていることに気付く。調べてみると、CoderOneというサイトで2020年冬にゲームAIコンテストが行われていたようだ。まだ遊べるようなので、少し見てみようと思いゲームをダウンロードしてみる。Pythonオンリーなので結局ほとんど触らなかったが、次のコンテストには参加してみたいのでDiscordサーバーに参加する。
2020年２～４月、AI Sports Challenge2021がアナウンスされる。2021年のコンテストではPython縛りが無くなり、言語が自由とのアナウンス。C++大好きマンの私には非常に嬉しい知らせだった。題材は今回もボンバーマンのようなので、CodinGameのHypersonicで練習する。
2020年４月中旬、提出はDockerFileをなんやかんやとアナウンスがある。Dockerを何も知らない私には提出難易度高そうだなと思いつつとりあえずDocker for Windowsをインストールし、Ubuntuのビルドなどを簡単に試してみる。
一通り準備が出来たので、コンテストの開始を待つ。
１日目（木）
ルールのドキュメントが公開されたので読んだ。
・Dockerでのゲーム実行環境構築
・ゲームのルール（概要）
・ゲームのルール（詳細）
・プログラムの提出方法
けっこうな分量があり、ざっと読んで雰囲気をつかんで１日目は終了
２日目（金）
ドキュメントに沿ってDockerのビルドを試す。私の環境はWindows10 Homeエディションだが、特に詰まることなくビルドできた。ここまででPythonで書かれたランダムウォークのサンプルプログラムが動く状態になった。
チュートリアルに沿ってやるならば次はこのランダムウォークを改良していくのだが、私はC++で参加したいのでPythonのチュートリアルはパス。
ゲームサーバーと通信する部分をC++で書こうと思いHTTPS通信フォーマットの仕様書を確認したが、死ぬほど複雑だったので一瞬で諦める。通信部分はPythonのサンプルプログラムをそのまま使い、PythonのSubProcessを使ってC++と標準入出力でやりとりする方式にすることに決める。これで２日目は終了。
３日目（土）
C++が動くDockerFileを作るのだが、Dockerに関する知識ゼロの状態だったのでかなり苦戦した。
まず、デフォルトのDockerFileはpython3 alphinというものを使うようになっていたがよく分からないので使い慣れたUbuntuに変更する。
C++バイナリを実行出来るようにしなければならないが、どうすればいいのかよくわからない。とりあえずWindowsのWSL上でコンパイルした実行ファイルをDocker環境に受け渡そうとしてみたが、なかなかうまくいかない。Copyコマンドとかを使ってみるが、Dockerビルド中は存在するがDocker runをするときに消えているという現象に悩まされる。Windowsのフォルダをマウントすればファイルは残ってうまくいくが、プログラム提出時はマウントを許可されていないので、他の方法を探す。build essentialsとかを入れてDockerビルド時にC++プログラムもコンパイルするとかいろいろ試したが、どれもこれもうまくいかない。
結論としては、Copyも何もせずDockerFileと同じディレクトリに実行ファイルのバイナリを置いておくだけで大丈夫だった。今日の私の苦労はいったいなんだったのか。。。
そんなこんなでPythonのSubProcessでC++の実行ファイルを起動できることを確認。
このころ、Discordではゲームのシミュレーションの順番を【爆発→移動】にするか【移動→爆発】にするか議論されていた。ロードインフェーズ（コンテスト開始から３日以内）はルール変更があるってもともとアナウンスされていたので、こういったルール変更は想定内。私はそこを議論するところまで全然進めてないのであまり深く追わず、結論の発表を待つことにした。
４日目（日）Scrim1提出期限
ゲームの入出力を見ていくことにする。ゲームルールのドキュメントを確認したところゲームサーバーから得られる情報は少なく、爆弾やアイテムは座標しか取得できないらしい。爆発ターンや爆弾の設置者は計算しなければならないようだ（めんどくさい）。
サンプルプログラムを読んでゲームサーバーと通信している部分を探す。通信はJson形式で行われており、サンプルプログラムではそれをParseしてPythonオブジェクトに突っ込んでいるだけだったので、結局そのオブジェクトにどのような情報が入っているのか、プログラムを読むだけでは分からない。とりあえずサーバーから受け取っているJsonをそのままDumpしてみる。
すると驚くことに、爆弾の爆発ターンや設置者、アイテムの消滅ターンなどの情報をゲームサーバーから受け取っていた。ドキュメントと異なるので頭の中が？？？になる。後で修正されるのが少し怖いが、受け取っている情報はとりあえず全て使うことにする。（この３日後ぐらいにドキュメントのほうが修正された。ドキュメントが間違っていたらしい）
ゲームの入出力が分かったので、それをPythonからC++へ受け渡す部分を書く。Pythonの出力処理とC++の入力処理を両方書かないといけないので、けっこう時間がかかった。
Scrim1の提出期限がこの日の午後４時だったので、左右に反復横とびするだけのボットをC++で書いてそれを提出し、４日目は終了。
お分かりだろうか。私はここまでゲームAIプログラムをほぼ組んでいないのである。けっこう苦しい気持ちになっていたが、ここからはようやくボットプログラミングに取り組めるので気合を入れ直して頑張ることにする。
ちなみにシミュレーションの順番は【爆発→移動】に決まったようだ。ターンの開始時に爆風の上にいたら、このターンに移動しても避けることはできない。
５日目（月）
いよいよボットを組んでいく。まずはシミュレーションを書く。５日目終わり
（え、このペースで間に合うんか？）
そうこうしているうちにScrim1の結果が出ていたのでさっそく確認、元気に反復横とびするWizardを見れたので一安心。無事にDocker Build Contestに優勝。
６日目（火）
DUCTを書く。プレイアウトはせず、評価関数を返すようにする。さらに、Expansionフェーズで子をランダムに１つ展開するのではなく、全ての子を評価してから、お互いが最も評価値の高い行動を選択したときの子を１つ展開するようにする（UCTで、評価関数が設計できるゲームでは最も評価値が高い子を１つ展開したほうが良いことが多いので、それをDUCTでも真似た感じ）
評価関数は
・HP差
・確実にダメージを与えられる状態か
・プレイヤーのステータス（爆弾数、火力）
・アイテムへの距離
・面積最大のエリアにいない場合はペナルティ大
ここで、確実にダメージを与えられる状態はなかなか発生しないことがわかった。なぜなら、例えば相手が自分のすぐ隣に爆弾を置くことを考えると
①相手が爆弾を置く
②自分も爆弾を置く＆相手が１マス移動する
③自分が爆破する ＆相手が１マス移動する
とすれば、③で相手が移動する前に自分の爆破が処理されるため、確実に自爆に持ち込めるからだ。相手が袋小路にハマっているとしても、単に相手の横に爆弾を置くだけでは自爆されるので意味がない。一方的にダメージを与えるのはかなり難しそうに思える。
ここまでで、とりあえず自分のHPが減らないような行動をするようにはなった。Scrim2の提出期限が明日の午後４時なので、もう提出しておく。これで６日目は終了。
７日目（水）Scrim2提出期限
PythonのSubProcessがBroken Pipeと表示されて異常終了するバグに悩まされる。
結論から言えば、SubProcessで呼び出しているC++側のプログラムがエラーで落ちるとこうなるらしい。これに気づかずSubProcessの仕様を永遠に調べていてかなりの時間を無駄にしてしまった。悲しい。
C++側プログラムが落ちている原因を調べていると、うっかりNDEBUGを定義していることに気づく。外してみたらassertが大量に鳴っていた。悲しい。
あとはひたすらバグ修正をする。おおかたバグが取れたところで７日目は終了。
８日目（木）
祝日なのでお仕事がお休み。
リプレイを確認したところたまに謎の行動が散見されるので、DUCTの状態をDumpして中身を調べる。するとExpansionフェーズで以下のようなことが起こっていた
・移動してもあまり意味がない、評価値は0.5
・爆弾を置くとやや不利になる、評価値は0.48。だが、相手も爆弾を置くとき、自分も爆弾を置くと必ず勝てる、評価値1.0
↓
移動の平均評価値は0.5、爆弾設置の平均評価値は0.6。よって、爆弾を置くのが期待値が高い！
のようなことになっていた。しかし相手にとったら、爆弾を置くと負け確になる可能性があるので、当然爆弾は置かない。それなのに、期待値計算に相手の爆弾設置が考慮されているのはおかしい。
そのため、以下のように改造した。
①自分の各行動について相手の各行動を試し、自分の各行動の期待値を計算する。
②相手側も同様に計算する
③自分の各行動の期待値を再度計算するが、このとき相手の行動は②で得た最も期待値の高い行動で固定する
④相手の各行動の期待値を再度計算するが、このとき自分の行動は①で得た最も期待値の高い行動で固定する
上の例に当てはめると、
①自分の移動の期待値は0.5、爆弾設置は0.6
②相手側は移動が0.5、爆弾設置は0.4
③相手側の行動を移動で固定、自分側の期待値を再計算すると移動が0.5、爆弾設置は0.48
④自分側の行動を爆弾設置で固定、相手側の期待値を再計算すると移動が0.5、爆弾設置は0.0
よって、自分の行動は移動、相手の行動も移動となり、それらの行動をとるときの子ノードが１つ展開される。
これをやったことで、おかしな行動はかなり減った。
しかしまだおかしな行動があったため調べると、以下のようなことが起こっていた。
UCB1第二項の力により、自分がズッコケた行動を選択してみる
UCB1第二項の力により、相手もズッコケた行動を選択してみる
↓
結果、お互いのズッコケた行動の評価値が上がる！
↓
ズッコケた行動の評価値が下がるまで、永遠にズッコケた行動を試し続ける
↓
評価値が下がる前に時間切れ、ズッコケた行動が最適！
という感じになっていた。
これを解決するために、MCTSのSelection～Backupを１イテレーションとして、イテレーションごとにUCB1第二項の係数Cを自分だけ0にする、UCB1第二項の係数Cを相手だけ0にする、というのを交互にやってお互いに同時にズッコケるのを防いだ。
これらの改造はこのゲームに限らず、DUCTに対して普遍的に使えそう。
あとは諸々のバグ修正をたくさんやって８日目は終了。
９日目（金）
バグ修正と評価関数の調整。自分で置いた爆弾に挟まれに行くことがあったので、評価関数に全ての爆弾が爆発するまでの生存可能チェックを追加した。生存不可の場合、HP-0.9と同等のペナルティ。
また、自分と相手から同時にFloodFillをして、自分が先に移動可能なマスの面積を評価値に加えた。（以下、これを面積最小化と呼びます。相手が移動できる面積を最小化するという意味）
９日目は終了。
１０日目（土）予選提出期限
予選前ということで余計なことはせず、ひたすらバグ修正をする。自分vs自分で対戦させてリプレイを見ておかしな行動を見つけ、原因を探す。これの繰り返し。かなりいい感じの動きになってきた。１０日目は終了。
１１日目（日）予選結果発表
予選の配信を見る。リプレイを見た感じ思ったとおりに動いてくれている。結果は２位だった。
予選に提出したチームは２４チームのみらしい。350人以上の参加登録があったと聞いていたので、100ぐらいは提出あるかと思っていたら全然そんなことなかった。Docker Build Contestを抜けられなかった人が多かったのかな。
自分と１位との対戦リプレイを見ると、こっちが画面端のアイテムを取りに行ったときに画面端に閉じ込められ、そのまま終焉ファイアーに焼かれて負けていた。アイテム収集よりも相手の行動可能範囲を最小化するほうが良いのだろうか？など考察しているうちに１１日目は終了。
ここで決勝のルール変更のアナウンスがDiscordに流れる。もともとは先に２勝したほうが勝ちだったが、４勝したほうが勝ちになった。良い変更だと思う。
１２日目（月）
アイテム収集と面積最小化のバランスに悩みながら、ひたすらバグ修正をする。１２日目は終了。
ちなみに、このゲームでは何百回も対戦まわして勝率計算みたいなことはやりにくい。ルールベースのAIで1msで応答できるみたいな場合は１戦10秒ぐらいで終わらせられるので可能だが、私のボットのように時間いっぱいゲーム木探索するような仕組みの場合、１戦が最大で４分ぐらいかかるためかなり厳しい。
１３日目（火）
ここで突如、新ルールが追加される。「10試合をしても勝敗が決まらない場合、自爆したほうが負けになる」というルール。運営側も、長時間試合が終わらない可能性を考慮してこのルールを追加したようだ。
しかしこのルールは非常に不明瞭で、例えば
１．自分の爆弾が爆発するターンに相手が爆弾を置くことで、自分の爆弾が相手の爆弾を誘発して引き分けになった場合
２．自分の爆弾で安地が無くなった結果、終焉ファイアーのある場所に移動してHP0になった場合
それぞれどちらの自爆なのか、それとも自爆じゃないのか非常に不明瞭。案の定、質問スレッドに質問が上がっていたのでこの件は公式の回答を待つことにする。
気を取り直してバグ修正と評価関数の調整を進めることにする。
ところが評価関数をいじりすぎてわけがわからなくなったので、いったんバグ修正だけコミットして他を全て元に戻す。
ここで１３日目は終了。
１４日目（水）
昨日の回答があった。
『最後に爆破を実行したプレイヤーの自爆とする』というものだった。この回答でもまだ曖昧だが、おそらく１のケースは自分の爆弾が爆発しているので自分が引き起こした自爆で、２も自分の自爆となりそう（分かんないけど）。
細かい部分が分からないままだが、出来る範囲で対処することにする。私のボットは少しでも不利な状態なら自爆引き分けにしようとするので、それを無くすために自爆する場合の評価を0.5から0.1へ下げることで概ね対処した。しかし、引き分けの『詰み』判定のほうが対処できない。その『詰み』が最終的にどちらの自爆で終了するのかを判断するのはかなり大変だからだ。時間があればやりたかったが、もう時間が無いのでそこは諦めることにした。
ここで、ずっと悩んでいたアイテム収集と面積最小化のバランスに良さそうな解決案が見つかる。アイテムを取りに行ったときに袋小路に閉じ込められるのが問題なので、袋小路に入らないならアイテムを回収したほうがよい。つまり以下のようになる
・幅１の通路を通らないととれないアイテムは無視、それ以外のアイテムは積極的に取る
・アイテムが無いときは相手の移動可能面積を最小化
これにより、良い場所を陣取りつつ、その場所から安全に取りにいけるアイテムだけ取るようになった。
さらに、せっかくアイテムを集めるのだからということで、攻撃モードを追加した。アイテムが一定量以上集まったとき、一定時間アイテム使用の評価値減少を０にする。これにより、惜しみなく爆弾を置いて敵を一気に攻撃する。(10戦後の)自爆は負けルールがあるため、相手を自爆せざるを得ない状況まで追い詰めれば実質勝ちだから、先に攻めたほうが有利になるのではと思い、この処理を追加した。
もろもろのパラメータを調整して、１４日目は終了。
１５日目（木）決勝提出期限
昨日寝る前に布団の中でふと頭に浮かんだバグを、朝起きてすぐ直す。目を閉じて心を鎮めることでバグに気づくこともあるので、何も考えずに落ち着くことも大切である。
１５日目は終了。
１６日目（金）決勝結果発表
優勝しました！！！！！
トーナメントの一番下から放送すると思っていたら、放送されるのは最後の４戦だけだった。初戦、1-3で負けてたときはもうダメだと思ったけど、そのあと奇跡的に２勝をとり、さらに最終試合で相手を自爆に追いこんで判定勝ち。
攻撃モードで爆弾を使い切って負けている試合もあったので、所持爆弾数0に対してもっと大きなペナルティを与えるべきだったかなと反省。
決勝では途中で2-1で勝っていたところを、自爆評価の下げすぎが仇となり、自爆できるところで自分だけ自滅するというまさかのズッコケムーブで2-2のタイになってしまうが、その後１勝をもぎ取って無事に１位になった。
とても嬉しいです。
感想
他の参加者のボットを見る機会が少ないのでみんなの強さが分からず、決勝でどのぐらいまで行けるか全然予想できなかったので決勝イベントを見るときは本当にドキドキでした。ドキドキコンテスト楽しい。
試合の結果を抜きにしても、DUCTに関する理解が深まったので参加してよかったと思います。
ちなみにこのコンテストはかなり過疎でしたが、その原因はDiscordのチャットを見た感じおおむね以下の点だったようです。
・Dockerを使った提出方法が複雑
・サンプルプログラムがPythonとTypeScriptしかない（例えばC++で参加したい場合、PythonからC++バイナリを呼び出す場合はPythonの知識が必要になるし、ゲームのフォーマットに合わせたHTTPS通信を組む場合は実装時間の面で大きなディスアドバンテージとなる）
・ゲームの題材が微妙（動かないのが最適、引き分けが多発する、同じセルには先に動いたほうが専有できるという若干の運要素など）
最初の２点に関しては、コンテスト初参加のときは苦労するけど２回目以降は大丈夫だろう、という感じです。
Dockerのビルドは１回参加して慣れれば次回は同じことやるだけなので大丈夫で、C++での参加についてもPythonからC++バイナリを呼び出す方法で特に不都合はなかったです。（PythonとC++の両方に標準入出力を書かないといけないのは少しだけ面倒でしたが、大きな問題ではないです）
ゲームの題材に関してはそんなに言うほど悪くはなかったと思うけれど、ほとんどカサカサ動いてるだけであまり爆弾を置かないので絵面は地味だったかなと思います。そのあたりは次回のコンテストに期待。
どんなコンテストだろうと、自分の書いたプログラムがかっこよく動いてくれればそれだけで楽しいものです。その機会を与えてくれた運営の皆様に感謝です。
PS.今回参加したかったけどコンテストの存在を知らなかったという方は、CodinGameのDiscordのexternal contestチャンネルをちょくちょく覗いてみると良いと思います。
