Kombinatorische Spieltheorie

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).
• 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.

Wer kann gezielt gewinnen?

In Bezug auf die mit guten Strategien sicher erzielbaren Gewinnaussichten gehört jede Position zu genau einer der folgenden vier Klassen:

• Der den ersten Zug machende Spieler besitzt eine Gewinnstrategie, die ihm unabhängig von der Spielweise seines Gegners einen Gewinn sichert.
• Der nachziehende Spieler besitzt eine Gewinnstrategie.
• Unabhängig davon, wer den ersten Zug macht, besitzt Spieler 1, meist als Links oder Weiß bezeichnet, eine Gewinnstrategie.
• Spieler 2, meist als Rechts oder Schwarz bezeichnet, besitzt eine Gewinnstrategie.

Ein Hauptbestandteil der Kombinatorischen Spieltheorie ist die so genannte Temperaturtheorie. Diese erlaubt es, die Gewinnaussichten eines Spiels aus Daten der einzelnen Komponenten zu approximeren.

Sonderfall: Neutrale Spiele

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 1936 von Sprague^[1] und 1940 von Grundy^[2] gefunden, ansatzweise zuvor bereits von dem Schachweltmeister und Mathematiker Emanuel Lasker^[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.

Beispiel: Go

Auch wenn Go eigentlich kein Spiel ist, bei dem der zuletzt ziehende Spieler gewinnt, können die üblichen Punktwertungen des Go in entsprechende Spielregeln transformiert werden, die den Voraussetzungen der Kombinatorischen Spieltheorie entsprechen^[6]. Es gibt allerdings auch einen alternativen Ansatz, der auf Milnor (1953)^[7], Hanner (1959)^[8] und Berlekamp (1996)^[9] zurückgeht. Dabei werden die Punktwertungen und deren Eigenschaften in Bezug auf die Komponenten einer (Endspiel-)Position direkt untersucht.

Siehe auch

• Spieltheorie

Einzelnachweise

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).
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 (Abstract im Electronic Research Archive for Mathematics)
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: Sum of positional games, Contrib. Theory of Games, II, Ann. Math. Stud., 28 (1953), S. 291-301 (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)

Literatur

• John Horton Conway: Über Zahlen und Spiele. Braunschweig, 1983, ISBN 3528084340
• Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: Gewinnen. Braunschweig, 1985/86, 4 Bände, ISBN 3528085312, ISBN 3528085320, ISBN 3528085339, ISBN 3528085347
• Elwyn R. Berlekamp, David Wolfe: Mathematical Go, Chilling Gets the Last Point. 1994, ISBN 1568810326
• Jörg Bewersdorff: Glück, Logik und Bluff: Mathematik im Spiel - Methoden, Ergebnisse und Grenzen, Vieweg+Teubner Verlag, 5. Auflage 2010, ISBN 3834807753, doi:10.1007/978-3-8348-9696-4 (Kapitel 2.4 bis 2.9)

Weblinks

• Go und Mathematik