🎴

Legends of Code and Magicで5位になったので取り組みをまとめる

に公開
競技プログラミング
CodinGame
tech

はじめに

Legends of Code and Magicは、CodinGameで常設されているカードゲームのプログラミングコンテストです。

このコンテストにおいて、執筆時点で5位のプログラムを作成できました。

このプログラムを作成する上で、カードゲームを統計的に分析することと、競技プログラミングとしてプログラムを最適化することのどちらも不可欠です。
そのため、どちらも好きな私としてはとても楽しいコンテストでした。

その楽しさを少しでも伝えられたら良いなと思っています。

全体の流れ

取り組んだことを、以下の流れで説明します。

  1. ルールを簡潔に説明します。
  2. プログラムの実装と最適化の方法を説明します。
  3. 最適化の方針の根拠となるカードゲームの統計分析の概要を説明します。
  4. 実際のカードゲームへの活用を考えます。

Legends of Code and Magicのルール

まずは、Legends of Code and Magicのルールを大まかに説明します。

マジック:ザ・ギャザリング、ハースストーン、Shadowverse: Worlds Beyond等のゲームを知っている方であれば、それと似ているということを念頭に置いてルールを見ると分かりやすいです。

全体の流れ

ゲームは、ドラフトフェーズとバトルフェーズの2つに分かれています。

ドラフトフェーズでは、すべてのカードの中からランダムに3枚のカードが提示されるので、その中から自分のデッキに加えるカードを1枚選びます。自分と対戦相手で、提示されるカードは同じです。


ドラフトフェーズ

バトルフェーズでは、ドラフトで作成したデッキを使い、対戦相手と戦います。
各プレイヤーには体力があり、はじめは30です。相手の体力を0以下にすることで勝利できます。


バトルフェーズ

バトルフェーズの進め方

先攻・後攻は交互に1ターンずつ行動します。

  • ターンのはじめにデッキからカードをドローします。
  • 手札にあるカードはマナコストを消費して使用します。 i ターン目には、マナコストを最大で \min(12, i) 消費できます。
  • カードには、クリーチャーとアイテムがあります。クリーチャーは、自分の盤面に召喚でき、毎ターン相手や相手のクリーチャーを攻撃できます。アイテムは、プレイヤーやクリーチャーを対象に様々な効果を発動します。

ただし、そのままだと先攻が有利なので、以下のハンデがあります。

  • 先攻のはじめの手札は4枚で、後攻のはじめの手札は5枚です。
  • 後攻は試合で一度だけそのターンで消費できるマナコストの上限を1増やすことができます。

カードの種類

カードには、以下の4種類があります。

クリーチャー 緑アイテム 赤アイテム 青アイテム

以下の画像は、カードの各項目が何を表しているかを示しています。キーワード能力については後述します。
自分や相手の体力を変化させる効果や、ドロー効果は、すべてのカードの種類で実装されています。

クリーチャー

クリーチャーは、自分の盤面に召喚して相手を攻撃します。攻撃力と体力があります。

自分のクリーチャーが相手のクリーチャーを攻撃したとき、クリーチャーはお互いに自身の攻撃力に等しいダメージを相手に与え、相手の体力が減少します。体力が0以下になると破壊されます。

また、いくつかのキーワード能力があり、クリーチャーはこれらを持っていることがあります。全部で6つありますが、ここでは重要なWard、Lethalだけ説明します。

Wardをもつクリーチャーは、受けるダメージを一度だけ無効にします。ハースストーンの「聖なる盾」、Shadowverse: Worlds Beyondの「バリア」をイメージするとよいです。

Lethalをもつクリーチャーは相手のクリーチャーにダメージを与えるとそれを破壊します。マジック:ザ・ギャザリングの「接死」、ハースストーンの「猛毒」、Shadowverse: Worlds Beyondの「必殺」をイメージするとよいです。

すべてのキーワード能力
  • Breakthrough: 相手のクリーチャーを攻撃したとき、余剰ダメージを相手のプレイヤーに与えることができます。(MtG: トランプル)
  • Charge: 召喚したターンに攻撃できます。(MtG: 速攻、HS: 突撃、SV: 疾走)
  • Drain: 自身の攻撃時に、与えたダメージと等しい量だけプレイヤーの体力を回復します。(MtG: 絆魂、HS: 生命奪取、SV: ドレイン)
  • Guard: 相手のクリーチャーは、これをもつクリーチャーを先に攻撃しなければいけません。(HS: 挑発、SV: 守護)
  • Lethal: 相手のクリーチャーにダメージを与えたとき、それを破壊します。(MtG: 接死、HS: 猛毒、SV: 必殺)
  • Ward: 次に受けるダメージを一度だけ無効にします。無効にしたあと、Wardは失われます。(HS: 聖なる盾、SV: バリア)

緑アイテム

緑アイテムは、自分の盤面のクリーチャーを対象に使用します。対象のクリーチャーに、攻撃力・体力・キーワード能力を付与します。

赤アイテム

赤アイテムは、相手の盤面のクリーチャーを対象に使用します。対象のクリーチャーのキーワード能力を除去し、攻撃力・体力を減少させます。

青アイテム

青アイテムは、自分を回復したり、相手にダメージを与えたりします。クリーチャーを対象にすると、そのクリーチャーにダメージを与えます。

また、回復効果をもつカードは自分自身の体力を回復し、ダメージ効果をもつカードは相手の体力を減らします。

プログラミングコンテストとしてのLegends of Code and Magic

ここまでLegends of Code and Magicのルールを説明しましたが、既存のカードゲームと異なるのは、これがプログラミングコンテストであるという点です。

コンテストでは、局面の情報が標準入力として与えられ、100msの実行時間制限で自分の行動の列を標準出力します。

既存のカードゲームでは、人間がプレイングを考え、実行します。ただ、Legends of Code and Magicはプログラミングコンテストなので、人間はプログラムを書くことしかできません。

そのため、人間がカードゲームをプレイするときに考えているようなことを、プログラムとしてどうやって表現するのかというのが問題になります。
そこで、まずはどうやって強いプログラムをつくるのかを説明します。

どうやって強いプログラムをつくるか

このゲームにはドラフトフェーズとバトルフェーズがあるので、それぞれ戦略を説明します。その後、それらを相互に改善する方法を説明します。

図を使って大まかに表すと、以下のように書けます。

ドラフトフェーズの戦略

まず、ドラフトフェーズの戦略を説明します。全体としては、以下のようになります。

  • カードの強さを評価するために、事前に自己対局を行ってデータを集めておきます。自己対局では、先攻・後攻共にランダムにドラフトを行います。バトルフェーズは、そのとき一番強いプログラムを使います。
  • データからドローしたときの勝率を調べておき、それを評価値のベースとします。
  • マナカーブに応じて補正項を加えます。理想のマナカーブを決め打って、それとの分布の距離を最小化するように補正しました。分布の距離はアースムーバーズ距離を使用します。

自己対局について、常にランダムドラフトでカードの強さを調べることは重要です。
前の世代で強いカードが分かったのであれば、それを利用し、強いカードがドラフトされる環境でのカードの強さを評価したくなります。ただ、弱いカードのサンプルサイズが増えなくなり、データを集めるのに必要な試合数が増大してしまいます。

ドローしたときの勝率はカードゲームの統計分析において重要な統計量です。ただ、なぜこれを評価に使うのか、そしてそれが上手く行くのかを簡潔に説明するのは難しいです。
そのため、後で実際のデータを見て説明することにします。

バトルフェーズの戦略

次に、バトルフェーズの戦略を説明します。全体としては、以下のようになります。

  • 局面の評価関数を設計します。
  • 自分の合法手と、それを行ったあとの相手のクリーチャーの行動までを探索し、評価関数を使って評価することで、最適な合法手を全探索します。

局面の評価関数は、自分や相手の体力、盤面のクリーチャーの攻撃力や体力、キーワード能力などを評価します。

また、以下のような工夫を入れています。

  • 体力を区分線形関数で評価します。プレイヤーの体力が多いときは盤面を重視し、少なくなると体力を考慮するようになります。
  • キーワード能力は、能力に応じて攻撃力や体力の値と組み合わせて評価します。


体力の評価のイメージ

パラメーターの最適化には、Optunaを使用しました。

プレイングの探索について、自分の合法手と、それを行ったあとの相手のクリーチャーの行動までを探索しています。実際のカードゲームでは、相手の手札をある程度予測することが多いので、考慮できていない要素があり、最適ではないように思えます。
ただ、実行時間制限100msの中で、不確定な情報に対して適切に評価を行うのは難しいです。自分の合法手と、それを行ったあとの相手のクリーチャーの行動までは自分から分かる確定情報なので、ここまでを考慮するようにしました。

評価関数から解釈するカードゲームのテンポ

ここまで、カードゲームのプレイングを探索する方法を示しました。そこで用いる評価関数は、勝率を最大化するように最適化されます。
ここには、人間がカードゲームをプレイするときに考えている理論は明示的には含まれていません。しかし、適切に設計し、最適化した評価関数はカードゲームのプレイングの理論の内の一つであるテンポという概念を持っていると解釈できます。

最適化された評価関数のパラメーターで、仮想的に攻撃力0・体力0のクリーチャーを自分や相手の盤面に召喚することを考えます。
すると、一般にどちらも0でない評価になり、評価の大きさは自分のクリーチャーよりも、相手のクリーチャーのほうが大きくなります。

これは、自分の盤面にクリーチャーが存在するという情報よりも、相手の盤面にクリーチャーが存在するという情報の方が不利であるということを意味します。原因としては、例えば自分のターンが終わったら相手のクリーチャーが行動できることは確定しているものの、自分のクリーチャーは行動できるとは限らないことが挙げられます。

このように、自分の選択肢を増やしたり、相手の選択肢を狭めたりして、試合の主導権を握ることをテンポを取ると表現します。テンポという概念についての詳しい説明は、マジック:ザ・ギャザリングであれば「TEMPO」テンポの基礎【LEVEL ONE翻訳】Concepts of Gameplay Part 1 – 02、ハースストーンであれば、テンポとは何か？ - Ombre's blog、Shadowverse: Worlds Beyondであれば、結局、テンポって「何」？｜Spiciesが分かりやすいと思います。

したがって、適切に設計し、最適化した評価関数はテンポという概念を持っていると考えることができます。

相互に改善する

ここまで、ドラフトフェーズとバトルフェーズの戦略を説明しました。

ただ、ドラフトフェーズではデータを集める必要がありますし、バトルフェーズでは評価関数のパラメーターを最適化する必要があります。
ドラフトフェーズの戦略が変われば、バトルフェーズの評価関数のパラメーターは最適でなくなる可能性があります。逆もまた然りです。

したがって、ドラフトフェーズのデータを集めたら、バトルフェーズの評価関数のパラメーターを最適化し、再びドラフトフェーズのデータを集めて、...というように、2つのフェーズの戦略を交互に改善します。

カードゲームの統計

ドローしたときの勝率を評価に使う理由や、なぜそれが上手く行くのかを説明します。

カードの強さとは何か

ドラフトでは、カードを評価して、一番強いカードを選びます。そこで、カードの強さとは何かという問題を考えます。

これへの直接的な答えは、このあと最適なプレイングをし続けたときに、勝率が最大になるカードです。ただし、それを直接計算することは不可能です。
そのため、事前にカードの情報を準備しておいて、それを活用することで、カードの強さを比較します。

その前提で、単純に考えると、そのカードがデッキに入っている試合での勝率が高ければ強いといえます。
ただ、カードはドローしないと使えず、試合に寄与しません。勝率を使ってカードの強さを評価しようとすると、そのカードが寄与しなかった試合も評価に含まれます。
また、カードをドローしてから、コストや機会の問題で使えなかったということも評価に含まれるのも重要です。

そういう意味では、カードの強さを評価する上では、ドローしたあとの試合だけを考慮する方が優れていると考えられます。

このドローしたときの勝率は以降、一般的な呼称に合わせてDrawn Win Rateと呼ぶことにします。

ランダムドラフト環境におけるDrawn Win Rate

具体的なデータを見て、Drawn Win Rateの有効性を確認します。

以下の図は、先攻・後攻がお互いにランダムにドラフトした試合でのDrawn Win Rateとコストの散布図です。

これを見ると、明らかにDrawn Win Rateが高いカードがいくつか存在するのが分かります。具体的に確認しましょう。

Giant Squid Elite Bilespitter Decimate Grow Stingers

Ward、Lethalを持ったクリーチャーや緑アイテムのDrawn Win Rateが高く、それを破壊できるDecimateもDrawn Win Rateが高くなっています。
まず、Wardはアイテムで除去されない限り、必ず2回ダメージを受けることができます。そのため、Wardをもったクリーチャー1枚で相手のカードを2枚以上使わせることが期待できます。
また、Lethalをもったクリーチャーは強力なクリーチャーを簡単に破壊できます。そのため、相手のプレイングを歪ませることが期待できます。

Drawn Win Rateとコストの散布図で、Ward、Lethalのカードを強調したのが以下の図です。明らかに、Drawn Win Rateが高いカードが多いことが確認できます。

また、Drawn Win Rateが低いカードも確認します。

Gargoyle Tamed Bilespitter Minor Life Steal Potion Healing Potion

これらのクリーチャーは、コストの割に攻撃力が低いです。また、青アイテムは、プレイヤーの体力を少し回復・減少させるカードであり、試合への寄与が小さいことが想像できます。

Drawn Win Rateがカードの強さを表していることを具体的に確認できたと思います。

Drawn Win Rateがカードの強さであるとすると、このゲームはカードプールの中でカードの強さにかなりばらつきがあります。したがって、Drawn Win Rateだけで一番強いカードを決めることができる場面はとても多そうに見えます。

もう少し具体的な問題として考えましょう。

上のDrawn Win Rateを固定して、各カードをドローした回数を一斉に動かすとします。
その設定で、3枚のカードの中から有意にDrawn Win Rateが高いと結論づけることができるカードがあるかを母比率の差の検定によって調べます。その結果が以下の画像です。

すべてのカードを 10^5 回程度ドローしていれば、 80\% 程度の確率で最も強いカードを決定できます。 10^5 回であれば、シミュレーターを十分高速に実装すれば、数時間で集められます。

Drawn Win Rateの数理

最後に、実際のカードゲームへの応用を意識して、Drawn Win Rateの性質をいくつか説明します。

例えば、Drawn Win Rateが勝率より高いのであれば、それを引いたら勝率が上がっていると考えられそうです。この考え方の妥当性を、Drawn Win Rateを勝率で表すように変形することで考えます。

以降、Drawn Win Rateを P(\text{Win} \vert \text{Drawn}) と表すことにして、このような確率論の記法を積極的に利用します。以下のように2x2で分割した図で考えると、イメージしやすいと思います。

\begin{aligned} P(\text{Win} \vert \text{Drawn}) &= \frac{P(\text{Win} \cap \text{Drawn})}{P(\text{Drawn})} \\ &= \frac{P(\text{Win} \cap \text{Drawn})}{P(\text{Win} \cap \text{Drawn}) + P(\text{Loss} \cap \text{Drawn})} \\ &= \frac{P(\text{Drawn} \vert \text{Win}) P(\text{Win})}{P(\text{Drawn} \vert \text{Win}) P(\text{Win}) + P(\text{Drawn} \vert \text{Loss}) P(\text{Loss})} \\ &= \frac{P(\text{Drawn} \vert \text{Win}) P(\text{Win})}{P(\text{Drawn} \vert \text{Win}) P(\text{Win}) + P(\text{Drawn} \vert \text{Loss}) \left\lbrace1 - P(\text{Win}) \right\rbrace} \end{aligned}

この表式から、以下のことが分かります。

  • P(\text{Win} \vert \text{Drawn}), P(\text{Win}) の大小関係は、 P(\text{Drawn} \vert \text{Win}), P(\text{Drawn} \vert \text{Loss}) の大小関係と一致します。

言葉で説明すると、Drawn Win Rateと勝率の大小関係は、勝った試合の平均ドロー枚数と負けた試合の平均ドロー枚数の大小関係に一致すると言えます。

この関係は、アグロとコントロールの間の比較でよく見られます。

  • アグロデッキは、環境の中で勝利時平均ターンが短いです。したがって、勝利時平均ドロー枚数が敗北時平均ドロー枚数より少なくなりやすいと言えます。よって、Drawn Win Rateは勝率より低くなりやすいです。
  • コントロールデッキは、環境の中で勝利時平均ターンが長いです。したがって、勝利時平均ドロー枚数が敗北時平均ドロー枚数より多くなりやすいと言えます。よって、Drawn Win Rateは勝率より高くなりやすいです。

要するに、性質が異なるデッキ間で、Drawn Win Rateだけを見てカードの強さの比較をすることは難しいということが言えます。

また、ドローしたことによる勝率の変化量を表すImprovement In Hand( = P(\text{Win} \vert \text{Drawn}) - P(\text{Win} \vert \neg\text{Drawn}) )という統計量について、導出は省きますが以下のように変形できます。

\begin{aligned} \text{IIH} &= P(\text{Win} \vert \text{Drawn}) - P(\text{Win} \vert \neg\text{Drawn}) \\ &= \frac{P(\text{Win} \vert \text{Drawn})-P(\text{Win}) }{1 - P(\text{Drawn})} \end{aligned}

分母は、ドローされなかった試合の割合であり、常に正です。
また、分子について、 P(\text{Win} \vert \text{Drawn}), P(\text{Win}) の大小関係は、 P(\text{Drawn} \vert \text{Win}), P(\text{Drawn} \vert \text{Loss}) の大小関係と一致します。したがって、Improvement In Handの正負は P(\text{Drawn} \vert \text{Win}), P(\text{Drawn} \vert \text{Loss}) の大小関係と一致します。

実際のカードゲームとの違い

はじめに挙げたマジック:ザ・ギャザリング、ハースストーン、Shadowverse: Worlds Beyondなどのゲームで統計分析を行うときの難しさを具体的に挙げます。

カードを引く頻度

Legends of Code and Magicは、マリガンがなく、サーチカードもありません。そのため、すべてのカードはほとんど同じ頻度でドローされます。

これは、Improvement In Handの表現 \frac{P(\text{Win} \vert \text{Drawn})-P(\text{Win}) }{1 - P(\text{Drawn})} で、分母がほとんど変わらないことを意味します。

一方、実際のカードゲームでは、カードによってドローされる頻度がばらつきます。また、カードごとにドローされるターンの分布が変わります。
そのため、特に役割の異なるカードの強さを統計データだけで比較するのはとても難しいです。

サンプルサイズの不足

実際のカードゲームでは、カードプールが数週間で入れ替わります。また、いろいろな情報によって、メタが変化することもあります。これらが原因で、統計データのサンプルサイズが不足していることはよくあります。

特殊な挙動

実際のカードゲームでは、デッキから直接召喚されるカードや、手札をデッキに戻すカードなどがあります。これまでの議論で前提としている、カードははじめデッキにあり、ドローされ、手札から使用するという流れに従わないものは、Drawn Win Rate等で強さを測ることはできません。

最後に

以下のBookに、取り組んだことをより詳しく書いています。

ミラーマッチの分析では、実際にドラフトで作成されたデッキを使ってデータを収集し、カードゲームの統計分析を丁寧に説明しています。特に、先攻と後攻の有利不利の分析はこの記事では説明していません。

また、Botの開発の上手く行かなかった方針では、上手く行かなかった方針と、その原因を考察しています。

あとがき

私は、ハースストーンが好きだったので、HSReplayというハースストーンのデータを提供するサービスを使って、趣味でデータを分析していたことがあります。

Drawn Win Rateがカードの強さと関連していることは、J AlexanderのUNDERSTANDING AND INTERPRETING HSREPLAY STATISTICSにもあり、ハースストーンではよく知られた話です。ちなみに、この文章はハースストーンの統計を分析する上で注意する点を丁寧に解説していて、他のカードゲームの分析でも役立つ内容になっています。

これが、別のカードゲームの、そしてプログラミングコンテストでも同様に成り立つことは、きちんと考えれば自然なことではあるのですが、面白いです。
また、カードゲームで自分が考えていることをプログラムに落とし込んでいくという作業も、今までにないことで楽しい取り組みでした。

リンク

Discussion