Hauptvarianten- bzw. Minimalfenstersuche (PVS, MVS )

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, in denen es wahrscheinlich ist, dass der betrachtende Zug ohnehin zu keiner Resultatsverbesserung führt – es also ausreicht, zu erkennen, dass dessen Evaluationswert niedriger als der bisher beste Evaluationswert ausfällt;
• hierfür setzt die MFS an sämtlichen inneren Knoten des Spielbaums an und macht sich zu Nutze, dass unter Verwendung einer guten Zugsortierung in den weitaus meisten Fällen der zuerst gesuchte Zug bereits das optimale Ergebnis liefert – ergo wird gemäß MFS nur der erste Zug eines jeden inneren Knotens k₁ mit dem vollen Alpha-Beta-Intervall der aktuellen Inkarnation von alphabetaminimax gesucht; der für den Knoten ermittelte Evaluationswert b(k₁) (bzw. das gegenwärtige alpha, insofern b(k₁) < alpha) bildet nun den Bezugspunkt für die Festlegung des sog. Nullfensters (b(k₁), b(k₁)+1), mit dem dann sämtliche verbleibenden Zugalternativen des Knotens zunächst betrachtet werden;
• es reicht nun aus, zu verifizieren, dass der für die übrigen Knoten ermittelte Wert b(k_i) kleiner oder gleich der unteren Schranke des Nullfensters ist;
• nur für den Fall, dass b(k_i) oberhalb liegt (und gleichzeitig unterhalb des aktuellen Werts beta), ergibt sich die Notwendigkeit eines Re-Searches mit der üblichen vollen Intervall-Größe der aktuellen Inkarnation von alphabetaminimax.

Die Anwendung des obigen Verfahrens erfordert eine geringfügige Modifikation der Alpha-Beta-Implementierung: Im Falle des Prunings eines Spielbaumknotens gibt alphabetaminimax nicht länger den Wert beta zurück, sondern den effektiven Evaluationswert, der beta überschritten hat – dies ist notwendig, um an der Aufrufstelle erkennen zu können, dass ein Re-Search notwendig ist. Wir sprechen hier von der sog. Fail-Soft-Implementierung des Alpha-Beta-Verfahrens.

Die MFS kommt auch im Rahmen der QS zum Einsatz.