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.

Neu auf Nerdcore:

Nerdcore auf Twitter

The Lumineers’ neues Album als Kurzfilm in zehn Musikvideos

Buch-Cover alter SciFi-Klassiker: The Illustrated Man, Metropolis, I Robot, Bodysnatchers, A Scanner Darkly

Evoboxx: Game of Life-Synthesizer

[Klimalinks 21.9.2019] Global Climate Strike; Klimapaket der Bundesregierung: Too little, too late; Google/Amazons Klima-Pläne

Musikvideos_Anyway Gang Planet B Comet Gain Rosegarden Funeral Party Vivian Girls Lou Rebecca Chromatics The New Pornographers M83 James Massiah Okay Kaya