Hex

Aus Wikiludia
Wechseln zu: Navigation, Suche

Hex bezeichnet ein strategisches Zwei-Personen-Spiel. Aus spieltheoretischer Sicht ist das Spiel interessant, weil sicher ist, dass der Spieler der zuerst zieht, eine Gewinnstrategie hat, dass diese Gewinnstrategie aber (bisher) nicht bekannt ist.


Inhaltsverzeichnis

Die Entwicklung des Spiels

John Forbes Nash veröffentlichte dieses Spiel im Jahr 1948, während seines Studiums in Princeton, wo es folglich als „Nash“ bekannt wurde. Unter dem Namen „Polygon“ wurde das Spiel aber bereits 6 Jahre zuvor von dem dänischen Mathematiker Piet Hein beschrieben. Die Entwicklung des Spiels durch Nash war zwar unabhängig von der Heins; dennoch wird heute meist Hein als Erfinder von Hex genannt.


Regeln

Das Spielfeld von Hex (in der Grundform) besteht aus n², n ∈ \mathbb{N}, Sechsecken (vgl. gr. Hexa = 6), die in Form einer Raute angeordnet sind. Hex07e.gif


Die 2 gegenüber liegenden Seiten der Raute gehören jeweils zusammen; sie sind in der gleichen Farbe markiert. (Die Sechsecke, die die Eckpunkte der Raute markieren gehören jeweils zu beiden angrenzenden Farben)

Die Spieler wählen je eine der beiden Farben, beispielsweise Schwarz und Weiß. Sie sind immer abwechselnd an der Reihe. in jeder Runde können sie je ein Sechseck mit ihrer Farbe markieren. Das Ziel ist für beide, die entsprechenden Felder so auszuwählen, dass sich eine Zusammenhangskomponente zwischen den beiden eigenen Seiten in der gleichen Farbe ergibt. Gelingt dies einem Spieler, dann ist das Spiel beendet.


Eigenschaften des Spiels

  • es gibt immer genau einen Gewinner des Spiels: eine Verbindung der eigenen Seiten bedeutet gleichzeitig eine strikte Trennung des Bretts in zwei Teilbereiche. Also macht eine Zusammenhangskomponente des einen Spielers die für den anderen unmöglich. sind letztlich alle Spielfelder besetzt, so gibt es genau eine Verbindung von gegenüberliegenden Parallelen.
  • Wegen der endlichen Anzahl an Spielfeldern werden höchstens n²/2 Runden gespielt; Hex ist also endlich.
  • Die Spieler verfügen über vollständige Information. Sie können jeden der Züge des anderen Spielers beobachten.


Theorem: Auf einem n x n- Brett kann der erste Spieler immer gewinnen.

Beweis (von John Nash) in 3 Schritten:

1) Mit einem rein topologischen Argument kann man zeigen, dass in jedem möglichen Spielverlauf immer genau einer der beiden Spieler gewinnt: ist das Spielbrett komplett mit Spielsteinen in beiden Farben besetzt, so existiert entweder eine weiße Kette, die die weißen Kanten verbindet, oder eine schwarze, die die übrigen zwei Seiten zusammenführt. es können niemals beide solchen Ketten gleichzeitig existieren, da sie sich in ihrer Existenz gegenseitig ausschließen.
2) Da das Spiel endlich ist und nur zwei mögliche Ausgänge (-1; 1) bzw. (1: -1) hat, und weil die Spieler abwechselnd mit vollständiger Information ihre Züge wählen können, kann man das Theorem von Zermelo anwenden. Dieses stellt sicher, dass einer der Spieler eine Gewinnstrategie haben muss.
3) (durch Ausnutzung von Symmetrie) Angenommen, der 2. Spieler hat eine. Spieler einen zufälligen ersten Zug wählen und dann der Strategie des 2. Spielers folgen. Weil dem 1. Spieler dessen Anfangszug niemals ein Nachteil sein kann, muss er folglich gewinnen. Damit kann der 2. Spieler nicht gewinnen, sondern muss verlieren. Widerspruch!
Also war die Annahme, dass Spieler 2 eine Gewinnstrategie besitzt, falsch.


Varianten

  • Nebeneinander liegende Seiten des Spielfeldes sind nicht gleich lang; das Hex-Spielbrett ist also nur Parallelogramm, nicht Raute. die Anzahl der Felder ist m * n mit m ≠ n. In diesem Fall ist für den Spieler, dessen Seiten näher zusammen liegen, eine Gewinnstrategie bekannt (vgl.Kuhn2002 für das 5x6 Spiel).
  • Um die Vorteile auszugleichen, die das Recht auf den ersten Zug nach sich zieht, kann eine Tauschregel verwendet werden. Beispielsweise kann man vereinbaren, dass der 2. Spieler nach dem Eröffnungszug des ersten entscheiden kann, ob er bei seiner ursprünglichen Farbe bleibt, oder ob die Farben getauscht werden sollen.


Quellen

  • Kuhn2002
  • www.hexwiki.org
Meine Werkzeuge