Minimax: Wie ein Gegner denkt, der Ihnen das Schlechteste wünscht

Spieltheorie, Teil 3 von 9

Manchester, 1952. Alan Turing spielt Schach gegen Alick Glennie, doch seine Züge wählt er nicht selbst. Er führt ein Programm aus, das er einige Jahre zuvor mit David Champernowne geschrieben hat.

Einen Computer, der es ausführen könnte, gibt es noch nicht. Also ist Turing selbst der Prozessor: Bleistift, Papier und Dutzende Minuten pro Zug.

Das Programm, später Turochamp genannt, verlor die Partie nach 29 Zügen. Doch die Regel, nach der Turing rechnete, hat ihn und seine Zeit überdauert. Heute wählen die meisten klassischen Schachprogramme ihre Züge danach aus – und auch der Dame-Bot von MindLounge. Diese Regel heißt Minimax.

Ein Zug wird nach seinem schlechtesten Fall beurteilt

Die Idee des Minimax passt in einen Satz: Beurteilen Sie Ihren Zug nach der besten Antwort des Gegners, nicht nach der Antwort, auf die Sie hoffen.

Am einfachsten zeigt das eine Falle, die fast alle kennen, die Schach lernen – der Schäferzug:

1.e4 e5 2.Lc4 Sc6 3.Dh5

Weiß droht 4.Dxf7 matt. Übersieht Schwarz die Drohung und spielt etwa 3...Sf6??, ist die Partie nach einem Zug vorbei. Manche stellen diese Falle, weil sie denken: „Und wenn es klappt?“

Minimax stellt eine andere Frage: Was passiert, wenn Schwarz die beste Antwort findet? So bewertet Stockfish 16 die beiden Möglichkeiten ungefähr (Tiefe 28–30, in Bauerneinheiten; Plus bedeutet Vorteil für Weiß):

Nach 3...g6 muss die Dame zurück, und Schwarz gewinnt Zeit für die Entwicklung. Der kleine Vorteil, den Weiß durch den Anzug hatte, geht auf den Gegner über. Er ist bescheiden, aber es ist ein Preis – und keiner, den man für die Hoffnung auf einen fremden Fehler zahlen sollte. Die Stellung nach 3.Dh5 können Sie selbst analysieren.

Woher kommt der Name? In jeder Stellung wählt der Gegner den Zug, der Ihr Ergebnis minimiert. Unter Ihren Zügen wählen Sie den, dessen Minimum am größten ist. Das Maximum der Minima: Minimax.

Warum Pessimismus hier keine Schwäche ist

Im Alltag nennt man jemanden, der immer das Schlimmste erwartet, selten weise. Warum ist es am Brett dann die richtige Strategie?

Die Antwort gab der aus Ungarn stammende Mathematiker John von Neumann. 1928 erschien in den Mathematischen Annalen sein Aufsatz „Zur Theorie der Gesellschaftsspiele“. Sein Schlüsselbegriff ist das Nullsummenspiel: Was ein Spieler gewinnt, verliert der andere. Schach, Dame, Go und Poker zu zweit sind Nullsummenspiele.

In einem solchen Spiel ist ein Gegner, der Ihnen das Schlechteste wünscht, nicht bösartig. Er spielt einfach für sich. Das Schlechteste für Sie ist genau das Beste für ihn. Anzunehmen, dass er die stärkste Antwort findet, ist deshalb kein Pessimismus, sondern heißt, seine Interessen ernst zu nehmen.

Von Neumann bewies noch mehr. Jedes endliche Nullsummenspiel zweier Personen hat eine Zahl – den Wert des Spiels.

Der erste Spieler kann sich mindestens dieses Ergebnis sichern, egal wie der Gegner spielt. Der zweite kann sicherstellen, dass der erste nicht mehr bekommt. Die Garantie „von unten“ und die Garantie „von oben“ fallen zusammen.

Eine wichtige Einschränkung gibt es. In Spielen mit verdeckter Information, etwa Schere, Stein, Papier, gilt diese Gleichheit nur, wenn die Spieler ihre Züge mit bestimmten Wahrscheinlichkeiten zufällig wählen. Solchen gemischten Strategien widmet die Reihe einen eigenen Teil.

Im Schach und im Damespiel, wo alles auf dem Brett zu sehen ist, wird der Wert durch eine gewöhnliche Zugfolge erreicht. Das ist das, was wir im zweiten Teil „die Antwort des Schachs“ genannt haben.

1944 veröffentlichten von Neumann und der Ökonom Oskar Morgenstern Theory of Games and Economic Behavior („Spieltheorie und wirtschaftliches Verhalten“). Mit diesem Buch verließ die Spieltheorie das Brett.

Wie Maschinen rechnen

Der Satz sagt, dass der Wert des Spiels existiert – nicht, wie man ihn findet. Schach lässt sich nicht bis zum Ende durchrechnen, das haben wir im vorigen Teil gesehen. Was macht ein Programm also?

1950 beschrieb Claude Shannon ein Rezept, das bis heute verwendet wird. Das Programm entfaltet einen Variantenbaum einige Halbzüge tief und hört dort auf. Die Endstellungen bewertet es näherungsweise mit einer Bewertungsfunktion: Material, Aktivität der Figuren, Königssicherheit.

Diese Werte wandern dann nach der Minimax-Regel den Baum hinauf. Wo das Programm am Zug ist, zählt das Maximum, wo der Gegner am Zug ist, das Minimum.

Turings Programm tat genau das, nur auf Papier. Es schaute etwa drei Halbzüge voraus und verfolgte Schlagzüge so lange, bis keine mehr möglich waren.

Die zweite wichtige Entdeckung war die Alpha-Beta-Suche. Mehrere Forscher fanden sie in den 1950er- und 1960er-Jahren unabhängig voneinander; eine vollständige Analyse veröffentlichten Donald Knuth und Ronald Moore 1975. Die Idee kennt jeder, der schon einmal zu lange ein Restaurant ausgesucht hat.

Angenommen, Sie haben bereits einen Zug gefunden, der Ihnen eine ausgeglichene Stellung sichert. Nun prüfen Sie einen anderen Zug und sehen, dass der Gegner eine Antwort hat, nach der Sie eine Figur verlieren. Die übrigen Antworten auf diesen Zug müssen Sie nicht mehr ansehen: Er ist bereits schlechter als der, den Sie haben. Bei idealer Zugreihenfolge kann ein Programm so in derselben Zeit bis zu etwa doppelt so tief rechnen.

Der heutige Stockfish ist genauso aufgebaut: Alpha-Beta-Suche plus Bewertungsfunktion. Geändert hat sich nur die Bewertung. Seit 2020 arbeitet darin ein neuronales Netz namens NNUE, nicht mehr nur von Menschen geschriebene Regeln.

Minimax bei MindLounge

Der Schach-Bot von MindLounge ist Stockfish, über seine Spielstärke-Einstellung absichtlich geschwächt. Für Dame gibt es keine fertige Engine dieser Klasse, deshalb wurde der Dame-Bot für die Seite von Grund auf geschrieben. Er ist Minimax mit Alpha-Beta-Suche in Reinform.

Das zeigt sein Code:

• die Stufen unterscheiden sich nur in der Tiefe: leicht rechnet 2 Halbzüge, mittel 4, schwer 6;
• ein Stein ist 1 Punkt wert, eine Dame 1,6, dazu kommen 0,05 für jede Reihe, die ein Stein vorgerückt ist;
• von zwei gleich sicheren Gewinnwegen wählt der Bot den kürzeren.

Ein Hinweis für alle, die Dame mit anderen Hausregeln kennen: MindLounge spielt auf 64 Feldern nach angloamerikanischen Regeln. Damen ziehen nur ein Feld weit, Schlagen ist Pflicht, und ein begonnener Mehrfachsprung muss zu Ende geführt werden.

Was bedeutet eine Tiefe von 2 in der Praxis? Wir haben eine für diesen Artikel konstruierte Stellung genommen und den Code des Bots darauf laufen lassen. Der Bot spielt Schwarz („s“); Schwarz ist am Zug:

8 · · · · 7 · · s s 6 · · · · 5 · · w s 4 · · · · 3 · · · w 2 · w · · 1 · · · · a b c d e f g h

Die leichte Stufe spielte e7-f6. Der Zug wirkt aktiv: Schwarz greift den Stein auf e5 an. Bei Tiefe 2 sieht der Bot seinen Zug und eine Antwort von Weiß. Vier Züge bekamen dieselbe Bewertung, und er nahm – so steht es im Code – den ersten.

Doch Weiß antwortet g3-h4! Jetzt muss Schwarz schlagen: f6xd4. Dieser Schlag räumt f6, und Weiß schlägt mit einem Zug zwei Steine, h4xf6xh8, und wird dabei auch noch Dame. Der letzte schwarze Stein auf d4 fällt im nächsten Zug.

Die mittlere und die schwere Stufe spielten g5-f4. Tiefe 4 sah, dass e7-f6 einen Stein kostet. Tiefe 6 sah mehr: Nach e7-f6 ist die Partie verloren.

Dieselbe Regel, derselbe Code, der einzige Unterschied ist die Sichtweite. Programmierer nennen das den Horizonteffekt: Was jenseits der Suchtiefe geschieht, existiert für Minimax nicht.

Wo Minimax nicht hilft

Es lohnt sich, auch die Grenzen dieser Denkweise zu kennen.

Der Horizont. Minimax ist genau so gut, wie es tief ist. Auch ein Mensch am Brett hat einen Horizont. Sich vor jedem Zug zu fragen „Was, wenn der Gegner die stärkste Antwort findet?“, schiebt ihn um mindestens einen Halbzug hinaus.

Ein Gegner aus Fleisch und Blut. Minimax nimmt an, dass der Gegner perfekt spielt. Menschen machen Fehler, und erfahrene Spielerinnen und Spieler wählen manchmal den Zug, der mehr praktische Probleme stellt. Doch eine ehrliche Rechnung prüft zuerst, ob dieser Zug die Stellung gegen genaues Spiel verschlechtert. Wenn ja, ist er keine Strategie mehr, sondern eine Wette auf einen Fehler.

Keine Nullsumme. Das ist die wichtigste Grenze. Minimax ist gerechtfertigt, wenn Ihr Gewinn der Verlust des Gegners ist. In Verhandlungen, im Beruf oder in Freundschaften ist das meist nicht so. Wer dort handelt, als wünsche ihm der andere das Schlechteste, riskiert, dass beide leer ausgehen. Genau darum geht es im nächsten Teil der Reihe.

Übung

1. Eine weitere Stellung, an der wir den Bot getestet haben. Die leichte Stufe (Schwarz) spielte a7-b6. Finden Sie den Zug von Weiß, der Material gewinnt.

8 · · · · 7 s s · · 6 · · · · 5 · s w · 4 s · · · 3 w · w · 2 w · · · 1 · · · · a b c d e f g h

1. Sie wählen zwischen den Zügen A und B. Gegen A hat der Gegner zwei Antworten: Nach der einen stehen Sie bei +3, nach der anderen bei −1. Gegen B führen die beiden Antworten zu +1 und +2. Welchen Zug wählt Minimax? Und welchen jemand, der auf einen Fehler hofft?
2. Spielen Sie gegen den Dame-Bot von MindLounge auf der leichten Stufe und versuchen Sie, ihm einen Schlag „einen geben, zwei nehmen“ zu stellen. Versuchen Sie danach dasselbe auf der mittleren Stufe.

Die Antworten finden Sie am Ende.

Fragen zur Diskussion

• Haben Sie schon einmal eine Falle gestellt und auf einen Fehler des Gegners gesetzt? Wie ging es aus?
• Wo in Ihrem Leben ist es nützlich, vom schlechtesten Zug des „Gegners“ auszugehen, und wo schadet diese Annahme?
• Auf der leichten Stufe verrechnet sich der Bot nicht – er sieht nur nicht weit. Ähneln Ihre eigenen Fehler am Brett dem?

Als Nächstes in der Reihe: „Das Gefangenendilemma“ – ein Spiel, in dem jeder für sich vernünftig handelt und beide verlieren.

Antworten. 1) e3-d4! Schwarz muss mit c5xe3 schlagen, und Weiß antwortet mit dem Doppelsprung a3xc5xa7. In dieser Stellung spielen die mittlere und die schwere Stufe c7-b6 und lassen den Schlag nicht zu. 2) Minimax wählt B: Der schlechteste Fall ist dort +1, bei A −1. Wer auf einen Fehler hofft, wählt A wegen der +3. 3) Hier gibt es keine fertige Antwort: Das Experiment gehört Ihnen.