⛳

CodinGame Spring Challenge 2021 参加記

2021/05/30に公開

競技プログラミング

CodinGame

tech

はじめに

年に2回、5月と11月に、約11日間にわたってゲームAIを実装するコンテストがCodinGameで開催されています。このコンテストが今年も開催されました。こちらのコンテストに参加したので、私が実装したAIについて、忘備録も兼ねてまとめました。

参加コンテスト名：CodinGame Spring Challenge 2021
開催期間：2021.05.06 23:00 - 2021.05.17 17:00 JST

前回のコンテストにも参加しており、そちらの参加記もまとめておりますので、よろしければご覧ください。

アジェンダ

CodinGameとは？
CodinGame Spring Challenge 2021のルールの概要
私のAIの実装方針
結果
上位陣のAIより学ぶ
感想
あとがき

CodinGameとは？

様々なゲームのお題について、ブラウザ上でAIを組んで、そのAIでゲームを攻略することができるウェブサービス（https://www.codingame.com/ ）。
難易度も様々で、簡単なAIの実装から徐々にステップアップすることができる。
使用可能言語は以下の27言語で（2021.5.30.現在）、自分の好きな言語を使ってAIを実装することができる。
　Bash, C, C++, C#, Clojure, D, Dart, F#, Java, JavaScript, Go, Groovy, Haskell, Kotlin, Lua, Objective-C, OCaml, Pascal, Perl, PHP, Python3, Ruby, Rust, Scala, Swift, TypeScript, VB.NET
メモリ制限はどの言語も768MB

各言語の動作環境はCodinGame公式サイトのFAQを参照してください。
https://www.codingame.com/faq

CodinGame Spring Challenge 2021のルールの概要

ルールを詳細にここに書いていくと、記事が長くなりすぎるので、概要のみお示しします。
詳細は下記の記事にまとめました。こちらも合わせてお読みいただけると、以降の記事がさらにわかりやすくなると思うので、よろしければご覧ください。

ゲーム概要

植林ゲーム！
木を成長させ、木の一生のサイクルを回すことで、勝利ポイントを得る
各ターンの最初に得られるSunPointを使って、行動を行う
各ターンで複数回行動が取れる
24ターン経過した時点で、勝利ポイントが多い方の勝利（同点の場合は、木の本数が多い方が勝利）
プレイヤーは、以下の4種類のコマンドのうち、実行可能なコマンドを１つ選択し、それを出力することでゲームを進める

コマンドの種類

SEED [cellIndex1] [cellIndex2]
[cellIndex1]のマスにある木から、[cellIndex2]の空きマスに種を飛ばす
GROW [cellIndex]
[cellIndex]のマスの木を1段階成長させる
COMPLETE [cellIndex]
最大サイズ（3）まで成長した[cellIndex]のマスの木の一生を終えさせて、ポイントを獲得する
WAIT
何もしない

私のAIの実装方針

以下のように実装方針を決め、ゲームAIの実装を行いました。

数ターンで大きく状況が変わるため、あまり先のターンまでは探索しない
次に実行できるコマンド全てについて、実行した場合の盤面の評価値を計算し、最も評価値が高いコマンドを実際に行う
より成長段階が進むようなGROWの優先度を高くする
理由：
- 勝利ポイントを得るためには、サイズ3の木が必要だから
- 木のサイズが大きいほど、各ターンのはじめに獲得できるSunPointが多いから
- 木のサイズが大きいほど、他の木に影の影響を与えやすいから
- 木のサイズが大きいほど、他の木による影の影響を受けにくいから
影の影響を受けにくいマスを計算し、SEEDをする
SunPointを多く得るために、基本的に後半のターンまではCOMPLETEを実行しないが、現在の木の配置で3ターン先までの影の影響を計算して、SunPoint獲得にあまり寄与していないサイズ3の木についてはCOMPLETEを行うようにする
- 早いうちにCOMPLETEを行った方が、獲得勝利ポイントが多いため、獲得SunPointと獲得勝利ポイントのトレードオフになる

各コマンドの評価基準の詳細

共通
- コマンド実行後の盤面で、次のターンに獲得できる見込みSunPointを計算し、この値が大きいコマンドほど評価値を高めに見積もる（他の基準に比べて重みは低め）
- サイズが大きい自分所有の木が多く存在する盤面ほど高く評価する
- 最終ターン（Day23のターン）にCOMPLETEが実行できなくなるターンでのSEED、GROWコマンドは行わない
  - Day20以降のSEEDは評価値を0にする
  - Day21以降のサイズ0 → 1のGROWは評価値を0にする
  - Day22以降のサイズ1 → 2のGROWは評価値を0にする
  - Day23以降のサイズ2 → 3のGROWは評価値を0にする
SEEDコマンド
- 現状の木の分布で、3ターン先までの影の影響を計算し、影の影響を受けないマスへのSEEDを高く評価する
- 同じ木のサイズの場合は、より土壌の肥沃度(richness)が高いマスほど高く評価する
GROWコマンド
- GROW元の木のサイズが大きいほど、評価を高くする
- 同じ木のサイズの場合は、より土壌の肥沃度(richness)が高いマスを高く評価する
COMPLETEコマンド
- 残り3ターン(Day21以降)は、コマンド実行に必要なSunPointがある限り、確定でCOMPLETEコマンドを実行する
- それ以外のターンは、3ターン先までの影の影響を考慮し、影の影響を受けるターン数が多いマス（SunPointを獲得できる見込みが少ないマス）についてCOMPLETEの評価を高くする
WAITコマンド
- それ以外のコマンドを行うために必要なSunPointがなくなった場合は確定で実行
- 共通の「最終ターンにCOMPLETEが実行できなくなるターンでのSEED、GROWコマンドは行わない」に該当し、かつサイズ3の木が存在しないため、COMPLETEも実行できない場合に実行。

結果

Silverリーグ600位代、全体順位2500位代で終了
日本人の上位割合が高かった
CodinGame Fall Challenge 2020に比べて、LegendリーグとGoldリーグの人数割合が多かった。全体の参加者数は前回と同程度であった（今回：6906人、前回：6872人）。

https://youtu.be/AFDzg6R-Xmw
私が実装したAIの対戦例

CodinGame Fall Challenge 2020のリーグ人数分布

CodinGame Spring Challenge 2021のリーグ人数分布

上位陣のAIより学ぶ

～reCurseさん（世界1位）vs bowwowforeachさん（世界2位）2021.05.28のとある対戦より～
https://youtu.be/AIdNVpJ4iaE
(下記の対戦記録のURLのリンクが切れたときのことを考えて、念のため、動画にも残させていただきました。)

上記対戦結果を閲覧できるURL

上記の対戦結果や他の方の対戦結果をもとに、実装に生かせる戦略をピックアップした。

将棋で言う桂馬（チェスでいうナイト）の配置になるように木を植えている
- 自分の木どうしの影がかからないようにするため
中盤のターンでも積極的にCOMPLETEを行っている
- 早いうちに、COMPLETEを行った方が、Nutrientが多いため、得られる勝利ポイントは大きいから
各サイズの木の本数を制限している
- 森全体にある自分の木の本数が増えると、各コマンドに必要なSunPointも多くなるため
- 木が多すぎると、自分自身の木からも影の影響を受けやすくなるので、その影響を低減するため

感想

「約11日間という限られた時間の中でいかに自分の構想をプログラムに落とし込めるかの勝負」という印象を改めて感じた。
今回実装した、1ターンだけ探索する（部分的に3ターン先まで考慮する）ルールベースに近いアルゴリズムでもSilverリーグまでは到達できることがわかった。
さらに上位のリーグに進むには、「上位のAIより学ぶ」で挙げた、SEEDの時点での影がかかりにくい配置にしたり、木の本数を制限したりといった工夫を実装に取り入れる必要性を感じた。
- 「上位のAIより学ぶ」で挙げた戦略を実装に組み込むことで、どれくらいAIが強くなるのか、今後検証したい。
限られた時間でできるだけ自分の構想をプログラムに落とし込めるように、ゲームAI実装でよく使われているアルゴリズムの理解と実装方法の習得をしておきたい。
- 気になったアルゴリズム
  - モンテカルロ木探索
  - DUCTアルゴリズム

あとがき

次回のCodinGame Fall Challenge 2021は、おそらく半年後の、今年の11月にあると思うので、このコンテストについても時間を見つけて参加したいです。

最後までご覧いただきありがとうございました。