Kombinatorische Spieltheorie ist ein von John Horton Conway ca. 1970 begründeter Zweig der Mathematik, der sich mit einer speziellen Klasse von Zwei-Personen-Spielen befasst.
Die Eigenschaften dieser Spiele, die auch als kombinatorische Spiele bezeichnet werden, sind: Kein Zufallseinfluss. Es gibt keine für einen einzelnen Spieler verborgene Information (wie bei Spielkarten), d. h., es liegt perfekte Information vor. Gezogen wird abwechselnd. Es gewinnt derjenige Spieler, dem es gelingt, den letzten Zug zu machen (eine Ausnahme sind Misère-Versionen, bei denen der zuletzt ziehende Spieler verliert). Jede Partie endet nach einer endlichen Zahl von Zügen.
Solche Spiele, zu denen Nim und (nach geringfügigen Regeltransformationen) Go und Schach gehören, eröffnen besonders dann interessante Möglichkeiten der mathematischen Analyse, wenn sie in Komponenten zerfallen, bei denen es keine gegenseitige Beeinflussung der Zugmöglichkeiten gibt. Beispiele sind Nim-Haufen und einige späte Endspielpositionen im Go; auch im Schach lassen sich einige Zugzwang-Positionen bei Bauernendspielen so deuten. Das Zusammensetzen von Positionen wird auch als Addition bezeichnet.
Die mathematische Bedeutung der kombinatorischen Spieltheorie resultiert daraus, dass die Spiele einer Unterklasse als Zahlen gedeutet werden können. Dabei lassen sich sowohl ganze als auch reelle und sogar transfinite (d. h. unendlich große und unendlich kleine) Zahlen konstruieren, deren Gesamtheit man auch surreale Zahlen nennt. Umgekehrt erscheinen die Spiele der kombinatorischen Spieltheorie als Verallgemeinerung der surrealen Zahlen.
Beispiel: Domineering Das Spiel Domineering ist eines der Spiele, welche im Rahmen der kombinatorischen Spieltheorie behandelt werden können. Es soll zur Veranschaulichung dienen und konkrete Beispiele liefern.
Spielregeln Beim Domineering legen zwei Spieler abwechselnd Dominosteine auf ein schachbrettartiges Spielfeld, wobei ein Stein genau zwei Felder abdeckt, die beim Setzen beide noch frei sein müssen. Wie in der kombinatorischen Spieltheorie allgemein üblich, werden die beiden Spieler als Links und Rechts bezeichnet. Der linke Spieler legt die in den folgenden Abbildungen blau dargestellten Dominosteine immer vertikal und der rechte Spieler seine rot dargestellten Steine immer horizontal auf das Brett. Wie bei allen Spielen der kombinatorischen Spieltheorie verliert derjenige Spieler das Spiel, der nicht mehr ziehen kann.
Will man eine Position analysieren, kommt es offensichtlich nur auf die Menge der noch freien Felder an, aber nicht, in welcher Weise die bereits belegten Felder bedeckt wurden.
Beispielpartie Eine Partie auf einem 3×3-Brett könnte z. B. so verlaufen, wie es die nachfolgende Abbildung zeigt: Links eröffnet durch Setzen des mit „1“ gekennzeichneten Steins. Rechts legt darauf den mit „2“ gekennzeichneten Stein, worauf Links durch Setzen des mit „3“ markierten Steins die Partie für sich entscheidet, weil Rechts dann keinen Platz mehr hat für einen horizontal zu setzenden, roten Stein.
A B C D E F G H I → 2 3 D 1 G I
Zur beispielhaft angeführten Partie bleibt noch anzumerken, dass Links in der mit dem dritten Zug erreichten Endposition sogar noch eine Zugmöglichkeit gehabt hätte. Außerdem kann die Menge der freien Felder, die alle weiteren Zugmöglichkeiten bestimmt, in Komponenten zerlegt werden, sofern diese Komponenten nicht über Seitenrändern von Feldern zusammenhängen. Zum Beispiel könnte bei der Endposition die Zerlegung D G I vorgenommen werden. Diese Möglichkeit der Zerlegung einer Position bzw. der umgekehrte Vorgang eines Nebeneinanderlegens von Positionen ist eine ganz wesentliche Eigenschaft kombinatorischer Spiele (siehe Summe von Spielen).
Mathematische Formalisierung
Für eine mathematische Modellierung wird jede innerhalb der kombinatorischen Spieltheorie mögliche Spielregel durch mathematische Objekte, nämlich insbesondere durch Mengen, beschrieben. Dazu sind für jede Position die Zugmöglichkeiten der beiden Spieler mathematisch formal zu charakterisieren.
Diese Charakterisierung der Zugmöglichkeiten konnte speziell beim Spiel Domineering für jede Position durch die Menge der noch freien Felder repräsentiert werden. Allgemein, d. h. für jedes beliebige kombinatorische Spiel, lassen sich die Zugmöglichkeiten einer Position durch zwei Mengen und charakterisieren, von denen jede jeweils die Positionen enthält, die der betreffende Spieler durch einen Zug erreichen kann. Im Sinne des mathematischen Modells wird dadurch jede Position zu einem kombinatorischen Spiel, das rekursiv durch diejenigen Spiele, die mit den durch einen Zug erreichbaren Positionen starten, definiert wird.
Allgemeine Schreibweise
Bei der Schreibweise hat sich die Notation von z. B. für das Paar eingebürgert, wenn der Spieler Links die beiden Zugmöglichkeiten nach und Rechts nur die Zugmöglichkeit nach besitzt:
A B C D C D A D A B
Ausgehend von dieser Schreibweise und der jeweiligen Identifikation einer Position mit dem Spiel, das von dieser Position startet, gelangt man zur folgenden Definition.
Definition eines Spiels
Ein Spiel (im Sinne von Spielposition, engl. game) ist über folgende selbstreferentielle Konstruktion definiert:
Konstruktionsregel Sind und zwei Mengen von Spielen, dann ist ein Spiel.
Die Mengen und werden auch die linken bzw. rechten Optionen des Spiels genannt und repräsentieren die Spielpositionen, die der linke bzw. rechte Spieler mit einem Zug aus der aktuellen Spielposition heraus erreichen kann.
Wie bereits für das Eingangsbeispiel erläutert, werden zur Verkürzung der Notation in der Regel die Optionen direkt aufgelistet und die Mengenklammern weggelassen:
Elementare Spiele
Das Fundament dieser rekursiven Definition bildet das Spiel 0, bei dem keiner der beiden Spieler mehr ziehen kann (die Menge der linken und rechten Optionen ist leer). Die entsprechende Position im Domineering ist das 1x1-„Brett“.
A
In einem nächsten Schritt lassen sich nun weitere Spiele finden:
A B A B A B C
Gewinnklassen
In Bezug auf die mit guten Strategien sicher erzielbaren Gewinnaussichten gehört jede Position zu genau einer der folgenden vier Klassen: Links kann bei optimaler Spielweise gewinnen, unabhängig davon, wer beginnt (Positiv) Rechts kann das Spiel gewinnen, unabhängig davon, wer beginnt (Negativ) Der den ersten Zug ausführende Spieler besitzt eine Gewinnstrategie (Fuzzy) Der nachziehende Spieler besitzt eine Gewinnstrategie (Null)
Links beginnt Links gewinnt Rechts gewinnt Rechtsbeginnt Linksgewinnt Positiv(Links gewinnt immer) Null(der Nachziehende gewinnt) Rechtsgewinnt Fuzzy(der Anziehende gewinnt) Negativ(Rechts gewinnt immer)
Die bereits definierten elementaren Spiele können wie folgt klassifiziert werden: 1 ist positiv, −1 ist negativ, 0 ein Null-Spiel und * ist fuzzy.
Viele der untersuchten Spiele zerfallen im Laufe der Partie in unabhängige Einzelkomponenten (Endspiele im Go, Reihen beim Nim). Diese Teil-Spiele sind oft einfach genug, um vollständig analysiert zu werden. Daher ist eine zentrale Fragestellung der kombinatorischen Spieltheorie, wie sich die Gewinnaussichten des Gesamtspiels aus den Informationen zu den Teil-Spielen ableiten lassen. Die Temperaturtheorie liefert einen Algorithmus, mit dem man annähernd optimal spielen kann. Die maximale Abweichung von der theoretisch besten Strategie lässt sich dabei eingrenzen.
In einigen Fällen kann man bereits aus den Gewinnklassen Schlüsse ziehen: Sind die beiden Komponenten eines Spiels positiv, so ist das gesamte Spiel positiv. Gleiches gilt für negative Spiele. Null-Spiele haben die Eigenschaft, dass sie als Komponente keinen Einfluss auf den Ausgang des Spiels haben und die Gewinnklasse unverändert lassen. Zwei Spiele, die sich nur um ein Null-Spiel unterscheiden, werden daher als gleichwertig betrachtet.Beweis: Sei ein Nullspiel und ein Spiel, für das Spieler A eine Gewinnstrategie hat. Dieser Spieler hat dann auch für das zusammengesetzte Spiel eine Gewinnstrategie: Für jeden Zug, den der Gegenspieler in macht, antwortet Spieler A mit der Gewinnstrategie des Nachziehenden. Andernfalls zieht er in , entsprechend seiner Gewinnstrategie für .
Summe von Spielen
Die Summe zweier Spiele ist ein zentrales Konzept der kombinatorischen Spieltheorie, mit dem das vom Nim bekannte Nebeneinanderlegen von Positionen formalisiert und verallgemeinert wird: Eine Nim-Position besteht aus mehreren Haufen von Spielsteinen, und bei jedem Zug wird genau ein Haufen ausgewählt, wo der aktuelle Zug durchgeführt wird. Dabei hängen die Zugmöglichkeiten nur vom ausgewählten Haufen ab. Außerdem lässt jeder Zug die nicht ausgewählten Haufen unverändert.
Analog kann man zwei Spiele dadurch miteinander addieren, dass man sie nebeneinanderlegt und die Zugmöglichkeiten derart definiert, dass der ziehende Spieler einen der beiden Summanden auswählen muss, um dann dort einen zulässigen Zug auszuführen. Insbesondere besitzt ein Spieler, der in keinem der Summanden ziehen kann, keine Zugmöglichkeit mehr, so dass er verloren hat.
Formal ist die Summe der Spiele und rekursiv definiert als
Vergleich zweier Spiele
Um zwei Spiele G und H miteinander vergleichen zu können, bestimmt man die Gewinnklasse des Differenzspiels . Das Inverse entspricht dabei einer Vertauschung der Rollen von Links und Rechts. Im Domineering kann dies durch ein Drehen des Brettes um 90 Grad erreicht werden. Formal ist
Auch diese Definition ist rekursiv.
Ist das Differenzspiel zweier Spiele und ein Null-Spiel, so hat für jedes Spiel die Summe dieselbe Gewinnklasse wie die Summe . Daher werden und als äquivalent angesehen. Unter Identifikation von Äquivalenzklasse und Vertreter schreibt man: , falls ein Null-Spiel ist.
Weiterhin wird definiert: , falls positiv ist. , falls negativ ist. , falls fuzzy ist. sowie , falls oder , falls oder
Entsprechend dieser Symbolik ist ein „größeres“ Spiel immer vorteilhaft für den linken Spieler.
Alternativ lassen sich die Ordnungsrelationen auch etwas formeller einführen, ohne Bezugnahme auf das nicht im Detail ausgeführte Konzept der optimalen SpielweiseDazu wird definiert: keine rechte Option von existiert mit und keine linke Option von existiert mit sowie
( und ) ( und nicht )
(weder noch )
Diese rekursive Definition ist mit dem Prinzip der optimalen Spielweise konsistent, denn für ein Spiel sind folgende Aussagen äquivalent: ist positiv oder null Wenn Rechts beginnt, so kann Links gewinnen Rechts hat keinen „gewinnenden Zug“ Es gibt keine rechte Option von , für die gilt: Wenn Links beginnt, so kann Rechts gewinnen. Es gibt keine rechte Option von , die negativ oder null ist D.h. symbolisch
keine rechte Option von existiert mit ..
Mit diesen Operatoren und Relationen erfüllen die Spiele (modulo Äquivalenz) die Eigenschaften einer kommutative Gruppe mit partieller Ordnung. Die Gesamtheit aller Spiele kann als echte Klasse jedoch genau genommen keine Gruppe sein, da die Definition einer Gruppe sich nur auf Mengen erstreckt. Wesentliche Beziehungen, welche sich im Fall von Mengen aus der Gruppeneigenschaft ableiten lassen, sind allerdings auch auf Klassen übertragbar.
Vereinfachung von Spielen und Normalform
Ein Spiel kann mit den folgenden zwei Regeln vereinfacht werden, ohne dass sich dabei der Wert des Spiels ändert (d. h. ohne die Äquivalenzklasse zu verlassen).
Dominierte Optionen Sind in dem Spiel zwei linke Optionen vergleichbar, z. B. , so ist eine durch dominierte Option. Entsprechend ist eine rechte Option durch dominiert, falls . Dominierte Optionen können weggelassen werden, ohne den Wert eines Spiels zu verändern: