Unerwartete Pfadabhängigkeit in Alpha-Beta-Suche?

Question

Ich schreibe eine künstliche Intelligenz für die alte nordische tafl Familie von Brettspielen (project here, source file at issue here). Sie sind nah genug an Schach, um das Wissen um Schach-KI in diesem Spiel anzuwenden. (Die betreffende Variante wird auf einem 7x7-Board mit einer radialsymmetrischen Startposition gespielt, wobei Weiß in der Mitte und Schwarz am Rand beginnt.) Ich stoße auf ein seltsames Problem mit der Implementierung der Alpha-Beta-Suche: Das Ergebnis einer Suche nach einer festen Tiefe, bei der neben der Alpha-Beta-Beschneidung keine Optimierungen aktiviert sind, ändert sich in Abhängigkeit von der Reihenfolge, in der die Knoten erkundet werden.

In der fraglichen Datei sind die wichtigen Methoden 'explore', 'exploreChildren', 'handleEvaluationResults' und 'generateSuccessorMoves'. 'explore' prüft, ob es eine Transpositionstabelle gibt (an anderer Stelle für diesen Test deaktiviert), wertet den Status aus, wenn es sich um einen Sieg- oder einen Blattknoten handelt, oder ruft exploreChildren auf. exploreChildren führt die rekursive Suche auf untergeordneten Knoten durch. generateSuccessorMoves generiert (und optional sortiert) die Bewegungen, die den aktuellen Status verlassen. handleEvaluationResults bestimmt, ob eine untergeordnete Auswertung einen Abbruch verursacht hat.

Also schrieb ich einen minimalen Testfall: generateSuccessorMoves sortiert zuerst überhaupt keine Sortierung, mischt dann einfach die Liste der Züge, anstatt sie zu sortieren. Die Ergebnisse der Suche werden in Folge nicht gleichwertig, noch in Folge Symmetrie Betrachtung noch in Wert:

MAIN SEARCH 
# cutoffs/avg. to 1st a/b a/b 
Depth 0: 0/0 0/0 
Depth 1: 0/22 0/1 
Depth 2: 42/0 3/0 
Finding best state... 
Best move: d3-g3 with path... 
    d3-g3 
    e1-f1 
    e4-e1xf1 
End of best path scored -477 
Observed/effective branching factor: 23.00/9.63 
Thought for: 72msec. Tree sizes: main search 893 nodes, continuation search: 0 nodes, horizon search: 0 nodes 
Overall speed: 12402.77777777778 nodes/sec 
Transposition table stats: Table hits/queries: 0/0 Table inserts/attempts: 0/0 
1. move: d3-g3 value: -477 
Using 5000msec, desired 9223372036854775807 
Depth 3 explored 1093 states in 0.037 sec at 29540.54/sec 
MAIN SEARCH 
# cutoffs/avg. to 1st a/b a/b 
Depth 0: 0/0 0/0 
Depth 1: 0/21 0/2 
Depth 2: 104/0 2/0 
Finding best state... 
Best move: d3-f3 with path... 
    d3-f3 
    d2-c2 
    d5-f5xf4 
End of best path scored -521 
Observed/effective branching factor: 23.00/10.30 
Thought for: 37msec. Tree sizes: main search 1093 nodes, continuation search: 0 nodes, horizon search: 0 nodes 
Overall speed: 29540.540540540544 nodes/sec 
Transposition table stats: Table hits/queries: 0/0 Table inserts/attempts: 0/0 
7. move: d3-f3 value: -521 

Dies ist ein Extremfall, natürlich, aber es ist mein Verständnis, dass Alpha-Beta in dieser Situation (dh , ohne irgendeine Funktion außer "Alpha-Beta-Beschneidung") sollte stabil sein, egal was die Reihenfolge der Suche ist - zumindest sollte es einen Knoten mit dem gleichen Wert zurückgeben. Liege ich falsch? Mache ich etwas falsch?

Erste Bearbeitung: obwohl ich vermute, dass es offensichtlich ist, aus der Beschreibung dieses Problems, stellt sich heraus, dass es in meiner Alpha-Beta-Implementierung einen noch unbekannten Bug gibt. Weitere Tests zeigen, dass es nicht das gleiche Ergebnis liefert wie reines Minimax.

Zweiter Schnitt: Dies ist die Pseudocode-Version der Alpha-Beta-Suche, die in der oben verlinkten Datei implementiert ist.

explore(depth, maxDepth, alpha, beta) 
    // some tafl variants feature rules where one player moves more than once in a turn 
    // each game tree node knows whether it's maximizing or minimizing 
    var isMaximizing = this.isMaximizing() 
    var value = NO_VALUE 

    if(isTerminal(depth, maxDepth)) 
     value = eval() 
    else 
     for(move in successorMoves) 
      if(cutoff) break 

      nodeValue = nextNode(move).explore(depth + 1, maxDepth, alpha, beta) 
      if(value == NO_VALUE) value = nodeValue 

      if(isMaximizing) 
       value = max(value, nodeValue) 
       alpha = max(alpha, value) 
       if(beta <= alpha) break 
      else 
       value = min(value, nodeValue) 
       beta = min(beta, value) 
       if(beta <= alpha) break 


rootNode.explore(0, 5, -infinity, infinity) 

Answer 1

Es stellt sich heraus, dass es meine Schuld war. Ich habe ein wenig Code, der die Knoten über einem bestimmten Knoten rekursiv neu berechnet, um sie bei der Suche nach Erweiterungen zu verwenden, und ich habe sie an der falschen Stelle aufgerufen (nachdem ich alle untergeordneten Elemente eines Knotens erkundet habe). Diese frühe Rückwärtsausbreitung verursachte inkorrekte Alpha- und Beta-Werte und daher frühe Cutoffs.