Tic-Tac-Toe-Minimax: die Maschine, die sich weigert zu verlieren
Spiel Drei gewinnt gegen eine Maschine, die jede mögliche Zukunft liest und nie verliert. Sieh zu, wie sie jeden Zug bewertet, Sieg, Unentschieden oder Niederlage, bevor sie ihn macht.
Diese Woche hört die KI auf zu raten und fängt an zu rechnen. Das Perzeptron hat gelernt, die Markov-Plappermaschine hat gezählt; der heutige Gast tut weder das eine noch das andere. Er sucht.
Das Gadget unten spielt Drei gewinnt mit einer perfekten Strategie namens Minimax. Vor jedem Zug betrachtet es das ganze Spiel, jeden Zug, den es machen könnte, jede Antwort, die du geben könntest, bis zum letzten freien Feld, und wählt dann einen Zug, der nicht verlieren kann. Versuch ruhig, es zu schlagen. Du kannst es nicht. Das Beste, was du je erreichst, ist ein Unentschieden.
So geht’s:
- Wähle, ob du X spielst (du beginnst) oder O (die Maschine beginnt).
- Tippe ein Feld an. Die Maschine antwortet sofort.
- Beobachte das Feld neben dem Brett: Es listet jedes Feld auf, das die Maschine in diesem Zug abgewogen hat, samt dem garantierten Ausgang bei perfektem Spiel, Maschine gewinnt, unentschieden oder Maschine verliert, und markiert das gewählte.
Suchen, nicht lernen
Minimax ist herrlich dumm. Es hat keine Erfahrung, kein Training, keine Daten. Es nimmt einfach an, dass beide Spieler perfekt sind, spielt jeden Ast des Spielbaums durch und bewertet jedes Ende: +1, wenn die Maschine gewinnt, −1, wenn sie verliert, 0 bei Unentschieden. Dann nimmt es den Ast mit dem besten garantierten Wert. Das ist der ganze Trick.
Das ist die andere große Familie der frühen KI, jene, die nichts mit Neuronen zu tun hatte. Sie reicht von Claude Shannons Entwurf einer Schach spielenden Maschine von 1950 bis zu Deep Blue, dem IBM-Rechner, der 1997 Weltmeister Garri Kasparow schlug, indem er Millionen Stellungen mit handgemachten Regeln durchsuchte, rohe Vorausschau statt Lernen.
Warum es bei Drei gewinnt haltmacht
Drei gewinnt hat nur 255.168 mögliche Partien, ein Laptop liest sie alle im Handumdrehen. Schach hat mehr Stellungen als es Atome im beobachtbaren Universum gibt, deshalb konnte Deep Blue nur ein paar Dutzend Züge vorausschauen und musste sich auf eine clevere Bewertungsfunktion stützen. Go ist noch gewaltiger, weshalb der Sieg dort eine völlig andere Idee brauchte: die Mischung aus Suche und Lernen hinter AlphaGo im Jahr 2016.
Genieße also dein ungewinnbares Spiel. Es ist das kleinste, reinste Beispiel für gute alte KI: eine Maschine, die brillant wirkt, einfach weil sie gründlich ist.
Die früheren Ausgaben verpasst? Trainiere ein Perzeptron im Browser oder sieh einer Markov-Kette beim Plappern zu.