Neu: Tao-Engine zum kostenlosen Download

Bas Hamstra (Foto: Theo Storm)

Im Jahr 2000 sorgte bei der 20. Offenen Niederländischen Computerschach Meisterschaft in Leiden ein Newcomer für viel Wirbel: Das Programm Tao des holländischen Programmierers Bas Hamstra wurde mit einem Sieg über Fritz auf Anhieb zweitbestes Amateurprogramm bei diesem Turnier. Die Engine belegte am Ende mit 6 Punkten aus 11 Partien einen respektablen siebten Platz und landete in diesem Jahr bei größerem Teilnehmerfeld sogar einen Platz vor The King auf Rang 11.

Bas Hamstra schreibt über sich und die Entwicklungsgeschichte von Tao:

Mein Name ist Bas Hamstra, ich bin 39 Jahre alt und von Beruf Consultant bei einer IT-Firma. Ich hatte schon immer Interesse am Puzzeln. Bevor es das Internet gab, konnte man in sog. "Bulletin Boards" über alle möglichen Themen diskutieren. Wir veranstalteten dort Programmier-Wettbewerbe, z.B. musste der kürzeste Weg durch 80 Städte gefunden werden. Das war eine schöne Zeit und einige Leute haben jeden Tag neue Rekorde gepostet. Oder wir suchten alle Kombinationen von Wörtern mit 7 Buchstaben, so dass sich von oben nach unten das selbe Wort ergab wie von links nach rechts. Dabei diente das holländische "green booklet" (ein kleines Wörterbuch) als Datenbank. Derjenige, der alle möglichen Kombinationen in der kürzesten Ausführungszeit auflisten konnte, hatte gewonnen. Während dieser Zeit begann ich mich für Suchprobleme zu interessieren. Ich habe immer noch eine Assembler-Version vom n-Damen Problem auf meiner Platte (DAM.COM mit einer Dateigröße von 654 Bytes). Man gibt nur einen Parameter an: DAM n rechnet die Anzahl der Möglichkeiten aus, wie n Damen auf einem n mal n Schachbrett aufgestellt werden können, so dass keine Dame die andere schlagen kann.

Aber zurück zum Schach: Als das Internet populärer wurde fand ich die Computerschach-Newsgroup RGCC und erfuhr etwas über den Alpha-Beta Suchalgorithmus, den alle Schachprogrammierer benutzen. Ich probierte das in einem 4-Gewinnt Spiel aus und es funktionierte exzellent (obwohl ich es nicht schaffte, das Spiel zu "lösen"). Das war der Auslöser dafür, dass ich meine erste Schachengine programmierte. Diese spielte bei der FICS Internet Chess Competition und bekam eine Wertung von 2200. Das war zu der Zeit als die amerikanischen Amateurprogramme Crafty und Ferret auf dem Server regierten. Ich muss sagen, dass mich das alles nach einer Zeit durch die vielen ziellosen Partien gegen Crafty langweilte. Außerdem konnte ich keine Fortschritte machen und hätte damals fast mit dem Computerschach aufgehört. Doch das Programm Comet bewahrte mich davor, denn es spielte einfach anders. Es griff meinen König an und mein Programm wurde nach 16 Zügen auf h8 mattgesetzt. In der nächsten Partie jagte es meinen König in die Mitte des Brettes und ich wurde auf e4 mattgesetzt. Beim nächsten Mal durchbrach mein Programm Comets Rochade-Formation, als wollte es sich für seine Verluste rächen! Doch Comets König versteckte sich einfach hinter ein paar Bauern und ich wurde auf g2 ausgeknockt. Ich war einfach begeistert! Es war also möglich, ein Programm zu schreiben, dass nicht nur eine so hohe Wertung hat wie Crafty, sondern das dazu auch noch attraktiv spielt!

Also begann ich an einem neuen Programm namens Tao zu arbeiten und dieses Mal wollte ich es richtig machen. Taos Struktur ist objektorientiert, seine Basisobjekte enthalten hochoptimierte Kernroutinen, die Züge erzeugen und auf dem Schachbrett ausführen können. Von diesem Kern leiten sich neue Objekte ab, so dass man stufenweise neue Funktionalitäten einbauen konnte. Ich merkte, dass man sein zweites Schachprogramm viel schneller schreiben kann als das erste und nach ein paar Monaten trat ich bei der offenen holländischen Computermeisterschaft mit meinem neuen Programm Tao an. Ich kann mich an dieses Turnier noch sehr gut erinnern: Dort waren diese "Programmier-Götter" über die ich gelesen hatte, Frans Morsch und Johan de Koning. Zu meinem Erstaunen waren sie nicht viel älter als ich, antworteten ganz normal auf meine Fragen und hatten beide einen großartigen Sinn für Humor. Am ersten Tag war ich ein nervöser Neuling, am zweiten Tag wusste ich, dass ich das Turnier nicht ohne Punkte verlassen würde und am dritten Tag schlug Tao sogar Fritz. Tao wurde am Ende zweitbester Amateur (hinter Kallisto).

Seitdem hat Tao schon viele Entwicklungsschritte hinter sich gebracht, beispielsweise eine Phase mit sehr hoher Bewertung für Königsangriffe. So konnte Tao viele Partien durch starken Königsangriff gewinnen. Doch ich merkte, dass dies gegen fortgeschrittenere Gegner nicht optimal war, da Tao oftmals vor allem in langen Partien positionell überspielt wurde. Ich versuchte, mehr Balance in die Parameter zu bringen und fand heraus, dass es leichter ist ein Buch zu schreiben als eine Schachengine zu tunen.

Die Zukunft: Mein Wunsch ist ein Schachprogramm mit einem Stil wie Shirov oder Tal ("Feuer auf dem Brett"), welches aber auch ziemlich stark spielt. Das ist sehr schwierig, doch ich bin jetzt eigentlich fast an diesem Punkt angelangt (Comet ist allerdings noch näher dran mit seinen tollen Königsattacken). Ich teste gerade eine noch aggressivere Version von Tao, die mehr Wissen aber dafür eine geringere Suchtiefe hat. Die Zeit wird zeigen, ob ich diesen Ansatz doch wieder verwerfe und wieder eine andere Richtung einschlagen werde...

Weitere Informationen über Tao:

Tao entstand in mühsamer Eigenarbeit, basiert nicht auf einem anderen Programm und wurde auch nicht analog zu einem anderen Programm gestaltet. Mit Ausnahme einiger allgemein üblicher Techniken, wie dem Alphabeta-Algorithmus, der Verwendung von Hash-Tabellen, Tablebases und einigen anderen, ist Tao 100% einzigartig. Es ist mein zweites Schachprogramm (mein erstes hatte keinen Namen und erreichte auf dem FICS-Server ein Rating von 2200.)

Tao ist drei bis vier Jahre alt. Es ist ein Bitboard-Programm mit PVS-Suche ohne Wurzelfenster (aspiration). Es wird keinerlei Beschneidung von
überflüssigen Ästen in den Bäumen verwendet, wohl aber Null-Move-Heuristiken. Das Programm ist im Wesentlichen objektorientiert programmiert.

Tao strebt danach anzugreifen und ist ein taktisches Programm. Der Schwachpunkt ist das Endspiel. Obwohl das Endspielverhalten sich nach und
nach bessert, gibt es hier noch viel zu tun.


Versionsgeschichte:

4.3. Unwissens-basierte Version, optimiert für tiefe Suchen. Wissen, das Zeit kostete, wurde rausgeschmissen. Ich habe auf der Basis von Blitzpartien getunt.

4.4. Wenig Unterschied, leicht effizientere Suche.

5.0. Ich habe eine Menge Wissen hinzu gefügt, besonders über Endspiele, Königsangriff, Beweglichkeit und eingesperrte Figuren. Die Version sucht weniger tief als die vorhergehende, was sich aber nur bei Blitzpartien auswirkt. Bei längeren Bedenkzeiten ist die Version stärker.

5.1 Es wurde versucht, die Bewertungsfunktion neu zu schreiben.

5.2 Ich habe die neue Bewertungsfunktion verworfen und die alte wieder aufgenommen, welche etwas aggressiver eingestellt wurde. Weiterhin gibt es nun Tablebase- und UCI-Unterstützung.

5.3 In der Version 5.2 existierten zuviele Probleme mit der Zeiteinteilung, deshalb wurde diese bei der UCI- und Winboard-Version korrigiert. Es gab weitere kleinere Reparaturen sowie ein Tuning an der Bewertungsfunktion.

5.4 Letzte Details bei der Zeiteinteilung wurden korrigiert. Bei der Königssicherheit gab es Veränderungen, da ich diese nicht als akkurat empfand. Da alles gut funktionierte, konnte der Wert hochgesetzt werden. Diese Einstellung erzielte bisher die besten Ergebnisse auf dem Internetserver. Die Version wurde mit MSVC kompiliert, was eine Geschwindigkeitssteigerung von 30% brachte.