Magic: The Gathering ist das komplexeste Spiel der Welt
Vor sieben Jahren stellte Alex Churchill seine Theorie über die Turing-Vollständigkeit von Magic The Gathering ins Netz. Turing-vollständig sind Systeme, wenn sie anderen Systeme simulieren können. Ein Computer kann alle möglichen Systeme simulieren und ist turingvollständig, andere Systeme die das können sind zum Beispiel Programmiersprachen (in denen ich alle möglichen anderen Systeme beschreiben kann), und schließlich gibt es noch accidental Turing Completeness wie den Pokémon Yellow Exploit oder sowas wie Excel.
Nun hat er seine Forschung in ein Paper geschrieben, in dem er den Nachweis für die Turing-Vollständigkeit von Magic The Gathering und die Nicht-Ausrechenbarkeit seiner Spielzüge, was das Game zum komplexesten Real-Life-Game der Spieltheorie macht.
Paper: Magic: The Gathering is Turing Complete
Technology Review: “Magic: The Gathering” is officially the world’s most complex game (Mirror)
We have presented a methodology for embedding Rogozhin’s (2, 18) universal Turing machine in a two-player game of Magic: The Gathering. Consequently, we have shown that identifying the outcome of a game of Magic in which all moves are forced for the rest of the game is undecidable. In addition to solving a decade-old outstanding open problem, in the process of arriving at our result we showed that Magic: The Gathering does not fit assumptions commonly made by computer scientists while modelling games. We conjecture that optimal play in Magic is far harder than this result alone implies, and leave the true complexity of Magic and the reconciliation of Magic with existing theories of games for future research.
