Kombinatorische Spieltheorie
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.
Die mathematische Bedeutung der Kombinatorischen Spieltheorie resultiert daraus, dass eine Unterklasse der Spiele 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 Verallgemeinung der surrealen Zahlen.
| Inhaltsverzeichnis |
|
2 Sonderfall: Neutrale Spiele 3 Beispiel: Go 4 Siehe auch 5 Literatur 6 Weblinks |
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.
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 Sprague (1936) und Grundy (1940) gefunden, ansatzweise zuvor bereits von dem Schachweltmeister und Mathematiker Emanuel Lasker.
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.
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 (Berlekamp 1991). Es gibt allerdings auch einen alternativen Ansatz, der auf Milnor (1953), Hanner (1959) und Berlekamp (1996) zurückgeht. Dabei werden die Punktwertungen und deren Eigenschaften in Bezug auf die Komponenten einer (Endspiel-)Position direkt untersucht.
Siehe auch
SpieltheorieLiteratur
- 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. Wiesbaden, 2003, ISBN 3528269979 (Kapitel 2.4 bis 2.9)
Weblinks
