Wie Computer Schach lernten

Der Mathematiker Norbert Wiener erfand die Kybernetik; sie kombinierte Biologie und Regelungstechnik. 1948 verfasste er dazu ein berühmtes Buch.  Der Mathematiker und Ingenieur Claude Shannon schuf die Informationstheorie. Im Februar und März 1950 legte er zwei Artikel vor, in denen er die Prinzipien von Schach spielenden Computern beschrieb. Ähnliche Ideen äußerte Wiener in seinem Kybernetik-Buch.

Claude Shannon müssen wir nicht mehr vorstellen. Er zählt zu den Gründervätern der Informatik; sein Hauptwerk ist die mathematische Informationstheorie. 2009 eröffnete das HNF über den Jongleur der Wissenschaft eine große Ausstellung. 2016 feierten wir im Blog seinen 100. Geburtstag. Im Mai 2019 erlebte ein neunzig Minuten langer Dokumentarfilm über ihn die Weltpremiere in New York.

Der Amerikaner war nicht nur ein begnadeter Mathematiker, Ingenieur, Bastler, Dichter und Artist, sondern auch ein Visionär. Seine Unterschrift finden wir unter dem Antrag an die Rockefeller Stiftung, der 1956 zur Konferenz von Dartmouth und zur Geburt der Künstlichen Intelligenz führte. Sechs Jahre vor der Tagung im US-Bundesstaat New Hampshire publizierte Shannon selbst zwei Artikel zum Thema. Sie klärten die Frage, wie man einen Computer dazu bringt, gut Schach zu spielen.

Gonzalo Torres-Quevedo, der Sohn des Erfinders, und Norbert Wiener 1951 am spanischen Schachautomaten. (Foto Computer History Museum)

Das erste Gerät für das königliche Spiel schuf 1770 der Österreicher Wolfgang von Kempelen. Es war eine Behelfslösung: Im Schachtürken saß ein Mensch und bediente Hand und Arm. 1912 baute Leonardo Torres Quevedo in Madrid einen Automaten, der im Endspiel mit drei Figuren siegte. Die verbesserte Version von 1920 ist in der Wochenschau überliefert. Claude Shannon wusste von den Automaten und entwickelte 1949 die Schachmaschine Caissac oder Endgame. Sie enthielt 150 Relais und berechnete ebenfalls Züge für das Endspiel.

Im Februar 1950 brachte das Magazin „Scientific American“ einen Artikel von Shannon über A Chess Playing-Machine. Schon der zweite Satz lautete, ins Deutsche übersetzt: „Lässt sich eine Maschine konstruieren, die ‚denken‘ kann?“ Die neuen Elektronenrechner, so hieß es weiter, würden Aufgaben lösen, die teils Lernen und teils Denken („semi-rote, semi-thinking“) erfordern. Der Rest des Artikels widmete sich dem Programmieren von Computern für „a fair game of chess“, ein Schachspiel auf gehobenem Niveau.

Claude Shannon beschrieb eine Strategie, die als Minimax-Prinzip bekannt wurde. Dazu gehört ein Algorithmus, der jede denkbare Schachposition bewertet, ihr also eine positive oder negative Zahl zuweist. Im einfachsten Fall folgt sie aus der Anzahl der Figuren einer Partei. Bauern erhalten eine 1, Läufer und Springer eine 3, Türme eine 5 usw.; am Ende wird alles aufsummiert. Ebenso wichtig ist die Vorausschau. Das Programm betrachtet die aktuelle Stellung auf dem Brett und ermittelt alle Positionen, die sich daraus in zwei, drei oder mehr Zügen entwickeln. Diese Positionen werden dann bewertet.

Claude Shannons Schachmaschine Caissac, benannt nach Caissa, der fiktiven Göttin des Schachspiels. (Foto Computer History Museum)

Das dritte Element ist die Bestimmung des Zuges. Es ist klar, dass jede Partei eine möglichst günstige Figurenstellung erreichen will. Jeder Spieler weiß aber auch, dass der Gegner die für ihn beste Position anstrebt. Eine selbst erklärende Animation für zwei Züge von zwei Spielern findet sich hier. Sie verwendet die Bewertungen 0, 1 und -1. Die Kreise stehen für die Entscheidungen von Spieler Nr. 1 beim ersten und zweiten Zug. Die Rauten unten zeigen den zweiten Antwortzug von Spieler Nr. 2 an, die Quadrate den ersten Antwortzug.

Im Artikel vom Februar 1950 deutete Claude Shannon an, dass der Computer neben dem Minimax-Prinzip eine Auswahl unter den jeweils möglichen Zügen vornehmen muss. Diesen Punkt arbeitete er in einem Aufsatz weiter aus, der einen Monat später im „Philosophical Magazine“ erschien: Programming a Computer for Playing Chess. Darin sprach er von Strategien des Typs A und B. Typ A ist das einfache Minimax-Prinzip mit Untersuchung aller Positionen nach drei abgeschlossenen Zügen. Der zweite Typ sah eine Konzentration auf wenige aber Erfolg versprechende Züge vor.

In den 1950er-Jahren entstanden nach Shannons Konzept zunächst Programme für das Damespiel – die Technik war einfach noch nicht weiter. Später bildete der Minimax-Algorithmus die Basis für Schachcomputer, die mit der Zeit immer stärker wurden. 1997 schlug der IBM-Spezialrechner Deep Blue den Russen Garri Kasparow, den besten Spieler der Welt, in enem Turnier. Claude Shannon hat es noch erlebt; er starb im Februar 2001. Erfand er aber auch das Minimax-Prinzip oder kam ihm jemand zuvor?

So scheint es zumindest. Wenn wir Norbert Wieners „Cybernetics“ aufschlagen, finden wir auf Seite 164 und 165 eine Notiz zum Schachspiel. Der Autor spricht von einem groben, doch nicht völlig trivialen Apparat. Er schaut mehrere Züge voraus und nimmt Bewertungen vor, allerdings nicht von Positionen, sondern von Zugfolgen. Im einfachsten Fall – ein Zug mit nachfolgendem Gegenzug – entscheidet sich Wieners Schachautomat für eine Aktion, die die bestmögliche Reaktion des Gegners erwartet. Die Passage bleibt letztlich rätselhaft.

Claude Shannon als Ehrengast der Computerschach-Weltmeisterschaft 1980 in Linz. (Foto Computer History Museum)

Könnte sie aber Claude Shannon zum Minimax-Prinzip inspiriert haben? Eher nicht, denn den Aufsatz aus dem „Philosophical Magazin“ oder eine frühe Fassung davon beendete Shannon am  8. Oktober 1948. So steht es gegen Ende des Textes nach den Danksagungen. Norbert Wieners Kybernetik-Buch war erst am 22. Oktober 1948 erhältlich. Die beiden Forscher erdachten unabhängig voneinander und zur gleichen Zeit ihre Schachverfahren. Der Algorithmus von Shannon ist dabei detailliert formuliert  und verrät gute Schachkenntnisse.

In den beiden Artikeln erwähnte Claude Shannon nirgends seinen Kollegen, er führte aber „Cybernetics“ im Literaturverzeichnis auf. Im „Scientific American“ verbirgt sich noch ein anderer Hinweis. Der Mann in dem Comic-Strip, der gegen einen Computer Schach spielt, ähnelt sehr dem Kybernetik-Vater. Das hing wohl damit zusammen, dass sich die oben erwähnte Passage aus Wieners Buch herumsprach und er plötzlich als Experte galt.

Am Ende des „Scientific American“-Textes stellte Shannon die Gretchenfrage: Kann ein Schachcomputer denken? Die Antwort hängt seiner Ansicht nach davon ab, wie wir das Wort definieren. Von außen betrachtet, ist der Computer tatsächlich denkfähig. Andrerseits macht der Rechner nur das, was er machen soll. Zitat: „Er arbeitete mit Versuch und Irrtum, aber die Versuche wurden vom Konstrukteur einprogrammiert, und die Irrtümer sind deshalb irrig, weil die Bewertungsfunktion der Figurenstellung einen niedrigen Wert zuwies.“

Soviel vernünftiges Denken ist siebzig Jahre später, in der Ära der KI-Euphorie, selten. Unser Eingangsbild zeigt keinen Schachcomputer, sondern einen Automaten für das Spiel „Wolf und Schaf“. Der Maschinenbaustudent Roderich Gräff baute ihn 1951 an der Technischen Hochschule Darmstadt mit Relais; er steht heute im HNF. Hier kann man das äquivalente „Fuchs und Hund“ spielen. Wer Lust auf Schach hat, findet hier einen Online-Partner, und unten Caissac, wie er jetzt aussieht. HNF-Geschäftsführer Dr. Jochen Viehoff traf ihn im MIT-Museum. Links hinter dem Gerät steht Claude Shannons Automat für das Brettspiel Hex.