Zeitschätzung für nächste Tiefe

Hallo!

Ich programmiere eine KI für ein Brettspiel. Dabei wird der MiniMax Alg. verwendet. Außerdem iterative Tiefensuche sowie Alpha-Beta-Pruning.

Nun möchte ich bestimmen, wie lange die nächste Tiefe in der iterativen Tiefensuche wohl ungefähr dauern wird.

Ich habe zuerst versucht zu bestimmen wie viele Blätter die Knoten (in der vorletzten Ebene) im Schnitt haben. Diesen Wert habe ich dann mit der Anzahl der Blätter multipliziert um eine geschätzte Anzahl Knoten in der nächsten Ebene zu erhalten.

Das funktioniert auch einigermaßen gut, wenn ich Alpha-Beta-Pruning abschalte. Aber mit A-B-P. haut das absolut nicht mehr hin.

Wisst ihr, wie man normalerweise die Zeit für die nächste Tiefe schätzt?

volkard

Einfach

schaetzung=zeitFuerAktuelleTiefe*faktor;

wobei der faktor empirisch ermittelt wird. Bei 4-Gewinnt in der Rohversion ist faktor=7 (logisch). Mit αβP so um 3.5.
Aber je nach Spielstellung kann der faktor deutlich kleiner werden, manchmal runter bis auf 1, wenn eine längere Zugfolge erzwungen ist. Naja, Hauptsache, die Schätzung wird nicht oft deutlich überschritten.