Ich versuche alpha-beta min-max prunning mit Transpositionstabellen zu implementieren. Ich benutze diesen Pseudocode als Referenz:
%Vor%Drei Fragen zu diesem Algorithmus:
Ich glaube, ich sollte die Tiefe (= Abstand zur Blattebene) mit jedem gespeicherten Transponierungstabelleneintrag speichern und den Eintrag nur verwenden, wenn entry.depth & gt; = currentDepth (= der Eintrag ist mehr oder gleich von der Blattebene entfernt). Das wird im obigen Pseudocode nicht gezeigt und wird dort nicht besprochen, ich wollte sicherstellen, dass ich das richtig verstehe.
Ich möchte die beste Bewegung für jede Position speichern, um sie für die Verschiebungsordnung zu verwenden und die beste Bewegung nach dem Ende der Suche zu extrahieren. In reinem Min-Max ist es offensichtlich, welcher Zug der Beste ist, aber welcher Zug ist der Beste, wenn man mit Alpha-Beta-Cutoffs iteriert? Kann ich annehmen, dass der beste Zug für die gegebene Position der beste Zug ist, der gefunden wird, wenn der Loop endet (mit Cut-off oder ohne)?
Wenn ich diesen Algorithmus im iterativen Vertiefungsschema ausführe - sollte ich die Transponierungstabelle vor jedem Tiefenanstieg löschen? Ich denke nicht, ich möchte die gespeicherte Position aus der vorherigen Iteration verwenden, aber ich bin mir nicht sicher, ob die Informationen für tiefere Suchen geeignet sind (sollte es sein, wenn ich die Tabelleneingabefläche überprüfe)?
Sie haben Recht. entry.depth speichert die Anzahl der Lagen, auf die die Informationen im Transpositionstabelle-Eintrag basieren. Sie können diese Informationen also nur verwenden, wenn entry.depth >= remaining_depth .
Die Logik ist, dass wir ein Ergebnis nicht schwächer als die "normale" Suche verwenden möchten.
Manchmal wird zu Debugging-Zwecken die Bedingung wie folgt geändert:
%Vor%Dies vermeidet einige Suchinstabilitäten . Trotzdem garantiert es nicht das gleiche Ergebnis einer Suche ohne Transponierungstabelle.
Es gibt nicht immer die beste Art zu speichern.
Wenn die Suche nicht erfolgreich ist, gibt es keine "beste Bewegung". Das einzige, was wir wissen, ist, dass kein Zug gut genug ist, um einen Score größer als alpha zu produzieren. Es gibt keine Möglichkeit zu erraten, welche Bewegung am besten ist.
Sie sollten also eine Bewegung in der Hash-Tabelle nur für untere Grenzen (Beta-Cutoff, d. h. eine Widerlegungsbewegung) und exakte Bewertungen (PV-Knoten) speichern.
Nein, du solltest nicht. Bei iterativer Vertiefung wird immer wieder die gleiche Position erreicht und die Transponiertabelle kann die Suche beschleunigen.
Sie sollten die Transpositionstabelle zwischen den Bewegungen löschen (oder besser ein zusätzliches entry.age Feld verwenden) .
Tags und Links algorithm artificial-intelligence chess alpha-beta-pruning minmax