Dr. Roland Stuckardt

IT-Beratung - Sprachtechnologie - Medienanalyse

Selektive Vertiefung der Suche

Wie in der QS geht es bei der Selektiven Suche um eine fallweise Vertiefung der Suche, jedoch hier nicht mit dem Ziel, unruhige Positionen tiefer auszuloten, sondern darum, Spielbaumknoten, für die nur wenige Zugoptionen (z. B. nur eine) bestehen, nicht auf die verfügbare Suchtiefe anzurechnen. Für Varianten, auf denen solche Knoten liegen, rechnen wir somit tiefer, wobei wir darauf hoffen, dass sich die Rechenzeit dennoch im üblichen Rahmen der vorgewählten Suchtiefe bewegt, da diese Knoten den Spielbaum nicht „nennenswert“ verbreitern.

Natürlich besteht eine gewisse Überschneidung mit der QS insofern, als Knoten, in denen sich die am Zug befindliche Partei im Schach befindet, oft die Bedingungen der selektiven Suchvertiefung erfüllen, da ja i. A. die Anzahl der Möglichkeiten, dem Schachgebot zu begegnen, begrenzt sind. Per definitionem jedoch findet die selektive Suchvertiefung alleine innerhalb der Non-QS-Suche statt: In der QS-Suche rekurrieren wir i. d. R. solange, bis wir eine „ruhige“ Position erreichen; die Anzahlen der in den QS-Knoten zu betrachtenden „spannungsresolvierenden“ Züge ist deshalb aus anderem Grunde beschränkt, weshalb wir uns (beinahe) keine Gedanken über die Anzahl zusätzlicher QS-Suchlevel zu machen brauchen.

Die selektive Vertiefung der Suche findet ferner keine Anwendung im Mattsuchmodus.

Implementierungstechnik

Fischerle verwendet derzeit folgende elementare Kriterien: Die Alpha-Beta-Suche wird mit zwei zusätzlichen int-Parametern ausgestattet, in denen wir mitzählen, wie viele fallweise einzulegende, dynamische Suchlevel noch zur Verfügung stehen:

  • verbleibende_dynsuchlevel;
  • verbleibende_trivdynsuchlevel.

Kandidaten für die durch Parameter verbleibende_dynsuchlevel abgedeckten dynamischen Suchlevel sind hierbei interne Knoten, die nur über eine geringe Anzahl von Zugoptionen verfügen. Maßgeblich ist hierbei der Wert der globalen Variablen DynSuchLevelZugKandidatenLimit: Insofern dieser Wert nicht überschritten wird und Parameter verbleibende_dynsuchlevel > 0 ist, so wird der gegenwärtige Suchlevel nicht auf die maximale Rekursionstiefe angerechnet. Derzeit ist DynSuchLevelZugKandidatenLimit auf den Ausgangswert 3 eingestellt, kann aber über das GUI bequem auf einen anderen Wert gesetzt werden. (Wie die Erfahrung lehrt, führt jedoch bereits ein Wert von 4 in einigen Fällen zu einer nicht mehr tolerablen Verlängerung der Suchzeit.)

Der zweite Parameter verbleibende_trivdynsuchlevel deckt nun sog. „triviale“ dynamische Suchlevel ab, die für solche Knoten eingeschoben werden, für die genau eine Zugoption besteht – also etwa für Fälle unbedingt erzwungener Antwortzüge auf ein Schachgebot; da derlei zusätzliche Zuglevel nur mehr die Variante verlängern, nicht jedoch den Suchbaum vergrößern können wir bezüglich der maximalen Anzahl derartiger als trivial bezeichneter zusätzlicher Suchlevel großzügiger sein, erfassen diese also durch einen gesonderten Parameter.

Wie viele entsprechende Selektive Suchebenen sollen also eingeschoben werden, d. h.: Wie sehen also die Initialwerte aus, mit denen die beiden genannten Parameter suchinitial ausgestattet werden? Fischerle verwaltet die entsprechenden Werte in zwei globalen Variablen:

  • DynSuchTiefe: Startwert 4;
  • TrivDynSuchTiefe: Startwert 10.

Die Belegungen beider Variabler können jedoch über das GUI modifiziert werden (letztere im Rahmen der ergänzenden Konfigurationswerkzeuge).

Bereits angedacht und vorbereitet, jedoch noch nicht umgesetzt, ist die Möglichkeit, die Anzahlen zusätzlicher selektiver Suchebenen zusätzlich abhängig zu machen von der modifizierten Suchbasistiefe .

Im Rahmen der Suche wird dann geschaut, ob der jeweils betrachtete Spielbaumknoten eines der Kriterien zur Einlegung eines dynamischen Suchlevels erfüllt und das Kontingent (gemäß dem entsprechenden Parameter) nicht bereits aufgebraucht ist. Sind beide Bedingungen erfüllt, so wird die Einschiebung des dynamischen Suchlevels dadurch umgesetzt, dass beim Übergang auf die nächst tiefere Rekursionsebene kein Dekrement des Parameters suchlevel durchgeführt wird.

Abschließend zu den Begriffen suchlevel vs. suchtiefe: Insbesondere die Selektive Suche macht eine entsprechende Unterscheidung unabdingbar:

  • Der sog. Suchlevel startet mit Werten > 0 (bzw. modisubati im ultimativen Schritt der Iterativen Vertiefung) und wird im Rahmen der rekursiven Vertiefung der Suche bedingt dekrementiert – allerdings mit der wichtigen Ausnahme der Einschiebung dynamischer Suchlevel. Wird der Wert 0 erreicht, so beginnt (fallabhängig) die QS; innerhalb der QS nimmt der Suchlevel dann negative Werte an.
  • Die sog. Suchtiefe startet mit dem Wert 0 und wird im Rahmen der rekursiven Vertiefung ausnahmslos inkrementiert – sie dient also als wichtige Basis insbesondere für den Zugriff auf die richtige (da suchebenenspezifische) Killerzug-Hashtafel sowie für die ebenfalls essenzielle korrekte Codierung der Mattdistanz bei der Anlegung von Transpositionstafel-Einträgen .