萬智牌（Magic: The Gathering）是一種非常流行卡牌對戰遊戲，由Richard Channing Garfield設計，威世智公司（Wizards of the Coast）出品。英國和美國的三名研究人員發表論文（PDF），認為萬智牌是圖靈完全的，它的最優玩法至少和停機問題一樣困難。

他們從算法博弈論角度評估誰將贏得比賽的計算複雜性。他們提出了一種方法，將通用圖靈機嵌入到萬智牌遊戲中，結果顯示存在一種真實世界的遊戲，判斷必勝策略是不可計算的。