ein-handwerker.de

Spiel mit perfekter Information

25.05.2012 @ 22:51, MerlIwBot,

Spiel mit perfekter Information, manchmal auch Spiel mit vollkommener Information genannt,Christian Rieck: Spieltheorie, Gabler, Wiesbaden 1993, ISBN 340916801X, 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 3528032146, S. 95

Unter den Gesellschaftsspielen besitzen die meisten Brettspiele perfekte Information. Beispiele sind Go, Schach, Dame, Mühle, 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 Bezug 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, S. 501-504.Auszüge daraus und Erläuterungen findet man bei 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, S. 94-102. 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.

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 ([http://www.pnas.org/content/36/10/570.full.pdf online]).

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

Ein endliches Zwei-Personen-Nullsummenspiel mit perfekter Information ohne Zufallseinfluss und Unentschieden ist Gegenstand der kombinatorischen Spieltheorie und ist ein „determiniertes“Zusammenfassung der Vorlesung Mathematische Logik Prof. Grädel RWTH (2005) ([http://s-inf.de/Skripte/MaLo.2004-WS-Graedel.(BvdH).Zusammenfassung.pdf Online]) Spiel, hat also eine eindeutige optimale Strategie, die auf folgender Vermutung („intuitively clear“Patrick M. Grundy: Mathematics and games, Eureka. 27 (1940), S. 9-11 ([http://www.archim.org.uk/eureka/27/games.html Online]).) beruht:
: Die Spielstellungen lassen sich in genau zwei Kategorien einteilen:
:# die Z-Stellung (von „Zwang“): Aus einer Z-Stellung muss immer eine C-Stellung gemacht werden.

:# die C-Stellung (von „Chance“): Aus einer C-Stellung kann immer eine Z-Stellung gemacht 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 R. SpragueRoland P. Sprague: Über mathematische Kampfspiele, Tôhoku Mathematical Journal, 41 (1935), S. 438-444 ([http://www.journalarchive.jst.go.jp/english/jnlabstract_en.php?cdjournal=tmj1911&cdvol=41&noissue=0&startpage=438 Online]).

und unabhängig davon 1939 von P. Grundy 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“).

Es müsste jedoch dazugesagt werden, dass dies die Sicht des den Zug abgebenden Spielers ist. Es geht aber um die Kennzeichnung einer Stellung, nicht eines Zuges, wie es die Z- und C-Sprechweise direkt 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.

Das Spiel von Rufus Isaacs

Im 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 $\backslash mathbb\{N\}\_0\; \backslash times\; \backslash mathbb\{N\}\_0$) 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.

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, 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 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 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 u zu einer direkten Nachfolger-Stellung v führt, in Zeichen u→v. Dieser „Spielgraph“ spiegelt die Spielregel eingeschränkt auf das Tableau genau wider.

Die eingangs aufgestellte Forderung nach Endlichkeit ist nur durch die Zyklenfreiheit des Spielgraphen erfüllbar, der darum ein gerichteter azyklischer Graph (engl. DAG für directed acyclic graph) ist.

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, mit welchem Zug der Gewinner abschließend den Sieg einheimst.

Die transitive Hülle eines gerichteten azyklischen Graphen ist eine Striktordnung (= „strenge Halbordnung“) ≻, wobei u ≻ v bedeuten soll, dass es einen gerichteten Weg von u nach v gibt, d. h. m (≥ 0) Zwischenknoten w₁, … , w_m und Zwischenzüge mit u→w₁→ … →w_m→v. Die Richtung des Zeichens ≻ zeigt somit in die des Pfeils →; anders ausgedrückt: die Wege des Spiels führen letztendlich zu einem der Minima der Striktordnung ≻.

Wir betten die Striktordnung ≻ in eine strenge Totalordnung ein und benennen diese wieder mit ≻. Wegen des Einbettens siehe lineare Erweiterung einer Striktordnung. Das Ergebnis ist eine mit → kompatible Totalordnung ≻, m. a. W. aus u→v folgt immer u ≻ v.

{{Anker|Kern-Algorithmus}}
AlgorithmusClaude 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.

: Kommen wir zu einem unmarkierten Knoten v, dann markieren wir ihn als Z-Knoten (=:  Z-Aktion(v)). Danach markieren wir alle seine direkten Vorgänger u (also die u→v) als C-Knoten (=:  C-Aktion(v,u)).

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 der Vermutung:

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

: Seine direkten Vorgänger u (also die u→v) können vor der C-Aktion(v,u) nur unmarkiert oder C-Knoten gewesen sein. Denn u kann nicht Z-Knoten sein, da wegen u ≻ v die Z-Aktion(v) allemal vor einer Z-Aktion(u) geschähe.

In graphentheoretischer Sprechweise haben wir zu einem gerichteten azyklischen Graphen einen Kern (engl. kernel, frz. noyau) konstruiert, d. i. eine stabile Untermenge von Knoten, die gleichzeitig dominierend ist.

Der Kern ist die Menge der Z-Knoten. Er existiert immerRichardson (1953), s. Claude Berge, a. a. O., S. 299. und ist eindeutigClaude Berge, a. a. O., S. 298.. 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 einer jeden Stellung klären, ob sie eine Gewinn- oder Verlustposition ist. Allerdings kann die Größe des Spielgraphen, der ja noch größer ist als der Stellungsraum, eine „praktische“ Implementierung unmöglich machen.

Die untenstehenden Graphiken können mit dem geschilderten Algorithmus gewonnen werden. Dabei sind die von den (grünen) Z-Knoten ausgehenden C-Aktionen durch rote „Strahlen“ dargestellt.

miniatur|140px|rechts|„Kern“ des Spiels von Rufus Isaacs

Eins oder zwei

Auch das triviale Spiel Eins oder zwei, dessen optimale Strategie auch ohne viel Mathematik sofort zu verstehen ist, lässt sich mit dem obigen Algorithmus behandeln: Der Stellungsraum ist ein Intervall [0,n] von nicht-negativen ganzen Zahlen.

Spiel von Rufus Isaacs

Beim Spiel von Rufus Isaacs kommen die Eigenschaften des Kerns gut heraus. Die schwarze Skizze der Spielregel in der unteren rechten Ecke symbolisiert eine Art „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.

miniatur|115px|rechts|2 kolorierte Stellungsräume des Nim-Spiels mit 3 Reihen

Nim

Den Spielgraphen bettet man bei Nim in naheliegender Weise in das �384�n�385�-dimensionale Intervall [0, r₁] × [0, r₂] × … × [0, r_n] der Stellungen ein, wo n die Anzahl der Reihen ist und r_i die Anzahl der Streichhölzer in der i-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 Koordinate mit Richtung auf den Ursprung zu.

Eine jede der lexikographischen Ordnungen ist eine mit der Zugfolge kompatible Totalordung. Es gibt nur eine Endstellung, die 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-Spiels – 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 (0,0,0) befindet sich jeweils links unten vorn.

Gültige Züge sind im Graphen Bewegungen auf genau einer der Koordinatenachsen, d. 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.

thumb|Hex-Brett mit 11 mal 11 Feldern

Hex

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

Als eine mit der Zugreihenfolge kompatible Totalordnung kann die lexikographische Ordnung von (f, a₁, ..., a_n²) dienen mit f ∈ [0,n²] als Zahl der freien Felder in der höchsten lexikographischen Priorität, i ∈ [1,n²] als Index eines Feldes $F\_i$ und

:{| class="left" style="text-align: left;"
|-
| rowspan="3" align="left" | $a\_i:=$
\begin{cases}
\\

\\

\end{cases}
|| $0$, falls $F\_i$ frei,
|-
| $1$, falls $F\_i$ rot,
|-
| $2$, falls $F\_i$ 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 Spielgraphen alternieren die Züge an den roten Steinen mit denen an den blauen.

Der Kern des Spielgraphen 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.

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 sind genau die Knoten, deren Abszisse durch 3 teilbar ist; bei der zugehörigen Misère-Regel ≡ 1 mod 3.

Spiel von Rufus Isaacs

Beim Spiel von Rufus Isaacs liegen die Z-Knoten auf den Koordinaten $\backslash big(\; \backslash lfloor\; n\; \backslash Phi^2\; \backslash rfloor,\backslash lfloor\; n\; \backslash Phi\; \backslash rfloor\; \backslash big)$ mit n≥ 0 und $\backslash Phi:=(1+\backslash sqrt\; 5)/2$  (Zahl des goldenen Schnitts) und dasselbe noch einmal an der Winkelhalbierenden gespiegelt.

Durch die Irrationalität von $\backslash Phi\; \backslash ,$ ergibt sich eine aperiodische unregelmäßige Verteilung.

Nim

Bezgl. der Formeln für die 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. h. der Komposition mehrerer „Spiele“, richtig zur Geltung. In einer 2-dimensionalen Graphik ist das jedoch nur schwer deutlich zu machen.

Fazit

Die Beispiele zeigen, dass der graphentheoretische Algorithmus ganz einheitlich und die numerischen Ergebnisse doch sehr unterschiedlich sein können. Die Graphen sind naturgemäß stets endlich und damit zwar für den „Eigenbedarf“ des Spielers ggf. ausreichend. Sie liefern auch gute Anhaltspunkte für die numerischen Formeln. Von der mathematischen Warte aus sind die Formeln aber auf höheren Rängen anzusiedeln und bedürfen auch eines speziell auf sie zugeschnittenen Beweises.

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.

Einzelnachweise

Literatur

G.H. Hardy, E. M. Wright: An introduction to the theory of numbers. Fifth edition. The Clarendon Press, Oxford University Press, New York, 1979. p.117-120.

{{Literatur
| Autor=Claude Berge
| Titel=Graphs et hypergraphes
| Verlag=Dunod
| Ort=Paris
| Jahr=1970
| Kapitel=Chapitre 14 Noyaux et fonctions de Grundy
| Seiten=291-313

}} (französisch)

Weblinks

* Partisan game in der englischen Wikipedia

* [http://www.hexwiki.org www.hexwiki.org] – weitere Informationen zum Spiel Hex (englisch)

Kategorie:Spieltheorie

ar:معلومات كاملة
ca:Informació perfecta
da:Perfekt information
Perfect information
hu:Teljesinformációs játék
ja:完全情報ゲーム
pl:Doskonała informacja
pt:Informação perfeita
ru:Игра с полной информацией
sv:Spel med fullständig information

weiter