부산대학교 도서관

Summary: ``{\it Magic: The Gathering} is a popular and famouslycomplicated trading card game about magical combat. In this paper weshow that optimal play in real-world {\it Magic} is at least as hard asthe Halting Problem. This provides a positive answer to the question`is there a real-world game where perfect play is undecidable under therules in which it is typically played?', a question that has been openfor a decade $[1, 9]$. To do this, we present a methodology forembedding an arbitrary Turing machine into a game of {\it Magic} suchthat the first player is guaranteed to win the game if and only if theTuring machine halts. Our result applies to how real {\it Magic} isplayed, can be achieved using standard-size tournament-legal decks, anddoes not rely on stochasticity or hidden information. Our result isalso highly unusual in that all moves of both players are forced in theconstruction. This shows that even recognising who will win a game inwhich neither player has a non-trivial decision to make for the rest ofthe game is undecidable. We conclude with a discussion of theimplications for a unified computational theory of games and remarksabout the playability of such a board in a tournament setting.''