Mathematical programming and Magic: The Gathering®
MetadataShow full item record
In this paper mathematical programming techniques were used to determine the optimal strategy for playing Magic: The Gathering®. Games with the cards Lightning Bolt, Mountain, and Vexing Devil were evaluated using the minimax algorithm to determine the winner when all information about the cards is assumed known to both players. Computation time was shortened through the use of an evaluation function, a random forest algorithm that had been trained on 1000 completed games. A winning percentage was established for each pair of decks where the number of creatures was less than eight. Using linear programming, the optimal mixed strategy was then calculated. By repeating the simulations, a standard deviation for the winning percentages was estimated. Techniques from robust optimization were then used to determine the optimal strategy under different possible variations. Last, an imperfect information player was constructed that made choices based on guessing the order of the cards in its deck and the composition of the opponent's deck, playing through the perfect information games of these guesses, and making the choice that won in most of these simulations. With decks of eight or fewer creatures, this imperfect information player played below or near a player who used an aggressive heuristic. When the number of possible creatures was increased to 16, the imperfect information player's performance was better than the aggressive heuristic.