Kombinatorische Spieltheorie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 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.
  • 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[Bearbeiten | Quelltext bearbeiten]

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.

Beim Domineering legen zwei Spieler abwechselnd Dominosteine auf ein Schachbrett, wobei ein Stein genau zwei Felder abdeckt. Die beiden Spieler werden in der kombinatorischen Spieltheorie allgemein als Links und Rechts bezeichnet. Der linke Spieler legt hier die Dominosteine immer vertikal und der rechte Spieler immer horizontal auf das Brett. Wer keinen Stein mehr legen kann, verliert das Spiel. Eine Partie auf einem 3x3-Brett könnte z.B. wie folgt ablaufen:

A B C
D E F
G H I
2 3
D 1
G I

Nach drei Zügen endet die Partie, da der rechte Spieler (rot) keinen Platz mehr für einen horizontalen Stein findet. Links (blau) hat gewonnen.

Grundlagen[Bearbeiten | Quelltext bearbeiten]

Formalisierung[Bearbeiten | Quelltext bearbeiten]

Für eine mathematische Modellierung werden die möglichen Spielregeln durch mathematische Objekte, nämlich insbesondere durch Mengen, beschrieben. Dazu werden die Zugmöglichkeiten einer Position durch zwei Mengen charakterisiert, die jeweils die Positionen enthalten, die einer der beiden Spieler durch einen Zug erreichen kann.

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

Bei der mathematischen Definition werden Positionen als Spiele aufgefasst, die von dieser Position starten. Man gelangt daher zur folgenden Definition.

Definition eines Spiels[Bearbeiten | Quelltext bearbeiten]

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.

Häufig werden die Optionen direkt aufgelistet und die Mengenklammern in einer verkürzten Notation weggelassen:

Elementare Spiele[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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
Rechts beginnt Links gewinnt Positiv
(Links gewinnt immer)
Null
(der Nachziehende gewinnt)
Rechts gewinnt 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.[Anmerkung 1]

Summe von Spielen[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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 Spielweise[Anmerkung 2].

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[Bearbeiten | Quelltext bearbeiten]

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:

Anschaulich gesehen entspricht dies einer Spielsituation, in der ein Spieler eine Zugmöglichkeit hat, die eindeutig schlechter als ein alternativer Zug ist. Der Spieler wird unter keinen Umständen den schlechteren Zug wählen – somit spielt es für den Ausgang der Partie keine Rolle, ob der schlechte Zug überhaupt existiert oder nicht.

Umkehrbare Züge
In einem Spiel wird der Zug des rechten Spielers nach umkehrbar genannt, falls eine linke Option von existiert mit . D.h. ist für Links mindestens so gut wie die ursprüngliche Position. (Entsprechend ist ein Zug des linken Spielers nach umkehrbar, falls eine rechte Option von existiert mit .)
Für einen umkehrbaren Zug ändert sich der Wert des Spieles nicht, wenn man annimmt, dass der Zug stets unmittelbar vom Gegenspieler beantwortet wird:
Ist in dem Spiel die rechte Option über umkehrbar, so gilt
.
Ist die linke Option über umkehrbar, so gilt
.

Umkehrbare Spielzüge können durchaus sinnvoll sein. Der Spieler sollte nach der Umkehrung allerdings in dieser Teilposition weiterspielen, andernfalls wäre der Abtausch ein reiner Verlust.

Für endliche Spiele (solche, die insgesamt endlich viele Positionen enthalten) führt eine wiederholte Anwendung dieser zwei Regeln zur Normalform des Spiels, welche für jede Äquivalenzklasse eindeutig ist.

Im allgemeinen Fall lässt sich zumindest folgende Aussage machen: Haben zwei Spiele und weder dominierte Optionen, noch umkehrbare Züge, so folgt aus , dass und gleiche linke und rechte Optionen haben. D.h. für jede linke / rechte Option von gibt es eine linke / rechte Option von mit .

Beispiele für Spiele höherer Stufe[Bearbeiten | Quelltext bearbeiten]

Mit vier Feldern lassen sich im Domineering Spiele der nächsten Stufe bilden:

A
B
C
D
A
D
C
D
A
D
C
D

(Die letzte Vereinfachung kann erfolgen, da und damit eine dominierte Option ist.)

Andererseits ist auch

Man definiert

, usw.

d.h.

, usw.

Die Spiele lassen sich als eine Art Punktestand deuten: Der linke bzw. rechte Spieler hat nicht nur gewonnen, sondern könnte sogar noch eine gewisse Zahl weiterer Züge machen. Neben den ganzzahligen Spielen, gibt es auch solche, die als Punktestand interpretiert werden können:

A
B
C D
C D
A
D
A
B
C D
A
D
A
B

Man definiert

.

Diese Zuordnung ist durch die folgenden Eigenschaften motiviert:

,

wobei sich die zweite Beziehung wie folgt nachrechnen lässt:

.

Des Weiteren gibt es aber auch Spiele, die sich nicht wie ein ausgespielter Punktestand verhalten. Sie sind „heiß“, in dem Sinne, dass jeder Spieler seine Situation verbessern kann, indem er in der entsprechenden Stellung zieht:

A
B C
D
C
D
A
D
C
D
A
D

Im Mittel hat denselben Wert wie :

Im Unterschied zu lässt sich jedoch nicht präzise einordnen, sondern ist fuzzy gegenüber Werten im abgesteckten Intervall:

Auf dem Zahlenstrahl lässt sich daher nur unbestimmt in dem Bereich von 0 bis 1 verorten.

Surreale Zahlen[Bearbeiten | Quelltext bearbeiten]

Unter den Spielen gibt es solche, welche mit reellen Zahlen identifiziert werden können, da sie derselben Arithmetik folgen. Genauer lassen sie sich die als surreale Zahlen bezeichneten Spiele wie folgt charakterisieren:

Eine surreale Zahl ist ein Spiel, bei dem
  • alle linken und rechten Optionen surreale Zahlen sind
  • gilt, für jede linke Option und rechte Option .

Im Kontext der kombinatorischen Spieltheorie werden surreale Zahlen auch kurz als Zahl (engl. number) bezeichnet. Von den bereits definierten Spielen sind und Zahlen, nicht jedoch und .

Zahlen zeichnen sich dadurch aus, dass sie total geordnet sind, d.h. für zwei Zahlen und gilt entweder , oder . Surreale Zahlen sind eine reichhaltige Klasse mit den Eigenschaften eines geordneten Körpers, welche nicht nur die ganzen, rationalen und reellen Zahlen enthält, sondern auch infinitesimale und infinite Vertreter hat. Genaueres dazu im Hauptartikel zu surrealen Zahlen.

Als Komponente in einer Spiel-Summe lassen sich Zahlen nach folgendem Satz sehr einfach Spiel-strategisch einordnen:

Zahl-Vermeidungs-Satz
Ist eine surreale Zahl und ein Spiel, aber keine surreale Zahl, so ist es im Summenspiel immer von Vorteil, im Spiel zu ziehen, sofern dies möglich ist.

D.h. in einem Spiel aus mehreren Komponenten ziehen die Spieler nur so lange in einer Komponente, bis eine Zahl (praktisch ein endgültiger Punktestand) erreicht ist. Am Ende wird abgerechnet, indem die verbleibenden Zahlen summiert werden: Ist die Summe positiv, so gewinnt Links, ist sie negativ gewinnt Rechts, ist sie 0, so gewinnt der nachziehende Spieler.

Eine unmittelbare Konsequenz des Satzes ist folgende Rechenregel:

Translationsprinzip
Ist eine Zahl und keine Zahl, so gilt
.

Hier wird vorausgesetzt, dass mindestens eine linke bzw. rechte Option besitzt. Dann folgt die Identität, da die restlichen Optionen der Summe nach dem Zahl-Vermeidungs-Satz dominiert sind.

Sonderfall: Neutrale Spiele[Bearbeiten | Quelltext bearbeiten]

Spiele, bei denen zusätzlich zu den oben aufgeführten Eigenschaften die Zugmöglichkeiten für beide Spieler stets identisch sind, heißen neutrale Spiele (der englische Originalbegriff impartial wird z.T. auch mit objektiv übersetzt). In Bezug auf die Gewinnaussichten gehört jede Position eines neutralen Spiels zu einer der beiden ersten Klassen der oben angeführten Liste.

Eine vollständige Analyse eines neutralen Spieles ist immer dadurch möglich, dass jeder Position eine äquivalente, aus nur einem Haufen bestehende Position des normalen Nim-Spiels zugeordnet wird. Diese Möglichkeit der Reduktion wurde unabhängig voneinander von 1935 von Roland Sprague[1] und 1940 von Grundy[2] gefunden und wird daher auch als Satz von Sprague-Grundy bezeichnet. Ansätze der Reduktion hatte zuvor bereits der Schachweltmeister und Mathematiker Emanuel Lasker erörtert.[3][4]

Die Größe des Nim-Haufens, die einer Position eines neutralen Spiels zugeordnet ist, wird auch als dessen Grundy-Zahl bezeichnet. Die Grundy-Zahl einer Position kann relativ einfach rekursiv, d.h. aus den Grundy-Zahlen der in einem Zug erreichbaren Positionen, berechnet werden: Sie ist gleich der kleinsten natürlichen Zahl, die nicht Grundy-Zahl einer Nachfolgeposition ist.

Grundy-Zahlen besitzen die folgenden beiden Eigenschaften:

  • Der anziehende Spieler verfügt genau dann über eine Gewinnstrategie, wenn die Grundy-Zahl ungleich 0 ist.
  • Die Grundy-Zahl einer Summe, d.h. einer aus Komponenten zusammengesetzten Position ist gleich der XOR-Summe der Grundy-Zahlen ihrer Komponenten, was die Berechnung in solchen Fällen komplexitätsmäßig entscheidend vereinfacht.

Die beiden Eigenschaften verallgemeinern die 1901 von Charles Leonard Bouton[5] für das Nim-Spiel gefundene Gewinnstrategie, nach der man immer so ziehen sollte, dass die XOR-Summe der Haufengrößen gleich 0 ist.

Anwendung: Endspiele bei Go[Bearbeiten | Quelltext bearbeiten]

Auch wenn Go eigentlich kein Spiel ist, bei dem der zuletzt ziehende Spieler gewinnt, so lassen sich doch Spiele im Sinne der kombinatorischen Spieltheorie konstruieren, welche die üblichen Go-Regeln nachbilden und effektiv zu demselben Spielresultat führen[6]. Am einfachsten lässt sich dies mit der historischen Steinbewertung realisieren, bei der beide Spieler das Brett mit Steinen vollsetzten (bis auf zwei Augen pro lebender Gruppe) und der Spieler mit den meisten Steinen auf dem Brett zum Sieger erklärt wird. Mit der Zusatzregel der Gefangenenrückgabe ist der Sieger zugleich auch die Person, welche zuletzt ziehen kann. Gefangenenrückgabe bedeutet, dass die Spieler nicht passen dürfen, aber anstelle eines regulären Zugs auch einen zuvor gefangenen Stein an den Gegner zurückgeben können (der Stein ist damit aus dem Spiel).

Die Steinbewertung unterscheidet sich von den heute weltweit üblichen Go-Regeln darin, dass auf jede Gruppe eine „Steuer“ von zwei Punkten erhoben wird. Aber auch die modernen Regel-Varianten lassen sich entsprechend abbilden.

Neben den Konventionen der klassischen kombinatorischen Spieltheorie nach John Conway gibt es allerdings auch alternative Formalismen, bei denen die Punktwertungen und deren Eigenschaften in Bezug auf die Komponenten einer (Endspiel-)Position direkt untersucht werden. Dies wird in den Arbeiten aus den 1950er Jahren von Milnor (1953)[7], Hanner (1959)[8] verfolgt, welche bereits wesentliche Ergebnisse der Temperaturtheorie enthalten, und von Berlekamp (1996)[9] weitergeführt.

In dem Buch Mathematical Go (1994) von Berlekamp und Wolfe werden die Ergebnisse der kombinatorischen Spieltheorie auf Endspiele im Go angewendet und die sich daraus ergebenen Spielstrategien herausgearbeitet. Es enthält Erkenntnisse und Leitlinien, welche zuvor nicht zum Wissenskanon von Profispielern gehörten und gilt als eine der wenigen Go-Publikationen von westlichen Autoren, welche im asiatischen Raum Beachtung fanden.

Anmerkungen[Bearbeiten | Quelltext bearbeiten]

  1. 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 .
  2. Dazu 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 .

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. R. Sprague: Über mathematische Kampfspiele, Tôhoku Mathematical Journal, 41 (1935), S. 438–444 (Online-Version).
  2. P. M. Grundy: Mathematics and games, Eureka. 27 (1940), S. 9–11 (Online-Version (Memento vom 27. September 2007 im Internet Archive)).
  3. Emanuel Lasker: Brettspiele der Völker. Berlin 1931, S. 177 ff.
  4. Auszugsweise zitiert in: Jörg Bewersdorff: Glück, Logik und Bluff: Mathematik im Spiel – Methoden, Ergebnisse und Grenzen, 5. Auflage, Wiesbaden 2010, S. 119–121
  5. C. L. Bouton: Nim, a game with a complete mathematical theory, Annals of Mathematics, (2) 3 (1901), S. 35–39 (online bei JSTOR)
  6. Elwyn Berlekamp: Introductory overview of mathematical Go endgames, Combinatorial games, Lecture Notes AMS Short Course, Columbus/OH (USA) 1990, S. 73–100 (Abstract im Zentralblatt MATH)
  7. John W. Milnor: Sums of positional games, Contrib. Theory of Games, II, Ann. Math. Stud., 28 (1953), S. 291–301, doi:10.1515/9781400881970-017 (Abstract im Zentralblatt MATH)
  8. Olof Hanner: Mean play of sums of positional games, Pacific Journal of Mathematics, 9 (1959), S. 81–99 (Online-Version).
  9. Elwyn Berlekamp: The economist's view of combinatorial games, Games of No Chance, 1996, S. 365–405 (Online-Version)