- Für 8×8-Othello/Reversi wurde rechnerisch bewiesen, dass das Endergebnis bei perfektem Spiel beider Seiten ein Unentschieden ist; nach Maßstab der Forschenden wurde damit ein schwach gelöster Zustand erreicht
- Der Suchraum blieb ein deutlich schwierigeres Problem als frühere gelöste Fälle wie Checkers, da mögliche Spielverläufe auf etwa 10^58 und Brettpositionen auf etwa 10^28 geschätzt werden
- Das Ergebnis bestimmt den spieltheoretischen Wert der Ausgangsposition und eine Strategie, die diesen Wert erreicht; es handelt sich nicht um eine starke Lösung, bei der alle Zwischenpositionen berechnet wurden
- Die Forschenden nutzten heuristische Suche auf Basis von Othello-Software sowie alpha-beta search und erklären, dass der für die exakte Lösung nötige Suchumfang kleiner war als frühere Prognosen
- Rohdaten und Programme zur Reproduktion der Ergebnisse wurden auf GitHub, Zenodo und figshare veröffentlicht und können als überprüfbarer Fall für die Erforschung gelöster reiner Strategiespiele dienen
Rechnerische Lösung von Othello
- Othello auf einem 8×8-Brett wurde schwach gelöst; der spieltheoretische Wert der Ausgangsposition wurde als Unentschieden berechnet
- Wenn beide Seiten fehlerfrei und optimal spielen, endet die Partie unentschieden; diese Studie weist das rechnerisch nach
- Figure 1 zeigt einen optimalen Spielverlauf und das Endergebnis
- Weicht an irgendeinem Punkt dieser Zugfolge eine Seite davon ab, garantiert die Software der Forschenden als Gegenseite ein Unentschieden oder einen Sieg
- Dieses Ergebnis entspricht der von menschlichen Othello-Experten erwarteten Remis-Prognose; die Forschenden halten das Ergebnis an sich daher nicht für überraschend
Umfang der Lösung und spieltheoretischer Wert
- Ein Spiel mit vollständiger Information zu lösen bedeutet, das Endergebnis bei perfektem Spiel beider Seiten zu bestimmen, also den spieltheoretischen Wert
- Gelöste Spiele werden üblicherweise in drei Stufen eingeteilt
- ultraschwach gelöst (ultra-weakly solved): wenn nur der spieltheoretische Wert der Ausgangsposition bekannt ist
- schwach gelöst (weakly solved): wenn der spieltheoretische Wert der Ausgangsposition bekannt ist und beide Seiten innerhalb vertretbarer Rechenressourcen eine Strategie kennen, um diesen Wert zu erreichen
- stark gelöst (strongly solved): wenn das Ergebnis aller möglichen Positionen berechnet wurde, die während des Spiels auftreten können
- Diese Studie ist ein Fall, in dem Othello schwach gelöst wurde; es ist keine starke Lösung, bei der alle möglichen Positionen berechnet wurden
- Checkers wird im selben Sinn als schwach gelöstes Spiel angeführt
Warum Othello so lange ungelöst blieb
- Othello ist ein populäres Spiel mit großer strategischer Tiefe; es wurde im 19. Jahrhundert in England erfunden, verbreitete sich im 20. Jahrhundert in seiner heutigen Form in Japan und wird weltweit gespielt
- Seit 1977 finden jährlich Weltmeisterschaften statt, was seine globale Popularität zeigt
- Der Suchraum ist sehr groß
- durchschnittlich etwa 10 Züge pro Position
- durchschnittlich etwa 58 Züge pro vollständiger Partie
- etwa 10^58 mögliche Spielverläufe
- etwa 10^28 mögliche Brettpositionen
- Diese Größenordnung wird als deutlich größer beschrieben als bei bisher als schwierige Probleme gelösten Spielen, insbesondere Checkers
- Wegen des großen Suchraums blieb Othello eine langfristige Herausforderung der Informatik
Suchverfahren und Recheneffizienz
- Die Forschenden setzten alpha-beta search mit dem Ziel einer schwachen Lösung ein
- Algorithmen zum Lösen von Spielen unterscheiden sich je nach Ziel und Spielcharakter
- Für schwache Lösungen wird häufig alpha-beta search verwendet
- Für starke Lösungen wird häufig retrograde analysis genutzt
- Für Rätsel mit sehr langen Lösungssequenzen wurden Verfahren wie df-pn search entwickelt
- alpha-beta search ist ein Algorithmus, der den Spielgraphen sequenziell per Tiefensuche durchsucht; deshalb lässt sich die Sucheffizienz durch einfache Parallelisierung nur schwer stark steigern
- Für parallele Suche wurden verschiedene Ansätze erforscht
- In Shared-Memory-Umgebungen sind YBWC und Lazy SMP beliebte Verfahren
- In Distributed-Memory-Umgebungen werden APHID und ABDADA als relevante Algorithmen genannt
- In Distributed-Memory-Umgebungen unterscheiden sich Bedingungen wie Bandbreite und Latenz zwischen Knoten stark, sodass Entwickler je nach Umgebung einen passenden Algorithmus auswählen oder neu entwickeln müssen
- Selbst mit modernen Computerclustern war die Lösung von Othello eine große Hürde; der Durchbruch bestand darin, aktuelle Othello-Software so zu modifizieren, dass die Sucheffizienz stieg
Andere gelöste Spiele und mögliche Nutzung
- Als jüngster vor Othello gelöster schwieriger Fall wird Checkers genannt
- Auch nichttriviale Spiele wie Connect Four, Qubic, Go-Moku, Nine Men’s Morris und Awari werden als gelöste Beispiele aufgeführt
- Der Schwierigkeitsgrad beim Lösen eines Spiels hängt im Allgemeinen stark von der Zahl der Positionen oder Situationen im Spiel ab
- Das Lösen eines Spiels beschränkt sich nicht darauf, das Endergebnis zu klären; es kann auch zur Puzzle-Generierung auf Basis des jeweiligen Spiels genutzt werden
- Die Forschenden stellen Rohdaten und Programme zur Reproduktion auf GitHub, Zenodo und figshare bereit
1 Kommentare
Meinungen auf Hacker News
Es heißt zwar, man habe „aus 2.958.551 Positionen 2.587 Positionen ausgewählt und eine Hypothese über deren Ergebnis aufgestellt; wenn all diese Hypothesen stimmen, beweist das, dass die Ausgangsposition ein Remis ist“, aber eine genauere Erklärung fehlt
Es klingt weniger so, als sei das Spiel vollständig gelöst, sondern eher, als habe der Autor sehr intensiv nach einer Gewinnfolge gesucht und keine gefunden
Dort steht, dass es viele Methoden gebe, eine Teilmenge auszuwählen, mit der sich beweisen lässt, dass die Ausgangsposition ein Remis ist, man aber mit Algorithm 1 eine kleine Teilmenge erhalten habe
Algorithm 1 wird so beschrieben, dass er die vorhergesagten Scores aller Positionen mit 50 leeren Feldern nimmt und eine Teilmenge zurückgibt, bei der, wenn alle Positionen dieser Teilmenge gelöst sind und die Lösungen mit den Vorhersagen übereinstimmen, daraus folgt, dass auch die Ausgangsposition gelöst ist
Insgesamt ist die Darstellung im Paper nicht intuitiv. Der Autor könnte recht haben, aber man müsste sich wohl wirklich hinsetzen und der Logik Schritt für Schritt folgen; mein erster Eindruck ist skeptisch
Solche Beweise gibt es auch anderswo. Zum Beispiel wurde auch der Vier-Farben-Satz auf eine endliche Zahl von Konfigurationen reduziert, die anschließend per Hand gefärbt wurden
Das Skript unter https://github.com/eukaryo/reversi-scripts/blob/main/reversi... spielt perfekt, unter der Annahme, dass das Ganze korrekt ist. Die anderen Skripte im Repository nutzen Daten, die mithilfe der Lösungen für Positionen mit 36 leeren Feldern berechnet wurden; das scheint in diesem Umfang auch auf gewöhnlicher Hardware machbar
Im Kern scheint die Struktur darin zu bestehen, eine Tabelle unter 300 GB mit allen Positionen mit 37 bis 64 leeren Feldern, die aus der schwachen Lösung erreichbar sind, nachzuschlagen, und Positionen mit 36 oder weniger leeren Feldern mit edax’
-solvezu lösenOthello ist ein gutes Spiel, um zu zeigen, wie stark man schon mit grundlegenden Heuristiken werden kann
Im Verlauf des Spiels gibt es Felder, auf die man auf keinen Fall setzen darf, und umgekehrt Felder, die man möglichst unbedingt besetzen sollte
Schon wenn man nur solche Regeln implementiert, entsteht ein ziemlich guter Gegner; interessant ist, wie schnell Menschen selbst sehr einfachen Dingen „Intelligenz“ zuschreiben
Darin wurde eine App mit ähnlich einfachen Heuristiken gegen eine ebenso simple, aber katastrophal schlechte Strategie-App antreten lassen, die „möglichst viele Steine umdreht“
Der Heuristik-Algorithmus gewann haushoch; ich meine, es war 60 zu 4 oder sogar noch deutlicher
Sobald noch 19 leere Felder übrig waren, löste es den Rest der Partie vollständig, und das war ziemlich beeindruckend
Othello war ein Spiel, das sogar auf 10-Dollar-LCD-Spielgeräten mit zwei AA-Batterien lief
Falls man sich für das Spiel interessiert: Die auch unter Informatik- und KI-Forschern beliebten Othello-Weltmeisterschaften laufen gerade in Rom, Italien
Die Partien werden live auf liveothello.com und YouTube @WorldOthello übertragen
Außerdem frage ich mich, ob Othello wie Dame ein Spiel ist, bei dem die meisten Partien auf Spitzenniveau remis enden
Cool
Vor etwa 15 Jahren habe ich einmal ein einfacheres Spiel gelöst, das ich mit meinem Bruder gespielt habe. Es war ein afrikanisches Spiel mit ungefähr je 10 Mulden auf beiden Seiten des Bretts, in die Steine gelegt werden
Ich schrieb eine Alpha-Beta-Engine und fand damit eine absurde immer gewinnende Strategie, die genau zu unserer Spielweise passte. Danach gewann ich plötzlich jede Partie, und mein Bruder wollte nie wieder mit mir spielen. Ein klassisches Duell Informatiker gegen Optometrist
Wenn man älteren Afrikanern beim Mancala zusieht, kann man viel lernen. Sie spielen unglaublich schnell, und es bekommt fast etwas Pokerartiges, bei dem Täuschung Teil des Spiels wird
Wenn man die Steine schnell genug verteilt, kann man eine Schale überspringen oder einen Stein zusätzlich fallen lassen und sich so einen Vorteil verschaffen
Ich bin nicht so geschickt und spiele mit meiner Familie, deshalb schummle ich nicht. Trotzdem wird daraus ein völlig anderes Spiel. Es ist wie der Unterschied zwischen britischen Damen, die beim Tee langsam Mahjong spielen, und einer Partie um Geld in einer chinesischen Spielhölle
Wenn man zu viel gewinnt oder zu viel verliert, hat man keinen Spaß mehr am Spiel
Allerdings weiß ich nicht, was der Beruf des Optometristen hier damit zu tun hat
Ist das echt? Dass es nur einen Autor gibt und er zu einem Deep-Learning-Startup gehört, von dem ich noch nie gehört habe, wirkt etwas seltsam
Vermutlich läuft gerade das Peer Review?
Und Othello ist nun nicht gerade auf dem Niveau der Riemannschen Vermutung. Es wurde entsprechend weniger erforscht, und vielleicht gab es noch niedrig hängende Früchte
Othello ist eines der Spiele, die sich wirklich gut mit kleinen Kindern spielen lassen.
Die Regeln sind einfach, es gibt Muster, die man lernen kann, und es macht Spaß, viele Steine auf einmal umzudrehen. Vor allem macht es nicht nur Kindern, sondern Erwachsenen genauso viel Spaß.
Ich konnte es ausreichend genießen, ohne ein sechsjähriges Kind zu überfordern und ohne dass es sich wie ein reines Glücksspiel anfühlte.
https://mancala.fandom.com/wiki/Hus
Theoretisch gibt es kein Glückselement, aber in der Praxis kann man wegen der Kettenreaktionen nicht so weit vorausrechnen.
Das Brett kann man leicht selbst bauen.
Wenn man das Spiel ausprobieren möchte: Ich habe etwas hochgeladen, das ich mit meinen Kindern gebaut habe: https://jawj.github.io/fliptiles
Der „KI“-Spieler ist sehr schwach.
Ich habe ein neues Spiel gelernt.
Der Computer hatte 33 Punkte, ich 31.
Wenn man Othello für trivial hält, sollte man Zebra ausprobieren.
Website des ursprünglichen Autors: http://radagast.se/othello/
GitHub-Quellcode: https://github.com/hoshir/zebra
Was ich an Othello mag, ist der Widerspruch zwischen Zug und Territorium.
Im Verlauf des Spiels ist es in gewisser Weise nachteilig für mich, wenn ich in meinem Zug einen Stein setze, aber ich muss es trotzdem tun.
Deshalb muss man beim Besetzen klein und innen bleiben, bis der Raum zu eng wird und der Zeitpunkt kommt, an dem man wieder gesicherten Einfluss zurückgewinnen muss.
Dazu passend gibt es auch perfektes Spiel für 6x6 Reversi.
https://mame.github.io/6x6-reversi-oracle/
Quelle: https://twitter.com/mametter/status/1476379841004183556
Dass 8x8 noch nicht gelöst ist, wusste ich bis jetzt nicht.