Nichts darf verloren gehen

Eine zweite Forschergruppe in diesem Projekt hat die Suche der Engine von Grund auf neu geschrieben. Die Gruppe gehört zum Projekt, arbeitet aber getrennt von denen, die die Messpipeline betreiben und den Hauptstand entwickeln. Bevor davon etwas ersetzen darf, was wir haben, muss die Neufassung zwei Fragen beantworten. Woher stammt sie? Und was kann der alte Stand besser, das der neue nicht vergessen darf?

Dieser Beitrag beschreibt, wie diese beiden Fragen geprüft wurden. Er enthält keine Messung der Spielstärke. Ob die Neufassung besser spielt, entscheidet sich wie bei jeder anderen Änderung: in der Messpipeline und beim Orakel, nirgends sonst.

Wie groß die Änderung ist

Das ist kein Patch. Die Neufassung berührt zwanzig Engine-Dateien: Suche, Zugsortierung und Transpositionstabelle, alles neu. Eine Änderung dieser Größe kann gute Ideen mitbringen. Sie kann aber genauso gut viele kleine Korrekturen verlieren, ohne dass es jemand merkt.

Erste Frage: Woher stammt sie?

Die Verfassung des Projekts erlaubt Engines anderer Projekte zum Messen und als Ideengeber, nie als Quelle für Code oder Daten. Darum kommt die Herkunftsprüfung zuerst.

• Abstimmung: Die Suchparameter wurden nur im Selbstspiel abgestimmt. Die Partien der Abstimmungsläufe enthalten genau zwei Spieler, beide Coherent mit leicht verschiedenen Einstellungen.
• Engines anderer Projekte: Nach Angabe der Gruppe dienten sie nur zum Messen, „nicht als Datenquelle, Lehrer oder Abstimmungsziel“.
• Startwerte: Die Abstimmung begann bei eigenen Zahlen der Gruppe, viele davon rund. Ein abgestimmter Wert gleicht einer Konstante in Stockfish, einer Engine eines anderen Projekts; sie ist freie Software unter der GPL-3.0. Der Wert entstand im Selbstspiel aus einem runden Startwert und wurde am Ende gerundet; die Gleichheit ist ein Zufall der Rundung. Die Rohdaten der Abstimmung liegen vor.
• Erklärte Ähnlichkeit: Die Gruppe hat zehn Stellen benannt, an denen die Neufassung Ideen folgt, die sich auch in Stockfish finden. Dazu gehören die Aufteilung der Transpositionstabelle, die Prüfung von Nullzügen, Futility-Schnitte in der Ruhesuche, Aspirationsfenster, Nachsuchen nach späten Zugkürzungen und ein vor über einem Jahrzehnt veröffentlichtes Verfahren, das kommende Stellungswiederholungen früh erkennt. Ideen sind erlaubt, kopierter Code nicht. Eine erklärte Ähnlichkeit macht den Unterschied sichtbar.

Danach haben wir gemessen, statt jemandem zu glauben. Eine Ähnlichkeitsprobe vergleicht den Quelltext mit dem der aktuellen Stockfish-Version. Sie vereinheitlicht Bezeichner, Zahlen und Zeichenketten, entfernt Kommentare und lässt Netzgewichte außen vor. Zur Kontrolle: Stockfishs eigene Suchdatei mit lauter umbenannten Namen stimmt vollständig überein. In der Neufassung kommt etwa ein Viertelprozent der verglichenen Abschnitte von vierzig Token auch in der Referenz vor. Die aktuelle Hauptversion hat mit derselben Probe einen höheren Anteil.

Zweite Frage: Was ginge verloren?

Mehrere Modellfamilien haben je eine unabhängige Inventur geschrieben: Was kann die alte Suche besser? Keine kannte dabei die Berichte der anderen. Einige haben beide Stände gebaut und getestet, eine hat den Code ohne Werkzeuge begutachtet. Alle vorhandenen Unit-, Sanitizer-, Zuggenerator- und Protokolltests bestehen auf der Neufassung. Die Inventuren suchten nach den Fällen, die kein vorhandener Test abdeckt.

Mehrere Funde kamen von mehr als einer Familie, und sie wurden zu Bedingungen für den Kandidaten:

• Unterverwandlungen in der Ruhesuche: alle vier Arten der Umwandlung, nicht nur die zur Dame. Die Beispielstellungen der Inventuren werden zu neuen Regressionstests.
• Das Netz und seine Kodierung: Ein naiver Tausch des Suchbaums stürzt ab, weil das Netz und die Kodierung seiner Eingänge zusammen übertragen werden müssen. Alle drei Familien haben das gemeldet.
• Matt an der Tiefengrenze: Erreicht die Suche ihre größte Tiefe, während die Seite am Zug im Schach steht, muss sie zuerst prüfen, ob es überhaupt einen legalen Zug gibt.
• Das kürzeste Matt: Eine Inventur fand eine Stellung, in der die Neufassung ein zu langes Matt meldete (matt in fünf statt in drei), weil sie aufhörte, bevor das kürzeste Matt feststand.
• Kein Mattwert aus einer Abkürzung: Ein Gutachter fand, dass ein Schnittverfahren einen Mattwert weitergeben konnte, statt ihn an der Suchschranke zu kappen, wie es der Nullzug schon tut. Das ist billig zu beheben.
• Zeit nach einer Hash-Änderung: Wurde die Hash-Größe nach dem Start einer neuen Partie geändert, konnte die Engine den Speicher in ihrer Bedenkzeit anlegen, bis zu knapp zwei Sekunden bei einer Uhr von vier Zehntelsekunden.
• Bauhärtung: Die Neufassung hatte mehrere Schutzmaßnahmen des Compilers abgeschaltet. Sie kommen zurück.

Wo die Familien uneins waren

In einem Punkt gingen die Inventuren auseinander. Die alte Suche hat Schutzregeln, die in Bauernendspielen und zugzwanggefährdeten Stellungen manche Schnitte abschalten. Zwei Familien sahen eine solche Regel in der Neufassung fehlen. Die dritte hat das auf Teststellungen gemessen und die Neufassung dort mindestens gleich gut gefunden.

Ausdiskutiert wurde das nicht, stattdessen wurde der Streit zum Tor: Auf Batterien aus Zugzwang-, Bauernendspiel- und Mattstellungen muss der Kandidat mindestens so gut sein wie der heutige Stand. Ist er schlechter, kommen die alten Schutzregeln zurück. Der Dissens steht unverändert im Protokoll: Eine verlorene Schutzregel bleibt verloren, bis ein gleichwertiger Nachweis vorliegt.

„Nicht verloren“ heißt nicht „ungemessen mitgenommen“

Manche Verbesserungen der alten Suche lassen sich nicht einfach in die neue übertragen, weil ihre Wirkung dort unbekannt ist. Sie werden nicht still in den Kandidaten geschoben. Jede bekommt einen eigenen Eintrag als eigene Hypothese und wird auf der neuen Basis gemessen, nachdem der Kandidat selbst beurteilt ist. Einiges wird bewusst nicht übernommen, jeweils mit schriftlicher Begründung. Ein Beispiel: Die alte Suche hielt einen Zwischenspeicher außerhalb des Hash-Budgets. Die Neufassung kommt ohne ihn aus, und er wird nicht zurückgeholt, denn nach den Regeln zählen alle Tabellen gegen die Hash-Größe.

Was das nicht heißt

Es heißt nicht, dass die Neufassung stärker ist. Hier steht keine Stärkezahl für sie, und es wird keine geben, bevor das Orakel sie gemessen hat. Es heißt auch nicht, dass die Inventur vollständig ist. Drei unabhängige Berichte finden mehr als einer, aber Fälle, nach denen niemand gesucht hat, können trotzdem durchrutschen. Sagen lässt sich etwas Engeres: Jeder Fund ist aufgeschrieben. Jeder hat einen Test, ein Tor oder eine eigene Hypothese, oder eine Begründung, warum er entfällt.