Ist „Magic: The Gathering“ das komplizierteste Spiel der Welt?

Magic: the Gathering ist rechnerisch komplex, nicht "kompliziert"

Zumindest ist es nicht in einer Weise "kompliziert", die von diesen Quellen quantifiziert wurde. Sie scheinen die Bedeutung zu verwirren, basierend auf einem schlampigen Verständnis einer wissenschaftlichen Arbeit.

„Computational Complexity“ ist ein mathematisches Konzept, und das in diesen Artikeln referenzierte Papier stellt fest, dass M:tG „Turing Complete“ ist, was wiederum ein mathematischer Begriff mit einer genauen Definition ist. Kurz gesagt, die Regeln von Magic können verwendet werden, um jedes Computerprogramm zu simulieren, wenn man genügend Zeit hat.

Das ist ein cleveres Ergebnis, sagt aber nicht viel darüber aus, ob das Spiel nach dem alltäglichen Verständnis des Wortes „kompliziert“ ist. Beispielsweise fand eine andere Zeitung aus dem Jahr 2007 einen ähnlichen Trick mit dem Spiel Minesweeper. Die meisten Leute würden zustimmen, dass Minesweeper weniger „kompliziert“ ist als Magic, aber laut diesen Papieren sind die beiden gleichermaßen „rechnerisch komplex“.

Es ist schwierig, etwas Negatives zu beweisen, es scheint keinen ernsthaften oder maßgeblichen Versuch zu geben, Spiele nach „Kompliziertheit“ zu klassifizieren. In jedem Fall beziehen sich die Ansprüche in der Frage nicht auf einen. Stattdessen verwechseln sie die Bedeutung eines mathematischen Begriffs, der in einer wissenschaftlichen Arbeit verwendet wird.

Die Autoren (Churchill et al.) stellen eine ziemlich starke Behauptung auf:

Vor dieser Arbeit waren keine unentscheidbaren realen Spiele bekannt.

Mit "echtem Spiel" meinen sie anscheinend ein Spiel, das mit den Regeln gespielt wird, die im wirklichen Leben verwendet werden, und nicht mit Modifikationen der Regeln. Dies könnte der Grund sein, warum Reporter auf die Idee kamen, dass Magic „das komplizierteste Spiel“ ist, also lohnt es sich, es genauer zu untersuchen.

Die Regeln der meisten Spiele schließen Turing-Vollständigkeit sofort aus, wie die Autoren selbst betonen:

Da die Komplexität der meisten Spiele begrenzt ist (z. B. die Größe eines Spielbretts), haben sich die meisten Forschungen zur algorithmischen Spieltheorie von Spielen in der realen Welt hauptsächlich mit Verallgemeinerungen häufig gespielter Spiele und nicht mit den Versionen der Spiele in der realen Welt befasst .

(Ich habe den Wikipedia-Link hinzugefügt.)

Turing-Vollständigkeit erfordert eine unbegrenzte Anzahl von Zuständen und eine unbegrenzte Anzahl von Zügen (Referenz: irgendein Informatiktext), daher schließt die Behauptung, dass Magic, wie es tatsächlich gespielt wird, Turing-vollständig ist, die Behauptung ein, dass es keine Begrenzung der Dauer, der Anzahl der Züge oder Größe (Anzahl der Spielsteine) eines Spiels in den realen Regeln. Wenn Sie zum Beispiel nur Karten und Spielsteine ​​verwenden dürfen, die vor Spielbeginn hergestellt wurden, dann ist die Anzahl der Spielsteine ​​begrenzt und das Spiel ist (in den Worten der Autoren) folglich „trivial entscheidbar“. Ich weiß nicht, ob Regeln dieser Art in Magic-Turnieren existieren, aber ich würde erwarten, dass sie es tun, entweder explizit oder als Folge anderer expliziter Regeln.

In der Zusammenfassung behaupten sie auch

dass selbst die Erkenntnis, wer ein Spiel gewinnen wird, in dem keiner der Spieler für den Rest des Spiels eine nicht triviale Entscheidung zu treffen hat, unentscheidbar ist.

Unentscheidbarkeit erfordert eine unendliche Menge von Probleminstanzen, daher gilt diese Behauptung nicht für Anfangszustände (Decks), da diese immer durch die Regeln in Größe und Inhalt begrenzt sind. Es gilt für Spiele, die vor einer unbegrenzten Anzahl von Zügen begonnen haben, in denen die Spieler bereits eine unbegrenzte Anzahl nicht trivialer Entscheidungen getroffen haben, da nur so eine unbegrenzte Anzahl verschiedener Zustände erzeugt werden kann. (Es gilt auch nur, wenn die Regeln die oben erwähnten Anforderungen der Turing-Vollständigkeit erfüllen.)

Sie stellen auch die folgende merkwürdige Behauptung auf:

[Führende formale Theorie strategischer Spiele behauptet, dass der unbegrenzte Speicher, der erforderlich ist, um eine Turing-Maschine vollständig in einem Spiel zu simulieren, eine Verletzung der eigentlichen Natur eines Spiels wäre [9].

Sie kommen später darauf zurück und scheinen zu glauben, dass sie gezeigt haben, dass bestehende Spielmodelle nicht ausreichen, um Magic zu beschreiben, was definitiv falsch ist. Referenz [9] ist "Constraint Logic: A Uniform Framework for Modeling Computation as Games" von Demaine und Hearn. Churchill et al beziehen sich möglicherweise auf den Abschnitt "Was ist ein Spiel?" wo Demaine und Hearn sagen

Ein wesentlicher Unterschied [zwischen Spielen und Turing-Maschinen] liegt in der Größe des Zustands: Turing-Maschinen haben unendliche Bänder, sodass der Zustand zu jeder Zeit unbegrenzt ist, während wir immer verlangen, dass der Zustand eines Spiels durch eine endliche Brettposition definiert wird . Wir können natürlich die Größe eines Turing-Maschinenbandes begrenzen oder ein Schaltungsmodell der Berechnung verwenden, aber solche Beschränkungen schränken die allgemeine Entscheidbarkeit des Berechnungsmodells ein. Im Gegensatz dazu zeigen wir, dass solche Einschränkungen für Spiele nicht existieren.

Mir ist unklar, was Demaine und Hearn hier zu sagen versuchen. Die Aussage, dass „der Zustand zu jeder Zeit unbegrenzt ist“, ist für bare Münze genommen falsch. Der Zustand einer Turing-Maschine ist zu jedem Zeitpunkt endlich (dh endlich beschreibbar), genauso wie die Spiele, die sie modellieren. Da sie sagen "es gibt keine solchen Einschränkungen für Spiele" und später Conway's Life (das seit langem als Turing-vollständig bekannt ist) als Beispiel für ein Spiel verwenden, scheint es klar, dass ihr Framework Spiele wie Unbounded Magic unterstützt - und sogar Wenn nicht, ist die Idee, solche Spiele mathematisch zu modellieren, nicht im Entferntesten neu.

Churchill et al sagen in ihrem Fazit sogar

Es scheint wahrscheinlich, dass ein Super-Turing- Modell von Spielen notwendig wäre, um Magic zu erklären .

(kursiv ihre). Wenn dies eine Behauptung ist, dass Magic gegen die Church-Turing_these verstoßen könnte – und ich sehe keine andere Möglichkeit, sie zu interpretieren – dann ist sie absurd und wird vom Rest des Preprints nicht unterstützt.

Die bisherige Antwort basiert auf dem arXiv-Preprint. Diese Arbeit wurde laut Bidermans Lebenslauf auch als Peer-Review-Konferenzpapier veröffentlicht . Der vollständige Tagungsband einschließlich dieses Papiers ist hier verfügbar . Die veröffentlichte Version scheint im Wesentlichen dieselbe zu sein, einschließlich sogar der extremeren Behauptungen aus dem Preprint, was mich dazu bringt, die Kompetenz der Rezensenten und Herausgeber in Frage zu stellen.

Ja, die Behauptung scheint in einem gewissen präzisen, technischen Sinne wahr zu sein, der auf Vorstellungen der theoretischen Informatik basiert. Dies kann der subjektiven menschlichen Erfahrung eines menschlichen Spielers entsprechen, der vergleicht, wie „kompliziert“ es für ihn ist, Magic: The Gathering im Vergleich zu einem anderen Spiel zu spielen.

1. Glaubwürdigkeit der Forschung.

Die Behauptung im Forbes-Artikel basiert auf einer wissenschaftlichen Arbeit („ Magic: The Gathering Is Turing Complete “, von Churchill, Biderman und Herrick). Es ist also sinnvoll, zuerst zu fragen, ob diese Forschung überhaupt richtig ist. Das Paper wurde in den Proceedings der 10th International Conference on Fun with Algorithms (FUN 2021), einer Informatikkonferenz, veröffentlicht. Es ist also von Experten begutachtet, zumindest nach den Standards einer Informatikkonferenz. Obwohl bekannt ist, dass Mathematik- und Informatikkonferenzen nicht ganz so streng mit ihrem Peer-Review-Verfahren sind wie akademische Zeitschriften (da sie einen engen Zeitplan haben), verleiht dies der Forschung eine gute Glaubwürdigkeit.

Darüber hinaus ist der technische Anspruch des Papiers durchaus plausibel. Ich habe die Details nicht gelesen, aber was es tut, ist den in der Literatur verwendeten Standardideen ziemlich ähnlich. Es gibt viele Artikel, die die Rechenkomplexität verschiedener Spiele diskutieren.

Basierend auf diesen beiden Faktoren würde ich davon ausgehen, dass das Ergebnis der Arbeit mit ziemlich hoher Wahrscheinlichkeit korrekt ist. Obwohl die Möglichkeit besteht, dass die Ergebnisse falsch sind – bei dieser Art der theoretischen Forschung passieren gelegentlich Fehler – scheinen die Chancen, dass dies hier der Fall ist, ziemlich gering.

2. Technischer Inhalt des Anspruchs.

Der technische Anspruch ist, dass Magic: The Gathering Turing-complete ist . Das bedeutet, grob gesagt, dass die Bestimmung des Ergebnisses eines Spiels in Anbetracht seines aktuellen Zustands und unter der Annahme, dass die Spieler optimal spielen, eine Frage ist, auf die die Antwort möglicherweise nicht nur sehr schwer zu finden, sondern sogar im Prinzip nicht erkennbar ist . In gewissem Sinne bedeutet das also, dass Magic nicht nur das komplexeste bekannte Spiel ist, sondern auch das komplexeste Spiel, das es geben kann. Das heißt, seine Komplexität kann von einigen anderen Spielen erreicht werden, kann aber nicht übertroffen werden.

Die Autoren der Arbeit zeigen dies, indem sie zeigen, dass man zur Beantwortung der Frage nach dem Ausgang des Spiels in der Lage sein muss, eine andere Frage zu beantworten („Hält eine bestimmte Turing-Maschine jemals an?“), für die das bereits bekannt ist die Antwort ist möglicherweise nicht erkennbar (in der Fachsprache ist das Halteproblem unentscheidbar ). Diese Art der Argumentation ist in der Theoretischen Informatik Standard, wobei die konkrete Durchführung von Fall zu Fall unterschiedlich ist.

3. Zusammenfassung.

Artikel in den Medien, die versuchen, akademische Forschung der Öffentlichkeit „zugänglich“ zu machen, leisten normalerweise keine gute Arbeit darin, genau das zu vermitteln, was die Forschung behauptet; oft versuchen sie sogar bewusst, die Ergebnisse zu sensationslüstern zu machen und sie so spannend (und, ich wage es zu sagen, Click-Baity) wie möglich klingen zu lassen, was zwangsläufig mit einem weiteren Verlust an Präzision und Nuancen einhergeht. Der hier zitierte Forbes-Artikel ist da keine Ausnahme, also ist eine gesunde Skepsis durchaus angebracht. Bemerkenswerterweise haben die ursprünglichen Autoren der Studie nicht behauptet, dass „Magie das komplizierteste Spiel ist“, sondern eine präzise technische Behauptung aufgestellt.

Vor diesem Hintergrund ist es nicht unangemessen, ihre Behauptung so zu interpretieren, dass Magic im theoretischen Sinne so kompliziert ist, wie es sich ein Spiel nur erhoffen kann.