Geschichte der Schachprogramme: Fritz und die Papiermaschine
Geschichte der Schachprogramme Siege durch brutale Gewalt
Frederic Friedel, 76, studierte Philosophie, Wissenschaftstheorie und Linguistik in Hamburg und Oxford. Als Wissenschaftsjournalist beschäftigte er sich für ZDF und ARD schon in den Siebzigern mit Computerschach. 1987 gründete Friedel zusammen mit Matthias Wüllenweber das Unternehmen ChessBase, das heute weltweit zu den größten Anbietern von Schachsoftware gehört und auch Kooperationspartner des SPIEGEL war. Friedel lebt in Hamburg.
Das ist der zweite Teil der Serie über Computerschach von ChessBase-Gründer Frederic Friedel. Den ersten Teil finden Sie hier.
Eigentlich ist es ganz einfach: Um Schach spielen zu können, muss eine Maschine die Regeln kennen - sie muss wissen, wie die Figuren ziehen. Die Regeln korrekt zu definieren, verlangt große Aufmerksamkeit. Wenn man einen Fehler macht, kann es beispielsweise sein, dass Springer über den Brettrand ziehen und auf der anderen Seite auftauchen.
Wenn nun der Computer die Schachregeln korrekt verstanden hat, kann er für eine beliebige Stellung eine Liste aller legalen Züge erzeugen. Damit kann er, wie jeder menschliche Spieler auch, mit der "Voraussuche" beginnen: Wenn ich das spiele, und mein Gegner so kontert, kann ich das spielen, und wenn er dann das spielt, kann ich seinen Springer schlagen. Kommt Ihnen das bekannt vor? Natürlich führen Maschinen diese Voraussuche in atemberaubender Geschwindigkeit durch, und das führt zu einer enormen Zahl an Möglichkeiten.
Es gibt eine sehr große Zahl, die im Zusammenhang mit dem Schachspiel berühmt wurde. Der Legende nach hat der indische Wesir Sissa ibn Dahir das Spiel erfunden. Sein König, Shirham, war darüber so erfreut, dass er dem Erfinder sagte, er könne sich zur Belohnung alles wünschen, was er wolle. "Nur etwas Weizen", sagte Sissa, "ein Korn auf dem ersten Feld des Schachbretts, zwei auf dem zweiten, vier auf dem dritten, und so weiter." Der König war ob der Bescheidenheit des Wesirs sehr überrascht - bis er begriff, wie viele Weizenkörner er ihm schuldete: 18.446.744.073.709.551.615. Das sind rund 18,5 Trillionen, was der heutigen Weltproduktion für viele Jahrhunderte gleichkäme.
Sissa hat offenkundig die geometrische Progression gekannt - er verstand, wie Zahlen exponentiell anwachsen, wenn man sie sukzessiv mit einem gleichbleibenden Faktor, z.B. zwei, multipliziert. Das spielt eine wichtige Rolle in der generellen Theorie des Schachs: Werden wir jemals das Spiel "lösen"? Können wir eine perfekte Gewinnstrategie finden, indem wir alle möglichen Zugfolgen untersuchen? Die Antwort ist ein ausdrückliches Nein!
Mehr Züge als Sterne im Universum
In einer durchschnittlichen Schachposition hat ein Spieler 40 Züge, aus denen er wählen kann. Für jeden dieser Züge kann der Gegner 40 verschiedene Antwortzüge spielen. Das macht 1600 mögliche Zugfolgen nach nur einem Zug. Und die Zahlen wachsen exponentiell an: Nach zwei Zügen für jede Seite sind 102 Millionen verschiedene Fortsetzungen möglich, nach drei Zügen sind es 4,1 Milliarden. Das übertrifft schon die Anzahl der Sekunden in einem Menschenleben. Sissas Weizenkorn-Zahl wird nach sechs Zügen erreicht, und nach sieben Zügen sind wir bei der Anzahl der Sterne im Universum. Wenn wir annehmen, dass eine Schachpartie 40 Züge dauert, landen wir bei einer Zahl von 10128 möglichen Varianten. Zum Vergleich: Die Anzahl der Elementarteilchen im bekannten Universum beträgt rund 1086 - eine lächerlich kleine Zahl. Wirklich.
Also wird das Spiel definitiv niemals auf diese Weise gelöst werden, weil niemals alle möglichen Zugfolgen berechnet werden können. Aber das ist nicht notwendig. Wenn man alle möglichen Fortsetzungen bis zu einer beschränkten Zugtiefe berechnet, kann man schon eine annehmbare Spielstärke erreichen. Das genau tun Computer: Sie führen die Züge bis zu einer festgelegten Zugtiefe aus und bewerten die entstandene Stellung. Dann variieren sie die Zugfolgen systematisch und bewerten alle entstehenden Stellungen. Am Ende spielen sie den ersten Zug der Folge, die zur vorteilhaftesten Stellung führte.
Das ist im Grunde genommen das, was menschliche Spieler auch tun, allerdings viel langsamer als Computer. Ein Schachgroßmeister kann ein oder zwei Stellungen pro Sekunde im Kopf erzeugen und überprüfen; der Rechner schafft in gleicher Zeit einige Millionen. Wie können also Menschen mit ihnen konkurrieren?
Intelligenz vs. Brute Force
Der Unterschied in der Vorgehensweise von Menschen und Maschinen ist, dass erfahrene Schachspieler nur Fortsetzungen erwägen, die sinnvoll erscheinen. Sie wissen instinktiv, dass bestimmte Züge gefahrlos ignoriert werden können, weil sie zu nichts führen. Anstatt alle möglichen Zugfolgen zu überprüfen, ziehen menschliche Spieler nur plausible Fortsetzungen in Betracht. Bei ihnen ist der Verzweigungsfaktor in der Voraussuche eine viel geringere Zahl als 40. Dagegen müssen Computer generell alles untersuchen.
An dieser Gewaltmethode ("Brute Force method") schien das Projekt der Schachprogrammierung zu scheitern. In der Tat führten Rechner in den Anfangstagen sehr flache Suchen durch und spielten wie blutige Anfänger. Also versuchten Programmierer, "intelligente Abschneidungen" in der Baumsuche einzuführen. Sie wollten bestimmte, wenig sinnvolle Fortsetzungen an der Wurzel abschneiden, sodass der Rechner tiefer vordringen könnte.
Ein solches Beispiel war MacHack, ein Schachprogramm, das am Massachusetts Institute of Technology (MIT) von Richard Greenblatt entwickelt wurde. Er setzte über 50 aufwendige Bewertungsfunktionen ein, um "plausible" Züge zu bestimmen und nur solche in der Voraussuche zu berücksichtigen. In den ersten beiden Zügen waren es 15, danach nur neun. Dadurch ergab eine Suche von fünf Halbzügen nur 127.575 Stellungen, die bewertet werden mussten, nicht 102 Millionen, wie bei einem Brute-Force-Programm.
Sowjetischer Traum von der künstlichen Intelligenz
MacHack erreichte die Stärke eines fortgeschrittenen Amateurs. Es spielte Hunderte von Partien gegen Menschen - auch gerüchteweise drei gegen Bobby Fischer. Das Programm trat indes erst richtig ins Rampenlicht, als es den Philosophen und Künstliche-Intelligenz-Skeptiker Hubert Dreyfus schlug. Dieser hatte vorhergesagt, dass Computer es niemals schaffen würden, auch nur einen Zehnjährigen im Schach zu besiegen. MacHack widerlegte das.
Ein weiterer (berühmterer) Versuch der intelligenten Schachprogrammierung wurde von Michail Botwinnik, dem ehemaligen Schachweltmeister (von 1948 bis 1963, mit zwei Unterbrechungen), unternommen. Botwinnik war von Beruf Elektroingenieur und träumte davon, einmal die Sowjetwirtschaft mit künstlicher Intelligenz zu steuern. Mit einer Mannschaft von Computerwissenschaftlern entwickelte er ein sehr selektives Schachprogramm namens Pioneer, das allgemeine Prinzipien des Spiels verwendete, um die Baumsuche radikal zu verkürzen. Das Projekt litt unter mangelnder Verfügbarkeit von Rechenpower in der Sowjetunion, erregte aber große Aufmerksamkeit im Westen.
Tiefer, immer tiefer
Der Grund für den Erfolg von den Gewaltprogrammen war, dass Wissenschaftler eine Reihe von "Tricks" entdeckten, um die Voraussuche radikal zu verkürzen, ohne das Ergebnis zu verändern. Ein wichtiges Beispiel ist der Alpha-Beta-Algorithmus. Es wurde klar, dass man, nachdem das Programm für einen Baumzweig in der Suche eine klare Bewertung gefunden hat, den nächsten Ast komplett abschneiden kann, sobald eine schlechtere Bewertung in einer einzigen Zugfolge entdeckt wird.
Danach entdeckte man, dass die Reihenfolge, in der die Züge abgearbeitet werden, eine entscheidende Rolle für Alpha-Beta-Abschneidungen spielt. Also führte man zuerst eine flachere Suche durch, um die Abschneidungen zu optimieren kommt. Das Verfahren nennt man Iterative Vertiefung.
Indem man diese und ein Dutzend weitere ähnlich schlaue Algorithmen einsetzte, konnte man erreichen, dass Schachprogramme immer tiefer rechneten und immer stärker spielten. Der Versuch, "sinnvolle" Züge zu definieren und die "intelligente" Methode voranzutreiben, war gescheitert und wurde aufgegeben. Dazu kam die wahrhaft atemberaubende Geschwindigkeitsbeschleunigung von Computer-Hardware, die zum endgültigen Sieg der Brute-Force-Methode führte.
Ist dies das Ende der Geschichte? Mitnichten. Gerade in diesem Jahr erlebten wir eine grundsätzlich neue Richtung in der Schachprogrammierung - eine Entwicklung, die nicht nur für Schach, sondern für die Menschheit allgemein von größter Bedeutung ist. Das ist das Thema für den letzten Beitrag dieser Serie.
