Deckchecks, Heuristics, and Decision Trees


Recently I had the pleasure of attending an online conference1: Practical Deck Checks with Oli Bird where they talked about the specifics of when, why we do deckchecks2, and how. The latter point sparked some ideation.

How do we chose the strategy by which we deck check?

Are we consciously choosing the best strategy for each deck check? Are we leveraging all the tools at our disposal to make such a decision?

In this post, I want to explore such questions; as at first glance, the answer seems to be: no.

TL;DR

Play around with the Deck Partitioner tool. Paste a deck. See the cost of each partition strategy and see if your heuristic matches my hypothesis of costs.

What are deck checks

Feel free to skip this section if you are already versed in what they are

In Magic: The Gathering™’s tournaments, players are expected not to cheat. And there are people (called judges) that train to, in addition to other more noble and customer-caring actions, prevent that from happening. One of the tools judges employ to thwart attempts to cheat is to require players to write down what cards they will be playing within a particular tournament or section of the tournament, and routinely checked that the cards they are playing with are those that they settled from the start.

Judges must perform these checks the fastest way possible to not delay the tournament. As such, they developed a myriad of techniques. In this blog post, I would like to explore their inner workings, propose a hypothesis on why they might work in some situations but not others, consider unexplored alternatives, and hopefully build a heuristic on what method is better for each circumstance.

Side note: It feels so weird writing about a deck check amidst a pandemic; when the last one I did was well over a year ago, and who knows how we’ll perform them in the future. The mere thought of manipulating other human being’s cards is bizarre. Time will tell…

Techniques

I’ll briefly go through two ways I know judges do deck checks. I highly recommend watching the video from Federico Donner where he goes in-depth with a visual aide on many other techniques (even though it is in Spanish, it has subtitles).

1. Type separation

Split the deck by dividing it into two piles: lands and non-lands. Then proceed to split each pile by card name. Afterward go through the decklist in order and verify the quantity is correct.

land / non-land

2. Mana value3 separation

Split the deck into piles, categorized by mana value. Then go through the decklist and retrieve the cards with the required quantity from the appropriate pile.

by mana value

This got me thinking, to perform a deck check, there are two critical pieces of information that we need:

  1. A sorted deck
  2. and a decklist.

Technique number 1 starts with a sorted deck and then uses the list. Technique number 2 starts to sort a deck, and then uses the decklist to make the remaining sorting easier. Thus I wondered: Is there something we can do with just the list? Considering we have unlimited access to a list, and (baring the opportunity cost of not being on the floor) looking at the list has no impact on the timings of a tournament.

It then dawned upon me that I know some judges that do a different permutation when checking Modern’s Tron than Modern’s Burn for example.

Their heuristics tell them that separating Burn by type is less efficient than separating by mana value. And separating by color is all but useless. Most lists run four copies of each card, and the mana values are very tightly packed. Whereas Tron benefits greatly by doing the first split by lands / non-lands, and then color.

This got me thinking, it would be great to devise a mathematical model of deck sorting to figure out what the best approach to separating a deck is. I feel we under-use the availability of the decklist, so having a clear plan ahead of actually getting the deck in our hands can prove highly effective.

Defining the problem statement

I want to find a mathematical formula to aid me in minimizing the time of performing a deck check. As I’m not a good mathematician. But I know a thing or two about coding. I reckon I can compute for a deck every single permutation of partition strategy; and with a way of putting a numeric value on the cost of each arrangement, select the optimal.

To do so, we’ll have to establish some common names and operations, and abstract away some details like “how much desk space does each technique use up”, or how to deal with a sideboard-ed deck.

Given those abstractions, we can reframe the problem of checking a deck, to one much closer to ~botanics~programming: Constructing a tree. In my model, the process of deck checking is equivalent to building a tree, where each node holds an intermediate pile of cards that have been split by some criteria. And the leaves are piles of same-name cards ready to be cross-checked with a decklist.

To construct the procedure tree you start with a node with all the cards. Then for each category you want to classify4 them, you split into sub-nodes with the cards that match that criteria. This way you learn more about each pile.

This test may be binary (e.g.: land vs non-land) or not (e.g.: by mana value, or by color). This process is repeated until cards are classified by name. Further sub-classifications are pointless, as cards with the same name will (by definition) have the same attributes.

Example

We’ll be using just a deck of 16 cards to make things concise:

4 Primeval Titan
2 Azusa, Lost but Seeking
4 Amulet of Vigor
2 Valakut, the Molten Pinnacle
4 Simic Growth Chamber

Remember you can play along in the Deck Partitioner web.

1. Type separation tree

Start with the whole deck.

no classification

We’ll represent this deck, unclassified, like so:

┌──a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
└──a card

We know nothing about these cards yet. So we proceed by the deck into a lands and a non-lands pile.

land / non-land

┌──┌──Non-Land
│  │  Non-Land
│  │  Non-Land
│  │  Non-Land
│  │  Non-Land
│  │  Non-Land
│  │  Non-Land
│  │  Non-Land
│  │  Non-Land
│  └──Non-Land
│  
│  ┌──Land
│  │  Land
│  │  Land
│  │  Land
│  │  Land
└──└──Land

We now know more about each pile, but not enough to verify the deck. So we continue to split each pile by card name.

by name

┌──┌──┌──Non-Land   Primeval Titan
│  │  │  Non-Land   Primeval Titan
│  │  │  Non-Land   Primeval Titan
│  │  └──Non-Land   Primeval Titan
│  │  
│  │  ┌──Non-Land   Azusa, Lost but Seeking
│  │  └──Non-Land   Azusa, Lost but Seeking
│  │  
│  │  ┌──Non-Land   Amulet of Vigor
│  │  │  Non-Land   Amulet of Vigor
│  │  │  Non-Land   Amulet of Vigor
│  └──└──Non-Land   Amulet of Vigor
│  
│  ┌──┌──Land       Valakut, the Molten Pinnacle
│  │  └──Land       Valakut, the Molten Pinnacle
│  │  
│  │  ┌──Land       Simic Growth Chamber
│  │  │  Land       Simic Growth Chamber
│  │  │  Land       Simic Growth Chamber
└──└──└──Land       Simic Growth Chamber

2. Type separation tree

Again start with the whole deck.

no classification

And once more, the same text representation, with no information whatsoever:

┌──a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
│  a card
└──a card

Afterward, split each pile by type.

by type

┌──┌──Creature
│  │  Creature
│  │  Creature
│  │  Creature
│  │  Creature
│  └──Creature
│  
│  ┌──Artifact
│  │  Artifact
│  │  Artifact
│  └──Artifact
│  
│  ┌──Land
│  │  Land
│  │  Land
│  │  Land
│  │  Land
└──└──Land

And finally each by card name.

by name

┌──┌──┌──Creature   Primeval Titan
│  │  │  Creature   Primeval Titan
│  │  │  Creature   Primeval Titan
│  │  └──Creature   Primeval Titan
│  │ 
│  │  ┌──Creature   Azusa, Lost but Seeking
│  └──└──Creature   Azusa, Lost but Seeking
│   
│  ┌──┌──Artifact   Amulet of Vigor
│  │  │  Artifact   Amulet of Vigor
│  │  │  Artifact   Amulet of Vigor
│  └──└──Artifact   Amulet of Vigor
│   
│  ┌──┌──Land       Valakut, the Molten Pinnacle
│  │  └──Land       Valakut, the Molten Pinnacle
│  │   
│  │  ┌──Land       Simic Growth Chamber
│  │  │  Land       Simic Growth Chamber
│  │  │  Land       Simic Growth Chamber
└──└──└──Land       Simic Growth Chamber

The result is, as to be expected, the same.

Evaluation

Now that we know how to construct any strategy of partitions, we need to decide which is the best.

In my model, I pose that the cost of each classification is associated with the number of piles4 generated by the test. It is faster to decide

  • land
  • non-land

than

  • mana value=0
  • mana value=1
  • mana value=2
  • etc.

Not only there is much more brainpower needed to parse a card into these categories, but the physical act of placing the card in the appropriate pile is costly. This action of deciding each pile is then multiplied for how many cards need to be sorted. It does not take the same time to sort 10 cards as 100. But I reckon that the cost is linearly proportional, as it is just doing the same classification over and over again.

So to go from

┌──a card  >>  ┌──┌──Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  │  Non-Land
│  a card  >>  │  └──Non-Land
│              │  
│  a card  >>  │  ┌──Land
│  a card  >>  │  │  Land
│  a card  >>  │  │  Land
│  a card  >>  │  │  Land
│  a card  >>  │  │  Land
└──a card  >>  └──└──Land

We need to go through each card (\(16\)) and with each one decide between one of two buckets. Thus the total cost is \(16 \times 2 = 32\). Whereas to classify like this:

┌──a card  >>  ┌──┌──Creature
│  a card  >>  │  │  Creature
│  a card  >>  │  │  Creature
│  a card  >>  │  │  Creature
│  a card  >>  │  │  Creature
│  a card  >>  │  └──Creature
│              │  
│  a card  >>  │  ┌──Artifact
│  a card  >>  │  │  Artifact
│  a card  >>  │  │  Artifact
│  a card  >>  │  └──Artifact
│              │
│  a card  >>  │  ┌──Land
│  a card  >>  │  │  Land
│  a card  >>  │  │  Land
│  a card  >>  │  │  Land
│  a card  >>  │  │  Land
└──a card  >>  └──└──Land

we again have to decide \(16\) times, but now on four possible classifications, so the cost is much higher (twice as high): \(16 \times 4 = 64\). But we end with smaller buckets.

The entire cost of a sorting technique then is adding up all the costs of each node’s classification cost (in the web you can mouse over each tree section to get the drill of the cost. And the total cost at the bottom of the page).

I did not add a cost associated with how many levels of the classification there are, as I think it is small enough to be ignored. Though in my limited testing, it does cause fatigue if above a certain number of classifications.

Going back to the Modern Burn, the math seems to agree with their heuristic, and the most cost-efficient partition is by mana value > by name; whereas for Tron, the most efficient way of splitting is by land/non-land > by color > by type > by name.

Request for help

I would love other people to experiment and time themselves to figure out if my hypothesis does hold; or if the cost of further sub-partitions is not, in fact, negligible. But rather scales exponentially each new level. I’m very curious.

If you want to help me out fine-tuning my cost function costs to find a better heuristic you can very much do so by classifying some cards and measuring the time it took in this form.

If you instead do a different classification strategy, I would be very interested in learning about it. So please feel free to comment on the application issue list.

Playground

As I said before, I write code for a living and very much enjoy it, so I came up with a small program to do these simulations. You can input any deck, and it will figure out all the possible ways of splitting and sorting it, and then choose the one with the least cost.

You can try it out here.


  1. It’s 2021 and we are still in lockdown because of the COVID-19, hence why the conference was virtual. 

  2. Deck Check Procedures in Wizard’s article page

  3. Previously known as “casting cost”, “total casting cost” or “converted mana cost” (cmc). 

  4. For those interested in the math, I can point you in the right direction of the formalization of this: Generating a Equivalence relation that yields a partition 2

Melian

Random Posts

Implementing Google OAuth to use Google API in Cloudflare Workers

In this blog-post, we'll go over the setup process and code required to implement a OAuth 2.0 flow, from the ground up, using Cloudflare Workers, their KV, and the Google API. #xpost

Haskell para mentes imperativas

En este post quiero explorar algunas cosas que creo que me hubiesen servido para aprender Haskell. Teniendo una base en algún lenguaje imperativo, usar esta para programar en Haskell. #xpost

Why Do I Write?

I have much room for improvement where it comes to communicating. A tool I think can help me with it is writing a blog entry every so often about things I care about. This blog is just that. A training ground. My training ground. #rambling

Discovering Crystal

I was working with Ruby on Rails on a project with other very skilled Ruby and Rails developers. As many others working with Ruby, we liked it’s syntax, it’s ease of use, it’s dependencies (gems) but had some issues with it. Every programming language does. As luck would have it, I was also in close contact with some very vociferous advocate of Crystal. You can imagine, with the tagline: “Fast as C, Slick as Ruby”, I was hooked. #xpost