SSS*

SSS* ist ein Suchalgorithmus, der 1979 von George Stockman eingeführt wurde. Er führt eine Zustandsraumsuche durch , indem er einen Spielbaum in einer Best-First- Methode durchläuft, ähnlich wie der A*-Suchalgorithmus .

SSS* basiert auf dem Konzept von Lösungsbäumen . Vereinfacht ausgedrückt, lässt sich aus jedem beliebigen Spielbaum ein Lösungsbaum bilden, indem man die Anzahl der Zweige an jedem MAX- Knoten auf einen reduziert. Ein solcher Baum repräsentiert eine vollständige Strategie für MAX, da er für jede mögliche Zugfolge des Gegners genau eine MAX-Aktion festlegt. Ausgehend von einem Spielbaum durchsucht SSS* den Raum der partiellen Lösungsbäume, analysiert schrittweise immer größere Teilbäume und erzeugt schließlich einen einzelnen Lösungsbaum mit derselben Wurzel und demselben Minimax-Wert wie der ursprüngliche Spielbaum. SSS* untersucht niemals einen Knoten, der auch durch Alpha-Beta-Pruning entfernt würde, und kann Zweige entfernen, die Alpha-Beta nicht entfernen würde. Stockman vermutete daher, dass SSS* ein besserer allgemeiner Algorithmus als Alpha-Beta sein könnte. Igor Roizen und Judea Pearl haben jedoch gezeigt ^{[ 1 ]} , dass die Einsparungen bei der Anzahl der von SSS* im Vergleich zu Alpha/Beta ausgewerteten Positionen begrenzt sind und im Allgemeinen nicht ausreichen, um den Mehraufwand an anderen Ressourcen (z. B. das Speichern und Sortieren einer Knotenliste aufgrund des Best-First-Algorithmus) zu kompensieren. Aske Plaat , Jonathan Schaeffer , Wim Pijls und Arie de Bruin haben jedoch gezeigt, dass eine Sequenz von Alpha-Beta-Aufrufen mit Null-Fenster äquivalent zu SSS* ist (d. h., sie expandiert dieselben Knoten in derselben Reihenfolge), wenn Alpha-Beta mit einer Transpositionstabelle verwendet wird , wie es in allen Spielprogrammen für Schach, Dame usw. der Fall ist. Das Speichern und Sortieren der OPEN-Liste war nun nicht mehr notwendig. Dies ermöglichte die Implementierung eines zu SSS* äquivalenten Algorithmus in Spielprogrammen in Turnierqualität. Experimente zeigten, dass es in der Praxis tatsächlich besser abschnitt als Alpha–Beta , aber NegaScout nicht übertreffen konnte . ^{[ 2 ]}

Die Umformulierung eines Best-First-Algorithmus als eine Folge von Tiefensuche-Aufrufen führte zur Formulierung einer Klasse von Null-Fenster-Alpha-Beta-Algorithmen, von denen MTD(f) das bekannteste Beispiel ist.

Es gibt eine Prioritätswarteschlange OPEN , die Zustände oder Knoten speichert. Dabei steht für : - Knotenidentifikator (Knoten werden in Punkt-Dezimal-Notation identifiziert; ist die Wurzel), - Knotenstatus (L – Knoten ist aktiv, d. h. noch nicht gelöst; S – Knoten ist gelöst), - Wert des gelösten Knotens. Die Elemente in der OPEN-Warteschlange sind absteigend nach ihrem Wert sortiert. Haben mehrere Knoten denselben Wert , wird der am weitesten links stehende Knoten im Baum ausgewählt. ${\displaystyle (J,s,h)}$${\displaystyle J}$${\displaystyle \epsilon }$${\displaystyle s\in \{L,S\}}$${\displaystyle J}$${\displaystyle h\in (-\infty ,\infty )}$${\displaystyle h}$${\displaystyle h}$

OPEN := { (e, L, inf) } while true do // wiederhole bis gestoppt Entferne ein Element p = ( J , s , h ) vom Anfang der OPEN-Warteschlange , falls J = e und s = S. Stoppe den Algorithmus und gib h als Ergebnis zurück. Andernfalls wende den Gamma-Operator auf p an.

${\displaystyle \Gamma }$Der Operator für ist folgendermaßen definiert: ${\displaystyle p=(J,s,h)}$

Wenn s = L und J ein Endknoten ist, dann ( 1.) füge ( J , S , min( h , Wert( J ))) zu OPEN hinzu. Andernfalls, wenn J ein MIN-Knoten ist, dann (2.) füge (J.1, L , h ) zu OPEN hinzu. Andernfalls (3.) für j = 1..Anzahl_der_Kinder( J ) füge (Jj, L , h ) zu OPEN hinzu. Andernfalls , wenn J ein MIN-Knoten ist , dann (4.) füge (Elternteil( J ), S , h ) zu OPEN hinzu. Entferne aus OPEN alle Zustände, die mit den Kindern von parent(J) verknüpft sind. else if is_last_child( J ) then // wenn J das letzte Kind von parent(J) ist (5.) Füge (parent( J ), S , h ) zu OPEN hinzu , sonst (6.) füge (parent( J ).( k +1), L , h ) zu OPEN hinzu // Füge den Zustand des nächsten Kindes von parent(J) zu OPEN hinzu 

• Schachprogrammierungs-Wiki
• George Stockmans Website