Über Zufälligkeit und Minmax-Algorithmus mit Alpha-Beta-Beschneidung

Question

Hat die Wahl des Kindes eines Knotens nach dem Zufallsprinzip im Alpha-Beta-Algorithmus eine bessere Chance, einen Schnitt zu bekommen, als sie in der Reihenfolge zu wählen?

Hier ist der Pseudocode mit meinem Zusatz mit *** markiert.

function alphabeta(node, depth, α, β, maximizingPlayer) 
    if depth = 0 or node is a terminal node 
     return the heuristic value of node 
    arrange childs of node randomly *** 
    if maximizingPlayer 
     v := -∞ 
     for each child of node 
      v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) 
      α := max(α, v) 
      if β ≤ α 
       break (* β cut-off*) 
     return v 
    else 
     v := ∞ 
     for each child of node 
      v := min(v, alphabeta(child, depth - 1, α, β, TRUE)) 
      β := min(β, v) 
      if β ≤ α 
       break (* α cut-off*) 
     return v 

lief ich eine kleine Probe mit diesem auf einem Vier-Spiel verbinden und es scheint ein wenig schneller zu laufen, aber wenn ich die Cutoffs mit und zählen eigentlich ohne Zufälligkeit, gibt es mehr Cutoffs ohne Beliebigkeit. Das ist ein bisschen seltsam.

Ist es möglich zu beweisen, dass es schneller (oder langsamer) ist?

Answer 1

Wird die Auswahl eines Knotens eines Knotens nach dem Zufallsprinzip im Alpha-Beta-Algorithmus eine bessere Chance haben, abgeschnitten zu werden, als die Auswahl in der richtigen Reihenfolge?

Kommt drauf an. In welcher Reihenfolge befinden sich die Kinder, wenn sie nicht explizit randomisiert werden?

Der beste Cutoff (die höchste Menge an Alpha-Beta-Beschneidung) tritt auf, wenn die Moveliste bereits nach Score sortiert ist - das heißt, die beste Bewegung tritt zuerst auf, dann die zweitbeste und so weiter.

Natürlich, wenn wir bereits wüssten, was der beste Schritt war, müssten wir nicht erst danach suchen.

Was viele Game-Engines machen, ist es, die vorherige Auswertung einer bestimmten Position zwischenzuspeichern und die Bewegungstabelle basierend auf der vorherigen Punktzahl zu sortieren (vorausgesetzt, die Position wurde zuvor evaluiert). Solche zwischengespeicherten Scores werden in der Regel nicht mehr korrekt sein, da der Ereignishorizont jetzt einen weiteren Weg darstellt, aber ihre Verwendung dient als eine gute Richtlinie für die Suche.