CodingGame Fall Challenge 2020 参加記

はじめに

この記事は「PERSOL PROCESS & TECHNOLOGY Advent Calendar 2020」の7日目の記事になります。
素敵な先輩方と同期が素敵な記事をたくさん書かれているので、是非他もご覧になってみてください。

概要と感想

世界2380位、Silver League1836位でした。一時はSilver800位くらいでGold Leagueも近いぜと意気揚々だったんですが、その後改善が思いつかずこんなことに...。
任意の勝負ごとに言えると思うのですが、伸びている間は自分をどこまでも行ける大天才であると感じ、停滞している間は自分が酷く愚かで惨めな人間になったように感じました。勝負事って怖いですね。
コンテスト期間かなり辛かったのでしばらく目を背けていましたが、この参加記を期に常設化されたコンテストに参戦しなおそうと思います。

CodinGame Fall Challenge 2020とは

一応社のアドベントカレンダーなので、社の人にも興味を持ってもらえるよう導入から丁寧に書きます。
CodinGame Fall Challenge 2020とは、CodinGameというフランスのサイトで11/13 - 11/24の11日間に渡って開催されたゲームAIコンテストです。
元々CodinGameというサイトはこういったゲームAIのコンテストを定期的に開催しており、今回はその秋の大会といった認識でいただければ良いと思います。

CodinGameそのものやゲームAIコンテストについて詳しく知りたい方はiwashi31さんのこれやツカモさんのこれを読んでみてください！とても面白い記事です！！

ルール

ツカモさんが和訳したものを公開してくださっています。ありがたい......。
ボドゲを嗜んでいる方は多分伝わるかと思いますが、ほぼセンチュリーです。
嗜んでいない方向けに言うと、呪文を唱えてポーションの素材を取得し、注文に応じたポーションを作ってお金を稼ぐゲームです。

ポーションを作る魔女のおばあさんを操作するAIを書きます。一対一で対戦し、お互いの戦略を競います。
各ターン、双方の魔女のおばあさんは以下の5つのアクションから1つ選んで行動します

LEARN: 新しい呪文を学ぶ
CAST: 呪文を唱えて素材を得る(一度唱えた呪文は休息するまで再使用不可)
REST: 休息により呪文を全て再使用可能にする
BREW: 与えられた注文リスト内のポーションを作る(そのポーションを作るだけの素材を所持している場合のみ可能)
WAIT: 何もしない

どちらかのおばあさんがポーションを6つ作るか、100ターン経過するまでゲームは続きます。ゲーム終了時に稼いだ額が大きかった方の勝利です。

具体的にどんな雰囲気なのか知りたければこちらのゲームリプレイを見てください。

やったこと

dequeに<inventoryの状態, 今覚えているmagicのリスト>を突っ込んで各ターンに唱えるmagicを全探索し、castable(休息不要)であればコスト+1, uncastable(休息が必要)であればコスト+2で01BFSを行い、現在の状態から各ポーションまでの最小手数を求めました。
最小手数を求めたはいいものの、その情報を実際の行動選択に反映するやり方が上手くなかったため、あまりいい結果は出せなかったというのが今回の敗因の分析です。

以下時系列で行きます

wood2 League

wood2 LeagueではBREWとWAIT以外は出来ないレギュレーション(素材は自動的に渡される)でした。
これは流石にやるだけで、与えられたポーションの注文の中から最も値段が高いものを見つけて出力すればよかったです。

wood1 League

LEARN以外は出来るレギュレーションです。私もここで苦しみました。いや、冗談を抜きにしても普通に難しかったと思います。
色々BFSを書いたりしてバグらせるなどしたのですが、wood1でいきなりガチガチに書かなくてもいいかと思い、

BREWできるポーションがあればその中で一番高いものを作る
なければランダムで適当な呪文を唱える(uncastableであればRESTする)

という方針で進めると突破できました。一日かかりました。

Bronze League

LEARNまで全てのアクションが解禁されました。ここからゲーム本番という感じでしたが、かなり苦しみました。
とりあえずLEARNを実装しないと話にならないので、ルールベースでtier-0の素材が沢山もらえるものと、tier-3の素材を他の素材に変換できるものを優先して取るような処理を書きました。
CASTについては、{tier-0: 2, tier-1: 2, tier-2: 3, tier-3: 3} みたいなバランスを保つようにCASTしていくと、大体の注文に対応できて強いんじゃないかなと思って書きました。ダメでした。
逆にtier-0が5個以下の時はひたすらtier-0を量産したらどうなるかなーと思ってやってみたけどやっぱりダメでした。
この辺りでTwitterを見ているとtier-3(黄色い三角形の素材)の素材を集めまくって詰むおばあちゃん(トライフォースババア)とか、LEARNしまくって全然ポーションを作らないおばあちゃん(勉強大好きおばあちゃん)にみんな苦しめられていて面白かったです。思うように動かないキャラへの呪詛も、神プレイを連発するキャラへの称賛も、全て自分に跳ね返ってくるのがゲームAIコンテストの面白いところですね。自分だけの最強ババアを育てましょう！

とはいえあまりにも上がれず辛かったので上述の01BFSを気合で書いて、雑に一番高いポーションまでの手数を経路復元するとBronze50位くらいまで上がり、そのままヤケクソsubmitしつつペン片手にノートとにらめっこしていたらSilverに昇格しました。放置でも上がれるとは知らなかったのでびっくりでしたね......。

Silver League

01BFSでポーションまでの最短手数はわかるようになったので、後は

どのポーションを狙いに行くか
どのタイミングで新しい呪文をLEARNするか

を考えればいいことがわかりました。
1については、ひとまず自分と相手の最短手数をそれぞれ計算し、相手の方が早く作れるポーションは目指さないようにしつつ、こちらが作れる範囲で一番高いポーションを狙いに行くようにしました。
2については、もう面倒だったので初回5ターンを全てLEARNに費やし、有用そうな呪文を事前に全て取ってから行動するようにしました。ヤケクソ感がありますが、後から知るところによると意外に上位層でもこの戦略を採用していた人は多かったようです。
この時点でSilver 800位くらいになりました。

ただここからが困ってしまって、何をすればいいのかわからず詰まってしまいました。1と2を良い感じに解決する評価関数を一生懸命考えていたんですが、相手の妨害とかを考えられなかったのは反省ですね......。

今回の敗因

ポーションを取りに行くシミュレーションは出来たが、それを実際の行動選択にうまく活かせなかった
ビームサーチなどのマラソンで汎用的なアルゴリズムを知らなかった

特にビームサーチは知らなかったといえば知りませんでしたが、発展形のchokudaiサーチも含めその名前は何度も聞いたことがあったので、ある程度詰まった段階でビームサーチについて調べ、どのような問題のときに使えるのかなどを理解し、この問題に応用することは当然可能であり、また実行すべきであったと反省しています。

上位陣はみんなビームサーチで結果を出しているようだったので(強いおばあちゃんは全員ビームババアになっていた)、常設化された方で勉強がてら書いてみたいと思っています。ビームサーチ、山登り、焼きなまし辺りはマラソンの度に聞くアルゴリズムなので、これを期に勉強していきます。
またマラソンで書くロジックは何とも泥臭くてきれいに書けないものが多く、デバッグもしづらかったため実装力がものを言うと強く感じました。どんなコンテストでも実装速度は正義なので、鍛えていきたいですね。ICPCは二度としたくありませんが......。

今後について考えていること

勝てなくて辛かったです。もっと頑張ります。来年頭くらいからAtCoderでマラソンコンテストがratedになる(マラソン用のrateが導入される？)らしいので、そこで頑張っていきたいですね！！
マラソンコンテストは、ガチガチのアルゴリズムコンテストに比べれば低レートにも勝機はある性質を持つ問題が多いので、初心者の皆さんも是非やってみてください。社でもっと競技プログラミングが流行れば、あーだこーだと感想戦も出来るし嬉しいのになと思っています。私のこの記事で、少しでも競技プログラミングに興味を持つ方が出てきてくれれば幸いです。