Kombinatorische Spieltheorie

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.

Inhaltsverzeichnis

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

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Spieltheorie — In der Spieltheorie werden Entscheidungssituationen modelliert, in denen sich mehrere Beteiligte gegenseitig beeinflussen. Die Spieltheorie versucht dabei unter anderem, das rationale Entscheidungsverhalten in sozialen Konfliktsituationen… …   Deutsch Wikipedia

  • Spieltheorie — I Spieltheorie,   den Wirtschafts und Sozialwissenschaften, insbesondere dem Operations Research zugeordnete mathematische Theorie zur Modellierung spezieller strategischer Entscheidungsprozesse (strategische Spiele). Basierend auf der… …   Universal-Lexikon

  • Unberechenbarkeit (Spieltheorie) — Die Unberechenbarkeit eines Spiels im spieltheoretischen Sinn entspricht der Ungewissheit, welcher die Spieler (und ggf. Zuschauer) eines Gesellschaftsspiels im Hinblick auf den Verlauf und das Resultat einer Partie ausgesetzt sind. Die Begriffe… …   Deutsch Wikipedia

  • Spieldarstellung — Bei einem Spiel im Sinne der Spieltheorie handelt es sich um ein mathematisches Modell zur Beschreibung von Vorgängen, in denen mehrere Akteure gegenseitig die Ergebnisse ihrer Entscheidung beeinflussen. Im Unterschied zur landläufigen Bedeutung… …   Deutsch Wikipedia

  • Surreale Zahlen — Die surrealen Zahlen bilden eine Klasse von Zahlen, die alle reellen Zahlen umfasst, sowie „unendlich große“ Zahlen, die größer sind als jede reelle Zahl. Dabei ist jede reelle Zahl von surrealen Zahlen umgeben, die ihr näher sind als jede andere …   Deutsch Wikipedia

  • Richard Guy — Richard Kenneth Guy (Juni 2005) Richard Kenneth Guy (* 30. September 1916 in Nuneaton, Warwickshire) ist ein britischer Mathematiker, er ist emeritierter Professor an der University of Calgary. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Richard K. Guy — Richard Kenneth Guy (Juni 2005) Richard Kenneth Guy (* 30. September 1916 in Nuneaton, Warwickshire) ist ein britischer Mathematiker, er ist emeritierter Professor an der University of Calgary. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Surreale Zahl — Die surrealen Zahlen bilden eine Klasse von Zahlen, die alle reellen Zahlen umfasst, sowie „unendlich große“ Zahlen, die größer sind als jede reelle Zahl. Dabei ist jede reelle Zahl von surrealen Zahlen umgeben, die ihr näher sind als jede andere …   Deutsch Wikipedia

  • Unicode-Block Verschiedene mathematische Symbole-B — Der Unicode Block Verschiedene mathematische Symbole B (2980–29FF, englisch Miscellaneous Mathematical Symbols B) enthält zahlreiche weitere mathematische Symbole und Operatoren. Weitere Blöcke mit mathematischen Symbolen sind der Unicode… …   Deutsch Wikipedia

  • Nimm — Das Nim Spiel ist ein Spiel mit vollständiger Information für zwei Spieler. Es ist ein beliebtes Beispiel der Spieltheorie, da es mit Papier und Bleistift vollständig analysiert werden kann. Inhaltsverzeichnis 1 Spielregel 1.1 Alternative Regeln… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”