Optimizing Magic: The Gathering in R

Magic: The Gathering

Two years ago I was in the midst of starting a gut rehab on my home, starting a new job, and ramping up PERRO’s lead in the water campaign. Someone suggested that it might be good to do something that wasn’t productive to relax. In this midst of this presidency, a lot of activists are getting burnt out, and the reaction to that has been to remind people that self-care is an act of political warfare. I had just heard a Planet Money podcast about Magic and I was blown away that it was still huge!

After a 2 decade hiatus, I started playing again, online and at my local game store. To no one’s surprise, the game has changed a bit over 2 decades. While I enjoy playing the game, I had no interest in studying up and no interest in filling in 2 decades of a missing collection. I was just trying to have fun. So I played the flavor of the game that only used a limited set of the most recent cards; Sealed Standard.

Sealed standard is the flavor of the game where you open 6 packs of random cards and build a small deck using 40 cards. Then you play other people who do the same thing. It’s a great way to play without all of the commitment and to get to know the newest iteration of the game.

Optimization

After some time I realized that building a reasonable deck with a random assortment of cards is an optimization problem of the variety that I studied while getting my Master’s degree in game theory. It’s also very, very similar to a previous blog post of selecting a fantasy football team for daily fantasy football.

So I wrote the algorithm up, played around with it, made it into an app, and posted it on the Magic sub-reddit in hopes that others might find it useful and I could make a little cash on the side… that didn’t happen. It was pointed out that using this algorithm in a competitive setting was against the rules; specifically, tournament rules section 2.11 and 2.12.

Womp, womp. No beer money for me! Regardless, it’s interesting enough that I figured if can’t make money off of it, I should at least open source it for a teachable moment. And after all, in these times of Nazi resurgences, we need to teach people how to beat Nazis again!

Seriously though, in my last 5 years in industry, these algorithms have blown people away. They’ve generated so much revenue that it’s clear to me that these algorithms and this field needs more attention! And the release of the Guilds of Ravnica set provided a great opportunity.

What follows is an algorithm for building an optimal Magic The Gathering standard sealed deck using linear programming. I also wrote up a quadratic programming version of it, but getting it to work required proprietary libraries… I’m sure my employer will look forward to that iteration. If you want to see the code, or add to it, or modify it, it’s on my github.

The Algorithm

If you’re really interested but don’t know about linear programming, there are plenty of resources online. Here’s Wikipedia to get you started.

This algorithm isn’t going make you a pro, but it will help you be competitive. This is also a very basic implementation of the algorithm. It doesn’t account for interactions between cards; e.g. lifelink cards won’t be valued more if you include Dawn of Hope in your deck.

Last time I had a linear implementation of this, but this is more naturally solved using quadratic programming.

Data

Data! Data! Data! I can’t make bricks without clay.

– Sherlock Holmes

I’m happy to report that mtgjson.com has most of the data required. It took a little bit of effort to parse the structure of the json (as a data scientist, I dislike json), but eventually I got what I needed. You can download the zip from here. As always, you can download the file with code, but I got excited and started clicking away 🙂

I used the jsonlite package to parse the data and then flattened it out. We want one row per card.

install.packages("jsonlite")
library(jsonlite)
mtg <- read_json(path = "AllSets.json")

# Doing some checks on the structure
length(mtg[[which(names(mtg)=="GRN")]])
names(mtg[[which(names(mtg)=="GRN")]])


GRN <- mtg$GRN$cards
col.names.GRN <- unique(unlist(lapply(GRN, names)))  

GRN.flat <- data.frame(matrix("", ncol = length(col.names.GRN), nrow = length(GRN)),
                        stringsAsFactors = FALSE)
colnames(GRN.flat) <- col.names.GRN

for(i in 1:length(GRN)){
  for(j in 1:ncol(GRN.flat)){
    if(sum(names(GRN[[i]])==col.names.GRN[j])){
      GRN.flat[i, j] <- GRN[[i]][[which(names(GRN[[i]])==col.names.GRN[j])]]
    }
  }
}
GRN.clean <- GRN.flat[, c("name", "rarity", "colorIdentity", "types", "cmc")]

Now we want to clean things up for our linear programming

GRN.clean <- cbind(GRN.clean, "score" = 0,
                   "B" = 0, "G" = 0, "R" = 0, "U" = 0, "W" = 0,
                   "quantity" = 0)

# Some of the colors identities got dropped in the flattening, so this:
for(i in 1:length(GRN)){
  card <- GRN[[i]]
  for(j in 1:length(card$colorIdentity)){
    GRN.clean[i, card$colorIdentity[[j]]] <- 1
  }
  if(length(card$colorIdentity) > 1){
    GRN.clean[i, "colorIdentity"] <- "M"
  }
}

# Fixing "colorIdentity" to handle these how we want them to
GRN.clean[which(GRN.clean$type == "Land"), "colorIdentity"] <- "Land"
GRN.clean[which(GRN.clean$type == "Artifact"), "colorIdentity"] <- "Artifact"

# We want artifact creatures as creatures for the optimization
GRN.clean[which(lapply(sapply(GRN,function(x) x["types"]), length)>1),
          "types"] <- "Creature"

# We don't want basic lands to be optimized, you can figure that out yourself
basic.land <- which(GRN.clean$rarity=="Basic Land")
GRN.clean <- GRN.clean[-basic.land, ]

# Next time I should remember to delete Planeswalker deck cards before reordering
# Finally I have to reorder to be able to copy down scores by hand more easily
GRN.clean <- GRN.clean[order(GRN.clean$colorIdentity, GRN.clean$name), ]

write.csv(GRN.clean, "GRN.csv", row.names = FALSE)

The above data is enough to define the problem constraints matrix, but I needed some card rankings to define the objective function. In trying to get a friend unacquainted to Magic to play, I stumbled upon Magic Community Set Review. Of course, this site is build using javascript, so scraping the data was going to be a headache. Instead of doing that, I spent about 20 minutes just copying the scores manually. No programming wizardry there, just good ol’ manual labor.  You could also use LSV’s reviews or your own… just change the entries in the spreadsheet, it’ll still work!

There was also some cleaning up to do with the rows of the csv. The planeswalker cards had to be removed and cards like Assure/Assemble had two rows that had to be combined into one.

# Read back in and sort by color and cmc
GRN.clean <- read.csv("GRN.csv")
GRN.clean <- GRN.clean[order(GRN.clean$colorIdentity, GRN.clean$cmc), ]
write.csv(GRN.clean, "GRN.csv", row.names = FALSE)

Code

At this point we have the data we need. Now to optimize!

First you’ll need to open your six packs of cards and fill in the number of cards you drafted in the quantity column and save. I saved mine as GRN_180927.csv. We also need to load in some standard settings; e.g. number of colors in the deck and number of non-land cards.

source("MTG/MTGopt_funcs.R")
draft <- read.csv("GRN_180927.csv", stringsAsFactors = FALSE)

num.colors <- 2
num.non.land <- 23

Above, I also loaded in a script MTGopt_funcs.R. I’ll explain the two main functions there. The function optimize.colors is where all the work is done. First we load in the lpSolve package. Then we pick out the colors of the deck that we want to optimize. Then we set constraints. I’m using the excellent Shadows Over Innistrad Prerelease Primer to determine the number of creatures at each converted mana cost (cmc) that we want; i.e. creature.curve. We add in slack variables to allow for deviations from that standard; i.e. creature.slack.mat. Without the slack variables, if we didn’t have any 1 cmc creatures, the function would return an error. The penalty for deviating from the recommendations in the primer is determined by the curve.penalty. Additionally there is a removal.penalty. That penalizes your deck for not having enough removal. I don’t have the time to manually encode which cards are removal cards, but if you want to add that to the GRN.csv send me a pull request! With 17 lands and 19 creatures prescribed, I hard-coded 4 removal spells to get up to the 40 card deck, but that could also be a variable.

library("lpSolve")

optimize.colors <- function(i, draft, deck.color.ind,
                            num.non.land = 23,
                            curve.penalty = 5,
                            removal.penalty = 5,
                            Mtg.colors = c("B", "G", "R", "U", "W"),
                            tribes = c("Artifact", "Ramp", "Goblin", "Dragon",
                                       "Lifelink", "Weenie", "Zombie"),
                            tribal.boost = rep(0, length(tribes))){
  remove.colors <- c(i)
  # Take out cards with other colors
  colors.ind <- which(rowSums(draft[, Mtg.colors[-deck.color.ind[i,]]]) == 0)
  colors.mat  0){
        tribe.ind  0)
        colors.mat[tribe.ind, "score"] <- colors.mat[tribe.ind, "score"] + tribal.boost[j]
      }
    }
  }
  # We are trying to maximize the collective score
  f.obj <- c(colors.mat$score)
  # adding in creature curve
  f.obj <- c(f.obj, rep(-1 * curve.penalty, 12))
  # adding in removal requirement
  f.obj <- c(f.obj, -1 * removal.penalty)
  
  
  # We can only select the cards we have, the constraint will be on the rhs
  f.con <- diag(1, nrow = nrow(colors.mat), ncol = nrow(colors.mat))
  # We need to have 23 non-land cards
  non.land.vec <- rep(1, nrow(colors.mat))
  non.land.vec[which(colors.mat$types == "Land")] <- 0
  f.con <- rbind(f.con, non.land.vec)
  # Add in creature curve 
  creature.mat <- matrix(0, ncol = nrow(colors.mat), nrow = 6)
  creature.mat[1, which(colors.mat$types == "Creature" & colors.mat$cmc == 1)] <- 1
  creature.mat[2, which(colors.mat$types == "Creature" & colors.mat$cmc == 2)] <- 1
  creature.mat[3, which(colors.mat$types == "Creature" & colors.mat$cmc == 3)] <- 1
  creature.mat[4, which(colors.mat$types == "Creature" & colors.mat$cmc == 4)] <- 1
  creature.mat[5, which(colors.mat$types == "Creature" & colors.mat$cmc == 5)]  5)] <- 1
  f.con <- rbind(f.con, creature.mat)
  # Add in slack.mat
  creature.slack.mat <- matrix(0, nrow = 6, ncol = 12)
  creature.slack.mat[cbind(1:6, seq(1, 11, 2))] <- 1
  creature.slack.mat[cbind(1:6, seq(2, 12, 2))] <- -1
  f.con <- cbind(f.con,
                 rbind(matrix(0, nrow = nrow(f.con) - nrow(creature.slack.mat),
                              ncol = 12),
                       creature.slack.mat))
  # Add in removal requirement
  removal.vec <- c(colors.mat$Removal, rep(0, length = ncol(f.con) - length(colors.mat$Removal)))
  f.con <- rbind(f.con, removal.vec)
  f.con <- cbind(f.con, c(rep(0, nrow(f.con) - 1), 1))
  
  # The constraint to only pick cards we have
  f.dir <- c(rep("=")
  
  # Using the cards we have for the RHS
  creature.curve <- c(1, 5, 4, 4, 3, 2)
  min.removal <- 4
  f.rhs <- c(colors.mat$quantity, num.non.land, creature.curve, min.removal)
  
  all.int <- TRUE
  
  fit <- lp("max", f.obj, f.con, f.dir, f.rhs, all.int = TRUE)
  
  cards <- cbind(colors.mat, quantity.used = fit$solution[1:nrow(colors.mat)])

  unused.cards  cards$quantity.used), ]

  deck <- cbind(colors.mat[which(fit$solution[1:nrow(colors.mat)] != 0),],
                quantity.used = fit$solution[which(fit$solution[1:nrow(colors.mat)] != 0)])
  fit.deck <- list(fit = fit, deck = deck, unused.cards = unused.cards)
}

The second important function is one that tests every color combination. You’ll see some of the “tribes” from the last set that I used this algorithm on; M19. That’s some more hand-coding into the GRN.csv that’d have to be done, but again, no time right now.

optimize.draft <- function(draft, num.colors, num.non.land,
                           curve.penalty = 5, removal.penalty = 5,
                           deck.choice = "Best",
                           tribes = c("Artifact", "Ramp", "Goblin", "Dragon",
                                      "Lifelink", "Weenie", "Zombie"),
                           tribal.boost = rep(0, length(tribes))){
  Mtg.colors <- c("B", "G", "R", "U", "W")
  deck.colors <- t(combn(Mtg.colors, num.colors))
  deck.color.ind <- t(combn(1:5, num.colors))
  objective.values <- data.frame(deck.colors, obj.val = rep(0, nrow(deck.colors)))
  # subset mat
  for(i in 1:nrow(objective.values)){
    fit.deck <- optimize.colors(i = i, draft = draft,
                                deck.color.ind = deck.color.ind,
                                num.non.land = num.non.land,
                                curve.penalty = curve.penalty,
                                removal.penalty = removal.penalty,
                                tribes = tribes,
                                tribal.boost = tribal.boost)
    objective.values[i, "obj.val"] <- fit.deck$fit$objval
  }
  ov.colors <- apply(objective.values[, -ncol(objective.values)],
                     1, paste0, collapse = "")
  obj.vals <- data.frame(colors = ov.colors, value = objective.values$obj.val)
  
  if(deck.choice == "Best"){
    fit.deck <- optimize.colors(i = which.max(objective.values$obj.val),
                                draft = draft,
                                deck.color.ind = deck.color.ind,
                                num.non.land = num.non.land,
                                curve.penalty = curve.penalty,
                                removal.penalty = removal.penalty,
                                tribes = NULL, #c("Artifact", "Ramp", "Goblin", "Dragon",
                                           # "Lifelink", "Weenie", "Zombie"),
                                tribal.boost = tribal.boost)
  } else {
    fit.deck <- optimize.colors(i = which(obj.vals$colors == deck.choice),
                                draft = draft,
                                deck.color.ind = deck.color.ind,
                                num.non.land = num.non.land,
                                curve.penalty = curve.penalty,
                                removal.penalty = removal.penalty,
                                tribes = NULL, # c("Artifact", "Ramp", "Goblin", "Dragon",
                                           # "Lifelink", "Weenie", "Zombie"),
                                tribal.boost = tribal.boost)
  }
  
  obj.vals <- obj.vals[order(obj.vals$value, decreasing = TRUE), ]
  
  # tribal.table <- rbind(colSums(fit.deck$deck[which(fit.deck$deck$quantity != 0), tribes] == 1),
                        # colSums(fit.deck$deck[which(fit.deck$deck$quantity != 0), tribes] == 2))
  # rownames(tribal.table) <- c("Followers", "Commanders")
  fit.deck <- list(fit.deck = fit.deck,
                   objective.values = obj.vals) # ,
                   # tribal.table = t(tribal.table))
}

Lastly, we put it all together with just one function!

fit <- optimize.draft(draft = draft,
               num.colors = num.colors,
               num.non.land = 40 - 17,
               curve.penalty = 2.5,
               removal.penalty = 0,
               deck.choice = "Best",
               tribes = NULL)

fit$fit.deck$deck[, c(1, 3:6, 12:13)]
##                      name colorIdentity       types cmc score quantity
## 73        Boros Guildgate          Land        Land   0  5.88        1
## 100   Fresh-Faced Recruit             M    Creature   2  5.60        3
## 104        Justice Strike             M     Instant   2  7.76        1
## 131 Skyknight Legionnaire             M    Creature   3  6.84        1
## 149      Truefire Captain             M    Creature   4  7.15        1
## 152     Garrison Sergeant             M    Creature   5  5.08        1
## 162     Swathcutter Giant             M    Creature   6  6.99        1
## 165       Goblin Banneret             R    Creature   1  5.66        1
## 174         Ornery Goblin             R    Creature   2  5.39        1
## 175     Runaway Steam-Kin             R    Creature   2  6.67        1
## 183      Arclight Phoenix             R    Creature   4  6.94        1
## 190     Command the Storm             R     Instant   5  6.76        1
## 191        Hellkite Whelp             R    Creature   5  6.59        1
## 233          Dawn of Hope             W Enchantment   2  7.26        1
## 237      Blade Instructor             W    Creature   3  4.45        3
## 243    Collar the Culprit             W     Instant   4  5.67        1
## 244     Conclave Tribunal             W Enchantment   4  9.03        1
## 246     Inspiring Unicorn             W    Creature   4  6.18        1
## 250   Intrusive Packbeast             W    Creature   5  5.43        1
## 253      Loxodon Restorer             W    Creature   6  4.58        1
##     quantity.used
## 73              1
## 100             3
## 104             1
## 131             1
## 149             1
## 152             1
## 162             1
## 165             1
## 174             1
## 175             1
## 183             1
## 190             1
## 191             1
## 233             1
## 237             3
## 243             1
## 244             1
## 246             1
## 250             1
## 253             1

There are some extras that I put in there for diagnostics. I put in the unused cards of that color in the likely event you want to swap out a card or two. I also put in all of the objective functions so you can compare the value of each color combination. Of course this is all coded into a shiny app. But that’s another blog post… or you can explore the repo.

Anyhow, I hope you learned a little about the glory of linear programming and R in your attempt to get a leg up on the competition. I used this to create two decks yesterday; mostly the Boros deck above and the Black/Green/White deck if you turn down the penalty curve all the way. I had 2 wins and 3 losses. Obviously, in addition to the inherent randomness that makes Magic so fun, it’s not perfect.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s