# Optimizing a Solution to an Overdetermined System

Hearthstone is a collectible card video game similar to Magic: The Gathering, where players play cards with certain values of "attack" and "health" for certain "mana" costs. After being introduced to some of the basics of R, I decided that I would find some of the "values" of these characteristics by finding the best solutions to an overdetermined system, as demonstrated here.

Let a card's mana cost, attack, health, and card value* be represented as the vector (m,a,h,v). Three cards are (1,1,2,1), (2,3,2,1), (4,4,5,1), and (7,9,5,1). This corresponds to the overdetermined system a+2h+v=1, 2a+3h+v=2, 4a+5h+v=4, 9a+5h+v=7. The below code would find values of a, h, and v that minimize the sum of the squared differences between the LHS and RHS of the four equations (more cards are shown than the example).

*Card value is the inherent value in having a card to play, as opposed to not having a card to play

numberOfCards = 9
numberOfEffects = 3 # Must be less than or equal to numberOfCards

# Mana, Attack, Health, Card Value

allCards = matrix(
c(1,2,1,1),                       # Murloc Raider
ncol = numberOfEffects + 1,
byrow = TRUE
)
allCards = rbind(allCards,c(2,2,3,1)) # River Crocolisk
allCards = rbind(allCards,c(2,3,2,1)) # Bloodfen Raptor
allCards = rbind(allCards,c(3,5,1,1)) # Magma Rager
allCards = rbind(allCards,c(4,2,7,1)) # Oasis Snapjaw
allCards = rbind(allCards,c(4,4,5,1)) # Chillwind Yeti
allCards = rbind(allCards,c(6,6,7,1)) # Boulderfist Ogre
allCards = rbind(allCards,c(7,7,7,1)) # War Golem
allCards = rbind(allCards,c(7,9,5,1)) # Core Hound

coefficientsMatrix = matrix(
NA,
nrow = numberOfEffects,
ncol = numberOfEffects,
byrow = TRUE)
for(i in 1:numberOfEffects) {
for(j in 1:numberOfEffects) {
coefficientsMatrix[i,j] = sum(allCards[,i+1] * allCards[,j+1])
}
}

constantsVector = vector(mode = "integer", length = numberOfEffects)
for(i in 1:numberOfEffects) {
constantsVector[i] = sum(allCards[,1] * allCards[,i+1])
}

effectValues = solve(coefficientsMatrix, constantsVector, tol = 1e-9)
cat(effectValues, "\n\n") # For demonstration of values of each effect

cardValueMatrix = allCards[,-1]

cardValues = vector(mode = "integer", length = numberOfCards)
for(i in 1:numberOfCards) {
cardValues[i] = round(sum(cardValueMatrix[i,] * effectValues), digits = 3)
cat("Card ", i, ": ", cardValues[i], "\n", sep = "")
}


I know of a couple things that could be improved in this code. The most glaring improvement that needs to be made is the creation of coefficientsMatrix; I've read that making a matrix of the correct size and filling it with NA only to fill in its values later is very memory-intensive. Additionally, I am unsure if the way I create the allCards matrix with rbind is the best way to do this.

• I notice you haven't accepted any of the answers to your four previous questions. If you have time, please consider doing so, as a thanks to their authors :-) – flodel Dec 6 '17 at 1:22

Here is how you can completely vectorize your code, making use of matrix functions such as crossprod, colSums, and %*%. Without for loops, your code will be more concise and faster to execute.

The construction of allCards was indeed a problem. Incrementally growing an object like you did is very memory intensive: each time you add a row, a new object is built from scratch. On the other hand, your comment that I've read that making a matrix of the correct size and filling it with NA only to fill in its values later is very memory-intensive is not accurate. Here the object is created once and filled in-place by the for loops.

To summarize: growing an object iteratively is the worst. Initializing an object to its final size and filling it in place via for loops is preferable. Using a vectorized function to create the object in one shot is the best. Hope it helps!

numberOfCards <- 9
numberOfEffects <- 3

allCards <- rbind(
c(1,2,1,1), # Murloc Raider
c(2,2,3,1), # River Crocolisk
c(2,3,2,1), # Bloodfen Raptor
c(3,5,1,1), # Magma Rager
c(4,2,7,1), # Oasis Snapjaw
c(4,4,5,1), # Chillwind Yeti
c(6,6,7,1), # Boulderfist Ogre
c(7,7,7,1), # War Golem
c(7,9,5,1)  # Core Hound
)

cardMana        <- allCards[, 1]
cardValueMatrix <- allCards[, -1]
coefficientsMatrix <- crossprod(cardValueMatrix)
constantsVector <- colSums(cardMana * cardValueMatrix)
effectValues <- solve(coefficientsMatrix, constantsVector, tol = 1e-9)
cat(effectValues, "\n\n")
cardValues <- cardValueMatrix %*% effectValues
cat(sprintf("Card %i: %.3f", seq(numberOfCards), cardValues), sep = "\n")

• Wow, I didn't know that R had this many builtins that would help me out. Thank you very much for making me aware of them. – Arcturus Dec 6 '17 at 3:25