Zenn
🔖

CodinGame Fall Challenge 2020総括

2020/12/05に公開
AI
競技プログラミング
CodinGame
tech

はじめに

本記事執筆に至った経緯について

今までにもゲームAIを実装するコンテストは様々開催されてきました。私も数年前にこのようなコンテストに参加しようとした過去があったのですが、十分にルールを把握できなかったり、最後まで実装しきれず結局サブミットせず終わっていたという過去がありました。
　しかし、今回ふと「CodinGame」で久々にWeb検索をし、興味惹かれる題材のゲームAI実装コンテストが開かれていることを知り、参加を決めました。それが「CodinGame Fall Challenge 2020」でした。
　今回楽しくコンテストに参加できたので、自分の思考の整理を兼ね、今後CodinGameなどのコンテストに参加する方の一助になれば良いなと考え、本記事を執筆することにしました。

アジェンダ

  • CodinGameとは？
  • Fall Challenge 2020のルール
  • 私が実装したAIの紹介
  • コンテスト結果
  • より良いAIを作るために（考察）
  • あとがき

CodinGameとは？

  • 様々なゲームのお題について、ブラウザ上でAIを組んで、そのAIでゲームを攻略することができるウェブサービス（https://www.codingame.com/ ）。

  • 難易度も様々で、簡単なAIの実装から徐々にステップアップすることができる。

  • 使用可能言語は以下の27言語（2020.11.25現在）あり、自分の好きな言語を使って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

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

CodinGame Fall Challenge 2020のルール

ゲーム概要

手持ちの素材を使ってポーションを醸造することで、スコアを稼ぎ、ゲーム終了時にスコアが高いプレイヤーが勝利となるターン制の対戦型ゲーム。初期状態ではポーション醸造に必要となる素材を持っていないため、スペルを使って、手持ちの素材の組を別の素材の組に変換することで、ポーション醸造に必要な素材を集める。
　また、初期スペルのみではこの素材集めの効率が悪いため、スペルを習得することでより効率の良い素材集めをできるようにすることがこのゲームの大事なポイントとなる。

各ターンですることについて（簡単に）

各ターンですることを簡単にまとめると以下のようになる。

  1. ターン開始時に各プレイヤーの情報、製作できるポーションのレシピなどの入力を受け取る。
  2. それを基にプレイヤーがこのターンで取るべき行動が何であるかを決定する。
  3. プレイヤーが取るべき行動を決められたフォーマットに従って標準出力する。

以下、入力情報と出力すべきコマンドについて詳しく説明していく。

各ターン冒頭で得られる入力情報

  • 各プレイヤーの累計獲得スコア
  • 各プレイヤーのインベントリの中身
  • 各プレイヤーが習得しているスペルのリスト（初期スペル４種を含む）
  • 習得可能スペル（最大６種類）
  • ポーションのレシピと、製作した場合に獲得できるスコア


↑初期状態（1ターン目のアクションを取る前）に与えられる情報

素材は、tier-0、tier-1、tier-2、tier-3の4種類がある。
互いにtier-0を3個持っており、初期スペルを４つ習得した状態で試合が開始される。

各試合の初期状態で提示されるポーションのレシピ（5種類）と習得可能スペル（6種類）は、以下に示すスペルリスト及びポーションレシピリストからランダムで選ばれる。

スペルリスト（初期スペル4種＋習得スペル42種）

ポーションレシピリスト（全36種）


↑各レシピの数字は、醸造した際に得られるスコアを示している。

上記レシピによれば、tier-0やtier-1を組み合わせて醸造するポーションに比べて、tier-2、tier-3を要するポーションの方が得られるスコアが大きいことがわかる。
　そのため、tier-2、tier-3を効率良く獲得できるスペルを習得し、使用することが基本戦略の一つになると考えられる。

このレシピのスコアに加えて、一番左に並ぶレシピには４回まで＋3点のボーナスが付与される。
左から２番目のレシピにも４回まで＋1点のボーナスが付与される。
　ポーションが醸造された後に新たに追加されるポーションは、一番右に追加される。残りの４つのポーションは左にスライドする。そのため、一番左のポーションが醸造された場合は、左から２番目のポーションが一番左に移動し、＋３点のボーナスに変化する。
　＋３点のボーナスが４回付与された後は、左から２番目のポーションに付与される＋１点ボーナスはなくなり、一番左のポーションに代わりに＋１点ボーナスが付与される。

出力コマンド

  • BREW ${actionId}

  • レシピの素材を使用して、ポーションを生成する。

  • CAST ${actionId} [times]

  • インベントリの"とある"素材の組を別の素材の組に変換するスペルを使用する。スペルの使用で素材の数の合計がインベントリの枠（10枠）を超えてしまう場合、あるいはスペルが「消耗状態」のときは、そのスペルを使用することができない。

  • 入力で与えられる「repeatable」フラグがtrueのスペルは、1ターンで何度もそのスペルを使用することができる。複数回使用する場合は、アクションIDの後に続けて使用回数（times）を指定する。一度しか使用しない場合は、使用回数を指定する必要はない。

  • 一度スキルを使用すると、そのスペルは「消耗状態」となり、RESTコマンドを使用し、再使用可能にするまでは使用できなくなる。

  • LEARN ${actionId}

  • 決められたコストを支払って中央のスペル本からスペルを１つ習得する。スペルを習得すると、次のターンからそのスペルが使用可能になる。また、各スペルの横にtier-0が置かれていた場合、そのtier-0をすべて獲得する。インベントリ枠（10枠）を超える分のtier-0は破棄される。

  • 習得したスペルは中央のスペル本から消滅し、スペルの在庫があれば、在庫からランダムに１つ補充される。42種類すべてのスペルが習得された場合は、中央のスペル本からスペルがなくなる。

  • 習得時に支払うコストは、スペル本の上に書かれたスペルほど高く、一番下は無コストで習得できる。下から2番目のスペルを獲得するには、tier-0を１つ支払い、下から3番目はtier-0を2つ支払う、以降必要数が1つずつ増えていく。

  • 支払ったtier-0は、下から順に１つずつスペルの隣に置かれる。

  • REST

すべてのスペルの「消耗状態」を回復し、再使用可能にする。

  • WAIT

何もしない。

勝敗判定

試合は、

  • 片方のプレイヤーが合計6個のポーションを醸造する
  • 100ターンに到達する
    のいずれかを満たした場合に終了し、勝敗判定を行う。
    出力が制限時間内（最初のターンの出力についてははじめの入力を受け取ってから1000ms。以降は50msが制限時間となる）に行われなかった場合や、出力が有効でなかった場合にはその時点で、それを発生させたプレイヤーの負けとなる。

以下の計算で求められる最終スコアが高い方がその試合の勝者となる。

（最終スコア）＝（ポーションで得たスコア合計）＋（ 素材ボーナス ）

素材ボーナスとは、試合終了時にインベントリにあるtier-1以上の素材1個につき、1点が加算されるというものである。

例えば、以下のような状態で試合が終了した場合、左のプレイヤーは素材ボーナスを1点獲得し、最終スコアは69点＋素材ボーナス1点の計70点となる。右のプレイヤーは素材ボーナスが3点で最終スコアは55点＋素材ボーナス1点の計58点となる。

私が実装したAIの紹介

基本戦略としては、8ターンまではほぼLEARNでスペルを習得し、以降はできる限り早くポーションを醸造するというものである。

  1. 現在ターンに実行できる全てのアクションについて、各アクション後のインベントリの中身の情報、使用可能スペルリストの状態をStateNodeとして再現し、その情報を用いてアクションの評価値を計算する（深さ１）。

  2. ①で作成したStateNodeから枝を伸ばし、さらにその次のターンで実行できるすべてのアクションについて①と同様の処理を行う。

  3. 深さ10まで探索を行う。途中でスコアが基準値以上を超えた場合、探索を打ち切って、枝を辿って深さ１まで戻り、深さ１でのアクションを出力する。

各コマンドのスコアリング

  • BREW
    　 score = 300 * portion.price / depth;
    　　　　　　　　　　　　　　　　　　　　　　　　　portion.priceは、ポーションの価値
    　　　　　　　　　　　　　　　　　　　　　　　depthは、ポーション醸造に必要なターン数

  • CAST
    　各ポーションを作るために必要な素材と比べて、Tierの区別なく、不足数を計算する。不足数をNとしたとき、i番目のポーションのスコアは、
    　score(i) = (8 - N) * portion.price + inv.tier2 + inv.tier3
    inv.tier2は、アクション後のインベントリにあるTier2素材の数
    inv.tier3は、アクション後のインベントリにあるTier3素材の数
    score = Max(score(i))

  • LEARN
    習得スペルについてもCASTと同じ評価を行った。
    ただし、8ターンまでについてはこのスコアに10をかけて、ほぼほぼLEARNを行うようにした。

  • REST
    　すべてのスペルについて、CASTと同様の評価を行い、その評価値をSとした。最終評価値scoreは、Sに1未満の値をかけたものとした。
    　score = 0.8 * S
    ただし、前のターンでRESTしている場合は、score = 0とした。

また、試合終了するまでに新たにポーションが醸造できない（相手の方が早く製作できるか100ターンに到達するまでに醸造できない）と判断した場合は、上記のスコアリングは行わず、tier-1以上の素材ができるだけ多くなるようなコマンドを選択するようにした（素材ボーナスをできるだけ増やすため）。

コンテスト結果


コンテスト終了時のランキング結果
　今回のコンテストの参加を決めたとき（コンテスト開始から3日目）に想定していたよりは良い順位を取ることができた。
　しかし、AIとしてはスペルの重ね掛けができない状態のものでコンテスト終了を迎えてしまったため残念さは残ってしまった。Goldに昇格するにはスペルの重ね掛けはできないと厳しいと体感として思った。

より良いAIにするために（考察）

  • インベントリの空き状況をスコアリングに組み込むべきだった

    • 各ポーション製作に必要な素材が“足りているか”に基づいて各コマンドのスコアリングを行っていたため、インベントリの空き状況を加味した評価ができていなかった（インベントリに適度な空きがないとスペルが使用できないため、良い空き状況を作れるかどうかもカギとなる）

  • スペルの価値を適切に評価し、その評価に基づいたLEARNをすることが必要

  • ポーションの価値を適切に評価し、価値の低いポーションはあえて製作しないといったアクションを取ることが必要

    • 安いポーションばかりを製作していると、6回の製作回数をうまく生かせず、最終スコアで負けることがある
    • とはいえ、作れるポーションを素早く作って、先に合計6個のポーションを製作し、試合を終わらせる速攻型AIも強いので、バランスが大切

コンテストに参加した感想

こうしてゲームAIのコンテストに参加するのは初でしたが、実際に自分の書いたコードで戦っているリプレイを見るのも面白く、改良するとどんどん強くなっていく感覚が楽しかったです。「自分もAI組むことできるんだ」ということを体感して自信にできたのも良かったです。
また一方で、まだまだ自分に足りていないAIに関する知識などもあることがわかり、次回のコンテストまでに今回は実装できなかったビームサーチの実装に関してやその他の探索手法についても勉強しておきたいです。

ちなみに次回コンテストは2021年5月6日からだそうです。
楽しみですね。

次回コンテスト「CodinGame Spring Challenge 2021」開催告知（公式HPより）

あとがき

今回、このような記事を書かせていただき、自分の理解をさらに深めることができ、自分のAIの間違い（スペルを重ね掛けするアクションを取らないバグの原因）に気づくことができたので良かったです。このコンテストのAIについてはもう少し改良してみようと思っています。
　また、普段記事を書いてくださる方の有難みを感じました。私もこれからどれくらい記事を書けるのかわかりませんが、自分の成長のためにもこれからも積極的に書いていければと思います。
最後にzennで記事を書くことの後押しをしてくださったzennの開発者のcatnoseさんに感謝を申し上げます。

長くなりましたが、ここまで読んでいただき、ありがとうございました！

Discussion