iTranslated by AI

The content below is an AI-generated translation. This is an experimental feature, and may contain errors. View original article
🎴

Introduction to the Legends of Code & Magic Contest and Fundamentals of Card Game Statistical Analysis

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

Overview

Legends of Code & Magic is a programming contest where you create a bot to play a two-player card game and compete for its strength. The contest is permanently available on CodinGame.

I will cover the following two main topics:

  • A brief introduction to the rules
  • Analysis and interpretation of statistical data

A brief introduction to the rules

The gif above is a recording of actual bots playing against each other. [1]
If you are familiar with them, you can think of it as a game similar to Magic: The Gathering, Hearthstone, or Shadowverse. The game systems are quite similar to these.

The game is divided into two major phases: the Draft Phase and the Battle Phase.

  • Draft Phase \dots Three cards are randomly presented from the entire pool, and each player chooses one to add to their deck. This is repeated 30 times to construct a deck.
  • Battle Phase \dots Players fight their opponent using the deck constructed during the draft. You win by reducing the opponent's HP to 0 or less.

First, I will explain the system of the Battle Phase, and then I will describe the types and effects of the cards.

Basic System

  • Each player has 30 HP.
  • The first player starts with 4 cards, and the second player starts with 5 cards. There are no mulligans. The maximum hand size is 8. You draw one card from your deck at the start of every turn.
    • Some cards can increase the number of cards drawn on the following turn.
  • Mana (the cost paid to use cards) starts at 1 for the first player and 2 for the second player. Every time your turn comes, your mana refills and the capacity increases by 1. The maximum capacity is 12.
    • For the second player, after they use up all their mana, the capacity decreases by 1. (It is helpful to think of it as having a right to temporarily increase the mana limit by 1 for that turn only.)
  • Each player has 5 runes. On the turn after a rune is lost, that player draws one additional card.
    • A rune is lost the first time HP drops to 25, 20, 15, 10, or 5 or less.
  • There are cards called Creatures, which can be summoned to your board. You can summon up to 6 at a time. (Card details are described later.)
    • Once per turn, a creature can attack the opponent or an opponent's creature on the board. When attacking a creature, both deal damage to each other equal to their attack power, and health is reduced.
      • For example, if a creature with 3 Attack/4 Health attacks a creature with 2 Attack/3 Health, your creature's health becomes 2, and the opponent's is destroyed.
    • Creatures cannot attack on the turn they are summoned.

The first and second players take turns, acting with the goal of reducing the opponent's HP to 0 or less.

Card Types

There are four main types of cards: Creatures, Green Items, Red Items, and Blue Items.

  • Creatures \dots Cards that can be summoned to your board by paying mana. They have attack power and health, and are destroyed when health reaches 0 or less.


Card Id: 4 Plated Toad 2 cost 1/5

  • Green Items \dots By paying mana and consuming the card, you can activate its effect. These target a creature on your board to make it stronger.


Card Id: 120 Venomfruit 2 cost 1/0 Give a friendly creature +1/+0 and Lethal.

  • Red Items \dots By paying mana and consuming the card, you can activate its effect. These target an opponent's creature on the board to give it disadvantageous effects such as reducing its attack or health.


Card Id: 145 Cursed Sword 3 cost -2/-2 Give an enemy creature -2/-2.

  • Blue Items \dots By paying mana and consuming the card, you can activate its effect. These target you, the opponent, or an opponent's creature on the board to activate an effect.


Card Id: 157 Life Sap Drop 3 cost 0/-1 Deal 1 damage, gain 1 health, and draw a card.

Creature Keyword Abilities

Some creatures have abilities represented by specific keywords. [2]

  • Breakthrough \dots When attacking a creature, if your attack power exceeds the opponent's health, the excess damage is dealt to the opponent.
  • Charge \dots Can attack on the turn it is summoned.
  • Drain \dots When it attacks, it restores its own health equal to the damage dealt.
  • Guard \dots Opposing creatures must first target creatures with this keyword ability when attacking.
  • Lethal \dots When it deals damage to a creature, that creature is destroyed.
  • Ward \dots Nullifies the next damage it would receive once.

Some items grant or remove keyword abilities when used on a creature.

Specifics of LOCM

LOCM is a programming contest and assumes that player actions are performed via standard input/output. Therefore, there are some differences from normal card games.

  • At the start of a turn, information such as the HP, mana, and runes of yourself and your opponent, as well as the cards in hand and on the board, are input.
  • Within a specified execution time limit, you must output the actions you will take that turn in a single line.

In general card games, drawing a card during a turn is common. In LOCM, due to the nature of only one input being possible per turn, there are no such effects.

Also, effects that would require decision-making by the opponent during your turn are not implemented.

Official rules and judges can be found at the following URLs. You can check the rules in more detail there.

Statistical Analysis

In CodinGame contests, you can run matches locally between your own programs.
Furthermore, by setting options, you can control the draft choices to present the same cards.
By utilizing this, you can conduct statistical analysis by repeatedly playing matches with constructed decks and collecting data from the logs. [3]

What to look at and what to know

This time, I obtained the following data:

  • Game Data
    • Whether the first or second player won or lost
    • At which turn the victory or defeat was decided
  • Card Data
    • At which turn a certain card was drawn
    • At which turn a certain card was played

By combining this data, you can investigate statistics such as:

  • Win rate in matches where a certain card was drawn (hereafter referred to as DrawnWR)
  • Win rate in matches where a certain card was played (hereafter referred to as PlayedWR)
  • Win rate for each turn a certain card was drawn in matches where it was drawn
  • Win rate for each turn a certain card was played in matches where it was played

Furthermore, considering what we want to know by investigating these, examples include:

  • From a player's perspective
    • I want to check the strength of each card. If there are weak cards, I want to swap them out to increase the win rate.
    • I want to analyze the strengths and weaknesses of the deck and apply it to my playstyle.
  • From an organizer's perspective
    • I want to analyze where to make adjustments to balance the game.

Playing with the Same Deck

I will have both players use the following deck list and analyze its statistics.

  • By controlling the draft choices and the drafting algorithm, the decks for the two competing bots are fixed.
  • During the Battle Phase, the thought routines for the two bots are identical.

Since it's 30 cards and quite long, you don't need to read through it all. Images of cards are attached where necessary for checking details.

Deck List Details
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.
  • The deck is constructed to be a standard midrange deck. The mana curve is as follows. (Mana curve: the distribution of costs for cards in the deck.)

Game-wide Statistics

In this section, we examine the overall game statistics, primarily focusing on the gap between the first and second players.

  • Out of 4,019 matches, the first player won 2,215 and lost 1,804. The win rate for the first player is 55.11% (leaving the second player with 44.89%).
  • The average turn to victory was 12.50 turns for the first player and 13.53 turns for the second player. The overall average turn to victory is 12.96 turns.

Below is a graph showing the number of victories for the first and second players per turn.

From these data, we can observe the following:

  • In matches ending on turns 5, 6, and 7, the second player has a higher win rate.
  • In matches ending between turns 8 and 14, the first player has a higher win rate.
  • As matches become longer, the second player tends to win more often.
    • Specifically, for matches lasting 13 turns or more, the first player's win rate is 47.42%, while the second player's is 52.58%.

Since the deck lists are identical, the advantages and disadvantages for the first and second players are likely due to the game system itself.

  • Factors favoring the first player:
    • (Obviously) they act first.
      • This factor seems significant in why the first player leads in matches ending between turns 8 and 14.
  • Factors favoring the second player:
    • They can use 1 extra mana once.
      • This factor seems significant in why the second player leads in matches ending on turns 5, 6, and 7.
    • they start with one more card.
      • This factor seems to contribute to the higher win rate for the second player in matches lasting 13 turns or more.

Card Statistics

In this section, we check the statistics for individual cards.

First, let's look at the PlayedWR and DrawnWR for each card. From left to right: Card ID, Cost, PlayedWR, First Player PlayedWR, Second Player PlayedWR, DrawnWR, First Player DrawnWR, and Second Player 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 and DrawnWR

Since information in a table can be hard to read, let's convert it into a more visible format to check card statistics. Below are scatter plots showing the relationship between card cost and PlayedWR, as well as card cost and DrawnWR.

For example, we can observe the following:

  • There appears to be little correlation between cost and PlayedWR (correlation coefficient r = -0.23).
  • There seems to be a slight negative correlation between cost and DrawnWR (correlation coefficient r = -0.63).

The reason for the negative correlation between cost and DrawnWR becomes clearer when looking at statistics per turn. Therefore, let's examine the turn-by-turn statistics.

PlayedWR and DrawnWR per Turn

As it is difficult to look at turn-by-turn statistics for every card, let's focus on two specific cards to check the data. These two cards are:


Card Id: 3 Beavrat 1 cost 2/2


Card Id: 82 Slithering Nightmare 7 cost 5/5 Breakthrough, Drain, Ward

The PlayedWR and DrawnWR for each turn are as follows:

From these graphs, we can interpret the following, focusing up to around turn 15, which is after the average victory turn:

  • For Beavrat, both PlayedWR and DrawnWR gradually decrease as the number of turns increases.
  • For Slithering Nightmare, PlayedWR gradually decreases as the number of turns increases.
    • Since it can only be played from the second player's turn 6 onwards, there are no statistics before turn 6.
  • For Slithering Nightmare, the DrawnWR is low in the early game but increases slightly after the turn it becomes playable.

Returning to the relationship between cost and DrawnWR:

  • Beavrat is a 1-cost creature, so naturally, it is a card you are happy to draw early. Conversely, Slithering Nightmare is a 7-cost creature, so it is a card you are happy to draw from turn 7 onwards.
    • Drawing Slithering Nightmare during turns when it cannot be used can be said to lower the win rate.
      • This can be viewed not just as this card being unusable, but also as it taking the place of another card that could have been used. Therefore, in a game system with a small hand size, the effect of early-game DrawnWR becoming lower is thought to be significant.
  • In other words, high-cost cards with long periods where they cannot be used tend to have lower DrawnWR.
    • Conversely, for low-cost cards, the benefit of drawing them late is lower than for high-cost cards. The balance of these factors results in the final DrawnWR, and in this case, high-cost cards are evaluated lower.

Finally, let's consider whether PlayedWR or DrawnWR is more suitable for investigating card strength.

We have seen that DrawnWR reflects effectiveness after a card is drawn. Furthermore, when considering what card strength is, it is clear that it is better to consider not only the strength when used but also the impact when it cannot be used.

Therefore, we can see that DrawnWR is more suitable than PlayedWR for evaluating card strength.

Strong and Weak Cards

Based on the discussion so far, here are some cards considered strong.


Card Id: 7 Rootkin Sapling 2 cost 2/2 Ward

  • Steelplume Defender is the exact same card.


Card Id: 48 Venom Hedgehog 1 cost 1/1 Lethal


Card Id: 53 Possessed Abomination 4 cost 1/1 Charge, Lethal


Card Id: 66 Staring Wickerbeast 5 cost 5/1 Ward


Card Id: 68 Giant Squid 6 cost 7/5 Ward


Card Id: 152 Mighty Throwing Axe 7 cost 0/-7 Deal 7 damage to an enemy creature.
Draw a card.

  • Many of these creatures have the keyword abilities Lethal or Ward.
    • These allow a single card to destroy multiple opponent creatures, or destroy a higher-cost creature even if only one can be destroyed.
  • Mighty Throwing Axe can be expected to play the role of destroying a relatively strong creature summoned by the opponent on the previous turn while increasing your draw for the next turn.
  • While these are qualitatively understood to be strong, their strength can also be inferred from the statistics alone.

Conversely, here are some cards considered weak based on the discussion so far.


Card Id: 45 Night Howler 6 cost 6/5 Breakthrough, Drain, Summon: You lose 3 health.


Card Id: 120 Venomfruit 2 cost 1/0 Give a friendly creature +1/+0 and Lethal.


Card Id: 158 Tome of Thunder 3 cost 0/-4 Deal 4 damage.

  • Items like Venomfruit and Tome of Thunder are cards that, even if they could be used in the current turn, often have situations where it's better not to use them from the perspective of the entire match.
    • For example, if the opponent's board is empty and you can use Tome of Thunder, it's stronger to use it against a creature the opponent summons next rather than using it to chip away at the opponent's HP.
  • Since LOCM is a contest, there is a 100ms execution time limit, making it difficult to perform deep look-aheads. Therefore, cards that are difficult to use effectively tend to be evaluated poorly.

Patterns for Overcoming the Second Player's Disadvantage

As mentioned earlier, the win rate for the second player was 44.89%. We will investigate what happens in matches where the second player wins.

Below are the PlayedWR per turn for the second player for several cards.


Card Id: 65 Steelplume Defender 2 cost 2/2 Ward


Card Id: 118 Royal Helm 0 cost 0/3 Give a friendly creature +0/+3.


Card Id: 128 Enchanted Cloth 4 cost 4/3 Give a friendly creature +4/+3.


Card Id: 139 Grow Stingers 4 cost 0/0 Give a friendly creature Lethal and Ward.

Focusing on the Green Items among the cards above, we can see that in games where these could be used in early turns, the win rate is around 60%. However, to use these, a creature must already exist on your board when the turn starts.
Ultimately, we can see that it is necessary to create a situation where you have a board advantage in the early game.

Below are the DrawnWR per turn for the second player for the same cards.

Looking at this, it's clear that simply drawing these Green Items early does not significantly improve the win rate. These cards can amplify an existing advantage, but they cannot turn a disadvantageous situation into an advantageous one.

Why the average DrawnWR is higher or lower than the win rate

The win rate for the first player is 55.11%, but the maximum DrawnWR for the first player is 54.97%. In other words, the DrawnWR for every card is lower than the win rate.
Intuitively, one might expect the average DrawnWR to be around the same value as the win rate, so why is this not the case?

Recalling the overall game statistics, the win rate deteriorated as the match became longer.
In other words, in winning matches, players drew fewer cards on average compared to losing matches.

Let's actually verify this. The total number of cards drawn in winning matches was 44,399, averaging 20.04 cards. In contrast, the total number of cards drawn in losing matches was 41,723, averaging 23.13 cards. The overall DrawnWR becomes \displaystyle \frac{44399}{44399+41723} = 0.5182... [4]

Ultimately, when the number of cards drawn differs between winning and losing matches, the DrawnWR will not align with the win rate.

Afterword

When it comes to statistical analysis of card games, services like HSReplay.net and Untapped.gg are famous. While these are convenient and interesting services, ever since I found the LOCM contest, I've wanted to do everything from processing raw data to aggregation and analysis myself, which led to this article.

Since turn-by-turn DrawnWR cannot be seen on those sites, I feel there was value in conducting this aggregation.

Initially, I planned to add a chapter analyzing data from matches between aggro and control decks, but it became too long and there was already plenty to write about even with the same deck list, so I decided to omit it.

脚注

  1. Clicking the gif will take you to a page where you can watch a clean replay. ↩︎

  2. I won't explain the behavior when keyword abilities are combined, but it's easier to think about whether the result was that damage was dealt. ↩︎

  3. For those who want to run local matches themselves: A quick web search suggests that building a local match environment using https://github.com/dreignier/cg-brutaltester is common, but the version listed as the LOCM Referee will not work because LOCM has been updated and the I/O format has changed. While it might not be the most elegant way, you can run it by replacing gameRunner.addAgent(PlayerEmpty.class); with gameRunner.addAgent(SOME_COMMAND); in src/test/java/Main.java from https://github.com/CodinGame/LegendsOfCodeAndMagic. ↩︎

  4. DrawnWR refers to the win rate when a certain card is drawn. Here, it can be thought of as finding the proportion of times the act of drawing a card belonged to a winning match. ↩︎

Discussion