gambit

Eine Schach-Engine sieht nur aus wie ein Projekt. Es sind drei Subsysteme, von denen jedes das Ganze auf seine eigene Weise ruinieren kann, und erst zusammen ergeben sie etwas, das sinnvoll spielt. Bei gambit geht es darum, diese drei Teile so gut aufeinander abzustimmen, dass das Ergebnis anfängt, einem echten Gegner zu ähneln, und nicht einem Zufallszuggenerator.

Scala 3 bietet hier eine ausdrucksstarke Sprache, um das Brett, die Züge und den Baum der Varianten zu modellieren. Aber die echte Herausforderung ist nicht syntaktisch, sondern algorithmisch: ein fehlerfreier Generator, eine faire Bewertung und eine Suche, die nicht endlos rechnet.

Ein Zuggenerator, der einen illegalen Zug pro Million Stellungen durchlässt, bringt die Engine dazu, etwas Unmögliches zu spielen. Eine Bewertung, die die Figuren falsch gewichtet, führt sie mit Überzeugung in eine Niederlage. Eine Suche ohne Beschneidung denkt stundenlang über einen Zug nach, der in einer Sekunde fallen sollte.

Keines dieser drei lässt sich abtun. Eine Engine, die in einem davon schwach ist, verliert, und zwar aus einem konkreten, benennbaren Grund, nicht aus allgemeiner Schwäche.

Die naive Suche prüft jede mögliche Fortsetzung, und davon gibt es schon wenige Züge tief Milliarden. Die Alpha-Beta-Beschneidung bemerkt, dass, wenn eine Antwort des Gegners eine Variante bereits widerlegt, der Rest seiner Antworten nicht berechnet werden muss. Bei guter Zugordnung schneidet das den Raum so stark, dass die Engine in derselben Zeit tiefer reicht.

Das ist keine kleine Optimierung, sondern der Unterschied zwischen einer Engine, die drei Züge vorausschaut, und einer, die sechs sieht. Im Schach schlägt sich diese Tiefe direkt in Spielstärke nieder.

Die Korrektheit des Zuggenerators wird mit dem sogenannten Perft überprüft: Sie zählen alle bis zu einer gegebenen Tiefe erreichbaren Stellungen und vergleichen sie mit Zahlen, die die ganze Schachgemeinschaft auswendig kennt. Stimmt Ihre Zahl nicht, haben Sie irgendwo einen Bug, und man sieht genau, bei welcher Tiefe die Abweichung beginnt.

Das Ergebnis ist eine vollständige Engine, die eine Stellung nimmt und einen Zug zurückgibt: Der Generator legt alle legalen Fortsetzungen aus, die Bewertung sagt, welche in eine bessere Richtung führt, und Alpha-Beta sucht so tief, wie es die Zeit erlaubt. Drei Subsysteme, die einzeln nur Teile sind, ergeben zusammen einen Gegner, der spielen kann.