Quelltext der Seite Spiel mit perfekter Information

'''Spiel mit perfekter Information''', manchmal auch '''Spiel mit vollkommener Information''' genannt,<ref>[[Christian Rieck]]: ''Spieltheorie'', Gabler, Wiesbaden 1993, ISBN 3-409-16801-X, S. 95.</ref> ist ein Begriff der mathematischen [[Spieltheorie]]. Demnach besitzt ein [[Spiel (Spieltheorie)|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.<ref>Walter Schlee, ''Einführung in die Spieltheorie: mit Beispielen und Aufgaben'', ISBN 3-528-03214-6, S. 95</ref>

Unter den  [[Gesellschaftsspiel]]en besitzen die meisten klassischen [[Brettspiel]]e perfekte Information. Beispiele sind [[Go (Spiel)|Go]], [[Schach]], [[Dame (Spiel)|Dame]], [[Mühle (Spiel)|Mühle]], [[Halma]], [[Nim-Spiel|Nim]] und [[Mancala]] als Zweipersonenspiele oder auch [[Solitär (Brettspiel)|Solitär]] und [[SameGame]] als Solitairespiel. Auch Spiele mit [[Zufall]]seinfluss 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 [[Kartenspiel]]e 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.<ref>E. Zermelo: ''Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels'', Proceedings of the Fifth Congress of Mathematics, Vol. II, Cambridge 1913, {{Webarchiv|url=www.mathunion.org/ICM/ICM1912.2/Main/icm1912.2.0501.0504.ocr.pdf|wayback=20160324182855|text=S. 501–504}}</ref> Für das von Zermelo beispielhaft betrachtete Schachspiel bedeutet dies konkret, dass Schach entweder
* wie bei einer [[Schachproblem|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 [[Determiniertheit (Mengenlehre)|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 (Spiel)|Dame]], [[Mühle (Spiel)|Mühle]] und [[Vier gewinnt]], sind mittlerweile [[Gelöste Spiele|vollständig gelöst]] und die entsprechenden Strategien sind bekannt. Für einige Spiele wie zum Beispiel [[Hex (Spiel)|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 [[Kombinatorische Spieltheorie|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 [[Nash-Gleichgewicht|Gleichgewichte]] in [[Reine Strategie|reinen Strategien]].<ref>[[Harold Kuhn|H. W. Kuhn]]: ''Extensive games'', Proceedings of the National Academy of Sciences of the USA, Band 36, 1950, S. 570–576 ([http://www.pnas.org/content/36/10/570.full.pdf online]; PDF; 713&nbsp;kB).</ref>

Die Eigenschaft der perfekten Information kann im Allgemeinen nicht aus der [[Normalform (Spieltheorie)|Normalform]] eines Spiels ersehen werden. Innerhalb der [[Extensivform]], die ein Spiel auf Basis eines gerichteten [[Graph (Graphentheorie)|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 [[Algorithmus|Algorithmen]] und Kriterien vorgestellt werden.

Die Kategorisierung der Stellungen lässt sich bei kleinen Tableaus mit Bleistift und Papier erarbeiten, was der [[#Graphentheoretische Kategorisierung|graphentheoretischen Kategorisierung]] entspricht. Hat man sich so einen ersten Eindruck verschafft, kann es gelingen, hieraus eine [[#Numerische Kategorisierung|numerische Kategorisierung]] zu entwickeln.

Das Nim-Spiel ([[#Nim|s.&nbsp;u.]]) wurde 1935 von [[Roland Sprague]]<ref name="Sprague">Roland P. Sprague: ''Über mathematische Kampfspiele'', Tôhoku Mathematical Journal, 41 (1935), S. 438–444 ([https://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_article online]).</ref>
und unabhängig davon 1939 von [[Patrick Michael Grundy]]<ref name="Grundy">Patrick M. Grundy: ''Mathematics and games'', Eureka. 27 (1940), S. 9–11 ({{Webarchiv|url=http://www.archim.org.uk/eureka/27/games.html |wayback=20070927192024 |text=online }}).</ref> 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|Berlekamp]] {{nowrap|«<math>\mathcal{N}</math>-Position»}} (für ''negativ'') bzw. {{nowrap|«<math>\mathcal{P}</math>-Position»}} (für ''positiv'');
bei [[#Wythoffs Spiel|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 [[Streichhölzer wegnehmen#Eins oder zwei|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 „[[#Wythoffs Spiel 2|Spiel]] von [[Willem Abraham Wijthoff|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 [[Niederlande|niederländischen]] Mathematiker im Jahr 1907 mathematisch analysiert,<ref>[[Willem Abraham Wijthoff|W. A. Wythoff]]: ''[https://archive.org/stream/nieuwarchiefvoo03genogoog#page/n219/mode/2up A modification of the game of Nim]'', Nieuw Archief voor Wiskunde. Tweede reeks 7, 1907, S. 199–202</ref> soll aber laut [[Martin Gardner]] in China unter dem Namen 捡石子 ''jiǎn shízǐ'' („Steine nehmen“) gespielt worden sein.<ref>[https://www.cut-the-knot.org/pythagoras/withoff.shtml Wythoffs Spiel auf Cut-the-knot] (zitiert das Buch von Martin Gardner [[Martin Gardner#Sammlung von Scientific American-Kolumnen|Penrose Tiles to Trapdoor Ciphers]])</ref>

Beim Spiel von [[Rufus Isaacs (Mathematiker)|Rufus Isaacs]] (zitiert aus Berge<ref>Claude Berge, a.&thinsp;a.&thinsp;O., S. 308.</ref>) markieren die Spieler im [[Kartesisches Koordinatensystem#Das Koordinatensystem im zweidimensionalen Raum|I. Quadranten]] der Ebene mit ganzzahligem Gitter ([[natürliche Zahl#Bezeichnungskonventionen|in Formeln <math>\mathbb{N}_0 \times \mathbb{N}_0</math>]]) 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.

{{Hauptartikel|Nim-Spiel}}

==== Misère-Nim ====
{{Anker|Misère-Regel}}

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 (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 (Spiel)|Hex]] ist ein ''nicht'' [[Kombinatorische Spieltheorie#Sonderfall: Neutrale Spiele|„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

{{Hauptartikel|Hex (Spiel)}}

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 [[Gerichteter Graph|gerichteten Graphen]] darstellen mit [[Knoten (Graphentheorie)|Knoten]] für die Stellungen und [[Kante (Graphentheorie)|Bögen]] (gerichteten [[Kante (Graphentheorie)|Kanten]]) für die möglichen Züge. D.&nbsp;h. ein einzelner möglicher Zug wird durch einen Bogen repräsentiert, der von einer [[Vorgänger (Graphentheorie)|direkten Vorgänger]]-Stellung <math>u</math> zu einer [[Nachfolger (Graphentheorie)|direkten Nachfolger]]-Stellung <math>v</math> führt, in Zeichen <math>u\to v.</math> Dieser Graph spiegelt die Spielregel [[Einschränkung|eingeschränkt]] auf das Tableau genau wider.

Die eingangs aufgestellte Forderung nach Endlichkeit ist nur durch die [[Zyklus (Graphentheorie)|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-Nim|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 [[Ordnungsrelation#Strenge Totalordnung|strenge Totalordnung]] <math>\succ</math> 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 [[Lexikographische Ordnung|lexikographischen Ordnung]] <math>\succ</math>. 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 <math>u\to v</math> immer <math>u\succ v</math> folgt.

{{Anker|Kern-Algorithmus}}
Algorithmus:<ref>Claude Berge, a.&thinsp;a.&thinsp;O., S. 296.</ref>
: Wir beginnen beim Minimum der gewählten Totalordnung – es muss eine [[Senke (Graphentheorie)|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.
: Kommen wir zu einem unmarkierten Knoten <math>v</math>, dann markieren wir ihn als Z-Knoten (=:&nbsp;&nbsp;''Z-Aktion''(<math>v</math>)). Danach markieren wir alle seine direkten Vorgänger <math>u</math> (also die <math>u\to v</math>) als C-Knoten (=:&nbsp;&nbsp;''C-Aktion''<math>(v,u)</math>).

Durch das schrittweise Vorgehen die Totalordnung „aufwärts“ ist sichergestellt, dass wir den ganzen Stellungsraum absuchen. Schon markierte Knoten bleiben ungeändert; es ist auch sonst keine Aktion bei ihnen erforderlich.

Beweis des Algorithmus und damit erneuter Beweis der Aussage:
: Ist der Knoten <math>v</math> ein Z-Knoten, dann sind alle seine direkten Nachfolger <math>w</math> (also die mit <math>v\to w</math>) C-Knoten. Wäre nämlich ein Z-Knoten <math>w</math> dabei, hätte <math>v</math> als direkter Vorgänger von <math>w</math> von <math>w</math> aus in einer ''C-Aktion''(<math>w,v</math>) als C-Knoten markiert werden müssen. Und unmarkiert kann ein Nachfolger <math>w</math> auch nicht sein, denn dann hätte eine ''Z-Aktion''(<math>w</math>) wegen der „Zeitumkehr“ eigentlich vor der ''Z-Aktion''(<math>v</math>) kommen müssen.

: Seine direkten Vorgänger <math>u</math> (also die <math>u\to v</math>) können vor der ''C-Aktion''(<math>v,u</math>) nur unmarkiert oder C-Knoten gewesen sein. Denn <math>u</math> kann nicht Z-Knoten sein, da wegen <math>u\succ v</math> die ''Z-Aktion''(<math>v</math>) allemal vor einer ''Z-Aktion''(<math>u</math>) geschähe.

{{Anker|Kern}}
In der graphentheoretischen Sprechweise haben wir zu einem gerichteten azyklischen Graphen einen [[Kern (Graphentheorie)|Kern]] (engl. ''kernel'', frz. ''noyau'') konstruiert, d.&nbsp;i. eine [[Stabile Menge|stabile]] Untermenge von Knoten, die gleichzeitig [[Dominierende Menge|dominierend]] ist.
Der Kern ist die Menge der Z-Knoten. Er existiert immer<ref>Richardson (1953), s. Claude Berge, a.&thinsp;a.&thinsp;O., S. 299.</ref> und ist eindeutig.<ref>Claude Berge, a.&thinsp;a.&thinsp;O., S. 298.</ref> Die Stabilität steht für den Zwang, von einem Z-Knoten zu einem C-Knoten gehen zu ''müssen'', und die Dominanz für die Chance, von einem C-Knoten zu einem Z-Knoten gehen zu ''können''.

Der angeführte Algorithmus kann – zumindest ''theoretisch'' – von jeder Stellung klären, ob sie eine Gewinn- oder Verlustposition ist. Allerdings kann die Größe des Stellungs-DAG, der ja noch größer ist als der Stellungsraum, eine „praktische“ Implementierung unmöglich machen.

Die untenstehenden Graphiken stellen die Ergebnisse dar, die mit dem geschilderten Algorithmus gewonnen werden können. Dabei sind die von den (grünen) Z-Knoten ausgehenden ''C-Aktion''en durch rote „Strahlen“ dargestellt, die die von ihnen getroffenen Knoten zu (roten) C-Knoten machen.

[[Datei:GameWythoff.svg|140px|mini|„Kern“ des Spiels von Wythoff]]

==== Eins oder zwei ====
Auch das triviale Spiel [[#Eins oder zwei|Eins oder zwei]], dessen optimale Strategie ohne viel Mathematik sofort zu verstehen ist, lässt sich mit dem obigen Algorithmus behandeln: Der Stellungsraum ist ein Intervall <math>\left[0,n\right]</math> von nicht-negativen [[Ganze Zahl|ganzen Zahlen]], die die augenblickliche Anzahl der Streichhölzer darstellen.

==== Wythoffs Spiel ====
Bei Wythoffs Spiel kommen die Eigenschaften des ''Kerns'' gut heraus. Die schwarze Skizze der Spielregel in der unteren rechten Ecke symbolisiert eine Art [[Minkowski-Diagramm#Lichtgeschwindigkeit und Kausalität|„Zukunftslichtkegel“]], dem die „Vergangenheitslichtkegel“ entsprechen, die von den Z-Knoten (grün) ausgehen. Wird ein C-Knoten (rot) als Anfangsstellung ausgelost, kann der anziehende Spieler den Sieg erzwingen. Bei einem Z-Knoten (grün) als Anfangsstellung kann der Anziehende nur einen C-Knoten erreichen, wonach sein Gegenspieler den Sieg erzwingen kann.

[[Datei:nim+misere-Spiel.svg|115px|mini|2 kolorierte Stellungsräume des Nim-Spiels mit 3 Reihen]]

==== Nim ====
Den Stellungs-DAG bettet man bei Nim in naheliegender Weise in das [[Intervall (Mathematik)#n-dimensionale Intervalle|<math>n</math>-dimensionale Intervall]] <math>\left[0,r_1\right]\times\left[0,r_2\right]\times\ldots\times\left[0,r_n\right]</math> der Stellungen ein, wo <math>n</math> die Anzahl der Reihen ist und <math>r_i</math> die Anzahl der Streichhölzer in der <math>i</math>-ten Reihe. Eine Spielstellung entspricht dann einem Knoten mit den momentanen Anzahlen von Streichhölzern als seinen Koordinaten. Die möglichen Züge (Bögen) sind parallel zu genau 1 [[Koordinatensystem|Koordinate]] mit Richtung auf den [[Koordinatensystem|Ursprung]] zu.

Eine jede der [[Lexikographische Ordnung|lexikographischen Ordnungen]] ist eine mit der Zugfolge kompatible Totalordnung. Es gibt nur eine Endstellung, welche mit dem Ursprung zusammenfällt.

Die Graphik rechts zeigt in 2 Diagrammen die Z-Stellungen (grüne Knoten) und die C-Stellungen (rote Knoten) für die Standard- (oben) und die Misère-Regel (unten) des [[Nim-Spiel]]s – jeweils der Einfachheit halber in einem Tableau von 3 Reihen (Achsen) zu 5, 4 und 1 Hölzchen. In beiden Diagrammen ist die Reihe mit 1 Streichholz durch 2 übereinanderliegende Ebenen, die 0- und die 1-Ebene dargestellt, so dass die 0-Ebene effektiv dem Fehlen der dritten Reihe und die 1-Ebene dem Vorhandensein 1 Hölzchens in dieser Reihe entspricht.

Der Ursprung <math>(0,0,0)</math> befindet sich jeweils links unten vorn.

Gültige Züge sind im Graphen Bewegungen auf genau einer der Koordinatenachsen, d.&nbsp;h. entweder waagerecht oder senkrecht oder auch in der dritten Richtung von der 1-Ebene auf die 0-Ebene, jeweils näher zum Ursprung hin.

Der Algorithmus beginnt am Ursprung, der bei der Standard-Regel grün, bei der Misère-Regel rot eingefärbt wird.

Es fällt auf, dass zwischen den 2 Nim-Varianten sich die Farben nur bei den Knoten ganz nahe am Ursprung unterscheiden.

Die Gewinnstrategie bei 2 Reihen für die Standard-Regel lautet: Wenn du kannst, ziehe mit deinem Gegenspieler gleich.

Bei 3 und mehr Reihen wird es komplizierter, wie schon die 1-Ebenen im Diagramm andeutungsweise zeigen. Die allgemeineren Fälle, insbesondere die mit mehr als 3 Reihen, sind noch schwieriger darzustellen.

[[Datei:Hex board 11x11.svg|mini|Hex-Brett mit 11 mal 11 Feldern]]

==== Hex ====
Besteht das rhombenförmige Brett aus <math>n</math> mal <math>n</math> sechseckigen Feldern, dann gibt es <math>\binom{n^2}{\big\lfloor \tfrac{n^2}2 \big\rfloor}</math> Endstellungen und gegen <math>3^{n^2}</math> Stellungen insgesamt. Der geschilderte Algorithmus ist somit nur für sehr kleine <math>n</math> praktikabel.

Als eine mit der Zugreihenfolge kompatible Totalordnung kann die [[lexikographische Ordnung]] von <math>(f,a_1,\ldots,a_{n^2})</math> dienen mit <math>f\in\left[0,n^2\right]</math> als Zahl der freien Felder in der höchsten lexikographischen Priorität, <math>i\in\left[1,n^2\right]</math> als Index eines Feldes <math>F_i</math> und

:{| class="left" style="text-align:left;"
|-
| rowspan="3" align="left" | <math>a_i:=
\begin{cases}
\\
\\
\\
\end{cases}
</math> || <math>0</math>, falls <math>F_i</math> ''frei'',
|-
| <math>1</math>, falls <math>F_i</math> ''rot'',
|-
| <math>2</math>, falls <math>F_i</math> ''blau'',
|}

bei der bspw. der Stellung (11² = 121, ''frei'', ''frei'', ''frei'', …) die Stellung (120, ''rot'', ''frei'', ''frei'', ''frei'', …) und dieser die Stellung (119, ''rot'', ''frei'', ''blau'', ''frei'', ''frei'', ''frei'', …) folgen kann.

Im Stellungs-DAG alternieren die Züge an den roten Steinen mit denen an den blauen.
Der ''Kern'' des Stellungs-DAG enthält Stellungen mit sowohl Rot wie Blau am Zug. Gut für Rot ist immer der erste Zug in die Mitte – aber er ist nicht der einzige gute. Schlecht ist der erste Zug in eine spitze Ecke, dann kann Blau mit seinem ersten Zug in die Mitte eine Z-Stellung erzeugen.

=== Minimax-Algorithmus ===
[[Datei:MiniMax on game 1or2.svg|240px|mini|Minimax am Spiel [[Streichhölzer wegnehmen#Eins oder zwei|Eins oder zwei]]<br />(Die dickeren Kanten sind die strategischen.)]]

Im Unterschied zum Stellungs-DAG des [[#Graphentheoretische Kategorisierung|obigen Algorithmus]] benötigt der Minimax-Algorithmus einen Spielbaum, d.&nbsp;h. eine auf [[Gewurzelter Baum|Wurzelbaum]] expandierte Version des Stellungs-DAG.

==== Eins oder zwei ====
Anhand des sehr einfachen Spiels [[#Eins oder zwei|Eins oder zwei]] sei der [[Minimax-Algorithmus]] erläutert.

In der nebenstehenden Abbildung ist der Spielbaum für ein Tableau des Spiels mit 6 Streichhölzern expandiert. Aus weiter unten angeführten Gründen seien die beiden Spieler „Maximierer“ und „Minimierer“ genannt. Die Knoten (Stellungen) und Kanten (Züge) sind <span style="color:#00FF00;">''grün''</span> für den Maximierer und <span style="color:#FF5555;">''rot''</span> für den Minimierer. Die Knoten enthalten eine Zahl und ein Vorzeichen: die Zahl ist die Anzahl der Streichhölzer und das Vorzeichen der [[Minimax-Algorithmus#Bewertungsfunktion|Wert der Stellung]] mit der Bedeutung:
{| style="margin-left:20px;"
| <code>+</code> &nbsp; || der Maximierer kann den Sieg erzwingen
|-
| <code>−</code>|| der Minimierer kann den Sieg erzwingen
|}
Der Algorithmus beginnt bei den [[Blatt (Graphentheorie)|Blättern des Baums]], die alle für eine Endstellung von 0 Streichhölzern stehen. Da der Spieler, der am Zug wäre, verloren hat, erhält ein Blatt mit Maximierer am Zug die Markierung <code>grün&nbsp;0−</code>, ein anderes <code>rot&nbsp;0+</code>. Ein grüner Knoten erhält als Spielwert das Maximum der Spielwerte der Nachfolgeknoten bzw. ein roter Knoten deren Minimum; daher der Name Minimax und auch die Namen der Spieler. <small>Sind die Werte der Nachfolgeknoten unterschiedlich, ist der strategisch optimale Zug verstärkt gezeichnet. Bei den Stellungen mit <code>grün&nbsp;−</code> und <code>rot&nbsp;+</code> ist es der den Zug abgebende Spieler, der den Sieg errungen hat oder erzwingen kann. (Es handelt sich um [[#Zufallsfreie endliche Spiele mit 2 Spielern ohne Unentschieden|Z-Stellungen]]. Da der Minimax-Algorithmus immer zu einem Ergebnis kommt, ist schon durch seine Anwendbarkeit die Existenz und Eindeutigkeit eines Kerns des Stellungs-DAG bewiesen.)</small>

Verglichen mit dem [[#Graphentheoretische Kategorisierung|obigen Algorithmus]] ist der Minimax-Algorithmus etwas aufwändiger:
* Er lässt beliebige reelle Spielwerte zu, auch wenn bei den ''zufallsfreien endlichen Spielen mit 2 Spielern ohne Unentschieden'' nur die 2 Werte  <code>+</code>&nbsp;(:=&nbsp;+1) und  <code>−</code>&nbsp;(:=&nbsp;−1) gebraucht werden.
* Im Beispiel enthält der Spielbaum Wiederholungen, z.&nbsp;B. 8-mal die Stellung mit 1, 5-mal die mit 2, 3-mal die mit 3 und 2-mal die mit 4 Streichhölzern.
* Die Knoten des Stellungs-DAG sind die Knoten in der Spalte ganz links. Sein [[#Kern|Kern]] wird gebildet von den Knoten mit <code>grün&nbsp;−</code> und <code>rot&nbsp;+</code>.
Beide Algorithmen beginnen bei den Blättern und arbeiten sich zur Wurzel hoch, also entgegen der Richtung des Spiels.

==== Die anderen Spiele ====
Bei den anderen in diesem Artikel beschriebenen Spielen ergeben sich Einsparungen von Spielbaum zu Stellungs-DAG schon dadurch, dass es eine beliebig große Anzahl von Zügen gibt, die zur gleichen Stellung führen. Diese muss im Baum wiederholt werden, wogegen sie im DAG nur einmal vorkommt.<br />
Darüber hinaus vereinfacht sich bei den Spielen Nim und Wythoffs Spiel der Stellungs-DAG dadurch, dass die Züge mit gemeinsamem Ziel in einer einfachen linearen Ordnung zueinander stehen.

=== Numerische Kategorisierung ===
Unter numerischer Kategorisierung soll verstanden werden, dass es eine Formel gibt, die für jede Stellung anhand ihrer numerisierten Parameter klärt, ob sie eine Gewinn- oder Verlustposition ist. Gibt es die Formel, dann darf in der Sprechweise des Artikels [[Gelöste Spiele]] das Spiel als „stark gelöst“ bezeichnet werden.

==== Eins oder zwei ====
Die Z-Knoten beim Spiel [[#Eins oder zwei|Eins oder zwei]] sind genau die Stellungen, bei denen die Anzahl der Streichhölzer durch 3 teilbar ist; bei der zugehörigen Misère-Regel ≡ 1 [[Modulo|mod]] 3.

==== Wythoffs Spiel ====
Bei Wythoffs Spiel liegen die Z-Knoten auf den Koordinaten <math>\big( \lfloor n \Phi^2 \rfloor,\lfloor n \Phi \rfloor \big) </math> mit <math>n\ge 0</math> und <math> \Phi:=(1+\sqrt 5)/2</math>&nbsp;(Zahl des [[Goldener Schnitt|goldenen Schnitts]]) und dasselbe noch einmal an der Winkelhalbierenden gespiegelt.

Durch die Irrationalität von <math> \Phi \, </math> ergibt sich eine aperiodische unregelmäßige Verteilung.

==== Nim ====
Bezgl. der Formeln für die [[Nim-Spiel#Gewinnstrategie nach Bouton|Nim-Summen]] des Nim-Spiels und des Beweises ihrer Optimalität sei auf den Hauptartikel [[Nim-Spiel]] verwiesen. Die Z-Knoten des Graphen entsprechen Stellungen mit ''geraden'' Nim-Summen. Letztere kommen erst bei einer Anzahl ≥ 3 von Reihen, d.&nbsp;h. der Komposition mehrerer „Spiele“, richtig zum Tragen. In einer 2-dimensionalen Graphik ist das jedoch nur schwer deutlich zu machen.

==== Hex ====
Eine Strategie für Hex mit beliebig großem {{nowrap|''n''×''n''-Tableau}} ist nicht bekannt.
Es gibt aber Untersuchungen bis ''n''≤10 zu gewissen Eröffnungszügen.
Bei {{nowrap|''m''×''n''-Tableaus}} mit ''m''<''n'' gibt es für den Spieler, der den kürzeren Weg hat, eine Gewinnstrategie (s. [[Hex (Spiel)|Hex]]).

=== Fazit ===
Der graphentheoretische Algorithmus bestimmt den „Spielwert“ einer Stellung.
Im Sinne des Artikels [[Gelöste Spiele]] stellt er eine „schwache Lösung“ eines Spieles dar. 
Die Graphen sind naturgemäß stets endlich und damit zwar für den „Eigenbedarf“ des Spielers ggf. ausreichend. <small>Die Expansion des Stellungsgraphen ist häufig von [[exponentiell]]er Komplexität.</small> Sie liefern auch Anhaltspunkte für die numerischen Formeln, die aber sehr unterschiedlich sein können.
Von der mathematischen Warte aus sind die Formeln auf höheren Rängen anzusiedeln und bedürfen auch eines speziell auf sie zugeschnittenen Beweises.
Sie sind – bei geeigneten Möglichkeiten der Auswertung – als „starke Lösungen“ anzusehen.

Offensichtlich ist es nicht interessant, eines dieser Spiele zu spielen, wenn beide Spieler die optimale Strategie kennen, da dann Sieger und Verlierer von vornherein feststehen. Beim Hex-Spiel ist diese allerdings nur für kleine ''n'' effektiv bekannt. Tatsächlich steht der Gewinner genau dann von vornherein fest, wenn einer der beiden Spieler die optimale Strategie spielt und an eine C-Stellung gerät.

Da bei einer vorliegenden C-Stellung die Z-Stellungen unter den Nachfolgestellungen eine verschwindende Minderheit darstellen, hat ein perfekter Spieler, der bei einer Z-Stellung beginnen – also seinem Gegenspieler eine C-Stellung überlassen – muss, umso größere Gewinnchancen, je größer das Ausgangstableau ist und je mehr Fehlermöglichkeiten damit für den Gegenspieler bestehen. Und nach dem ersten Fehlgriff von dessen Seite ist er von der Straße des Sieges nicht mehr abzubringen.

== Literatur ==
* {{Literatur
   |Autor=[[Claude Berge]]
   |Titel=Graphs et hypergraphes
   |Verlag=Dunod
   |Ort=Paris
   |Datum=1970
   |Kapitel=Chapitre 14 Noyaux et fonctions de Grundy
   |Seiten=291–313
   |Sprache=fr}}
* [[Jörg Bewersdorff]]: ''Glück, Logik und Bluff: Mathematik im Spiel – Methoden, Ergebnisse und Grenzen.'' Springer Spektrum, 6. Auflage, Wiesbaden 2012, ISBN 978-3-8348-1923-9, [[doi:10.1007/978-3-8348-2319-9_2]], S. 95–245.
* {{Anker|Berlekamp}}[[Elwyn Berlekamp]], [[John Horton Conway]], [[Richard Kenneth Guy|Richard K. Guy]]: ''Gewinnen'', Braunschweig, 1985/86, 4 Bände, ISBN 3528085312, ISBN 3528085320, ISBN 3528085339, ISBN 3528085347 (engl. Original: ''Winning Ways for your Mathematical Plays.'', 2 Bände, ISBN 0120911019, ISBN 0120911027, aktualisierte Neuauflagen 2001 bis 2004).
* [[Godfrey Harold Hardy|G.H. Hardy]], E. M. Wright: ''An introduction to the theory of numbers.'' Fifth edition. The Clarendon Press, Oxford University Press, New York, 1979, S. 117–120.

== Einzelnachweise ==
<references />

== Siehe auch ==
* [[Satz von Fürstenberg-Sárközy#Anwendung|Nimm-ein-Quadrat-Spiel]]

[[Kategorie:Spieltheorie]]