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
Andererseits sind die Verbindungen bei Go, nicht so eindeutig definiert, wenn man alle Pon-Nuki-Situationen mit einbezieht. Das große Problem, dass ich bei der Go-Programmierung sehe, ist der Umstand, dass es keinen besten Zug gibt. Der beste Zug ist abhängig von der Geschicklichkeitsdifferenz der beiden Spieler abhängig. Der Computer müsste in der Eröffnungsphase eine Bewertung des Gegners vornehmen, um seine eigenen Spielzüge zu optimieren. Kürzlich war ich wieder mit einem Go-Programm konfrontiert. Auf Blitzspiel-Level hatte ich überhaupt keine Schwierigkeiten, sprich, ich musste eigentlich nicht nachdenken.
Wenn ich gegen einen Menschen spiele, sind die ersten 20 Züge die absolut schwersten.
Ich meinte aber die Idee, das Spielfeld über ein Widerstandsnetzwerk zu modellieren und die Züge über Änderungen einzelner Widerstände, die dadurch den Gesamtwiderstand verändern. Für Hex wird der Gesamtwiderstand quer, von einer Seite zur anderen, gemessen. Im Go wären es vermutlich Widerstände von oben nach unten, weil es auf den Raumgewinn ankommt. Das Widerstandsnetzwerk wird dann durch die Relationen zwischen nah und fern benachtbarten Zellen bestimmt, das Netzwerk ist dreidimensional. Über den Abschluss des Netzwerks am Rand wird automatisch die endliche Größe des Feldes und die unterschiedliche Bedeutung von Feldern in der Mitte und am Rand berücksichtigt.
Der Ansatz erinnert in etwa an die Anwendung eines neuronalen Netzes, nur dass sich die Gewichte der einzelnen Knoten a priori aus der Topologie des Netzes und nicht aus einer aufwändigen Belehrung ergeben.
Das Spielbrett von John Nash bestand übrigens nicht aus Sechsecken. Er hat ein Go-Brett genommen und dort in einer Richtung zusätzliche Diagonalen eingezeichnet. Dadurch schneiden sich in einem Punkt nicht vier, sondern sechs Linien. Dieses Brett ist dann topologisch äquivalent einem Brett, bei dem ein Feld sechs Nachbarzellen hat. Es ist nur für unsere Vorstellungskraft weit schwieriger, weil die beiden Diagonalen unterschiedlich behandelt werden. Für Nash und die mathematischen Genies in seiner Umgebung war das sicher kein Problem, für mich schon.
Es ginge mit einem 19x19-Tensor mit entsprechenden ∂R/∂Richtung-Einträgen.
Mir haben persönlich schon die drei-dimensionalen Maxwell-Gleichungen gereicht, wobei ich bei Gedanken ∆φ=0 bezogen auf das ganze Go-Feld auch gewisse Ähnlichkeiten entdecken könnte.
Du müsstest, um beim Widerstandsnetzwerk zu bleiben, bestimmte Stellungen, bestimmte Muster ebenfalls mit Widerstandswerten belegen. (Leiter, Affensprung etc.)
Die Eingangsmenge von zu bewertenden Faktoren wird einfach verdammt groß.
Aber auf meinen wesentlichen Einwand bist Du ja nicht eingegangen, nämlich auf das Fehlen des "besten Zugs" beim Go.
Wie man das Nash-Diagonalen-Problem löst
Die waagrechten Linien (das wären die anderen Diagonalen) sind bedeutungslos.
Fehlen des besten Zuges
1. Existenz: a) Es gibt einen einzigen besten Zug / b) mehrere gleichwertige Züge
2. Theorie: a) Die optimale Strategie ist uns bekannt / b) nicht bekannt
3. Praxis: a) Die optimale Strategie ist für uns verstehbar / b) nicht verstehbar
Schach fällt unter 1x-2b-3b. Schachendspiele (reduzierte Komplexität) sind manchmal 1a, manchmal 1b und häufig 2a. Mühle ist von Beginn an 1b-2a-3a. Bei Hex kann die Komplexität über die Brettgröße exponentiell skaliert werden. Ähnliches vermute ich bei Go. Auf einem 5x5-Brett wird es wahrscheinlich einen besten ersten Zug geben, bei steigender Brettgröße dann mehrere.
Im praktischen Sinn kann eine uns unbekannte bzw. eine zu komplizierte Optimalstrategie nicht unterschieden werden. In beiden Fällen gibt es mehrere Züge, und der Partieausgang ist stark von der Spielstärke und schwach vom Zufall abhängt. Schach, Hex und Go sind Spiele mit vollständiger Information (beide Spieler wissen nach Ansicht der Position (theoretisch) alles über diese) aber sehr großer Komplexität. Ich sehe da zwischen den Spielen wenig Unterschiede. Man hat in den ersten Zügen große Freiheiten, danach bestimmt mehr und mehr der Charakter der gemachten Züge den weiteren Verlauf.
Bezüglich eines Widerstandsnetzwerkes: Es gibt mehrere Ersetzungen (0, oo), die denselben Gesamtwiderstand ergeben -> die Züge sind gleichwertig, führen aber, wenn es keine simple Zugumstellung ist, zu unterschiedlichen Partien.
Diagonalenproblem
Nash muss mit beiden Bretttypen klargekommen sein, denn angeblich haben sie auch im Waschraum oder auf dem Klo gespielt, und dort soll es sechseckige Fliesen gegeben haben.