Kategorie: Suchtechniken im Detail

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 …

Fischerle verwendet eine Standardtechnik zur Suchverkürzung, die von praktisch allen State-of-the-Art-Schachmotoren eingesetzt wird: Transpositionstafeln (auch: Hashtafeln oder kurz TransTa) zur Verfügbarhaltung bereits berechneter Suchergebnisse. Konzeptuelle Beschreibung Skizze der Grundidee: (Besonders) im Rahmen einer vollständigen Suche des Spielbaums wird ein und dieselbe Stellung qua Zugumstellung (daher die Bezeichnung Transposition) auf unterschiedliche Weise erreicht. Es bietet sich deshalb an, die Suchergebnisse insbesondere der häufiger in Erscheinung tretenden Positionen abzuspeichern; wird nun eine Stellung erneut erreicht, so kann unter bestimmten Voraussetzungen eine erneute Suche über den Stellungsknoten hinaus entfallen. Je höher ein bestimmter Stellungsknoten im Spielbaum lokalisiert ist, desto höher die potenzielle Ersparnis. …

Fischerle verwendet eine Reihe weiterer Standardtechniken zur sog. Suchbeschleunigung, bei denen es im Unterschied zur oben beschriebenen Technik der Zwischenspeicherung von Evaluationsresultaten nicht darum geht, eine Suche a priori qua Rückgriff auf bereits bekannte Bewertungen abzukürzen, sondern vielmehr die Alpha-Beta-Cutoff-Rate dadurch zu beschleunigen, indem „viel versprechende“ Zugkandidaten zuerst exploriert werden. Insofern stehen die in diesem und den nachfolgenden Abschnitten beschriebenen Heuristiken zur Suchbeschleunigung eher auf einer Ebene mit den Ansätzen zur Optimierung der Zugkandidatensortierung. Konzeptuelle Beschreibung Die Idee hinter der Killerzug-Heuristik ist elementar, jedoch in der Praxis sehr wirkungsvoll: Züge, die sich bereits in Nachbarknoten derselben Suchtiefe als Cutoff-Verursacher (vulgo: …

Auf derselben Ebene wie die Killerzug-Heuristik kommt eine zweite Priorisierungsstrategie zum Einsatz. Konzeptuelle Beschreibung Sollte der Transpositionstafel-Look-Up für die aktuelle Stellung wie oben beschrieben zwar einen Eintrag geliefert, jedoch nicht die Bedingungen in Sachen Suchlevel und/oder beta erfüllt haben – eine unmittelbare Übernahme der in TransTa gespeicherten Bewertung somit nicht statthaft sein, so sehen wir den entsprechenden Zug dennoch als besonders plausiblen High Performer an, da er sich ja bereits in – möglicherweise nur unwesentlich abgewandeltem – Anwendungskontext gegenüber den Mitbewerbern durchgesetzt hat. Deshalb betrachten wir diesen als ersten zu suchenden Zugkandidaten, d. h. noch vor einem allfälligen Killerzug sowie …

Auf derselben Ebene wie Killerzug- und Transpositionstafel-Heuristiken angesiedelt. Die Präferierung von Zügen soll hier anhand von Kriterien erfolgen, die an der globalen Nützlichkeit von Zügen festmachen. Anders gesagt: Wir schauen auf die globale Statistik innerhalb der jeweils laufenden Partie und nicht alleine auf die suchlokale Nützlichkeit als Cutoff-Zug, wie dies die Killerzüge tun. Deshalb die Bezeichnung History-Heuristik. Konzeptuelle Beschreibung In der Literatur werden verschiedene Erfolg versprechende komplexere statistische Verfahren zur Implementierung einer History-Heuristik beschrieben. Im Rahmen der gegenwärtigen Version von Fischerle wird hingegen nur ein vergleichsweise elementares Verfahren verwendet. Wie die Killerzug-Heuristik basiert es auf einer Hashtafel, jedoch nur einer …

Die allgemeine Vorsortierung der Züge gemäß Plausibilitätsgesichtspunkten erfolgt in Methoden generiereZuege (allgemeine Suche) bzw. generiereQSZuege (Ruhesuche). Grundsätzlich geht es hier natürlich ebenfalls darum, dafür zu sorgen, dass potenzielle Cutoff-Verursacher in der Liste ganz vorne stehen. Die Zugsortierung basiert vornehmlich auf statischen (i. S. v.: keine volle rekursive Suche involvierenden) Kriterien wie beispielsweise die Präferierung von Bauernumwandlungen, LVA-MVV (least valuable aggressor – most valuable victim, d. h.: Erfolg versprechende Schlagfälle werden bevorzugt) oder eine weiter verfeinerte Statische Evaluation von Abtauschsequenzen (SEE – in der jedoch selbst bereits wieder „gesucht“ wird). Hauptanforderungen sind hier natürlich: Möglichst hohe Erfolgsquote – zu messen daran, …

Grundgedanken und Merkmale der Iterativen Vertiefung: Wir suchen nicht gleich mit maximaler Suchtiefe, sondern steigern diese mit 1 oder 2 beginnend; Vorteil: Wir können die Suche jederzeit abbrechen und erhalten trotzdem ein Ergebnis. → insbesondere zentrale Voraussetzung für die ausstehende Implementierung eines Zeitmanagements. Anders als auf den ersten Blick zu erwarten entsteht hierdurch in aller Regel kein Zusatzaufwand, da wir ja schrittweise die Transpositionstafel auffüllen und somit redundante Mehrfachberechnungen (weitestgehend!?) vermeiden; gemäß den Erfahrungen, die mit dieser Technik in vielen anderen Schach-Engines gemacht wurden, soll sich sogar i. A. eine signifikante Effizienzsteigerung ergeben. Grundgedanken und Merkmale der Aspirationsfenster-Suche: Die Aspirationsfenstersuche …

Vorab zur Terminologie: Hauptvariantensuche (englisch: Principal Variant Search – kurz PVS) und Minimalfenstersuche (MFS) seien nachfolgend als Bezeichner ein und desselben Konzepts verstanden: Es wird angestrebt, nur für die (vermutliche) Hauptvariante bzw. den (vermutlich) besten Zug der internen Spielbaumknoten eine Suche mit vollem Alpha-Beta-Fenster durchzuführen; für die übrigen Varianten soll ein sog. Minimalfenster gesetzt werden. In der Literatur wird deshalb auch von PVS/MFS gesprochen; nachfolgend verwenden wir jedoch der Einfachheit halber alleine den Bezeichner MFS. Konzeptuelle Beschreibung Grundgedanken und Merkmale der Minimalfenstersuche (kurz: MFS): wie im Falle der Aspirationsfenster-Suche: Beförderung des Spielbaum-Prunings per Wahl eines möglichst kleinen Alpha-Beta-Suchintervalls in Situationen, …

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 …