Minimax-Algorithmus mit Memoization?

Question

Ich versuche, eine Verbindung vier AI mit dem Minimax-Algorithmus in Javascript zu implementieren. Derzeit ist es sehr langsam. Anders als das Alpha-Beta-Beschneiden, das ich implementieren werde, habe ich mich gefragt, ob es sich lohnt, Gamestates zu 1) ihren heuristischen Auswertungen und 2) dem nächstbesten Zug zu hashen. Ich kann sofort sehen, warum 2 nützlich wäre, da es viele Möglichkeiten gibt, denselben Spielstatus zu erreichen, aber ich frage mich, ob ich auch die aktuelle Tiefe hacken muss, um das zu schaffen. Wenn ich zum Beispiel diesen Zustand mit einer Tiefe von 3 (also sage nur 4 weitere Züge nach vorne) gegen eine Tiefe von 2 mit 5 Zügen erreichen würde, könnte ich zu einer anderen Antwort kommen. Bedeutet das nicht, dass ich die Tiefe mit dem Hash in Betracht ziehe? Meine zweite Frage ist, ob sich Hashes zu ihren Bewertungen lohnen. Ich brauche O (n) Zeit, um meinen Hash zu erstellen, und O (n) Zeit, um ein Board auszuwerten (obwohl es wirklich mehr wie O (2 oder 3n) ist). Sind Gamestates in der Regel zu ihren Bewertungen gehashed, oder ist das Overkill? Danke für jede Hilfe

Answer 1

Wenn Sie einen Wert eines Zustands (mit Heuristiken) Hashwert, müssen Sie Informationen über die Tiefe, bei der dieser Zustand ausgewertet wurde. Dies liegt daran, dass zwischen the value is 0.1 at depth 1 und the value is 0.1 at depth 20 ein großer Unterschied besteht. Im ersten Fall haben wir den Raum kaum untersucht, so dass wir uns nicht sicher sind, was passiert. Im zweiten Fall haben wir schon sehr viel Arbeit geleistet, also wissen wir, wovon wir reden.

Die Sache ist, dass wir für einige Spiele nicht wissen, was die Tiefe für eine Position ist. Zum Beispiel Schach. Aber in Verbindung 4, wenn Sie eine Position betrachten, wissen Sie, was die Tiefe ist.

Für die connect 4 hier die Tiefe 14 (nur 14 Kreise gesetzt wurden). Sie müssen also die Tiefe nicht speichern.

Ob Sie tatsächlich den Zustand Hash oder neu bewerten müssen. Natürlich kann eine Position in diesem Spiel über viele Spielpfade erreicht werden, so dass Sie erwarten, dass der Hash hilfreich ist. Eine wichtige Frage ist der Kompromiss zwischen dem Erstellen/Betrachten eines Hashes und der Intensität der Evaluierungsfunktion. Wenn es so aussieht, als würde es viel Arbeit machen - hash it und benchmarken.

Ein letzter Vorschlag. Sie haben alpha-beta erwähnt, was hilfreicher ist als Hashing (und nicht so schwer zu implementieren). Sie können weiter gehen und move ordering für Ihr Alpha-Beta implementieren. Wenn ich du wäre, würde ich es tun, und erst danach würde ich Hashing implementieren.