Hex
Das Buch Auf den fremden Meeren des Denkens von Sylvia Nasar enthält die Biografie des Nobelpreisträger John Nash. Dieses Buch diente auch als Vorlage für den Film A beautiful Mind. Im Buch wird an einer Stelle über ein Spiel berichtet, das Nash während seiner Studentenzeit entwickelt hat, und das heute Hex genannt wird. Ich hatte das jahrelang vergessen, aber unlängst wurde ich wieder daran erinnert, als ich im Netz das entsprechende Wiki gefunden habe und noch einige andere Seiten mit weiterführenden Links.
Eine interessante Quelle ist die Seite von Thomas Maarup. In dessen Buch habe ich dann auch erfahren, dass Nash gar nicht der eigentliche Erfinder des Spiels ist. Unabhängig von und vor ihm hat das Spiel der dänische Dichter und Mathematiker Piet Hein erfunden.
Die Spielregeln sind verblüffend einfach: Gespielt wird auf einem rhombenförmigen Spielbrett, dessen einzelne Felder sechseckig sind. Zwei Spieler versuchen jeweils durch abwechselndes Setzen ihrer Steine, eine geschlossene Kette von einem Ende des Brettes zum anderen ihrer Farbe zu bilden. That's all.
Das Spielfeld kann verschiedene Größen haben, die am häufigsten verwendete ist 11x11. Eine Partie kann nicht unentschieden enden, denn nur eine geschlossene Kette des eines Spielers kann die Bildung einer geschlossenen Kette des anderen Spielers verhindern. Die optimale Strategie ist für Bretter bis zu einer Größe von 8x8 durch Brut force im Rechner ermittelt, für größere Bretter jedoch unbekannt. Sicher ist nur, dass der Spieler, der beginnt, einen entscheidenden Vorteil hat und theoretisch immer gewinnen sollte. Um diesen Nachteil auszugleichen, wurde die zusätzliche Regel eingeführt ("Swap"), dass, wenn der nachziehende Spieler der Meinung ist, der erste gegnerische Zug sei zu gut, diesen für sich reklamieren kann. Die Reihenfolge, wer beginnen darf, wird damit nachträglich umgekehrt. Das führt dazu, dass der Anziehende besser einen nicht zu starken Zug wählt, danach sind die Chancen für beide Spieler einigermaßen ausgeglichen.
Obwohl das Spiel etwa 60 Jahre existiert und eine ähnliche Komplexität wie Schach und Go hat, gibt es fast keine Literatur darüber. Das einzige Buch, das ich gefunden habe, ist Cameron Browns Hex strategy. Man erfährt dort, warum dieses Spiel für Mathematiker und Graphentheoretiker so interessant ist, und welche Methoden Spieler und Mathematiker in Unkenntnis der Optimalstrategie bisher ersonnen haben.
Um eigene Partien spielen zu können, habe ich mir Hexy von Vadim V. Anshelevich heruntergeladen. Es ist ein Windowsprogramm, läuft aber sehr gut auch mit Wine unter Linux. Das Programm ist Freeware, muss jedoch nach einigen Partien beim Autor registriert werden. Auf die Antwortmail von Anshelevich muss man ein paar Tage warten, offensichtlich leert er seinen Briefkasten nicht täglich. Derzeit murkse ich immer noch auf Anfängerlevel gegen sein Programm herum, aber das Programm verfügt über genau die Eigenschaften, die man zum Selbststudium benötigt: Vor und Zurücknehmen von Zügen, Zugvorschläge, automatisches Speichern von Partien.
In "Hex strategy" wird das Programm kurz erwähnt. Man erfährt dort auch etwas über den wahrscheinlich verwendeten Algorithmus. (Der Alpha-Beta-Ansatz, der in Schachprogrammen überaus gute Resultate gebracht hat und heute Spitzenspieler gegen Spitzenprogramme chancenlos aussehen lässt, funktioniert in Hex nicht. Das hat es mit Go gemeinsam.) Anshelevich modelliert das Spielbrett offenbar über ein Netzwerk von "elektrischen" Widerständen. Setzt eine Seite einen Spielstein, wird die entsprechende Verbindung im Netz kurzgeschlossen, für Züge der anderen Seite werden Verbindungen aufgetrennt. Das Optimierungskriterium für beide Seiten ist damit klar: Die eine Seite möchte den Widerstand zwischen ihren beiden Seiten verringern. Sie hat gewonnen, wenn der Gesamtwiderstand null geworden ist. Die zweite Seite versucht, den Widerstand zu erhöhen und hat gewonnen, wenn er unendlich groß ist. Dieses Kriterium ist ein globales, im Gegensatz zu den eher lokal wirkenden Strategien eines Alpha-Beta-Ansatzes. Vielleicht wäre das auch eine Idee für stärker spielende Go-Programe?
Kategorien: Bücher, Filme, Mathematik & Logik
Eine interessante Quelle ist die Seite von Thomas Maarup. In dessen Buch habe ich dann auch erfahren, dass Nash gar nicht der eigentliche Erfinder des Spiels ist. Unabhängig von und vor ihm hat das Spiel der dänische Dichter und Mathematiker Piet Hein erfunden.
Die Spielregeln sind verblüffend einfach: Gespielt wird auf einem rhombenförmigen Spielbrett, dessen einzelne Felder sechseckig sind. Zwei Spieler versuchen jeweils durch abwechselndes Setzen ihrer Steine, eine geschlossene Kette von einem Ende des Brettes zum anderen ihrer Farbe zu bilden. That's all.
Das Spielfeld kann verschiedene Größen haben, die am häufigsten verwendete ist 11x11. Eine Partie kann nicht unentschieden enden, denn nur eine geschlossene Kette des eines Spielers kann die Bildung einer geschlossenen Kette des anderen Spielers verhindern. Die optimale Strategie ist für Bretter bis zu einer Größe von 8x8 durch Brut force im Rechner ermittelt, für größere Bretter jedoch unbekannt. Sicher ist nur, dass der Spieler, der beginnt, einen entscheidenden Vorteil hat und theoretisch immer gewinnen sollte. Um diesen Nachteil auszugleichen, wurde die zusätzliche Regel eingeführt ("Swap"), dass, wenn der nachziehende Spieler der Meinung ist, der erste gegnerische Zug sei zu gut, diesen für sich reklamieren kann. Die Reihenfolge, wer beginnen darf, wird damit nachträglich umgekehrt. Das führt dazu, dass der Anziehende besser einen nicht zu starken Zug wählt, danach sind die Chancen für beide Spieler einigermaßen ausgeglichen.
Obwohl das Spiel etwa 60 Jahre existiert und eine ähnliche Komplexität wie Schach und Go hat, gibt es fast keine Literatur darüber. Das einzige Buch, das ich gefunden habe, ist Cameron Browns Hex strategy. Man erfährt dort, warum dieses Spiel für Mathematiker und Graphentheoretiker so interessant ist, und welche Methoden Spieler und Mathematiker in Unkenntnis der Optimalstrategie bisher ersonnen haben.
Um eigene Partien spielen zu können, habe ich mir Hexy von Vadim V. Anshelevich heruntergeladen. Es ist ein Windowsprogramm, läuft aber sehr gut auch mit Wine unter Linux. Das Programm ist Freeware, muss jedoch nach einigen Partien beim Autor registriert werden. Auf die Antwortmail von Anshelevich muss man ein paar Tage warten, offensichtlich leert er seinen Briefkasten nicht täglich. Derzeit murkse ich immer noch auf Anfängerlevel gegen sein Programm herum, aber das Programm verfügt über genau die Eigenschaften, die man zum Selbststudium benötigt: Vor und Zurücknehmen von Zügen, Zugvorschläge, automatisches Speichern von Partien.
In "Hex strategy" wird das Programm kurz erwähnt. Man erfährt dort auch etwas über den wahrscheinlich verwendeten Algorithmus. (Der Alpha-Beta-Ansatz, der in Schachprogrammen überaus gute Resultate gebracht hat und heute Spitzenspieler gegen Spitzenprogramme chancenlos aussehen lässt, funktioniert in Hex nicht. Das hat es mit Go gemeinsam.) Anshelevich modelliert das Spielbrett offenbar über ein Netzwerk von "elektrischen" Widerständen. Setzt eine Seite einen Spielstein, wird die entsprechende Verbindung im Netz kurzgeschlossen, für Züge der anderen Seite werden Verbindungen aufgetrennt. Das Optimierungskriterium für beide Seiten ist damit klar: Die eine Seite möchte den Widerstand zwischen ihren beiden Seiten verringern. Sie hat gewonnen, wenn der Gesamtwiderstand null geworden ist. Die zweite Seite versucht, den Widerstand zu erhöhen und hat gewonnen, wenn er unendlich groß ist. Dieses Kriterium ist ein globales, im Gegensatz zu den eher lokal wirkenden Strategien eines Alpha-Beta-Ansatzes. Vielleicht wäre das auch eine Idee für stärker spielende Go-Programe?
Kategorien: Bücher, Filme, Mathematik & Logik
Sonntag, 04.Mai 2008