Denkspiele

Allis veröffentlichte seine Arbeit detailliert in seinen Masters Thesis. Es ist sehr interessant, leistet aber nicht allzuviel, wenn es darum geht, eines Menschen Spielstärke zu verbessern -- zu abstrakt sind die acht Regeln. Außerdem fehlt die in der Praxis nicht perfekter Spieler wichtige Unterscheidung zwischen unentschieden und Gewinn für den Nachziehenden. Für Menschen gibt es aber eine sehr ausführliche, verständliche Strategieanleitung. Wer den Artikel Expert play in connect four gelesen hat, weiß alles über die Strategie beim Vier Gewinnt, ob er das Spiel beginnt oder nicht, und kann mal sein Glück gegen eins der starken Programme versuchen.

Für Programmierer ist Vier Gewinnt eigentlich ein totes Spiel. Es gibt schon mehrere perfekt spielende Programme, und auch über die Funktionsvielfalt kann man nicht meckern. Wer sich dennoch damit befassen möchte, kann eine von John Tromp berechneteDatenbank aller nichttrivialen Eröffnungsstellungen mit acht Steinen herunterladen (Textformat, 319kByte), wobei jede Stellung korrekt bewertet ist. Nichttrivial bedeutet in diesem Zusammenhang, daß Stellungen fehlen, in denen der nächste (neunte) Halbzug ein Zwangszug wäre, der einen sofortigen Gewinn des Gegners verhindert. Den Stand der Technik habe ich in einem Artikel für die CSS beschrieben.

Es gibt aber noch heißere Sachen als die Tromp-Achtsteiner-Datenbank! Ein rühriger Programmierer, Markus Thill, hat nämlich die Zehn- und die Zwölfsteiner berechnet und nebenbei auch die fehlenden Stellungen in John Tromps Achtsteiner-DB ergänzt. Er hat mir angeboten, diese Datenbanken hier zum Nutzen der Allgemeinheit zum Download anzubieten, was ich sehr gern tue:

Thill-Achtsteiner (77.238 Stellungen, 278 kByte, zip)
Thill-Zehnsteiner (634.338 Stellungen, 2,2 MByte, tar.bz2)
Thill-Zwölfsteiner (4.200.899 Stellungen, 19,8 MByte, tar.bz2)

Das Format entspricht der Einfachheit halber dem der Tromp-DB; eine Stellung besteht aus einer Text-Zeile mit 43 Zeichen:
linke Spalte von unten nach oben
...
mittlere Spalte von unten nach oben
...
rechte Spalte von unten nach oben

b -> leeres Feld
x -> Anziehender
o -> Nachziehender

+ -> Gewinn für den Anziehenden
- -> Gewinn für den Nachziehenden
= -> Remis

Enthalten sind alle möglichen Stellungen der jeweiligen Steine-Anzahl bis auf Positionen, die der Spieler am Zug (also der Anziehende) sofort (einzügig) gewinnen kann. Da jede Stellung an der mittleren Spalte gespiegelt werden kann, wurden solche Spiegelstellungen entfernt; es ist immer nur eine Position eines Spiegelpaares in der DB vorhanden.

Wer Mustrum 2.1 herunterlädt, bekommt diese Datenbanken schon mitgeliefert, allerdings nicht im Text-, sondern in einem platzsparenden Binärformat.

4inarow rechnet noch schneller als Mustrum und hat ein Eröffnungsbuch, das für den Anziehenden perfektes Spiel ermöglicht. Als Nachziehender hat es kein Buch, spielt aber wegen der großen Suchtiefe trotzdem recht gut. Die Oberfläche finde ich etwas spartanisch, aber das ist Geschmackssache. Speichern und Laden von Spielen ist möglich, Nachspielen vorwärts und rückwärts, Zweispielermodus zur Eingabe von Stellungen. Eine sehr schnelle Mattsuche ist ebenfalls vorhanden, ebenso eine Funktion "alle Züge bewerten". Die Hilfe ist ausgezeichnet und gibt neben einfachen taktischen Aufgaben sogar Tipps zur Strategie. Kann man also uneingeschränkt empfehlen.

Wer Backgammon für ein Glücksspiel hält, nur weil dabei Würfel rollen, der sollte mal sein "Glück" gegen Gnu Backgammon oder BGBlitz versuchen, er wird schnell herausfinden, welch entscheidende Rolle die Strategie spielt.

Es wundert nicht, dass ein Computer besser Wahrscheinlichkeiten kalkulieren kann als ein anderthalb Kilo schwerer Eiweißklumpen; tatsächlich spielen die Spitzenprogramme stärker als alle Menschen. Was nicht heißt, dass sie jedes Spiel oder auch nur jedes Match gewinnen, ein bisschen Einfluss hat das Würfelglück ja doch. Die guten Programme bestechen nicht nur durch große Spielstärke, sondern auch durch viele Analyse- und Datenbank-Funktionen und viele dramatisch schöne grafische Steinsätze. Beispielsweise kann Gnu Backgammon eine Partie oder gleich ein gesamtes Match analysieren, kommentieren und seine Ergebnisse als HTML-Datei ausgeben. Ein neuronales Netz, das mehrere Millionen Partien gegen sich selbst gespielt und so praktisch alles über das Spiel gelernt hat, sorgt für die gewaltige Spielstärke der Spitzenprogramme; Backgammon-Software mit selbstgefrickelter Bewertungsfunktion kann seit Jahren nicht mehr konkurrieren. Über die Funktionsweise habe ich mal einen Artikel in der CSS veröffentlicht, den es hier als PDF gibt.

Es gibt einige sehr gute Programme. Mein persönlicher Favorit ist die Shareware BGBlitz – ein todschickes Spiel, das 2002 Olympiasieger und 2003 Weltmeister der Backgammonprogramme wurde. Es läuft dank Java unter den meisten Betriebssystemen und kann eigentlich alles außer Brötchen holen. Eine ausführliche Programmvorstellung und ein Interview mit dem Autor gibt es in diesem PDF eines CSS-Artikels. BGBlitz gibt es auch als Instant-Version zum Mitnehmen, vulgo: für Java-fähige Handys.

Ebenso empfehlenswert ist das auch systemübergreifend lauffähige und darüber hinaus quelloffene GnuBackgammon.

Die amerikanische Dame-Variante Checkers steht schon auf der roten Liste der vom Lösen bedrohten Spiele; seit 1994 hält der Computer Chinook den Weltmeistertitel, drei der 144 möglichen Eröffnungen sind bereits bis zum Remis ausanalysiert und alle Stellungen mit bis zu zehn Steinen liegen als allwissende Datenbank vor. Den Stand der Technik habe ich in CSS beschrieben; hier gibt es ein PDF des Artikels.

[Update] Mittlerweile ist Checkers tatsächlich gelöst, wie hier beschrieben. Das wenig überraschende Ergebnis: REMIS in allen Varianten. Auf der Chinook-Seite kann man ein Spielchen wagen, allerdings wäre die Hoffnung auf einen Sieg ziemlich vermessen :-)

Ganz perfekt spielt zumindest die PC-Software aber noch nicht, und so kann man zumindest theoretisch das Weltklasse-Programm Cake des Schweizers Martin Fierz gelegentlich schlagen. Leicht wird das aber nicht, denn ein Eröffnungsbuch mit mehreren Millionen Zügen und Endspieldatenbanken mit Wissen über alle Positionen bis zu sechs Steinen unterstützen ein Programm, das auf modernen Computern in zehn Sekunden mindestens 20 Halbzüge tief rechnet und in bestimmten Varianten mehr als 40 Halbzüge voraussieht -- notfalls kann man aber eine niedrige Spielstufe ein- und die Datenbanken abstellen. Die zugehörige Oberfläche Checkerboard kommt auch mit anderen Engines zurecht, zum Beispiel Kingsrow; es wird sogar eine simple Engine im Quelltext mitgeliefert. Die Sechssteiner-Endspieldatenbanken liegen nicht bei, per Knopfdruck generiert sie Checkerboard aber innerhalb weniger Stunden. Das Programm kann mit Partiedatenbanken umgehen und Spiele automatisch analysieren. Der Anwender kann Partien als Webseite exportieren und eigene Erffnungszüge in die Bibliothek aufnehmen.

Das heißeste Spiel, das in den letzten 200 Jahren erfunden wurde, dürfte ConHex sein. Es ist ein Verbindungsspiel, aber eins, das eher an Go erinnert; es geht um Raum und Einfluß, auch wenn das Ziel letztlich darin besteht, Ränder zu verbinden. Wie bei allen Verbindungsspielen kann es kein Remis geben. Die Regeln und eine Beispielpartie finden sich in diesem Artikel. Ein Programm existiert zwar, allerdings ist es nicht frei verfügbar, sondern wurde an der Uni Jena im Rahmen einer Seminararbeit entwickelt. Es läuft nur unter Linux, hat keine GUI und rechnet nach dem Monte-Carlo-Verfahren. Ich glaube ja nicht daran, daß man damit ein wirklich starkes Conhex-Programm erreichen kann; immerhin konnte Günthex aber ein Match gegen den sehr spielstarken Conhex-Erfinder Michael Antonow remisieren mit einem Sieg und einer Niederlage.

Man kann Conhex online spielen, und zwar auf Richards PBeM-Server, allerdings nur als Fernpartie.

Die stärksten Gegner findet man aber auf Little Golem, ebenfalls für Fernpartien.

Go ist eines der am schnellsten zu lernenden Spiele -- ganze drei einfache Regeln zu verstehen reicht, um das Tor zum Go-Universum aufzustoßen. Für die ersten Schritte, den taktischen Kleinkram, ist aber ein bißchen Hilfe ganz praktisch. Hier kommt IgoWin ins Spiel, eine Demo-Version des kommerziellen Many Faces of Go: Auf einem 9x9 Felder großen (oder eher kleinen) Spielbrett passt es sich der Spielstärke seines Kontrahenten an. Zunächst bekommt der Spieler fünf Vorgabesteine und wird als 25. Kyu eingestuft. Gewinnt er die Partie, gilt er als 24. Kyu; mit jedem weiteren Sieg verbessert sich die Einstufung um einen Grad, mit jeder Niederlage rutscht der Spieler einen Rang zurück. Das ist gut für die Motivation, und nebenbei bekommt man von dem Programm die kleinen Tricks vorgeführt, ohne die man nicht besser wird.

Bevor man sich Taktik und Strategie widmet, lohnt sich auch ein Blick auf die Hilfe von IgoWin, die ein nettes Tutorial enthält. Der Anfänger bekommt haarklein die grundlegenden Dinge wie Punkte, Freiheiten, Leben und Tod, Zählen und mehr leicht verständlich erklärt, Übungsaufgaben inklusive. Als überladen kann man IgoWin kaum bezeichnen, die Funktionen beschränken sich auf das Allernötigste. Ein Button, um ein neues Spiel zu starten, einer zum Speichern im SGF-Format (das PGN der Go-Programme), ein Button zum Passen und einer, um die Hilfe aufzurufen. Die Funktionen reichen für das schnelle Spielchen zwischendurch, fortgeschrittene Spieler erwarten mehr und greifen eher zu einem anderen Programm. IgoWin ist sicher nicht das stärkste Programm für 9x9-Go. Es eignet sich aber wegen der automatischen Spielstärke-Anpassung und der gelungenen Einführung in der Hilfe besonders für Anfänger und wenig geübte Spieler. Es verwirrt nicht durch viele Einstellmöglichkeiten und japanische Fachbegriffe, sondern tut nur das, wofür es da ist: Go spielen. Und das gar nicht mal so schlecht.

Zu den stärksten Go-Programmen zählten lange Zeit GnuGo und Go++. In der CSS habe ich mal einen Vergleichstest veröffentlicht. Mittlerweile hat aber ein Paradigmenwechsel im Computergo stattgefunden; Programme, die mit dem Monte-Carlo-Derivat UTC und einem Häppchen KI arbeiten, spielen auf Hochdan-Niveau und stärker als jeder Mensch. Vorreiter war Alphago, das 2016 den koreanischen Champion Lee Sedol schlug.

Das Alphago für zu Hause ist das extrem starke Windows-Programm Leela. Eine Kurz-Rezension findet sich auf CSS-Online; im Anhang daran eine Beschreibung der verwendeten Techniken. Leela besticht nicht nur durch seine Spielstärke und die Möglichkeit, Wertungspartien zu spielen, sondern auch durch einen Analyse-Funktion, etwas, das anderen Go-Programmen unverständlicherweise fehlt. Zudem ist die GUI sehr aufgeräumt und intuitiv zu bedienen. Gewöhnen muß man sich sowohl an die extrem aggressive Spielweise sowie knappe Niederlagen; für ein Monte-Carlo-Programm wie Leela ist es kein Unterschied, ob es mit einem halben Punkt Vorsprung gewinnt oder das ganze Brett erobert. Typisch sind daher Partien, die Leela sehr knapp gewinnt, was einem das Gefühl gibt, es fast geschafft zu haben. Gerät Leela dagegen in Nachteil, macht sie sich nichts daraus, sämtliche Gruppen zu verlieren.

Beim Deutschen Go-Bund findet man Links zu allem, was mit Go zu tun hat.

Wer Schach zu remislastig und Go zu kompliziert findet oder überhaupt etwas gegen langweilige rechteckige Spielbretter hat, sollte sich mal an Hex versuchen! Das Spiel gehört zu den connection games; auf einem aus lauter Sechsecken zusammengesetzten Spielfeld in Parallelogrammform gilt es, mit seinen Spielsteinen zwei gegenberliegende Ränder zu verbinden -- der Gegner versucht dasselbe mit den anderen beiden Spielfeldrndern. Die Taktik ist zwar ziemlich simpel, erfordert jedoch im Detail erhebliche Sorgfalt, und remis gibt es nicht. Mit Hexy, dem Sieger in dieser Disziplin auf der 5. Computerolympiade 2000, können Einsteiger erstmal auf kleinen Brettern wie 5x5 die grundlegende Technik üben; Könner trainieren auf 11x11 - Hexy spielt auf allen Brettern stark. Natürlich gibt es noch weitere gute Hex-Programme für unterschiedliche Betriebssysteme.

Im Reversi sind auch die besten Menschen schon lange chancenlos gegen die Software, gleichwohl ist das Spiel auf dem 8x8-Brett noch nicht gelöst. Das Programm Zebra bietet dem Spieler Funktionen und Einstellmöglichkeiten bis zum Abwinken. Von Analysefunktionen, die einem genau zeigen, warum man vom Programm so furchtbar verhauen wurde über Speichern und Laden in mehreren unterschiedlich verbreiteten Formaten bis hin zur endgültigen Bewertung einer Stellung durch Dauerrechnen ist alles dabei. Während des Spiels zeigt Zebra auf Wunsch alle in einer Stellung möglichen Züge -- sehr praktisch, weil man sehr schnell in Zugzwang gerät gegen das starke Programm und auf diese Weise sofort sehen kann, dass es wirklich keine wundersame Rettung mehr gibt. Dem Computergegner kann man aber ins Hirn greifen und ihm die Anzahl der Züge vorgeben, die er vorausberechnen soll. So tastet sich ein mittelmäßiger Spieler schnell an seine Grenzen heran. Allerdings sollte man sich als Nicht-Profi keinen Illusionen hingeben, Zebra ist auch auf der schwächsten Stufe noch ein ernstzunehmender Gegner für ungeübte Reversi-Freunde. Kein Spielzeug für Anfänger also, wäre da nicht ein in der Online-Hilfe verborgene Strategie-Kurs der Extraklasse. Der beschreibt detailliert, worauf es ankommt, welche Strukturen es zu vermeiden und welche anzustreben gilt ... und wo die Ausnahmen sind. In den nächsten Partien wirkt das Spiel des Programmes dann ein bißchen verständlicher, ohne dass es aber deswegen weniger hoch gewinnt.

Auf der Homepage des Autors gibt es Zebra gratis für Windows, Linux und Pocket-PCs -- es sollte auf keiner Festplatte fehlen, sofern sich deren Besitzer auch nur ein klitzekleines bißchen für Denkspiele interessiert. Vielleicht findet sich sogar mal jemand für eine deutschsprachige Übersetzung, immerhin gibt es Zebra schon in Chinesisch und Japanisch.

Zillions of Games kann alles spielen. Wirklich alles, sogar Spiele, die es noch gar nicht gibt, denn es verwendet eine universelle Baumsuche und Regeldateien. In diesen Dateien steht eine Beschreibung der Spielregeln in einer einfachen Scriptsprache. Daraus bastelt sich Zillions dann selbst eine Bewertungsfunktion zusammen, die, kombiniert mit einer tiefen Suche, ausreicht, um die meisten Spiele einigermaßen gut zu spielen. Das klingt genial und ist es sicher auch, hat aber auch negative Seiten. Die Spielstärke ist natürlich ein Problem. In diesen Scripten wird ja nur angegeben, wie die Regeln sind und eben das Spielziel, keine Zwischenziele, keine Eröffnungsvorgaben etc. Das bastelt sich das Teil alles selbst zusammen. Dafür ist es gar nicht so schlecht. Mir ist aufgefallen, daß ich Spiele, die ich gut kenne, relativ leicht gewinne. Ok, Schach ohne Eröffnungsbuch und ohne handoptimierte Bewertung, da hat auch ein schwacher Spieler wie ich keine Probleme, aber auch 4-Gewinnt, GoMoku, Mühle (da ist's besonders schlecht), alles nicht die Stärke. Ausnahme ist Blobs (gab es früher als "infections"), aber da kann man als Mensch extrem schwer vorausberechnen, dito Reversi, wo allerdings eine spezielle DLL werkelt, kein Skript. Sofort chancenlos bin ich aber, wenn Chinesisches Schach, Shogi oder ähnliches kommt, was ich nur oberflächlich kenne, obgleich die Engine, zumindest beim Shogi, wesentlich schwächer als beim Schach sein müßte. Allgemein gesagt: Spiele, die man eingermaßen gut kennt, muß man nicht spielen gegen Zillions, aber wer kennt schon alle... Zillions kommt mit 48 verschiedenen Spielen, jedes in mehreren Varianten (beim Schach z.B. 23 verschiedene). Zu jedem Spiel werden die Regeln und die Geschichte erklärt, meist gibt es noch (allerdings überaus triviale und daher überflüssige) Tips zur Strategie. Es gab leider nur die erste Version in Deutschland zu kaufen; die wesentlich verbesserte zweite Version muß man sich in den USA besorgen.