Wenn ein Spiel einfache Regeln hat, muß es deswegen noch lange nicht einfach zu spielen sein. Manchmal gibt es zwar eine einfache Gewinnstrategie – Ticktacktoe ist ein gutes Beispiel –, manchmal aber auch nicht. Ein schwieriges Spiel in diesem Sinne ist zum Beispiel „Käsekästchen“: Zwei Spieler ziehen abwechselnd waagerechte und senkrechte Linien in einem quadratischen Punktegitter und versuchen, möglichst viele vollständig umrandete Quadrate für sich einzuheimsen. Die Spiele mit einer bekannten Gewinnstrategie will ich „Traumspiele“ nennen, die anderen „Alptraumspiele“. Mitunter macht eine kleine Änderung der Regeln aus einem Traum- ein Alptraumspiel. Letztere sind meist interessanter, weil man nicht von vornherein weiß, wer eigentlich gewinnen müßte. Und bei manchen Alptraumspielen weiß man zwar, welcher der beiden Spieler gewinnen sollte, aber nicht wie.

Schauen wir uns zwei einfache Spiele näher an, die mit Schokoladentafeln gespielt werden: das Ritterspiel (Yucky Chocolate) und das Eckbrecherspiel (Chomp). Das erste ist ein Traumspiel, das zweite trotz sehr ähnlicher Regeln ein Alptraumspiel: Bei optimalem Spiel sollte der Anziehende gewinnen, aber niemand weiß wie.

Ich weiß nicht, wer das Ritterspiel erfunden hat. Erklärt hat es mir Keith Austin, ein Mathematiker von der Universität Sheffield (England). Gespielt wird mit einer idealisierten Schokoladentafel: einem in kleine Quadrate eingeteilten Rechteck. Zwei Spieler, nennen wir sie Eins und Zwei nach der Reihenfolge, in der sie ziehen, brechen abwechselnd Stücke von der Tafel ab und essen sie auf. Jede Bruchlinie muß entlang einer der vorgegebenen Kerben laufen und ganz durchgehen. Wer das Eckstück links oben essen muß, hat verloren; denn das ist aus Seife.

Die roten Pfeile im Diagramm unten zeigen die Züge in einem denkbaren Spiel auf einer 4x4-Schokoladentafel. In diesem Spiel unterläuft Zwei bei seinem ersten Zug ein böser Fehler; dadurch vergibt er seine sichere Gewinnchance.

Das Ritterspiel ist ein typischer Fall eines endlichen Spiels, das heißt, es kann nicht beliebig lange andauern, und es gibt kein Unentschieden. Eine Gewinnstrategie ist eine Folge von Zügen, die stets zum Sieg führt, einerlei was der Gegner tut. Die Theorie der endlichen Spiele beruht auf zwei Prinzipien: Eine Stellung ist eine Gewinnstellung, wenn man darin einen Zug ausführen kann, der den Gegner in eine Verluststellung bringt. Und eine Stellung ist eine Verluststellung, wenn jeder mögliche Zug den Gegner in eine Gewinnstellung bringt. Das klingt albern: Der Begriff „Gewinnstellung“ wird über „Verluststellung“ definiert – und umgekehrt. Aber die Logik dreht sich trotzdem nicht im Kreise, jedenfalls nicht unbegrenzt. Es gibt nämlich eine Stellung, die von vornherein als Verluststellung bekannt ist: das Stück Seife ohne Schokolade daran.

Man findet nun eine Gewinnstrategie für das 4x4-Ritterspiel, indem man sich von dieser Endstellung rückwärts nach vorne arbeitet. Wenn ein Spieler irgendwann ein Schokoladenrechteck vorfindet, das aus dem oberen linken Eckfeld und einem oder mehreren weiteren Quadraten der oberen Reihe besteht, dann befindet er sich in einer Gewinnstellung; denn er kann die süßen Quadrate abbrechen und seinem Gegner die Seife übriglassen. Ebenso sind die Stellungen, die aus dem oberen linken Eckquadrat und einem oder mehreren Quadraten in der ersten Spalte bestehen, Gewinnstellungen. In dem abgebildeten Spielbaum führt von jeder solchen Stellung ein Pfeil direkt zur Endstellung.

Wie steht es mit einer quadratischen Tafel der Seitenlänge 2, mit der Seife in der linken oberen Ecke? Wie der Spielbaum zeigt, ist

das eine Verluststellung, weil alle möglichen Züge dem Gegner eine Gewinnstellung verschaffen. Daraus folgt wiederum, daß alle Stellungen, von denen aus es einen direkten Zug in diese Quadratstellung gibt, Gewinnstellungen sind. Wenn wir uns auf diese Weise rückwärts hangeln, entdecken wir bald ein Muster: Die Stellungen mit quadratischen Schokoladentafeln sind offenbar Verluststellungen, alle anderen sind Gewinnstellungen. In diesem Falle ist also quadratisch praktisch schlecht, denn von jedem nichtquadratischen Stück kann man etwas abbrechen und aufessen, so daß ein quadratischer Rest übrig bleibt. Und wenn man in einem quadratischen Stück einen Zug macht, bleibt dem Gegner unweigerlich ein nichtquadratisches Stück.

Wenn also beim 4x4-Ritterspiel beide Kontrahenten keine Fehler machen, wird Eins stets verlieren. Zwei gewinnt, indem er seinem Gegner stets eine quadratische Tafel hinterläßt. (In dem abgebildeten Beispiel hat Zwei verloren, weil er diese Regel nicht befolgt hat.) Aber wenn das Spiel mit einer Tafel der Größe 4x5, 3x5 oder irgendeiner Größe mit ungleichen Seitenlängen beginnt, sollte stets der anziehende Spieler gewinnen. Das Ritterspiel ist ein Traumspiel, einerlei wie groß die Tafel anfänglich ist.

Was macht also der Unglückliche, der eine quadratische Tafel vor sich hat? Er ißt sie auf der Stelle auf. Denn wenn ihm die Seife ohnehin nicht erspart bleibt, kann er sie sich auf diese Weise wenigstens optimal versüßen. Und ob ihm hinterher von der Seife schlecht ist oder vom Übermaß an Schokolade – was macht das schon für einen Unterschied?

Entscheidungsbäume

Im Prinzip läßt sich nach dem beschriebenen Verfahren für jedes endliche Spiel eine Gewinnstrategie bestimmen. Die Wurzel des Spielbaumes ist die Anfangsstellung, und die Blätter sind die Endstellungen. (Anders als bei echten Bäumen können hier mehrere Zweige in demselben Blatt enden; aber das tut der Theorie keinen Abbruch.) Da wir wissen, welche Endstellungen gewinnen und welche verlieren, können wir uns die Äste des Spielbaumes entlang rückwärts hangeln und zu jeder Stellung bestimmen, ob sie eine Gewinn- oder eine Verluststellung ist. Da der Spielbaum endlich ist, erreichen wir so irgendwann die Wurzel, also die Anfangsstellung. Wenn diese eine Gewinnstellung ist, kann Eins gewinnen, indem er seinem Gegner stets Verluststellungen hinterläßt. Im anderen Fall kann der nachziehende Spieler stets gewinnen.

Leider kann diese Rückwärtsanalyse ziemlich kompliziert werden, wenn der Spielbaum groß ist. Und das ist selbst bei einfachen Spielen schnell der Fall, denn der Spielbaum enthält alle nur möglichen Positionen und alle möglichen Züge.

Das Eckbrecherspiel hat fast die gleichen Regeln wie das Ritterspiel, aber die Rückwärtsanalyse wird schnell praktisch unmöglich. Und soweit sie möglich ist, zeigt sich kein Muster, aus dem eine einfache Gewinnstrategie herzuleiten wäre. Erfinder ist der Mathematiker David Gale von der Universität von Kalifornien in Berkeley. Er beschreibt sein Spiel mit Hilfe einer rechteckigen Anordnung von Plätzchen, aber ich bleibe bei der Schokolade. Das Ziel ist wie beim Ritterspiel, den Gegner zum Verzehr des Seifenstücks in der linken oberen Ecke zu zwingen. Aber diesmal haben die Spieler mehr Möglichkeiten, etwas abzubrechen: Wer am Zug ist, bricht ein Feld aus der Tafel heraus mitsamt allem, was rechts und unterhalb dieses Feldes ist.

Es gibt einen netten Beweis dafür, daß es im Eckbrecherspiel für alle Anfangsgrößen außer 1x1 eine Gewinnstrategie für den ersten Spieler geben muß. Nehmen wir an, Zwei hätte eine Gewinnstrategie. Eins beginnt das Spiel mit irgendeinem Zug; sagen wir, er ißt die rechte untere Ecke. Das kann Zwei nicht in eine Verluststellung bringen, denn nach Annahme ist die Anfangsstellung eine Verluststellung für Eins. Also kann Zwei einen Gewinnzug spielen, etwa den Zug in der Abbildung, und damit Eins in eine Verluststellung bringen. Aber Eins hätte diesen Zug als erster selber spielen können (siehe Diagramm links oben)! Das steht im Widerspruch zu der Annahme, Zwei habe eine Gewinnstrategie. Also muß diese Annahme falsch sein. Also hat Eins eine Gewinnstrategie.

Wenn also Zwei eine Gewinnstrategie hätte, könnte Eins sie ihm stehlen und für sich selbst ausnutzen. Leider liefert ein derartiger Beweis keinen Hinweis darauf, wie die Gewinnstrategie aussieht.

Für das Eckbrecherspiel kennt man nur in sehr einfachen Fällen Gewinnstrategien. Bei einer Tafel der Größe 2xn (oder nx2) nimmt Eins nur das rechte untere Stück und hinterläßt seinem Gegner dadurch eine Verluststellung (Diagramm rechts oben). Bei einer quadratischen Tafel beliebiger Größe gewinnt Eins, indem er alles bis auf ein L-förmiges Stück der Breite 1 abbricht. In den darauffolgenden Zügen tut Eins immer das, was Zwei soeben getan hat, aber im jeweils anderen Schenkel des L-Stücks. Einige weitere Fälle sind bekannt. So besteht beim 3x5-Eckbrecherspiel der erste Gewinnzug für Eins darin, die beiden rechten Quadrate aus der untersten Reihe zu entfernen. Beim 6x13-Spiel gibt es zwei verschiedene erste Gewinnzüge.

Man kann das Eckbrecherspiel auch mit unendlich großen Schokoladentafeln spielen. Paradoxerweise bleibt es ein endliches Spiel, weil nach endlich vielen Zügen nur noch eine endliche Tafel übrig bleibt (und ein Spieler, dem unendlich schlecht ist). Allerdings kann bei unendlichen Tafeln Zwei manchmal gewinnen, so bei einer 2xunendlich-Tafel. Was auch immer Eins im ersten Zug macht, Zwei kann daraufhin ein 2xn-Rechteck ohne das rechte untere Quadrat herstellen, und wir wissen bereits, daß dies eine Verluststellung ist. Das Spiel kann auch mit einer unendlichxunendlich-Tafel gespielt werden oder in drei oder mehr Dimensionen. Über Gewinnstrategien in diesen verallgemeinerten Fällen ist ebenfalls fast nichts bekannt.


Aus: Spektrum der Wissenschaft 8 / 1999, Seite 102
© Spektrum der Wissenschaft Verlagsgesellschaft mbH