Legends of Code & Magic(LOCM)コンテストの紹介とカードゲームの統計分析の基本
概要
Legends of Code & Magicは、2人対戦のカードゲームを行うボットを作成し、その強さを競うプログラミングコンテストです。コンテストはCodinGameで常設されています。
大きく分けて、以下の2つのトピックについて書きます。
- ルールの簡単な紹介
- 統計データの分析と解釈
ルールの簡単な紹介
上のgifは実際にボット同士が対戦しているところを録画したものです。[1]
知っている方であれば、マジック:ザ・ギャザリング、ハースストーン、Shadowverse等に似たゲームであると捉えておくとよいです。これらのゲームとゲームシステムはかなり類似しています。
ゲームは大きく2つのフェーズに分かれています。ドラフトフェーズと対戦フェーズです。
- ドラフトフェーズ
\dots - 対戦フェーズ
\dots
まず、対戦フェーズのシステムについて説明し、その後カードの種類や効果にどのようなものがあるのかについて説明します。
基本的なシステム
- HPはお互いに30あります。
- 手札は先手が4枚、後手が5枚です。マリガンはありません。手札は最大で8枚です。毎ターンデッキからカードを1枚引きます。
- カードの中には、次のターンにカードをドローする枚数を増やすことができるものがあります。
- マナ(カードを使用する際に支払うコスト)は先手が1、後手が2で、自分のターンが来るたびにマナの個数は回復し、上限が1増えます。上限は最大で12です。
- 後手は、マナを使い切ると、その後上限が1減ります。(そのターンに限り、一時的にマナの上限を1増やせる権利があると考えるとよいです。)
- ルーンをお互いに5個もっています。これが失われた次のターン、カードを1枚多くドローすることができます。
- はじめてHPが25、20、15、10、5以下になったとき、ルーンが一つ失われます。
- クリーチャーというカードがあり、それを自分の盤面に召喚できます。最大で6体まで同時に召喚できます。(カードの詳細については後述します。)
- 一ターンに一度、対戦相手、または対戦相手の盤面のクリーチャーを攻撃できます。クリーチャーを攻撃するとき、お互いに相手に自身の攻撃力分のダメージを与え、体力が減少します。
- 例えば、攻撃力3・体力4のクリーチャーが攻撃力2・体力3のクリーチャーを攻撃すると、自分の体力は2になり、相手は破壊されます。
- 召喚されたターンには攻撃できません。
- 一ターンに一度、対戦相手、または対戦相手の盤面のクリーチャーを攻撃できます。クリーチャーを攻撃するとき、お互いに相手に自身の攻撃力分のダメージを与え、体力が減少します。
先手、後手が互いにターンを進め、対戦相手のHPを0以下にすることを目的に行動します。
カードの種類
カードは大きく分けて4種類あります。クリーチャー、緑アイテム、赤アイテム、青アイテムです。
- クリーチャー
\dots
Card Id: 4 Plated Toad 2コスト1/5
- 緑アイテム
\dots
Card Id: 120 Venomfruit 2コスト1/0 Give a friendly creature +1/+0 and Lethal.
- 赤アイテム
\dots
Card Id: 145 Cursed Sword 3コスト-2/-2 Give an enemy creature -2/-2.
- 青アイテム
\dots
Card Id: 157 Life Sap Drop 3コスト0/-1 Deal 1 damage, gain 1 health, and draw a card.
クリーチャーのキーワード能力
クリーチャーの中には、固有のキーワードで表現される能力を持っているものがあります。[2]
- Breakthrough
\dots - Charge
\dots - Drain
\dots - Guard
\dots - Lethal
\dots - Ward
\dots
アイテムの中には、それをクリーチャーに使用した場合にキーワード能力を付与する、もしくは破棄させるものがあります。
LOCM特有のこと
LOCMは、プログラミングコンテストであり、標準入出力を介してプレイヤーの操作が行われることを前提としています。そのため、通常のカードゲームとは異なる部分があります。
- ターン開始時に自身や対戦相手のHP、マナ、ルーン等の情報や手札、盤面の情報が入力されます。
- 決められた実行時間制限以内に、自身がそのターンに行う行動を一行で出力します。
一般的なカードゲームでは、ターン中にデッキからカードをドローことはよくあります。LOCMでは、ターン毎に一度しか入力が行えない都合上、そのような効果はありません。
また、自分のターン中に相手の意思決定が必要になるような効果は実装されていません。
公式のルール、ジャッジ等は以下のURLにあります。より詳細なルールを確認できます。
統計分析
CodinGameのコンテストは、自分のプログラム同士であればローカルで対戦を行うことができます。
また、オプションを設定すれば、ドラフトの選択肢を操作し、同じカードを提示させることができます。
これを利用して、構築したデッキを使用して繰り返し対戦を行い、そのログからデータを収集することで、統計分析を行います。[3]
何を見るのか、何が知りたいのか
今回は、以下のデータを取得しました。
- ゲームのデータ
- 先手・後手のいずれが勝利・敗北したか
- 何ターン目に勝敗が決定したか
- カードのデータ
- あるカードが何ターン目にドローされたか
- あるカードが何ターン目に使用されたか
これらのデータを組み合わせて、例えば以下のような統計を調べることもできます。
- あるカードがドローされた試合における勝率(以降、DrawnWRと表記します)
- あるカードが使用された試合における勝率(以降、PlayedWRと表記します)
- あるカードがドローされた試合について、そのドローされたターンごとの勝率
- あるカードが使用された試合について、その使用ターンごとの勝率
また、これらを調べることによって、何が知りたいのかについて考えると、例えば以下のようなものが挙げられます。
- プレイヤー目線
- それぞれのカードの強さを調べたい。弱いカードがあるなら入れ替えて勝率を上げたい。
- デッキの強み・弱みを分析し、プレイングに活用したい。
- 運営目線
- ゲームのバランスを調整するために、どこを調整すればよいのか分析したい。
同じデッキで対戦させる
以下のデッキリストをどちらのプレイヤーにも使用させ、その統計を分析します。
- ドラフトの選択肢を操作し、ドラフトのアルゴリズムを操作することで、対戦する2つのボットのデッキを固定します。
- 対戦フェーズにおいて、2つのボットの思考ルーチンは全く同じです。
30枚あって長大であるため、見なくてもよいです。カードの詳細を確認する必要がある場合、適宜カードの画像を添付しています。
デッキリスト詳細
| Id | Name | Type | Cost | Damage | Health | Abilities | PlayerHP | EnemyHP | CardDraw | Text Description |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | Beavrat | creature | 1 | 2 | 2 | ------ | 0 | 0 | 0 | |
| 7 | Rootkin Sapling | creature | 2 | 2 | 2 | -----W | 0 | 0 | 0 | |
| 12 | Woodshroom | creature | 3 | 2 | 5 | ------ | 0 | 0 | 0 | |
| 15 | Pouncing Flailmouth | creature | 4 | 4 | 5 | ------ | 0 | 0 | 0 | |
| 19 | Foulbeast | creature | 5 | 5 | 6 | ------ | 0 | 0 | 0 | |
| 21 | Crested Scuttler | creature | 5 | 6 | 5 | ------ | 0 | 0 | 0 | |
| 23 | Titan Cave Hog | creature | 7 | 8 | 8 | ------ | 0 | 0 | 0 | |
| 29 | Steelplume Nestling | creature | 2 | 2 | 1 | ------ | 0 | 0 | 1 | Summon: Draw a card. |
| 32 | Sandsplat | creature | 3 | 3 | 2 | ------ | 0 | 0 | 1 | Summon: Draw a card. |
| 33 | Chameleskulk | creature | 4 | 4 | 3 | ------ | 0 | 0 | 1 | Summon: Draw a card. |
| 37 | Eldritch Multiclops | creature | 6 | 5 | 7 | ------ | 0 | 0 | 1 | Summon: Draw a card. |
| 45 | Night Howler | creature | 6 | 6 | 5 | B-D--- | -3 | 0 | 0 | Summon: You lose 3 health. |
| 48 | Venom Hedgehog | creature | 1 | 1 | 1 | ----L- | 0 | 0 | 0 | |
| 53 | Possessed Abomination | creature | 4 | 1 | 1 | -C--L- | 0 | 0 | 0 | |
| 56 | Giant Louse | creature | 4 | 2 | 7 | ------ | 0 | 0 | 0 | |
| 65 | Steelplume Defender | creature | 2 | 2 | 2 | -----W | 0 | 0 | 0 | |
| 66 | Staring Wickerbeast | creature | 5 | 5 | 1 | -----W | 0 | 0 | 0 | |
| 68 | Giant Squid | creature | 6 | 7 | 5 | -----W | 0 | 0 | 0 | |
| 82 | Slithering Nightmare | creature | 7 | 5 | 5 | B-D--W | 0 | 0 | 0 | |
| 88 | Abyss Nightmare | creature | 5 | 4 | 4 | -C---- | 0 | 0 | 0 | |
| 98 | Lilly Hopper | creature | 3 | 2 | 4 | ---G-- | 0 | 0 | 0 | |
| 103 | Mutating Rootkin | creature | 4 | 3 | 6 | ---G-- | 0 | 0 | 0 | |
| 112 | Rootkin Leader | creature | 6 | 4 | 7 | ---G-- | 0 | 0 | 0 | |
| 118 | Royal Helm | itemGreen | 0 | 0 | 3 | ------ | 0 | 0 | 0 | Give a friendly creature +0/+3. |
| 120 | Venomfruit | itemGreen | 2 | 1 | 0 | ----L- | 0 | 0 | 0 | Give a friendly creature +1/+0 and Lethal. |
| 128 | Enchanted Cloth | itemGreen | 4 | 4 | 3 | ------ | 0 | 0 | 0 | Give a friendly creature +4/+3. |
| 139 | Grow Stingers | itemGreen | 4 | 0 | 0 | ----LW | 0 | 0 | 0 | Give a friendly creature Lethal and Ward. |
| 144 | Rune Axe | itemRed | 1 | 0 | -2 | ------ | 0 | 0 | 0 | Deal 2 damage to an enemy creature. |
| 152 | Mighty Throwing Axe | itemRed | 7 | 0 | -7 | ------ | 0 | 0 | 1 | Deal 7 damage to an enemy creature.\nDraw a card. |
| 158 | Tome of Thunder | itemBlue | 3 | 0 | -4 | ------ | 0 | 0 | 0 | Deal 4 damage. |
- くせのないミッドレンジデッキになるようにデッキを構築しています。マナカーブは以下の通りです。(マナカーブ: デッキのカードのコストの分布のこと。)
ゲーム全体の統計
ここでは、ゲーム全体の統計を確認します。主に、先手・後手の格差を確認します。
- 4019試合行い、先手が2215勝1804敗でした。先手の勝率は55.11%です。(後手の勝率は44.89%です。)
- 先手の平均勝利ターン数は12.50ターンで、後手の平均勝利ターン数は13.53ターンでした。全体の平均勝利ターン数は12.96ターンです。
以下は、ターンごとの先手・後手の勝利数を表すグラフです。
これらから、以下のことが分かります。
- 5、6、7ターン目で終わる試合では後手が勝ち越しています。
- 8 ~ 14ターン目で終わる試合では、先手が勝ち越しています。
- それより試合が長期的になると、後手が勝ち越しています。
- 特に、13ターン目以降の勝率は先手が47.42%、後手が52.58%です。
デッキリストが完全に同じであるため、先手・後手の有利不利はゲームシステムに起因すると考えられます。
- 先手を有利にしている要素
- (当たり前ですが)先に行動できます。
- 8 ~ 14ターン目で先手が勝ち越しているのは、この要素が大きそうです。
- (当たり前ですが)先に行動できます。
- 後手を有利にしている要素
- 一回だけ1マナ多く使用できます。
- 5、6、7ターン目で後手が勝ち越しているのは、この要素が大きそうです。
- はじめカードを1枚多く持っています。
- 13ターン目以降の勝率が後手のほうが高いのは、この要素が大きそうです。
- 一回だけ1マナ多く使用できます。
カードの統計
ここでは、カードの統計を確認します。
まずは、カードごとのPlayedWR、DrawnWRを見てみます。左から、カードのID、コスト、PlayedWR、先手のPlayedWR、後手のPlayedWR、DrawnWR、先手のDrawnWR、後手のDrawnWRです。
| CardId | Cost | PlayedWR | FirstPlayedWR | SecondPlayedWR | DrawnWR | FirstDrawnWR | SecondDrawnWR |
|---|---|---|---|---|---|---|---|
| 3 | 1 | 49.05% | 51.76% | 46.30% | 49.85% | 52.52% | 47.15% |
| 7 | 2 | 51.83% | 54.57% | 49.10% | 52.17% | 54.97% | 49.40% |
| 12 | 3 | 49.70% | 51.36% | 48.05% | 49.40% | 51.99% | 46.87% |
| 15 | 4 | 48.29% | 49.71% | 46.86% | 47.81% | 50.35% | 45.33% |
| 19 | 5 | 48.38% | 49.31% | 47.43% | 47.89% | 50.29% | 45.53% |
| 21 | 5 | 49.40% | 49.03% | 49.79% | 47.75% | 49.79% | 45.78% |
| 23 | 7 | 48.65% | 49.34% | 47.94% | 47.46% | 50.29% | 44.70% |
| 29 | 2 | 50.59% | 52.68% | 48.48% | 50.20% | 53.63% | 46.84% |
| 32 | 3 | 51.11% | 53.16% | 49.01% | 49.37% | 52.85% | 46.02% |
| 33 | 4 | 51.82% | 51.55% | 52.10% | 48.40% | 51.20% | 45.78% |
| 37 | 6 | 49.58% | 49.36% | 49.81% | 47.24% | 49.43% | 45.12% |
| 45 | 6 | 50.77% | 50.42% | 51.16% | 45.72% | 48.61% | 42.93% |
| 48 | 1 | 51.74% | 53.23% | 50.24% | 52.11% | 54.01% | 50.24% |
| 53 | 4 | 48.17% | 50.70% | 45.72% | 49.77% | 52.91% | 46.67% |
| 56 | 4 | 48.25% | 50.74% | 45.74% | 47.63% | 50.84% | 44.54% |
| 65 | 2 | 51.58% | 53.67% | 49.47% | 52.10% | 54.34% | 49.84% |
| 66 | 5 | 50.56% | 51.84% | 49.29% | 48.94% | 51.44% | 46.52% |
| 68 | 6 | 50.54% | 53.25% | 47.87% | 50.86% | 53.59% | 48.15% |
| 82 | 7 | 49.45% | 50.57% | 48.29% | 47.60% | 50.03% | 45.23% |
| 88 | 5 | 47.05% | 47.97% | 46.13% | 47.81% | 50.14% | 45.55% |
| 98 | 3 | 49.03% | 51.19% | 46.86% | 49.43% | 52.51% | 46.36% |
| 103 | 4 | 47.74% | 49.91% | 45.57% | 48.35% | 50.89% | 45.86% |
| 112 | 6 | 46.76% | 46.79% | 46.72% | 47.50% | 50.85% | 44.19% |
| 118 | 0 | 48.79% | 50.99% | 46.67% | 49.95% | 52.24% | 47.73% |
| 120 | 2 | 48.22% | 50.31% | 46.15% | 48.23% | 50.66% | 45.87% |
| 128 | 4 | 51.26% | 53.65% | 48.88% | 47.99% | 50.97% | 45.16% |
| 139 | 4 | 51.25% | 52.50% | 49.98% | 48.96% | 51.37% | 46.60% |
| 144 | 1 | 48.30% | 50.55% | 46.07% | 49.86% | 52.07% | 47.67% |
| 152 | 7 | 48.24% | 48.20% | 48.28% | 48.45% | 51.28% | 45.74% |
| 158 | 3 | 50.31% | 47.09% | 53.82% | 47.48% | 50.45% | 44.54% |
PlayedWRとDrawnWR
表だと情報が見にくいので、見やすい形に変換してカードの統計を確認します。以下は、カードのコストとPlayedWR, DrawnWRの散布図です。
例えば、以下のことが読み取れます。
- コストとPlayedWRにはあまり相関がなさそうに見えます。(相関係数
r = -0.23 - コストとDrawnWRには少し負の相関があるように見えます。(相関係数
r = -0.63
コストとDrawnWRに負の相関があることの原因は、ターンごとの統計を見ると分かりやすいです。そのため、ターンごとの統計を見ていきます。
ターンごとのPlayedWRとDrawnWR
すべてのカードのターンごとの統計を見るのは難しいので、2枚に注目して統計を確認します。以下の2枚です。
Card Id:3 Beavrat 1コスト2/2
Card Id: 82 Slithering Nightmare 7コスト5/5 Breakthrough, Drain, Ward
それぞれのターンごとのPlayedWR、DrawnWRは以下の通りです。
これらから、以下のことが読み取れます。平均の勝利ターン数後の15ターン目くらいまでに注目します。
- Beavrat はPlayedWR、DrawnWR共にターン数が後になると少しずつ下がっています。
- Slithering Nightmare はPlayedWRはターン数が後になると少しずつ下がっています。
- 後攻6ターン目にはじめて使用できるので、6ターン目までの統計はありません。
- Slithering Nightmare は序盤のDrawnWRが低いですが、使用可能になるターンのあとから少し上がっています。
話を戻して、コストとDrawnWRの関係について考えます。
- Beavrat は1コストのクリーチャーなので、当然序盤に引けると嬉しいカードです。逆に、Slithering Nightmareは7コストのクリーチャーなので、7ターン目以降に引けると嬉しいカードです。
- Slithering Nightmareを使えないターンに引くことは、勝率を下げているといえます。
- 単にこのカードが使えないというだけでなく、他の使用できたはずのカードの分を奪っているという見方もできます。従って、手札が少ないゲームシステムである場合、序盤のDrawnWRが低くなる効果が大きくなると考えられます。
- Slithering Nightmareを使えないターンに引くことは、勝率を下げているといえます。
- つまり、使えないターンが長いコストの高いカードはDrawnWRが低くなると考えることができます。
強いカード、弱いカード
ここまでの議論によって強いと考えられるカードをいくつか挙げます。
Card Id: 7 Rootkin Sapling 2コスト2/2 Ward
- Steelplume Defenderも全く同じカードです。
Card Id: 48 Venom Hedgehog 1コスト1/1 Lethal
Card Id: 53 Possessed Abomination 4コスト1/1 Charge, Lethal
Card Id: 66 Staring Wickerbeast 5コスト5/1 Ward
Card Id: 68 Giant Squid 6コスト7/5 Ward
Card Id: 152 Mighty Throwing Axe 7コスト0/-7 Deal 7 damage to an enemy creature.
Draw a card.
- キーワード能力 Lethal, Wardをもっているクリーチャーが多いです。
- これらは、1体で相手のクリーチャーを複数破壊することや、1体しか破壊できないとしてもかけたコストがより多いクリーチャーを破壊することができます。
- Mighty Throwing Axeは、前のターンに相手が召喚した比較的強いクリーチャーを破壊しながら、自身の次のターンのドローを増やすような役割が期待できます。
- これらは定性的に考えても強いことが分かりますが、統計だけを見ても強いことを読み取ることができます。
逆に、ここまでの議論によって弱いと考えられるカードをいくつか挙げます。
Card Id: 45 Night Howler 6コスト6/5 Breakthrough, Drain, Summon: You lose 3 health.
Card Id: 120 Venomfruit 2コスト1/0 Give a friendly creature +1/+0 and Lethal.
Card Id: 158 Tome of Thunder 3コスト0/-4 Deal 4 damage.
- Venomfruit、Tome of Thunderのようなアイテムは仮に今のターンに使用できるとしても、試合全体で見れば使わないほうがよい場面が発生しやすいカードです。
- 例えば、相手の盤面が空で、かつTome of Thunderを使用できるとき、これを相手のHPを削るために使うより、相手が次に召喚したクリーチャーに対して使用するほうが強いです。
- LOCMはコンテストである都合上、100msの実行時間制限があり、深い先読みを行うのが難しいです。そのため、このような使い所の難しいカードは弱く評価されやすいです。
後手の不利を覆すパターン
先に述べたように後手の勝率は、44.89%でした。後手が勝つ試合では、どのようなことが起こっているかについて調べます。
以下は、いくつかのカードの後手のターンごとのPlayed WRです。
Card Id: 65 Steelplume Defender 2コスト2/2 Ward
Card Id: 118 Royal Helm 0コスト0/3 Give a friendly creature +0/+3.
Card Id: 128 Enchanted Cloth 4コスト4/3 Give a friendly creature +4/+3.
Card Id: 139 Grow Stingers 4コスト0/0 Give a friendly creature Lethal and Ward.
上記のカードのうち、緑アイテムに注目します。これらを早いターンに使用できたゲームでは、勝率が60%程度あることが分かります。ただ、これらを使用するためには、ターンが始まったときに自分の盤面にクリーチャーが存在する必要があります。
結局、序盤に盤面の有利が取れている状況を作り出すことが必要であると分かります。
以下は、同じカードの後手のターンごとのDrawn WRです。
これを見ると、これらの緑アイテムを序盤に引いたというだけでは勝率はあまり改善していないということが分かります。これらのカードは取れた有利をより大きくすることはできますが、今有利が取れていない状況を有利にすることはできません。
DrawnWRの平均が勝率より高い・低いこと
先手の勝率は55.11%ですが、先手のDrawnWRの最大値は54.97%です。つまり、すべてのカードのDrawnWRは勝率よりも低いです。
直感的には、DrawnWRの平均は勝率くらいの値になりそうな気がしますが、そうなっていないのはなぜでしょうか？
ゲーム全体の統計を思い出すと、試合が長期的になると勝率が悪化していました。
これを言い換えると、勝った試合では、負けた試合に比べて平均して引いているカードの枚数が少ないといえます。
実際に確認してみます。勝った試合で引いたカードの枚数の合計は、44399枚です。平均では20.04枚です。また、負けた試合で引いたカードの枚数の合計は、41723枚です。平均では、23.13枚です。全体のDrawnWRは
結局、勝った試合と負けた試合でカードを引く枚数が異なるとき、DrawnWRは勝率と一致しないということが分かります。
あとがき
カードゲームの統計分析といえば、HSReplay.netやUntapped.ggが有名だと思います。これらは便利で面白いサービスなのですが、LOCMのコンテストを見つけたときに、自分で生データの加工、集計、分析までをやりたいとずっと思っていて、今回記事を書きました。[5]
ターンごとのDrawnWRは上記のサイトでは見ることができないので、今回集計した意味があったのかなと思っています。
本当は、アグロデッキとコントロールデッキを対戦させたデータを分析する章を追加する予定でしたが、長すぎる上に同じデッキリストでもたくさん書けることはあったので、省略することにしました。
-
gifをクリックすると綺麗なリプレイを見ることができるページに飛べます。 ↩︎
-
キーワード能力が複合している場合の挙動は説明しませんでしたが、結果としてダメージを与えることができたかを軸に考えると分かりやすいです。 ↩︎
-
自分でもローカル対戦を行わせたいという方へ: 適当にネットで検索すると、https://github.com/dreignier/cg-brutaltester を使ったローカル対戦環境の構築が主流なようですが、LOCMのRefreeとして記載されているものはLOCMが更新され、入出力の形式が変更されていることにより動きません。好ましいやり方ではない気がしますが、 https://github.com/CodinGame/LegendsOfCodeAndMagic の
src/test/java/Main.javaのgameRunner.addAgent(PlayerEmpty.class);をgameRunner.addAgent(SOME_COMMAND);に書き換えて実行すればよいです。 ↩︎ -
DrawnWRは、あるカードを引いたときの勝率のことでした。ここでは、引いたという行為が勝った試合のものである割合を求めていると考えればよいです。 ↩︎
-
まだコンテスト自体もLegend Leagueに行けていないし工夫の余地はかなりあるのでまた時間があるときにもう少し取り組む予定です。 ↩︎
Discussion