Dr. Roland Stuckardt

IT-Beratung - Sprachtechnologie - Medienanalyse

Ruhesuche (Quiescence Search)

Die Ruhesuche bzw. Quiescence Search (nachfolgend kurz QS) verkörpert eine Tiefensuche über die Basistiefe der herkömmlichen Suche hinaus. Sie verfolgt das Ziel, solche Stellungen tiefer zu explorieren, in denen die statische Positionsevaluation keine aussagenkräftigen Werte liefert, da sie mitten in einer mutmaßlich erzwungenen Zugsequenz liegt, in der die am Zug befindliche Partei die Chance hat, eine erhebliche Verbesserung ihrer Verhältnisse zu erzielen. Eine wichtige Teilklasse verkörpern Stellungen in einer Abtauschsequenz, in der eine Partei bereits geschlagen hat, die andere Partei jedoch die Chance hat, die materielle Imbalance per Zurückschlagen auszugleichen. Solche Stellungen können demnach als unruhig bezeichnet werden; die QS verfolgt demnach das Ziel, solche Stellungen dynamisch zu explorieren, indem weiter in Richtung der mutmaßlich erzwungenen Folgezüge exploriert wird.

Die QS ist somit im Unterschied zur vollständigen Kernsuche, die bis zur Suchbasistiefe reicht, selektiv, da sie sich auf die Exploration derjenigen Zugoptionen beschränkt, die unmittelbar dazu geeignet erscheinen, die bestehende Dynamik aufzulösen.

Die QS von Fischerle

In der derzeitigen Version setzt Fischerle eine hochgradig selektive QS-Strategie ein, die die Ruhesuche auf folgende Fälle beschränkt: Die am Zug befindliche Partie

1. befindet sich im Schach;

2. hat die Möglichkeit, einen potenziell vorteilhaften Schlagzug zu tätigen;

3. kann mit einem Bauern die letzte Reihe erreichen und diesen somit in eine Figur umwandeln.

In der Ruhesuche werden bei Bauernumwandlungen nur die Möglichkeiten der Umwandlung in eine Dame oder einen Springer berücksichtigt, da Pattgefahr hier mutmaßlich nur eine untergeordnete Rolle spielt. Bauernumwandlungen können übrigens nicht nur im Rahmen der Fallklasse 3, sondern ebenso in Fällen der Klassen 1 und 2 auftreten.

In Zusammenhang mit Klasse 2 ist essenziell, was unter einem potenziell vorteilhaften Schlagzug zu verstehen ist. Fischerle verwendet hier folgende Kriterien: Als potenziell vorteilhaft eingestuft wird ein möglicher Schlagzug dann, wenn

a. die Möglichkeit besteht, eine höherwertige Figur mit einer geringerwertigen zu schlagen – wobei die Implementierung derzeit so gefasst ist, dass ein Läufer noch nicht als hinreichend höherwertig als ein Springer aufgefasst wird (obwohl eigentlich ein Materialvorteil von ¼ BE modelliert ist);

b. die am Zug befindliche Partei das Schlagfeld feldbeherrschungstechnisch majorisiert – m. a. W., die Partei verfügt über mehr Feldeinwirkungen auf das Feld als die gegnerische Partei.

Kriterium a erscheint unmittelbar klar: Insbesondere ist hier keine feldbeherrschungstechnische Majorisierung notwendig, da ja die am Zug befindliche Partei nach einmaligem Schlagen auf dem betroffenen Feld nicht gezwungen ist, eine ggf. verfügbare Abtauschsequenz nach eventuellem Zurückschlagen des Gegners weiter zu verfolgen.

Kriterium b hingegen greift auch in Fällen, in denen die zuerst schlagende Figur von gleichem oder sogar höherem Wert ist als die geschlagene Figur – dies im Hinblick darauf, dass die Materialbilanz der gesamten Abtauschsequenz auch hier letztendlich positiv ausfallen kann – Beispiel: wTurm schlägt sLäufer; sSpringer schlägt wTurm; wDame schlägt sSpringer.

Wichtig in diesem Zusammenhang ist, sich zu vergegenwärtigen, dass insbesondere die Erfüllung von Kriterium b noch nicht hinreichend dafür ist, dass eine Abtauschsequenz über dem entsprechenden Feld letztendlich tatsächlich „gewonnen“ ist – dies u. A. deshalb, weil dessen Operationalisierung auf die in der Stellungsrepräsentation verfügbaren Feldbeherrschungsinformationen zurück­greift, in denen ja mit gutem Grund (im Hinblick auf die technische Im­praktikabilität) darauf verzichtet wurde, etwaige Fesselungsrelationen mitabzubilden, da diese mitunter erst dynamisch in Erscheinung treten können. M. a. W.: Kriterium b spezifiziert einen heuristischen Anhaltspunkt, wann es sich lohnen könnte, einen bestimmten Schlagfall einer dynamischen Detailevaluation (d. h. einer QS) zuzuführen, nicht hingegen ein hinreichendes Kriterium, das eine statische Abtauschevaluation erlaubt.

Wichtig hierbei: Kriterium b basiert auf der Verfügbarkeit einer verfeinerten Stellungsrepräsentation, die auch transitive Figurenwirkungen („Batterien“ / Röntgen-Wirkungen) abbilden.

Unter alleiniger Berücksichtigung der Fälle 1, 2 und 3 führt nun Fischerle auf der Grundlage der Kriterien a und b selektive Ruhesuchen großer Tiefe durch. Es wird eine globale Variable QSMinSuchLevel geführt, die die maximale Tiefe dieser QS beschränkt. Es hat sich empirisch gezeigt, dass Kriterien a und b zu einer derart hohen Selektivität führen, dass es unter Effizienzgesichtspunkten unproblematisch ist, QSMinSuchLevel auf -30 (Der Wert ist per definitionem negativ – den „Nullpunkt“ verkörpern die Blätter der herkömmlichen Suche.) zu setzen; vermutlich käme man auch ohne jedwede Schranke aus, da die (materiellen) Ressourcen für die „Unruhe“ von Positionen naturgemäß begrenzt sind; ein Wert von -20 führte hingegen dazu, dass manche Ruhesuchen vor Erreichung einer ruhigen Stellung beendet werden mussten.

Eine weitere Feinheit, die sich im Rahmen der Implementierung der obigen QS-Strategien als essenziell erwies: Liegen QS-Fälle 2 oder 3 (d. h. kein Schachgebot) vor, so ist stets auch die Möglichkeit zu berücksichtigen, dass die am Zug befindliche Partei auch darauf verzichten kann, von der jeweiligen Schlagoption Gebrauch zu machen. Für die QS bedeutet dies in Bezug auf diese Fälle, dass nicht nur die rekursiv aus der QS gewonnene Bewertung, sondern darüber hinaus die statische Positionsevaluation der Stellung selbst in das Ergebnis einfließen muss. Für Fall 1 – Partei steht im Schach – gilt dies hingegen nicht, da dem Schachgebot in jedem Falle zu begegnen ist.

Insgesamt ließ sich erwartungsgemäß ein deutlich positiver Effekt der QS auf die Suchqualität beobachten. Offenbar wird mit der Ruhesuche dem Horizont-Effekt erfolgreich entgegengewirkt.

Fischerle implementiert die obigen Strategien als Bestandteil einer auf die Erfordernisse der QS spezialisierten Zuggenerierungsmethode generiereQSZuege() sowie der QS-Minimax-Methode alphabetaQSminimax().