Designing Card Game Strategies with Genetic Programming and Monte-Carlo Tree Search: A Case Study of Hearthstone

This paper addresses an agent design problem of a digital collectible card game, Hearthstone, which is a two-player turn-based game. The agent has to play cards based on the game state, the hand cards, and the deck of cards to defeat the opponent. First, we design a rule-based agent by searching for the board evaluation criterion through genetic programming (GP). Then, we integrate the rule-based agent into the Monte-Carlo tree search (MCTS) framework to generate an advanced agent. Performance of the proposed agents are verified by playing against three participants in two recent Hearthstone competitions. Experimental results showed that the GP-agent can beat a simple MCTS agent and the mid-level agent in the competition. The MCTS-GP agent showed competitive performance against the best agents in the competition. We also examine the rule found by GP and observed that GP is able to identify key attributes of game states and to combine them into a useful rule automatically.