Wie funktioniert der NegaScout-Algorithmus?

Beim Alpha-Beta- Bereinigen behauptet NegaScout , dass es den Prozess beschleunigen kann, indem [Alpha, Beta] auf [Alpha, Alpha-1] gesetzt wird.

Ich verstehe den gesamten Prozess von NegaScout nicht.

Wie funktioniert es? Was ist sein Wiederherstellungsmechanismus, wenn seine Vermutung fehlgeschlagen ist?

Entschuldigung für die späte Antwort ( 4 Jahre !)

NegaScout ist ein sehr einfacher Algorithmus. Um zu verstehen, sollten wir die iterative Vertiefung überarbeiten .

Die iterative Vertiefung ist eine Technik für eine Schachengine, um nach der Tiefe i, dann i + 1, dann i + 2 usw. zu suchen. Dies ist ein Beispiel für dynamische Programmierung. Während jeder Iteration haben wir unsere beste Vermutung, was der beste Zug wäre. Die meisten Schach-Engines würden diesen Zug in einem Hashing-Tisch behalten.

Stellen Sie sich vor, wir befinden uns jetzt bei Iteration i + 1 und haben den besten Zug von der letzten Iteration i. Jetzt haben wir 5 Knoten zu suchen, sollten wir tun?

Wenn wir annehmen , wir haben recht gute Arbeit während unserer letzten Iteration getan, der beste Zug aus der letzten Iteration (die wir aus der Hash - Tabelle erhalten) soll auch der beste Zug für die aktuelle Iteration sein.

Wenn unsere Annahme richtig ist, sollten wir in der Lage sein, Zeit zu sparen, indem wir jeden anderen Zug als den besten Zug (die vier Züge, die nicht in der Hash-Tabelle enthalten sind) mit a durchsuchen null window. Ein Nullfenster ist so etwas wie:

score := -pvs(child, depth-1, -α-1, -α, -color)

Beachten Sie -α-1und -α. Dies sind die Alpha- und Betawerte, die wir für die nächste Rekursion angeben werden. Da die Breite des Fensters nur 1 beträgt, schlägt die Suche immer fehl:

• Wenn es unter α fehlschlägt, ist die Bewegung schlechter als wir es bereits haben, so dass wir sie ignorieren können
• Wenn es oberhalb von β fehlschlägt, ist der Zug zu gut zum Spielen, sodass wir ihn ignorieren können
• Andernfalls müssen wir eine neue Suche ordnungsgemäß durchführen

Natürlich werden wir immer noch den besten Zug (den, den wir aus der Hash-Tabelle erhalten) mit einem richtigen Alpha- und Betafenster suchen. Wir müssen dies tun, weil wir den Wert des Knotens genau kennen müssen, wir können ihn nicht einfach ignorieren.

Alles, was ich gesagt habe, ist im folgenden Pseudocode implementiert. Der Pseudocode gibt an, child is not first childaber dies ist eine Möglichkeit zu überprüfen, ob die Verschiebung auch die beste Bewegung in der vorherigen Iteration ist. Hash-Tabelle ist die häufigste Implementierung.

# Negasort is also termed Principal Variation Search - hence - pvs

function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α < score < β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # beta cut-off
        if α >= β
            break

    return α