English · Deutsch

MorrisTalk › Mühle lernen › Ist Mühle gelöst?

Ist Mühle gelöst?

Ja, und das Ergebnis ist ein Remis. Wenn keiner je einen Fehler macht, gewinnt niemand. Deshalb schlagen die Videos, die „immer gewinnen“ versprechen, in Wahrheit einen bestimmten Computergegner und nicht das Spiel.

Das Ergebnis: Remis vom leeren Brett aus

Im November 1993 gab Ralph Gasser bekannt, den Wert der Mühle vom leeren Brett aus berechnet zu haben. Keine Seite kann einen Sieg erzwingen. Wenn beide jedes Mal den besten Zug finden, endet die Partie unentschieden, und gestritten wird nur darüber, wer zuerst patzt. Seine ausführliche Arbeit „Solving Nine Men's Morris“ erschien 1996 in dem Sammelband Games of No Chance.

Er benutzte das Verfahren, das auch die Endspieltabellen im Schach hervorgebracht hat: am Ende anfangen und rückwärts rechnen. Eine Stellung, in der eine Seite nur noch zwei Steine hat oder nicht ziehen kann, ist für sie verloren. Eine Stellung, aus der man in so eine Stellung ziehen kann, ist gewonnen. So geht es Schicht für Schicht weiter, bis jede Stellung der Zugphase ein Etikett trägt. Die Tabellen umfassten rund zehn Milliarden Stellungen. Danach durchsuchte er die Setzphase, die 18 Halbzüge lang ist (je neun Steine), vom leeren Brett aus vorwärts, bis jede Variante in einer bekannten Stellung endete. Das leere Brett kam als Remis heraus.

Was „stark gelöst“ heißt

Gassers Tabellen kennen die richtige Antwort für jede Stellung, die vorkommen kann, nicht nur für die Anfangsstellung. Ein Programm, das darauf aufbaut, spielt auch nach Ihrem Patzer fehlerfrei und kann Ihnen für jede Stellung sagen, ob der Spieler am Zug gewinnt, remis hält oder verliert.

Gábor Gévay und Gábor Danner (Eötvös-Loránd-Universität und Universität Szeged) haben diese Arbeit neu gerechnet, erweitert und ein freies Programm namens Malom veröffentlicht. Ihr Aufsatz benennt ein Problem: Ein Programm, das einfach irgendeinen Remiszug wählt, spielt sehr oft Remis, „auch gegen Anfänger“, weil die meisten Remiszüge dem Gegner keine Gelegenheit zum Fehler geben. Also bauten sie eine ultra-starke Version. Sind mehrere Züge gleich gut, nimmt sie den, nach dem der Gegner die meisten Möglichkeiten hat, die Partie wegzuwerfen. Die komprimierte Datenbank ist etwa 12 GB groß (entpackt 78 GB), der Code ist quelloffen unter der GPLv3.

Also gibt es kein „immer gewinnen“

Gegen einen perfekten Gegner gibt es nichts zu gewinnen. Die Videos mit dem Versprechen gibt es in zwei Sorten.

Die erste schlägt einen bestimmten Computergegner, meistens den aus einem Videospiel. Der antwortet in derselben Stellung immer gleich; hat man seine Antworten einmal aufgeschrieben, kann man die Partie wiederholen. Das ist Auswendiglernen eines Programms und sagt nichts über den Freund am Küchentisch.

Die zweite zeigt eine Falle, fast immer die mit den zwei offenen Mühlen (die genaue Form und die einfache Gegenwehr stehen in der Eröffnungsanleitung). Sie funktioniert bei jemandem, der sie noch nicht kennt, und scheitert bei jedem, der sie kennt.

Wie man trotzdem Menschen schlägt

Viele Stellungen, die theoretisch Remis sind, sind es nur knapp: Eine Seite muss den einzigen guten Zug finden, die andere kann herumspazieren. Gévay und Danner sagen das ausdrücklich. Dort fallen die Partien unter Menschen. Ein paar Gewohnheiten daraus, als Rat und nicht als Beweis:

• Beweglich bleiben. Wer blockiert ist, verliert, und nach der Setzphase sind ohne einen genommenen Stein nur sechs Punkte frei (24 Punkte, 18 Steine).
• Stellungen suchen, in denen Sie drei brauchbare Züge haben und der Gegner nur einen guten, und dann weiterspielen, bis er ihn verpasst.
• Die Zwickmühle lernen. Sie macht aus einem kleinen Vorteil eine gewonnene Partie.
• Mit Uhr spielen. Turniere des Welt-Mühlespiel-Dachverbands (WMD) laufen mit Schachuhren, 5, 7 oder 10 Minuten pro Seite, auch damit es weniger Remis gibt.

Ist Anziehen ein Vorteil?

Theoretisch nicht: Anziehender und Nachziehender halten beide das Remis. Die deutsche Wikipedia nennt einen praktischen Punkt: Der Nachziehende setzt den achtzehnten Stein und sieht damit die ganze Setzphase, bevor er den letzten festlegt. Ein kleiner Vorteil, und nur, wenn man ihn nutzt.

Andere Bretter, andere Antworten

Die Lasker-Mühle (zehn Steine, man darf schon ziehen, solange man noch Steine in der Hand hat) ist ebenfalls Remis. Anders das Zwölf-Steine-Brett mit Diagonalen, im südlichen Afrika als Morabaraba gespielt: Gévay und Danner fanden dort nach ihren Regeln einen Sieg für den Anziehenden. Die Zwölf-Steine-Mühle in MorrisTalk hat eigene Regeldetails (Springen bei drei Steinen, Remis bei vollem Brett), das Ergebnis lässt sich also nicht einfach übertragen.

Und in MorrisTalk?

Die Roboter rechnen ein paar Züge voraus. Sie sind nicht Malom, und die Fallen in diesen Anleitungen funktionieren bei ihnen. Eine Partie endet remis, wenn dieselbe Stellung dreimal vorkommt oder 50 Züge ohne Setzen und ohne Schlagen vergehen. Wer wissen will, wie die Partie hätte laufen sollen, lässt sie hinterher durch Malom laufen. Während des Spiels sind Sie, Ihr Freund und der Sprachkanal unter sich.

Häufige Fragen

Weitere Mühle-Anleitungen

Quellen

• Ralph Gasser, Solving Nine Men's Morris, Games of No Chance (MSRI Publications 29), 1996 (englisch)
• Gévay und Danner, Calculating Ultra-Strong and Extended Solutions for Nine Men's Morris, Morabaraba, and Lasker Morris (arXiv:1408.0032, englisch)
• Malom, Projektseite, Universität Szeged (englisch)
• Mühle (Spiel), Wikipedia