Wer im September 2018 in Las Vegas war, konnte sich leicht in die beliebte Fernsehserie »The Big Bang Theory« versetzt fühlen: In einem Raum bekämpften sich 24 erwachsene Männer mit bunten Fantasy-Spielkarten, auf denen magische Kreaturen und Zaubersprüche abgebildet sind. Tatsächlich handelte es sich um die jährlich stattfindende »Magic: The Gathering«-Weltmeisterschaft, bei der die Spieler um Preisgelder von insgesamt 300 000 Dollar wetteifern.

Mittlerweile hat das Kartenspiel auch in wissenschaftlicher Hinsicht viele Menschen in seinen Bann gezogen, denn es scheint jahrzehntealte Überzeugungen von Spieltheoretikern über den Haufen zu werfen: Offenbar ist Magic mit seinen vielen Karten, komplizierten Regeln und ausgeklügelten Strategien für Computer eine größere Herausforderung als Informatiker für möglich gehalten haben.

Das Hauptinteresse von algorithmischen Spieltheoretikern ist, Gewinnstrategien für laufende Spiele zu berechnen. Je schwerer es einem Computer fällt, den Ausgang einer Partie vorherzusagen, desto komplexer stufen Informatiker ein Spiel ein. Magic scheint hier im Vergleich mit anderen Spielen auf besondere Weise herauszustechen: Wie der unabhängige Forscher Alex Churchill aus Cambridge in Großbritannien nun mit Stella Biderman vom Georgia Institute of Technology in Atlanta und Austin Herrick von der University of Pennsylvania in Philadelphia in einer auf dem Preprint-Dokumentenserver ArXiv veröffentlichten Arbeit festgestellt hat, lässt sich der Ausgang eines Magic-Duells nicht immer vorhersagen – damit handelt es sich um das komplexeste aller bisher bekannten Spiele.

Um zwischen verschiedenen Schwierigkeitsstufen zu unterscheiden, teilen theoretische Informatiker Probleme in so genannte Komplexitätsklassen ein. Dabei ist entscheidend, wie lange ein Computer braucht – wenn er es überhaupt schafft –, um eine Aufgabe zu lösen. Möchte man beispielsweise eine Zahl in ihre Primfaktoren zerlegen, wächst die dafür benötigte Rechendauer exponentiell mit ihrer Größe an. Die gegenteilige Operation, also das Multiplizieren zweier Primfaktoren, gestaltet sich dagegen wesentlich einfacher: Hier wächst die Rechendauer nach neuesten Untersuchungen bloß mit n log(n) an, wobei n die Länge beider Faktoren ist.

Für extrem große Zahlen gibt es daher keine effiziente Möglichkeit, sie in ihre Primfaktoren zu zerlegen, während es sehr einfach ist, das Ergebnis zu überprüfen. Solche Probleme sind in der Informatik als NP-Probleme bekannt.

Mit dem Schema lässt sich auch die Komplexität eines Spiels bewerten. Zum Beispiel kann ein Computer während einer kurz vor dem Ende stehenden Partie Schach berechnen, ob und wie die Farbe Weiß noch gewinnen kann. Dazu muss er bloß alle möglichen Spielzüge durchgehen. Das klingt zwar ziemlich aufwändig, allerdings führt das begrenzte Spielbrett dazu, dass ein Rechner diese Aufgabe in kurzer Zeit bewältigen kann. Weil die meisten echten Spiele (das heißt solche, die Menschen tatsächlich spielen und nicht bloß künstlich konstruiert wurden) nicht wirklich komplex sind, interessierten sich Informatiker kaum für sie. Tatsächlich gingen Experten bisher davon aus, dass es kein echtes Spiel gibt, dessen Komplexität die Klasse NP erreicht.

Überraschung für Spieltheoretiker

Wie Churchill und seine zwei Kollegen nun gezeigt haben wollen, ist das bei Magic aber der Fall. Sie vermuten sogar, dass das Sammelkartenspiel noch komplexer sein könnte. Um zu diesen Schlüssen zu kommen, bedienten sich die Forscher eines gängigen Konzepts der theoretischen Informatik: einer so genannten Turingmaschine. Dieses 1936 vom britischen Wissenschaftler Alan Turing eingeführte Rechnermodell simuliert die Arbeitsweise klassischer Computer.

Es besteht aus einem Band, das in einzelne Felder unterteilt ist, und einem Kopf, der die Felder ausliest und gegebenenfalls beschreibt. Die Maschine kann das Band nach links oder rechts bewegen, um zu den gewünschten Feldern zu gelangen. Sie repräsentiert damit das, was Mathematiker eine Funktion nennen: Sie wandelt Zahlen nach einer bestimmten, eindeutigen Vorschrift in andere Zahlen um. Ein typischer Ausschnitt eines Programms für eine Turingmaschine lautet beispielsweise: »Wenn die Maschine im Zustand 3 ist und das Feld die Zahl 0 enthält, dann überschreibe sie mit einer 1, gehe in Zustand 5 über und rücke 4 Felder nach rechts.«

Ein Klassiker bei der Auseinandersetzung mit Turingmaschinen ist die Frage, ob eine Maschine bei der Berechnung eines Problems jemals zum Ende gelangt oder endlos weiterläuft, Informatiker sprechen vom Halteproblem. Bereits 1936 hatte Turing gezeigt, dass es keine Möglichkeit gibt, diese Frage allgemein für alle möglichen Algorithmen zu beantworten.

Churchill und seinem Team gelang es jetzt zu beweisen, dass die Frage nach dem Spielausgang eines Magic-Duells dem Halteproblem entspricht: Das bedeutet, dass es Spielsituationen gibt, in denen ein Computer nicht berechnen kann, wer gewinnen wird.

Die Wissenschaftler gelangten zu dem überraschenden Ergebnis, indem sie zeigten, dass Magic: The Gathering die gleichen Funktionen besitzt wie eine Turingmaschine, also »Turing-vollständig« ist, wie Experten sagen. Anders ausgedrückt: Man kann mit Magic eine Turingmaschine simulieren und umgekehrt.

Dazu konstruierten Churchill, Biderman und Herrick eine spezielle Ausgangssituation zwischen zwei Magic-Spielern und identifizierten die möglichen Spielzüge mit den wesentlichen Funktionen einer Turingmaschine: das Auslesen, Beschreiben und Bewegen des Bands. Dadurch besitzt das Spiel sämtliche Eigenschaften des theoretischen Rechnermodells und kann mit den Mitteln der theoretischen Informatik untersucht werden.

Ein Spiel als Computer

Die passende Spielsituation bei Magic: The Gathering auszuwählen, gestaltete sich jedoch schwierig. Denn sie musste einerseits genügend komplizierte Elemente des Spiels enthalten, um eine Turingmaschine zu simulieren, andererseits sollte sie dabei aber simpel genug bleiben, damit man die möglichen Spielzüge noch überblickt. Immerhin gibt es mehr als 20 000 verschiedene Magic-Karten, die jeweils unterschiedliche Funktionen haben. Zudem enthalten einige von ihnen freiwillige Aktionen, die dem Spieler strategischen Freiraum lassen, was sich nur schwer simulieren lässt. Churchill und seine Kollegen bezogen deshalb nur Karten mit ein, die einen eindeutigen Effekt haben. In ihrer kreierten Spielsituation – die durchaus in einem realistischen Turnier entstehen kann – gibt es daher nur noch erzwungene Spielzüge; die Spieler haben keinerlei Entscheidungsfreiheit.

Vor dem Beginn eines Magic-Spiels wählt ein Spieler aus seiner Sammlung 60 Karten aus – diese Auswahl aus dem riesigen Fundus der verfügbaren Karten und die damit einhergehenden Kombinationsmöglichkeiten führen zu der außergewöhnlichen Komplexität des Spiels. Hat der Spieler eine Auswahl getroffen, mischt er seine Karten sorgfältig und nimmt anschließend sieben davon auf die Hand. Die übrigen bilden seinen Nachziehstapel.

Unter den Karten befinden sich Kreaturen, die den Gegner angreifen, oder auch Zauber und Artefakte. Zu Beginn jeder Runde zieht man eine Karte. Sobald ein Spieler eine Karte von einem leeren Nachziehstapel aufnehmen soll, hat dieser verloren. Ansonsten besiegt man seinen Gegenüber, indem man seine Lebenspunkte durch gezielte Attacken auf null oder niedriger reduziert.

In dem von Churchill und seinen Kollegen konstruierten Spiel treten Alice und Bob gegeneinander an. Bob ist in der Situation, dass er weder Karten auf der Hand hat und sein Nachziehstapel leer ist – er steht also kurz vor der Niederlage. Dafür kontrolliert er alle Kreaturen, die auf dem Tisch liegen. Alice kann daher nur versuchen, Bobs Kreaturen mit den Karten aus ihrem Stapel anzugreifen.

Diese Ausgangssituation erlaubt es den Forschern, das Spiel mit einer Turingmaschine zu identifizieren. Die Kreaturen auf dem Tisch entsprechen in diesem Modell dem Band: Auf jedem Feld befindet sich eine Kreatur, mit ihrem Stärke- und Widerstandswert, die jeweils angeben, wie viel Schaden sie anrichtet und was sie einstecken kann. Zudem verfügen gibt es bei Magic fünf verschiedene »magischen« Farben, die eine Karte charakterisieren. In dem von Churchill und seinen Kollegen erdachten Spiel tauchen weiße oder grüne Kreaturen mit jeweils gleichen Stärke- und Widerstandswerten (zum Beispiel 2/2 oder 3/3) auf.

Das Band ist im Anfangszustand so angeordnet, dass der Lesekopf auf der schwächsten Kreatur (2/2) ruht; rechts davon befinden sich der Stärke nach alle weißen Kreaturen und analog dazu links alle grünen. Eine weiße Kreatur mit den Werten 5/5 steht demnach auf dem dritten Feld rechts vom Kopf. Die Art der Kreatur ist durch ein Symbol auf dem Feld vermerkt.

Die verschiedenen Funktionen der Turingmaschine werden durch das Spielen von Alices Karten initiiert: Um das Band nach rechts oder links zu bewegen, muss Alice eine Karte legen, die allen Kreaturen einer bestimmten Farbe Schaden zufügen. Doch was, wenn dabei eine Kreatur stirbt? Churchill und seine Kollegen haben für diesen Fall vorgesorgt: Eine von Bobs Karten ist der »Moderlungen-Wiederbeleber«, der eine tote Kreatur durch eine neue der gleichen Stärke ersetzt. Damit ist auch geklärt, wie der Kopf der Turingmaschine ein Feld ausliest und neu beschreibt: nämlich indem Alice eine Kreatur tötet und Bob sie daraufhin wiederbelebt.

Entscheidend für den gesamten Vorgang ist die Karte »Künstliche Entwicklung«, die es einem Spieler erlaubt, die Aktionen anderer Karten abzuändern. Während der Moderlungen-Wiederbeleber beispielsweise bloß Kleriker als Zombies wiederauferstehen lässt, kann man mit der Künstlichen Entwicklung den Zombie durch eine beliebige andere Kreatur austauschen. Genau diese Fähigkeit zeichnet Churchill zufolge Magic: The Gathering aus: »Damit ein Spiel die gleiche Komplexität wie Magic aufweist, muss ein Spieler es während einer Partie kontrollieren oder programmieren können, so wie es durch die Künstliche Entwicklung möglich ist«, teilt er mit.

Mit dieser Kartenauswahl hat das Spiel zwischen Alice und Bob alle Fähigkeiten einer Turingmaschine. »Wählt man sein liebstes Matheproblem aus, kann man durch geeignete Wahl der Karten eine Magic-Spielsituation kreieren, die dieses Problem berechnet«, erklärt Stella Biderman, Koautorin der Arbeit. Das ist allerdings sehr aufwändig: Zuerst muss man die Aufgabe in die Sprache einer Turingmaschine übersetzen, was schon ziemlich kompliziert ist, und danach die richtige Auswahl und Anordnung der Magic-Karten finden, die dem Problem entspricht. Hat man jedoch die richtige Ausgangssituation gefunden, muss man Alice und Bob nur noch loslegen lassen; ihre erzwungenen Spielzüge entsprechen dann den einzelnen Berechnungsschritten. Sobald das Spiel zwischen ihnen beendet ist, lässt sich die Lösung der Aufgabe auslesen.

Churchill und sein Team haben das Spiel so konstruiert, dass Bob gar nicht gewinnen kann. Daher hält die Turingmaschine erst an, wenn Alice gewinnt, ansonsten läuft sie ewig weiter. In echten Magic-Spielen können solche Situationen tatsächlich entstehen. Es gibt sogar eine Regel, wonach im Fall von sich immer wieder wiederholenden Zügen eine Partie unentschieden ausgeht.

Insgesamt können im Spiel zwischen Alice und Bob also drei Situationen eintreten: Die Karten entsprechen einem Problem, das eine Turingmaschine lösen kann, etwa der Aufgabe »2 + 2« zu berechnen. In so einem Fall wird Alice das Spiel gewinnen. Andererseits könnte das Spiel ein unlösbares Problem darstellen, wie »berechne die natürliche Zahl x, für die x² = 2 ergibt«. Da eine solche Zahl nicht existiert, wird die Turingmaschine ewig weiterlaufen; das Spiel geht also unentschieden aus. Es gibt aber auch noch eine dritte Möglichkeit: Die Karten könnten für etwas stehen, von dem man nicht weiß, ob es lösbar ist oder nicht. Ein Beispiel dafür wäre »Berechne ein Paar Primzahlzwillinge (also zwei Primzahlen mit einer Differenz von 2), die größer sind als 10^500 000«. Weil Mathematiker bisher nicht wissen, ob es Primzahlzwillinge dieser Größe gibt, ist es auch ungewiss, ob die Turingmaschine jemals halten wird.

Wenn ein Computer also den Spielausgang zwischen Alice und Bob vorhersagen soll, muss er das Halteproblem für Turingmaschinen lösen. Für viele Situationen, wie in den ersten beiden zuvor genannten Beispielen, ist das kein Problem. Doch es gibt auch Spiele, in denen der Ausgang unklar ist, wie im letzten Fall. Insgesamt kann daher kein Algorithmus für jedes beliebige Duell vorhersagen, wie, ob und wann das Spiel zwischen Alice und Bob endet – und das, obwohl jeder Zug der beiden Spieler erzwungen ist. Der Ausgang einer Partie hängt also nur davon ab, welche Kreaturen Bob anfangs beherrscht und in welcher Reihenfolge Alice ihre Karten zieht.

Die Forscher konnten zeigen, dass ihre erdachte Spielsituation tatsächlich in einem realistischen Duell auftreten kann – und nicht bloß ein künstliches Konstrukt ist. Zudem gehen sie davon aus, dass auch andere Spielsituationen in ähnliche Sackgassen führen können. Daher erreiche das Spiel mindestens die Komplexitätsstufe NP, schreiben die Autoren. Um zu prüfen, ob es vielleicht sogar noch komplexer ist, muss man allerdings eine andere Herangehensweise wählen.

Dennoch bleibt das Ergebnis aus spieltheoretischer Sicht erstaunlich, auch wenn es Magic-Spieler vielleicht weniger überraschen mag: Schon lange rühmen sich einige von ihnen damit, dass sie ein extrem kompliziertes Spiel beherrschen. Nun können sie auch offiziell von sich behaupten, das komplexeste Spiel der Welt zu spielen.