Magic: The Gathering ist offiziell das komplexeste Spiel der Welt

Ein Bild von Spielkartenpaketen aus Magic: The Gathering

Ein Bild von Spielkartenpaketen aus Magic: The GatheringNathan Rupert



Magic: The Gathering ist ein Kartenspiel, in dem Zauberer Zaubersprüche wirken, Kreaturen beschwören und magische Objekte ausnutzen, um ihre Gegner zu besiegen.

Im Spiel stellen zwei oder mehr Spieler jeweils ein Deck aus 60 Karten mit unterschiedlichen Kräften zusammen. Sie wählen diese Decks aus einem Pool von rund 20.000 Karten aus, die im Laufe der Entwicklung des Spiels erstellt wurden. Obwohl es Fantasy-Rollenspielen wie Dungeons and Dragons ähnlich ist, hat es deutlich mehr Karten und komplexere Regeln als andere Kartenspiele.





Und das wirft eine interessante Frage auf: Wo fällt Magic in Bezug auf die Komplexität unter realen Spielen (denjenigen, die Menschen tatsächlich spielen, im Gegensatz zu den hypothetischen Spielen, die Spieltheoretiker normalerweise in Betracht ziehen)?

Heute erhalten wir dank der Arbeit von Alex Churchill, einem unabhängigen Forscher und Brettspieldesigner in Cambridge, Großbritannien, eine Antwort; Stella Biderman am Georgia Institute of Technology; und Austin Herrick an der University of Pennsylvania.

Sein Team hat die Rechenkomplexität des Spiels zum ersten Mal gemessen, indem es es so codiert hat, dass es von einem Computer oder einer Turing-Maschine gespielt werden kann. Diese Konstruktion stellt das fest Magic the Gathering ist das rechnerisch komplexeste reale Spiel, das in der Literatur bekannt ist, sagen sie.



Zunächst etwas Hintergrund. Eine wichtige Aufgabe in der Informatik ist es festzustellen, ob ein Problem prinzipiell lösbar ist. Beispielsweise ist die Entscheidung, ob zwei Zahlen teilerfremd sind (mit anderen Worten, ob ihr größter gemeinsamer Teiler größer als 1 ist), eine Aufgabe, die in einer endlichen Anzahl wohldefinierter Schritte erledigt werden kann und daher berechenbar ist.

In einem gewöhnlichen Schachspiel ist die Entscheidung, ob Weiß eine Gewinnstrategie hat, ebenfalls berechenbar. Der Prozess beinhaltet das Testen jeder möglichen Zugfolge, um zu sehen, ob Weiß einen Gewinn erzwingen kann.

Aber während diese beiden Probleme berechenbar sind, sind die Ressourcen, die zu ihrer Lösung erforderlich sind, sehr unterschiedlich.

kostenlose Quanten-Machine-Learning-Software

Hier kommt der Begriff der Rechenkomplexität ins Spiel. Dies ist ein Ranking, das auf den Ressourcen basiert, die zur Lösung der Probleme erforderlich sind.



In diesem Fall kann die Entscheidung, ob zwei Zahlen teilerfremd sind, in einer Anzahl von Schritten gelöst werden, die proportional zu einer Polynomfunktion der Eingabezahlen ist. Wenn die Eingabe ist x , der wichtigste Term in einer Polynomfunktion ist von der Form Cxn , wo C und n sind Konstanten. Dies fällt in eine Klasse, die als P bekannt ist , wobei P für Polynomzeit steht.

Im Gegensatz dazu muss das Schachproblem mit roher Gewalt gelöst werden, und die Anzahl der Schritte, die dazu erforderlich sind, steigt proportional zu einer Exponentialfunktion der Eingabe. Wenn die Eingabe ist x , ist der wichtigste Term in einer Exponentialfunktion von der Form Cnx , wo C und n sind Konstanten. Und wie x steigt, wird dies viel schneller als größer Cxn . Dies fällt also in eine Kategorie größerer Komplexität namens EXP oder exponentielle Zeit.

Darüber hinaus gibt es verschiedene andere Kategorien unterschiedlicher Komplexität und sogar Probleme, für die es keine Algorithmen gibt, um sie zu lösen. Diese werden als nicht berechenbar bezeichnet.

Herauszufinden, in welche Komplexitätsklasse Spiele fallen, ist eine knifflige Angelegenheit. Die meisten realen Spiele haben begrenzte Grenzen hinsichtlich ihrer Komplexität, wie z. B. der Größe eines Spielbretts. Und das macht viele von ihnen unter dem Gesichtspunkt der Komplexität trivial. Die meisten Forschungen in der algorithmischen Spieltheorie von realen Spielen haben sich in erster Linie mit Verallgemeinerungen häufig gespielter Spiele und nicht mit realen Versionen der Spiele befasst, sagen Churchill und Co.

Es ist also bekannt, dass nur wenige reale Spiele eine nicht triviale Komplexität aufweisen. Dazu gehören Dots-and-Boxes, Jenga und Tetris. Wir glauben, dass vor dieser Arbeit kein reales Spiel bekanntermaßen schwieriger als NP war, sagen Churchill und Co.

Das neue Werk zeigt, dass Magic: the Gathering deutlich komplexer ist. Die Methode ist im Prinzip einfach. Churchill und Co beginnen damit, die Kräfte und Eigenschaften jeder Karte in eine Reihe von Schritten zu übersetzen, die codiert werden können.

Sie spielen dann ein Spiel zwischen zwei Spielern, bei dem sich das Spiel in einer Turing-Maschine entfaltet. Und schließlich zeigen sie, dass die Feststellung, ob ein Spieler eine Gewinnstrategie hat, dem berühmten Halteproblem in der Informatik entspricht.

Dies ist das Problem der Entscheidung, ob ein Computerprogramm mit einer bestimmten Eingabe beendet oder für immer fortgesetzt wird. 1936 bewies Alan Turing, dass kein Algorithmus die Antwort bestimmen kann. Mit anderen Worten, das Problem ist nicht berechenbar.

Das wichtigste Ergebnis von Churchill und Co. ist also, dass die Bestimmung des Ergebnisses einer Magic-Partie nicht berechenbar ist. Dies ist das erste Ergebnis, das zeigt, dass es ein reales Spiel gibt, für das die Bestimmung der Gewinnstrategie nicht berechenbar ist, sagen sie.

Das ist eine interessante Arbeit, die wichtige grundlegende Fragen für die Spieltheorie aufwirft. Zum Beispiel sagen Churchill und Co, dass die führende formale Theorie der Spiele davon ausgeht, dass jedes Spiel berechenbar sein muss. Magic the Gathering passen nicht zu den Annahmen, die üblicherweise von Informatikern bei der Modellierung von Spielen gemacht werden, sagen sie.

Das deutet darauf hin, dass Informatiker ihre Vorstellungen von Spielen überdenken müssen, insbesondere wenn sie hoffen, eine einheitliche computergestützte Theorie von Spielen zu erstellen. In dieser Hinsicht ist Magic eindeutig ein Haar in der verzauberten Suppe.

Ref: arxiv.org/abs/1904.09828 : Magic: The Gathering is Turing abgeschlossen

verbergen

Tatsächliche Technologien

Kategorie

Unkategorisiert

Technologie

Biotechnologie

Technologierichtlinie

Klimawandel

Mensch Und Technik

Silicon Valley

Computer

Mit News Magazine

Künstliche Intelligenz

Platz

Intelligente Städte

Blockchain

Reportage

Alumni-Profil

Alumni-Verbindung

Mit News Feature

1865

Meine Sicht

77 Mass Avenue

Treffen Sie Den Autor

Profile In Großzügigkeit

Auf Dem Campus Gesehen

Alumni-Briefe

Nachrichten

Wahl 2020

Mit Index

Unter Der Kuppel

Feuerwehrschlauch

Unendliche Geschichten

Pandemie-Technologieprojekt

Vom Präsidenten

Titelstory

Fotogallerie

Empfohlen