Im Ort Min-Max-Baum Ungültigkeitsprobleme

Question

Ich versuche, eine parallele Implementierung eines min-max search zu bauen. Mein derzeitiger Ansatz besteht darin, den Baum auf eine kleine Tiefe zu bringen und dann von jedem dieser Knoten das normale Ding zu machen.

Der einfache Weg, dies zu tun ist, den heuristischen Wert für jedes Blatt zu berechnen und dann aufzureißen und das min/max zu berechnen. Das Problem ist, dass es alpha/beta pruning auf den oberen Ebenen weglässt und für einen großen Leistungshit sorgt.

Meine erste "Lösung" war es, die min/max nach jedem Blatt hochzudrücken. Dies gibt einen Aktualisierungswert, so dass ich den Baum einscannen und prüfen kann, ob ein Blatt beschnitten werden sollte.

Das Problem ist, dass es total kaputt ist. (2 Tage Debugging zu bemerken, dass, darn ich fühle mich dumm)

Nun zur Frage:

Gibt es eine Möglichkeit, einen Min-Max-Baum zu bauen, die die Blätter werden in zufälliger Reihenfolge ausgewertet werden können und erlaubt auch Alpha/Beta-Beschneidung?

Answer 1

Auschecken Parallelspiel Baumsuche, z.B. this paper.

Answer 2

Ich glaube, ich habe eine Lösung gefunden, aber ich es nicht in ein paar Grüße mag:

1. Beschriften der Baum mit der Zahl der noch nicht abgeschlossenen Kinder.
2. Nachdem ein Blatt ausgewertet wird, aktualisieren Sie es Eltern, dekrementiert der gräflichen Eltern
3. Wenn diese Zählung Null nur erreicht, aktualisieren Sie es Eltern, Abnahme, die
4. Lather, aufstieg, wiederholen

Alpha zählen/Beta-Beschneidung funktioniert wie erwartet.

Die Probleme damit ist, dass mit zufälliger Reihenfolge Auswertung mehr Knoten ausgewertet werden, bevor es beginnt, beschnitten zu werden. Auf der anderen Seite könnte dies durch eine bessere Anordnung der Blätter gemildert werden.