5. Unendliche Zweipersonenspiele

Dieses Kapitel bringt scheinbar gänzlich verschiedene Bereiche zusammen: Unendliche Spiele, Regularitätseigenschaften von Mengen reeller Zahlen und eine gewisse Regel der Logik.

 Wir beginnen mit der logischen Regel, die die beiden Quantoren „für alle“ und „es gibt“ betrifft. Im Wechsel aufeinander folgende All- und Existenzquantoren können dem Verstand Schwierigkeiten bereiten, man denke etwa an die ε-δ-Formulierungen in der Analysis. In der Mathematikgeschichte und vielleicht auch in der persönlichen Erfahrung des Lesers finden sich unerlaubte Vertauschungen von

für alle x gibt es ein y, sodass gilt …  mit

es gibt ein y, sodass für alle x gilt …

Die zweite Form drückt vielleicht die Sehnsucht nach universell geeigneten Objekten aus − doch anstelle einer psychologischen Erklärung solcher Fehlschlüsse versuchen wir lieber, der Mathematik des Quantorenwechsels auf die Spur zu kommen. Wir borgen aus der mathematischen Logik die Zeichen ∀ für „für alle“, ∃ für „es gibt“ und schließlich ¬ für „non“ oder „nicht“; wir gebrauchen sie hier lediglich zur Abkürzung. Weithin bekannt sind die beiden Verneinungsregeln

¬ ∃x φ(x)  gdw  ∀x ¬ φ(x)  und 

¬ ∀x φ(x)  gdw  ∃x ¬ φ(x)

für beliebige mathematische Aussagen φ(x). Iteration dieser Regeln liefert für alle n  ∈  ℕ:

wobei hier Q gleich ∀ ist für ungerade n und gleich ∃ sonst, und Q* den von Q verschiedenen Quantor bezeichnet. Für spezielle Aussagen φ können wir diesen Formeln eine verblüffende, einfache und intuitive Interpretation geben, die den iterierten Quantorenwechsel in einem sehr sympathischen Licht erscheinen lässt.

 Wir betrachten hierzu eine nichtleere Menge A als Bereich, über den die Quantoren laufen, und lesen dann ∀x als „für alle x  ∈  A“ und analog ∃x als „es existiert ein x  ∈  A“. Für n  ∈  ℕ betrachten wir als Formeln φ(x₀, …, x_n) Aussagen der Form (x₀, …, x_n)  ∈  P mit P ⊆ A^n + 1.

 Wir lesen nun x₀, x₁, …, x_n als eine Menge von Spielzügen, die zwei Spieler I und II − zuweilen auch Adam und Eva genannt − wechselweise ausführen. Die einzelnen Züge sind Elemente der Menge A, d. h. es gilt x_i  ∈  A für alle i.

 Wir betrachten folgende Situation: Gegeben ist ein n  ∈  ℕ und ein P ⊆ A^n + 1. Spieler I eröffnet das Spiel mit einem wohlpräparierten Zug x₀  ∈  A, Spieler II antwortet abgeklärt mit x₁  ∈  A, Spieler I kontert unbeeindruckt mit x₂  ∈  A, Spieler II spielt ein besonders tiefsinniges x₃, Spieler I ein selten gesehenes x₄, Spieler II ein denkwürdiges x₅, Spieler I ein x₆, das die Fachwelt schockiert, usw. Allgemein ist x_2k der (k + 1)-te Zug von Spieler I und x_2k + 1 der k-te Zug von Spieler II, solange 2k bzw. 2k + 1 kleinergleich n ist. Das Spiel endet, wenn insgesamt n + 1 Züge gespielt sind, also mit dem Zug x_n. Es liegt nun die Partie x₀, …, x_n vor. Wir erklären

Spieler I als den Gewinner der Partie (x₀, …, x_n) im Spiel G_A(P),

falls (x₀, …, x_n)  ∈  P gilt. Andernfalls gebührt dem Spieler II Ruhm und Ehre des Sieges. Es gibt also kein Unentschieden. Spieler I versucht, die Partie in der Gewinnmenge P zu halten, Spieler II versucht eine Partie in A^n + 1 − P zu erzeugen.

 Der Leser wird nach einem Moment der logischen Besinnung sehen, dass die zunächst undurchdringlich erscheinende Aussage

∃x₀ ∀x₁ … Qx_n (x₀, …, x_n)  ∈  P

nichts anderes bedeutet als die seit Kindertagen vertraute Behauptung: Spieler I kann bei gutem Spiel das Spiel G_A(P) gewinnen, oder, etwas fremdwortreicher formuliert, Spieler I hat eine Gewinnstrategie im Spiel G_A(P). Dies heißt nämlich: Es gibt einen „guten“ Zug x₀, sodass es für alle Antworten x₁ von Spieler II einen „guten“ Zug x₂ gibt (der von x₁ abhängt), sodass es für alle Antworten x₃ von Spieler II … … …, sodass die am Ende gespielte Partie x₀, …, x_n in P liegt. Spielt Spieler I immer „gute“ Züge, so gewinnt er die Partie, egal wie sich Spieler II krümmt und wendet. Wir werden die hier verwendeten Begriffe, insbesondere „Gewinnstrategie“, später noch mathematisch genau definieren.

 Analog besagt nun aber die Formel

∀x₀ ∃x₁ … Qx_n (x₀, …, x_n)  ∉  P,

dass Spieler II das Spiel G_A(P) bei gutem Spiel gewinnt.

 Wir sagen kurz: Spieler I gewinnt G_A(P), falls I eine Gewinnstrategie im Spiel G_A(P) besitzt. Analoge Sprechweisen gelten für II. In der Kürze liegt eine gewisse Ungenauigkeit: „I gewinnt P“ meint nicht, dass Spieler I bei beliebig dusseligem Spiel gewinnen würde; wir meinen „bei gutem Spiel“.

 Die obigen Verneinungsregeln für Quantorenketten liefern nun die beiden folgenden Äquivalenzen:

 Die Aussage (a) besagt nun einfach: Spieler I gewinnt G_A(P) genau dann nicht, wenn Spieler II das Spiel G_A(P) gewinnt. Ähnliches gilt für (b). Es gilt also, dass genau einer der beiden Spieler eine Gewinnstrategie im Spiel G_A(P) besitzt. Wir sagen statt dieser Aussage auch, dass das Spiel G_A(P) bzw. die Menge P determiniert ist. Dass nicht beide Spieler zugleich eine Gewinnstrategie haben können, liegt auf der Hand. Die nichttriviale Aussage ist die Existenz einer Gewinnstrategie für einen der beiden Kontrahenten.

 Dass jedes endliche Spiel G_P determiniert ist, ist vielleicht nicht überraschend, bedarf aber doch eines Beweises. Dieser wird, modulo einiger fehlender formaler Definitionen, vollständig durch die Äquivalenz (a) geliefert. In den einfachen Verneinungsregeln für Quantorenketten steckt eine bemerkenswerte Kraft.

 Der Leser mag sich überlegen, wie wir diese Betrachtungen in einen Beweis umwandeln können, dass etwa die Spiele Schach oder Go determiniert sind. Wir skizzieren das Argument für Schach, da es das bekanntere Spiel ist.

 Drei Aspekte des Schachspiels passen noch nicht in unseren Aufbau: Erstens wird nach Regeln gespielt, zweitens ist die Spieldauer variabel, und drittens ist ein Remis möglich. Alle drei Punkte lassen sich in natürlicher Weise in unserer Umgebung behandeln.

 Als Zugmenge A wählen wir die Menge aller Paare von Feldern des Schachbretts wie etwa (e2, e4). Genauer wäre etwa

A  =  { (x, i, y, j)  |  x, y  ∈  { a, …, h },  i, j  ∈  { 1, …, 8 } }.

Weiter legen wir etwa n = 1000 als obere Grenze der Spieldauer fest. Jede Partie mit einem Matt wird künstlich um konstante Züge (a1, a1) zu einer Partie der Länge n verlängert. Partien der Länge n ohne Matt gelten als Remis. Die Menge P ⊆ Aⁿ besteht nun aus den üblichen (verlängerten) Gewinnpartien für den Spieler der weißen Steine, ergänzt um diejenigen Partien, bei denen Spieler II einen regelwidrigen Zug wie etwa (a1, h2) macht. Insbesondere wird hier Schwarz als Sieger von Remispartien erklärt. Wir wissen dann, dass G_A(A) determiniert ist. Wählen wir andererseits als P′ die Menge P vereinigt mit den Remispartien, so gewinnt diesmal I auch alle Remisspiele. G_A(P′) ist einfacher für Weiß und härter für Schwarz als G_A(P). Auch das Spiel G_A(P′) ist determiniert, und wir erhalten dann als Ergebnis für das übliche (zeitlich begrenzte) Schachspiel mit Remis:

 Wir haben durch die Analyse der Verneinungsregeln keine Information gewonnen, welcher der beiden Spieler ein Spiel G_A(P), P ⊆ A^n + 1, gewinnt, und dies lässt sich wohl im konkreten Fall wenn überhaupt nur durch eine kombinatorische Feinanalyse von P selbst beantworten; das Schachspiel ist hier wieder ein gutes Beispiel.

 Mathematiker fliehen gerne die Qualen der endlichen Kombinatorik und hoffen, über den Weg ins Unendliche mehr über die endliche Welt und ihre Mathematik herauszufinden (zuweilen finden sie dann nicht mehr zurück). Es ist nun in der Tat verführerisch, auch unendliche Spiele zu betrachten. Die Gewinnmengen für Spieler I sind dann von der Form P ⊆ ^ℕA. Eine Partie ist eine unendliche Folge x₀, x₁, …, x_n, …, n  ∈  ℕ, mit x_n  ∈  A für alle n  ∈  ℕ, also einfach ein Element f des Folgenraumes ^ℕA. Solche f hatten wir eine unendliche, sich stückweise preisgebende Information genannt. Der neue Aspekt ist, dass wir nun eine Folge f  ∈  ^ℕA als verzahntes Kräftespiel zweier Gegner lesen. Dieser spezielle Blickwinkel auf die Folgenräume erweist sich als ungemein fruchtbar. Ganz unabhängig von dem für sich interessanten unendlichen Spielkontext führt er zu einem tieferen Verständnis scheinbar weit entfernter Begriffe. Die aufgedeckten Zusammenhänge sind überraschend. Wer kann an dieser Stelle ahnen, dass unendliche Spiele etwas mit der Baire- oder Lebesgue-Messbarkeit einer Punktmenge im Baireraum zu tun haben?

 Damit erscheint das jetzt schon vertraute Objekt 𝒩 noch einmal in einem ganz anderen Licht, nämlich als das mathematische Universal-Casino für unendliche Zweipersonenspiele mit abzählbarem Zugvorrat. Der Baireraum hat nun seinen großen Auftritt als interstellares Las Vegas im platonischen Mengenuniversum. Weiter wird die Stellung der Bäume auf den natürlichen Zahlen noch einmal gestärkt. Sie stellen den benötigten Begriffsapparat für Spiele mit Regeln zur Verfügung. Die einem Spieler offen stehenden Optionen in einem Spiel mit Regeln werden einfach durch die Nachfolger eines Knotens in einem Baum beschrieben. Der aktuelle Stand der Partie kann dann mit einem Knoten des Regelbaumes selber identifiziert werden. Der Knoten kodiert den Verlauf der ganzen bislang gespielten Partie.

 Wie steht es um Gewinnstrategien für unendliche Spiele? Es steht zunächst keine allgemeine unendliche Verneinungsregel für Quantoren mehr zur Verfügung. Die Frage nach der Determiniertheit einer Menge P ⊆ 𝒩 wird zu einem großen und unerwartet reichen mathematischen Problem. Die Determiniertheit eines P ⊆ 𝒩 können wir als die Erlaubnis lesen, die Verneinung auch durch unendlich viele Quantoren ziehen zu dürfen:

(+_P)  ¬ ∃x₀ ∀x₁ … (x₀, x₁, … )  ∈  P  gdw  ∀x₀ ∃x₁ … (x₀, x₁, …)  ∉  P.

 Denn dies sagt nichts anderes als: I hat genau dann keine Gewinnstrategie in G_ℕ(P), wenn II eine Gewinnstrategie in G_ℕ(P) hat. Es gilt also (+_P) genau dann, wenn das Spiel G_ℕ(P) determiniert ist.

 Die unendliche ∃∀∃∀…-Regel (+_P) gilt bei Anwesenheit des Auswahlaxioms nicht für alle P ⊆ 𝒩, wie wir zeigen werden. Sie gilt aber für viele P und erweist sich im Verlauf der systematischen Untersuchung unendlicher Spiele als die vielleicht längste mathematische Praline der Welt. Man darf sie als die ultimative Regularitätseigenschaft bezeichnen. Ein großes Stück der klassischen Theorie der Untersuchung von Mengen reeller Zahlen ist vom heutigen Standpunkt aus gesehen eine Exegese des Satzes von der Determiniertheit offener P ⊆ 𝒩. Der genaue Zusammenhang ist kompliziert, aber grob gesprochen heißt „determiniert“ nichts anderes als „superregulär“.

 Es wird Zeit für genaue mathematische Definitionen.