HearthStone: the super-fun frontier for card game AI

Blizzard's latest title, Hearthstone: Heroes of Warcraft , is pretty entertaining. For the game theorist's out there, it's also a stochastic game with imperfect information of complexity similar to online poker---which means it should be (just barely) solveable.

Featuring ~10^26 possible decks, 10^32 possible shuffle orders, and a player strategy tree with a nontrivial number of choices available, Hearthstone's apparent complexity is immense and on the scale of Texas Hold Em. Despite the incredible amount of variability in the game, Hearthstone is similar to chess in that a 'points system' or objective function accurately measures how players are doing at every step through the game. Life points, the number of cards in a hand and remaining in a deck, and the strength of the creatures and spells that have been played give such a good sense of position in the game that professional streamer's speak with authority about a play's correctness and game advantage live while playing on camera and are seldom shown wrong.

Most of the difficulty of Hearthstone is in choosing the right combinations of creatures, weapons, and spells to include in your deck from the beginning, rather than solving the simpler, in-game tactical puzzles of whether to attack, what to play, etc. Understanding what goes into creating a great deck is of enormous interest to the game designers and community managers in charge of balancing the game. Cards are frequently subject to 'nerfs' and 'buffs' --- changes to features like the rarity, cost, and strength of cards, which are intended to affect the overall ecosystem to accomplish goals both noble (ensure game fairness, a fun degree of skill, include creative and interesting cards) and more corporate (raising revenue per player, player engagement, and growth in the player base). A champion deckbuilder system would allow game designers to easily simulate new changes to the card ecosystem before releasing them to the public, obviating the need for balance testing. Key metrics like the degree of skill for the game, variability in winrate, and include/exclude percentages on key cards across the top winning percentiles of decks would give a strong sense of what gameplay dynamics are at work across all levels of play.

The ease at which strategic decisions are made in Hearthstone begs the question --- if it's relatively simple to rig up an AI to play a predetermined deck well in Hearthstone, can we also create a champion computer deckbuilder, even one that can react to arbitrary changes to cards and rules?

The complexity of this problem is immense and represents a significant challenge to the current class of AI techniques out there. I don't have the solution but I do have a couple ideas below, including a recipe that should be enough for a naive gold farmer to exploit the game.

First, it's clear that some cards are strictly dominated by cheaper or stronger alternatives. The set of 'good cards' may be significantly smaller than the total card set, reducing the complexity of the analysis.

Second, the shuffle and gameplay introduce tremendous variance into game outcomes. Solving an abstract game may be the only thing that cuts down the model space. The 'cards face up' game would be interesting to explore for it's relationship to the full game with hidden information, as would a 'card strength bucketed' abstract game.

Last, standard A/B pruning techniques from chess AI may be quite excellent proxies for best play. As a result, it may be possible to cost-effectively simulate many games to completion from chosen decklists, allowing expected winrates to be generated from pairs of decks. It may be that a small number of decks tend to dominate the others, possibly suggesting a king of the hill-style genetic algorithm.

Of course no blog post on card game AI would be complete without citing the great work from the University of Alberta CPRG -- highly encourage the mathematically inclined to dig into their papers for great related exposition.