โMagic: the Gathering Is As Hard As Arithmeticโ, 2020-03-11 (; backlinks; similar)โ :
Magic: the Gathering is a popular and famously complicated card game about magical combat. Recently, several authors including Chatterjee and Ibsen-2016 and et al 2019 have investigated the computational complexity of playing Magic optimally.
In this paper we show that the โmate-in-nโ problem for Magic is ฮn0-hard and that optimal play in two-player Magic is non-arithmetic in general. These results apply to how real Magic is played, can be achieved using standard-size tournament legal decks, and do not rely on stochasticity or hidden information.
Our paper builds upon the construction that Churchill, Biderman, and 2019 used to show that this problem was at least as hard as the halting problem.