Spiel mit perfekter Information, manchmal auch Spiel mit vollkommener Information genannt,Christian Rieck: Spieltheorie, Gabler, Wiesbaden 1993, ISBN 3-409-16801-X, S. 95. ist ein Begriff der mathematischen Spieltheorie. Demnach besitzt ein Spiel perfekte Information, wenn jedem Spieler zum Zeitpunkt einer Entscheidung stets das vorangegangene Spielgeschehen, d. h. die zuvor getroffenen Entscheidungen seiner Mitspieler sowie die zuvor getroffenen Zufallsentscheidungen, bekannt sind.Walter Schlee, Einführung in die Spieltheorie: mit Beispielen und Aufgaben, ISBN 3-528-03214-6, S. 95
Unter den Gesellschaftsspielen besitzen die meisten klassischen Brettspiele perfekte Information. Beispiele sind Go, Schach, Dame, Mühle, Halma, Nim und Mancala als Zweipersonenspiele oder auch Solitär und SameGame als Solitairespiel. Auch Spiele mit Zufallseinfluss wie Backgammon und Mensch ärgere Dich nicht, letzteres unabhängig von der Anzahl der Spieler, besitzen perfekte Information.
Ein Spiel ohne perfekte Information wird auch als Spiel mit imperfekter Information bezeichnet. Beispiele sind Kartenspiele wie Skat und Poker, weil dort jeder Spieler nur seine eigenen Karten kennt. Auch ein Spiel mit gleichzeitigen Zügen wie Schere, Stein, Papier ist kein Spiel mit perfekter Information, da dem sich entscheidenden Spieler die simultan erfolgende Entscheidung des Kontrahenten nicht bekannt ist. Insofern sind Informationsstände, die bezogen auf die Spieler asymmetrisch sind, kennzeichnend für Spiele mit imperfekter Information.
Eigenschaften 1912 bewies Ernst Zermelo, dass ein endliches Zwei-Personen-Nullsummenspiel mit perfekter Information und ohne Zufallseinfluss ein eindeutig bestimmtes Spielergebnis besitzt, und zwar in dem Sinn, dass der eine Spieler mindestens dieses Ergebnis unabhängig von der Spielweise des Kontrahenten erzwingen kann, während es dem Kontrahenten möglich ist, ein noch höheres Ergebnis zu verhindern.E. Zermelo: Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proceedings of the Fifth Congress of Mathematics, Vol. II, Cambridge 1913, Für das von Zermelo beispielhaft betrachtete Schachspiel bedeutet dies konkret, dass Schach entweder wie bei einer Problemstellung Weiß eine Gewinnstrategie erlaubt, oder aber Schwarz eine solche Gewinnstrategie besitzt, oder aber beide Spieler für sich jeweils mindestens ein Remis erzwingen können. Man nennt solche Spiele auch determiniert.
Angewendet auf eine Hin- und Rückpartie mit vertauschten Farben hat Zermelos Satz zur Konsequenz, dass ein Spieler mit fehlerfreiem Spiel mindestens ein ausgeglichenes Gesamtergebnis erzwingen kann – aber auch nicht mehr, wenn der Kontrahent ebenfalls fehlerfrei spielt.
Das bei beidseitig fehlerfreiem Spiel entstehende Spielergebnis wird als Wert des Spiels bezeichnet. Seine praktische Bestimmung kann für ein gegebenes Spiel sehr schwierig sein, auch wenn mit dem Minimax-Algorithmus theoretisch immer eine Berechnungsmöglichkeit besteht. Zahlreiche Spiele, darunter Dame, Mühle und Vier gewinnt, sind mittlerweile vollständig gelöst und die entsprechenden Strategien sind bekannt. Für einige Spiele wie zum Beispiel Hex sind nur die Werte der Anfangsposition aufgrund von Symmetrieüberlegungen bestimmbar, ohne dass man zugehörige Strategien kennt.
Spiele einer speziellen Unterklasse werden innerhalb der sogenannten Kombinatorischen Spieltheorie untersucht.
Für ein endliches Zwei-Personen-Nullsummenspiel mit perfekter Information und Zufallseinfluss gilt Zermelos Satz analog in Bezug auf den Erwartungswert des Gewinns. Das heißt, ein Spieler besitzt eine Strategie, so dass der Erwartungswert seines Gewinns mindestens diesen Wert erreicht, während für seinen Kontrahenten eine Strategie existiert, welche die Gewinnerwartung des ersten Spielers auf maximal diesen Wert begrenzt. Folglich besitzt beispielsweise jede Position des Backgammon, das streng genommen auf eine endliche Länge begrenzt werden muss, einen eindeutig definierten Wert.
Für endliche Spiele mit perfekter Information, die mit mehr als zwei Personen gespielt werden oder die keinen Nullsummen-Charakter aufweisen, gilt Zermelos Satz nicht. Das heißt, für solche Spiele lassen sich im Allgemeinen keine objektiv besten Strategien finden. Allerdings existieren nach einem Satz von Harold Kuhn aus dem Jahr 1950 Gleichgewichte in reinen Strategien.H. W. Kuhn: Extensive games, Proceedings of the National Academy of Sciences of the USA, Band 36, 1950, S. 570–576 (online; PDF; 713 kB).
Die Eigenschaft der perfekten Information kann im Allgemeinen nicht aus der Normalform eines Spiels ersehen werden. Innerhalb der Extensivform, die ein Spiel auf Basis eines gerichteten Graphen darstellt, wird die perfekte Information durch einelementige Informationsmengen charakterisiert.
Zufallsfreie endliche Spiele mit 2 Spielern ohne Unentschieden Zermelos Satz gilt umso mehr für diejenigen unter den genannten Spielen, bei denen ein Unentschieden nicht vorkommen kann. Bei diesen endlichen Zwei-Personen-Nullsummenspielen mit perfekter Information ohne Zufallseinfluss und Unentschieden folgt aus seinem Satz die Aussage: Eine Spielstellung gehört zu einer von genau zwei Kategorien: Z-Stellung (von „Zwang“): Aus einer Z-Stellung muss immer eine C-Stellung gemacht werden. C-Stellung (von „Chance“): Aus einer C-Stellung kann immer eine Z-Stellung gemacht werden. Zermelos Argument ist allerdings ein mengentheoretisches Existenzargument und enthält keinen Algorithmus zur Kategorisierung der Stellungen eines bestimmten Spiels.
Wie oben erwähnt, liefert der Minimax-Algorithmus, der zu den graphentheoretischen Vorgehensweisen zu rechnen ist, zu jeder Stellung einen sie kategorisierenden Wert. Im Folgenden sollen jedoch weniger aufwändige Algorithmen und Kriterien vorgestellt werden.
Die Kategorisierung der Stellungen lässt sich bei kleinen Tableaus mit Bleistift und Papier erarbeiten, was der graphentheoretischen Kategorisierung entspricht. Hat man sich so einen ersten Eindruck verschafft, kann es gelingen, hieraus eine numerische Kategorisierung zu entwickeln.
Das Nim-Spiel (s. u.) wurde 1935 von Roland SpragueRoland P. Sprague: Über mathematische Kampfspiele, Tôhoku Mathematical Journal, 41 (1935), S. 438–444 (online). und unabhängig davon 1939 von Patrick Michael GrundyPatrick M. Grundy: Mathematics and games, Eureka. 27 (1940), S. 9–11 (). detailliert untersucht und zum Paradebeispiel dieser Art von Spielen gemacht (siehe auch Satz von Sprague-Grundy). Insofern markiert es einen Ausgangspunkt der mathematischen Spieltheorie.
Im genannten Papier von Grundy heißt die Z-Stellung «W» (für winning) und die C-Stellung «L» (für losing); bei Berlekamp (für negativ) bzw. (für positiv); bei Wythoff «kalt» bzw. «heiß». Es geht um die Kennzeichnung einer Stellung und nicht eines Zuges, was die Z- und C-Sprechweise am ehesten zum Ausdruck bringt.
Beispiele Eins oder zwei Dieses Streichholzspiel ist eines der einfachsten:
Zwischen zwei Spielern liegt ein Haufen Streichhölzer. Beide Spieler nehmen abwechselnd ein oder zwei Hölzchen. Wer das letzte Hölzchen nimmt, gewinnt (siehe Eins oder zwei und Bachet’sches Spiel).
Man kann die Regel auch abändern, indem derjenige verliert, der das letzte Hölzchen nehmen muss.
Wythoffs Spiel Beim „Spiel von Wythoff“ (auch: „Wythoffs Nim“) entnehmen 2 Spieler abwechselnd von 2 Stapeln Gegenstände, und zwar von einem der beiden Stapel oder von beiden, dann aber gleich viele von jedem Stapel. Das Spiel endet, wenn ein Spieler den letzten Gegenstand entnimmt – womit er das Spiel gewinnt.
Das Spiel wurde von diesem niederländischen Mathematiker im Jahr 1907 mathematisch analysiert,W. A. Wythoff: A modification of the game of Nim, Nieuw Archief voor Wiskunde. Tweede reeks 7, 1907, S. 199–202 soll aber laut Martin Gardner in China unter dem Namen 捡石子 jiǎn shízǐ („Steine nehmen“) gespielt worden sein.Wythoffs Spiel auf Cut-the-knot (zitiert das Buch von Martin Gardner Penrose Tiles to Trapdoor Ciphers)
Beim Spiel von Rufus Isaacs (zitiert aus BergeClaude Berge, a. a. O., S. 308.) markieren die Spieler im I. Quadranten der Ebene mit ganzzahligem Gitter (in Formeln ) abwechselnd einen Knoten, wobei sich der Nachfolgeknoten vom Vorgängerknoten aus gesehen auf einer gleichen Koordinate (waagerecht oder senkrecht) oder der Winkelhalbierenden jeweils in Richtung Ursprung befinden muss. Der Spieler, der als Erster den Ursprung erreicht, hat gewonnen. Die Anfangsstellung wird ausgelost.
Die beiden Spielregeln sind äquivalent. Allerdings eignet sich die graphische Auffassung besonders gut zur Darstellung des graphentheoretischen Algorithmus.
Nim Beim Nim-Spiel sind mehrere Reihen mit Streichhölzern vorhanden. Zwei Spieler nehmen abwechselnd Streichhölzer aus einer der Reihen weg. Wie viele sie nehmen, spielt keine Rolle; es muss mindestens ein Streichholz sein und es dürfen bei einem Zug nur Streichhölzer einer einzigen Reihe genommen werden. Derjenige Spieler, der den letzten Zug macht – also die letzten Streichhölzer wegnimmt – gewinnt.
Misère-Nim
Der Spieler, der den letzten Zug macht (das letzte Streichholz nimmt), hat nicht gewonnen, sondern verloren. Diese Regel heißt Misère-Regel.
Das Nim-Spiel Marienbad, das durch den Film Letztes Jahr in Marienbad von Alain Resnais bekannt wurde, ist eine Misère-Variante.
Hex Das strategische Brettspiel Hex ist ein nicht „neutrales“ (engl. impartial) Spiel, da die 2 Spieler, genannt „Rot“ und „Blau“, nur Züge mit Steinen ihrer Farbe machen können. Als Spiel dieses Typs kann es nicht mit dem Satz von Sprague-Grundy analysiert werden.
Für Spielregel etc. sei auf den
verwiesen. In diesem Artikel soll nur dargelegt werden, dass sich die Stellungen graphentheoretisch genauso kategorisieren lassen wie bei den anderen determinierten Spielen.
Graphentheoretische Kategorisierung Die Stellungen lassen sich für jedes (endliche) Tableau in einem gerichteten Graphen darstellen mit Knoten für die Stellungen und Bögen (gerichteten Kanten) für die möglichen Züge. D. h. ein einzelner möglicher Zug wird durch einen Bogen repräsentiert, der von einer direkten Vorgänger-Stellung zu einer direkten Nachfolger-Stellung führt, in Zeichen Dieser Graph spiegelt die Spielregel eingeschränkt auf das Tableau genau wider.
Die eingangs aufgestellte Forderung nach Endlichkeit ist nur durch die Zyklenfreiheit des Graphen erfüllbar, der darum ein gerichteter azyklischer Graph (engl. DAG für directed acyclic graph) ist. In der so definierten Form werde er darum Stellungs-DAG genannt. Aus der Endlichkeit des Graphen selbst folgt, dass es Endknoten geben muss, also Knoten, zu denen es keine Nachfolgeknoten gibt.
Ferner nehmen wir an: Das Spiel soll zu Ende sein, wenn ein Spieler nicht mehr ziehen kann. Dieser soll dann auch der Verlierer sein. Falls es einen Endknoten mit Misère-Gewinnregel gibt, fügen wir an ihn einen Bogen zu einem zusätzlichen Knoten hinzu, nach welch letztem Zug der nächste Spieler nicht mehr ziehen kann, somit der korrekte Verlierer ist.
Die Darlegung des nachfolgenden Algorithmus vereinfacht sich durch eine strenge Totalordnung der Stellungen, die mit der Zugfolge kompatibel ist. Sie kann bspw. wie folgt konstruiert werden: Bei den genannten Spielen nimmt die Anzahl der Gegenstände im Tableau in jedem Zug entweder ab oder zu. Also nimmt man diese Anzahl als höchstrangiges Kriterium in einer lexikographischen Ordnung . Nachrangige Kriterien müssen dafür sorgen, dass verschiedene Stellungen als größer resp. kleiner herauskommen, was immer möglich ist. Eine solche Totalordnung stellt sicher, dass aus immer folgt.
Algorithmus:Claude Berge, a. a. O., S. 296. Wir beginnen beim Minimum der gewählten Totalordnung – es muss eine Senke und Endstellung sein. Wir arbeiten den Stellungsraum die Totalordnung aufsteigend (gegen die Richtung des Pfeils quasi „kausal rückwärts“) und schrittweise in Richtung ihres Maximums ab.