Lars Bremer

Klipp & klar:Populäre FehldeutungenModerne Schachprogramme lassen sich tief ins Hirn schauen, denn sie ge-ben eine Menge Informationen über ihren Rechenvorgang preis. Aller-dings muss man diese auch richtig interpretieren – und das scheint nichtimmer ganz leicht zu sein, wie ein Rundblick über die Forenlandschaftzeigt.

„Wie schnell ist Ihr Schachpro-gramm und wie tief rechnet es dennso?“ Einfache Frage? „600.000 Kno-ten pro Sekunde und 18 Halbzügetief“ wäre die falsche Antwort. Nein,es hat auch nichts mit magischenWörtern wie „brute force“ und „Se-lektivität“ zu tun. Die Auflösung gibtes ausnahmsweise im Vorspann:Schon die Frage war falsch gestellt.Warum das so ist, kann man auchohne Programmierkenntnisse verste-hen – wenn man sich nur die Mühemacht, alte Vorurteile über Bord zuwerfen.

Knoten

„Käpt‘n, was‘n das hier für einTau mit vielen Knoten drin?“

„Möönsch, Hein Blöd, du lernst esnicht mehr“, sprach Käpt‘n Blaubär.„Das ist doch kein gewöhnliches Tau,sondern eine Log-Leine. Die dient derPositionsbestimmung!“

Spricht ein Computerschach-freund von Knoten, meint er wederPalstek noch Englische Trompete,sondern eine (von einem Programmuntersuchte) Schachposition. Für denSchachspieler ist hier alles klar. JedesMal, wenn das Programm intern einenZug ausführt und so eine neue Stel-lung erzeugt, ist es ein Knoten mehrals vorher. Schachprogramme funk-tionieren aber anders als ein Gehirn.Manche erzeugen zunächst alle Züge,auch illegale. Das ist einfacher undgeht darum viel schneller als das Er-zeugen der legalen Züge. Beispiels-weise könnte ein Programm Schachsignorieren. Im nächsten Zug würdedann durch das Schlagen des Königsdie Variante als illegal erkannt. Weilaber die Suche öfter aufgerufen wur-de, hat solch ein Programm mehrKnoten berechnet als eines, das dieZüge vorher auf Legalität prüft.

Die Anzeige der berechneten Kno-ten, wie auch immer diese Zahl pro-

grammintern zustande kommt, besagtübrigens nicht das geringste über dieAnzahl der untersuchten unterschied-lichen Stellungen. Schachprogrammedurchsuchen den Spielbaum iterativ.Zuerst Tiefe Eins, dann Tiefe Zwei,usw. Bei jeder neuen Iteration kommtes an vielen schon vorher mit geringe-rer Tiefe berechneten Stellungen vor-bei und zählt diese nochmals. Wenndas Programm also eine Variante be-ginnend mit 1.Sf3 bis zur Iterations-tiefe 18 berechnet, hat es die nach demersten Zug Sf3 entstehende Stellungauch mindestens 18mal gezählt, eben-so sämtliche Stellungen nach anderenersten Zügen.

Knotenleistung

„Der Kutter ist zu langsam,Käpt‘n!“, rief ängstlich Hein Blöd.

„Wirf die Ladung über Bord, dannmachen wir mehr Knoten!“ gabKäpt‘n Blaubär zurück und rettetesich, Hein und den Kutter auf dieseWeise vor den grausamen Klipper-klar-Piraten von Engine-Bay.

Schachprogramme sind BlaubärsKutter sehr ähnlich – je mehr Regelnsie pro Stellung abarbeiten müssen,desto weniger Knoten berechnen siein einer bestimmten Zeitspanne. Inter-pretiert man „Regeln abarbeiten“kühn als „Schachwissen besitzen“,gelangt man schnell zum vielleichtverbreitetsten Irrtum der Computer-schach-Geschichte: Ein Programm,das wenig Knoten/Sekunde berech-net, ist klüger als eines, das viele Kno-ten/Sekunde berechnet. Viele Kno-ten/s = schnell und dumm, wenigKnoten/s = langsam und „wissensba-siert“, so der funkensprühende men-tale Sicherungsausfall.

Es handelt sich hier aber um einenunzulässigen Umkehrschluss. Frei-lich braucht zusätzlich hinzugefügterProgrammcode Zeit, bis er abgearbei-tet ist. Erweiterungen in der Bewer-

tungsfunktion schlagen sich deshalbtatsächlich in weniger angezeigtenKnoten/Sekunde nieder. Das bedeu-ten aber keinesfalls, dass jede Redu-zierung der Knotenzahl auf zusätzli-ches Wissen zurückzuführen wäre.

Grundsätzlich drückt jeder Pro-grammcode, der während der Sucheviele tausend Male abgearbeitet wird,die Anzahl der Knoten pro Sekunde.Die Verschwendung nur einer einzi-gen Mikrosekunde kostet an einerStelle, die pro ausgeführtem Partiezugeine Million Mal aufgerufen wird, 1Sekunde Bedenkzeit. Und eine Milli-on Knoten berechnen heutzutagedoch die meisten Programme schonim Blitz.

Als Beispiel mag eine grundlegen-de Technik wie der Killer-Algorith-mus dienen: Man stelle sich tief imSuchbaum eine einzügig hängendeweiße Dame vor. Weiß macht einenZug, der die Tante nicht in Sicherheitbringt und Schwarz schlägt sie mit ei-nem Bauern. Dieser Bauernzug, dereine ganze Dame einheimst, wird zumKillerzug erklärt. In der weiteren Be-rechnung probiert Schwarz nun aufjeden anderen weißen Zug zuerst denBauernzug, sodass sofort auffällt,wenn die Dame noch einsteht. DasProgramm kann auf diese Weise vielRechenzeit sparen, weil es in solchenVarianten die Suche abbrechen kann.Ohne den Killerzug wären vielleichtzunächst schwarze Züge untersuchtworden, die die Dame nicht schlagen,und erst nach der vollständigen Be-rechnung dieser nutzlosen Züge hättedas Programm den Damengewinn be-merkt. Der Killer-Algorithmus hatmit Schachwissen nicht das Geringstezu tun, er funktioniert genau so auchin Dame- oder Reversiprogrammen.

Angenommen, von zwei ansons-ten identischen Programmen verwen-det A diese Killer-Technik und Bnicht. B berechnet dann mehr Knotenpro Sekunde, weil A Zeit braucht, sichden Zug zu merken und nach vorn zusortieren. Trotzdem spielt A stärkerals B, weil es pro Halbzug Suchtiefeweniger Knoten benötigt (es kann javiele Varianten eher abbrechen) unddemzufolge tiefer in den Suchbaumeindringen kann.

Dieser Effekt tritt bei jeder Tech-nik auf, welche die Suche optimiert –der Code für den neuen und genialenTrick zur Baumbeschneidung musseben erst einmal abgearbeitet werdenund das kostet Zeit resp. Knoten/s.

Ratgeber

1 CSS 1/04

Suchtiefe

„Vorsicht, Käpt‘n, da vorn ist eineUntiefe!“ brüllte Hein Blöd. Blaubärblieb ganz ruhig. „Keine Bange,Hein, wir segeln nur eine Abkürzung.Das da vorn sind nur die berüchtigtenStromschnellen von Abschneid, wirkommen aber gleich in den Extension-Strom, da haben wir wieder jede Men-ge Wasser unter'm Kiel.“

Die ersten Schachprogramme,zum Beispiel die Turing-Engine,durchsuchten den Spielbaum bis zueiner bestimmten Tiefe. Jeder noch sounbedeutende Zweig wurde berech-net, jede Fortsetzung geprüft. Die Er-findung des Alpha-Beta-Verfahrensänderte daran zunächst wenig. Zwarmusste ein Programm nun nicht mehrjede Variante durchsuchen, der besteZug aber blieb derselbe. Innerhalb derSuchtiefe (gern „Brute-force-Sockel“genannt) spielte das Programm abso-lut göttlich und übersah nichts. Au-ßerhalb dieser Suchtiefe aber lag einunentdecktes Land, von dem jedesProgramm nur soviel wusste wie Ker-mit der Frosch vom Gefühlslebenblonder Stoffschweinchen. Die sau-bere Trennung zwischen Perfektionund Blindheit an den Blättern desSuchbaums, dem Horizont, führte zulustigen Effekten; hier eine Stellungvon 1983:XABCDEFGHY8 +ktr + +(7+ +ntR + '6p+ vL zp +&5+p+ +Lzp %4 zP zP + zp$3+ zP + +P#2P+ + +PmK"1+ + + + !xabcdefghy

Eine aussichtslose Situation fürdas schwarz spielende Programm –egal, was Schwarz anstellt, der Sprin-ger muss auch noch über die Klingespringen. Aber vielleicht kann mandas Pferdchen retten, dachte der Com-puter und rechnete los. Tatsächlich,man lenkt den Gegner einfach mitBauern ab: 1...g4 2.Lxg4 f5 3.Lxf5 a54.bxa5 b4 5.cxb4, und hier nun gab eskeine Ablenkungsopfer mehr. DerSpringer geht trotzdem verloren. DasProgramm schob den endgültigenVerlust der Figur über den Suchhori-

zont hinaus – ganze vier Bauern kos-tete das, bevor der Springer schluss-endlich doch verloren ging.

Um diesen Horizonteffekt abzu-mildern, dachten sich die Program-mierer vielerlei Tricks aus. ModerneSchachprogramme nehmen die ange-zeigte Brute-Force-Rechentiefe nichtmehr allzu ernst, sondern berechnenVarianten oftmals weniger tief, ande-re dafür umso tiefer. Ein veröffent-lichtes Verfahren zur Vorwärtsab-schneidung ist die Null-Move-Tech-nik. Dabei wird davon ausgegangen,dass es ein Vorteil sein müsste, zwei-mal hintereinander ziehen zu können.Die Suche führt also für eine Seite ei-nen Nullzug aus, der die Stellungnicht verändert, reduziert die maxi-male Suchtiefe und gibt das Zugrechtan die Gegenseite ab. Gelingt es die-ser nicht, ihre Bewertung (innerhalbder verkürzten Suche!) damit zu ver-bessern, taugt mit großer Wahrschein-lichkeit die ganze Variante nichts undes erfolgt ein Suchabbruch. Aller-dings ist die Annahme, es sei von Vor-teil, zweimal hintereinander ziehen zudürfen, nicht in jedem Falle richtig,weil besonders im Endspiel manch-mal Situationen auftreten, in denen esnachteilig ist, am Zug zu sein.

Auch bei anderen Vorwärtsab-schneidungen kann es vorkommen,dass ab und zu ein wichtiger Zug erst-mal durch den Rost fällt und von demProgramm erst viel später gefundenwird, als die angezeigte nominelleSuchtiefe vermuten ließe.

Lassen die Programmierer ihreSchöpfungen also eine bestimmteSuchtiefe anzeigen, verschweigen sieuns schamhaft, dass es sich eigentlichgar nicht wirklich um eine Suchtiefehandelt, sondern nur um eine interneVariable, welche die vom Programmdurchlaufenen Iterationen zählt. Stolzpräsentiert man uns dafür die Vertie-fungen, Varianten, die ein Programmweit tiefer als normal untersucht.Übrigens reicht schon ein kurzerBlick durch die Mathebrille, um zu er-kennen, wie viel die Programme vom

Suchbaum abschneiden, denn diehöchstmögliche Effizienz eines rei-nen Alpha-Beta-Algorithmus wird lo-cker übertroffen.

Wenn der neue Fritz oder Shred-der also anzeigt, „Tiefe = 18/43“, soheißt das keineswegs, dass sämtlicheVarianten bis zu einer Tiefe von 18Halbzügen untersucht worden wären.Dass manche Programme auch eineganz vom üblichen abweichendeTechnik erfolgreich umsetzen kön-nen, zeigt der vielfache Computer-schach-Weltmeister Junior, dessenIterationen kaum etwas mit der tat-sächlichen Suchtiefe zu tun haben.Auch „The King“ liefert eine von derFritz- und Shredder-Norm abwei-chende Suchtiefenanzeige.

Über eine neue Programmversionzu sagen „sucht drei Halbzüge tieferals der Vorgänger“ ist äquivalent zu„im Unterschied zum Vorgängermo-dell hat der neue Passat eine leicht ge-schwungene Kofferklappe“, keines-wegs aber zu „der neue Passat hat 50PS mehr als der Vorgänger“. Es wärefür jeden Schachprogrammierer ein-fach, eine Version zu erstellen, die100 Halbzüge tief sucht. Nur würdeein solcher Tiefenbohrer leider nichtvernünftig Schach spielen, weil zuviele wichtige Varianten aus demSuchbaum geschnitten wurden.

Fazit

„Käpt‘n, ich glaub‘ Ihnen keinWort.“ – „Aber Hein, ich sage dielautere Wahrheit!“

Wie schnell ist mein Programmdenn jetzt wirklich? Wer das für wirk-lich wichtig hält, muss schon Lösezei-ten messen. Ansonsten gilt: Wenn Ih-nen jemand von größerer Suchtiefe er-zählt, von schnelleren und langsame-ren Programmen oder von ach so vielWissenszuwachs einer neuen Pro-grammversion, der deutlich an der ge-ringeren Knotenleistung zu erkennensei – schenken Sie ihm genauso vielVertrauen wie einem blauen Bärenmit Kapitänsmütze.

Ratgeber

CSS 1/04 2

Abb. 1: Bewertung, Hauptvarianten, Suchtiefe, Knotenanzeige – Schach-programme geben jede Menge Informationen aus, die man fast alle fehlin-terpretieren kann.