Ist es möglich, eine heuristische Bewertungsfunktion für Zustände zu erstellen? Ich bin mir bewusst, dass einer der Hauptvorteile von MCTS darin besteht, dass Sie dies theoretisch nicht benötigen würden, ABER: Wenn Sie trotzdem eine einigermaßen vernünftige Bewertungsfunktion erstellen können, können Sie die Simulationen frühzeitig stoppen, bevor sie einen Terminalspielzustand erreichen . Dann können Sie die Bewertung eines solchen Nicht-Terminal-Spielzustands anstatt nur eines Gewinns oder eines Verlustes sichern. Wenn Sie Ihre Simulationen so früh stoppen, können Sie möglicherweise mehr Simulationen durchführen (weil jede einzelne Simulation weniger Zeit benötigt).
Abgesehen davon wollen Sie versuchen, Wege zu finden, um zu "verallgemeinern". Wenn Sie eine Simulation ausführen, sollten Sie versuchen, zu ermitteln, ob Sie aus dieser Simulation auch nützliche Informationen für andere Knoten in der Baumstruktur extrahieren können, die Sie nicht durchlaufen haben. Beispiele für Verbesserungen, die Sie in diesem Sinne in Erwägung ziehen könnten, sind AMAF, RAVE, Progressive History, N-Gram Selection Technique.
Wissen Sie, wo der Engpass für Ihre Leistung liegt? Sie könnten dies mit einem Profiler untersuchen. Wenn die meiste Rechenzeit in Funktionen verbracht wird, die mit dem Spiel zu tun haben (Bewegungserzeugung, Fortschritt von einem Zustand zum nächsten usw.), wissen Sie sicher, dass die Anzahl der Simulationen, die Sie ausführen können, begrenzt ist . Sie sollten dann versuchen, Verbesserungen zu implementieren, die jede einzelne Simulation so informativ wie möglich machen. Dies kann beispielsweise bedeuten, dass wirklich gute, rechenintensive Auswertefunktionen verwendet werden. Wenn der Spielecode selbst bereits sehr gut optimiert und schnell ist, wird das Verschieben zusätzlicher Rechenzeit in Dinge wie Bewertungsfunktionen für Ihre Simulationszählung schädlicher sein und sich wahrscheinlich weniger auszahlen.
Für mehr zu dieser letzten Idee, könnte es interessant sein, einige Sachen zu sehen, die ich auf meiner MCTS-based agent in General Video Game AI geschrieben habe, die auch eine Echtzeitumgebung mit einem sehr rechenintensiven Spiel ist, was bedeutet, dass Simulationszählungen stark eingeschränkt sind (aber der Verzweigungsfaktor ist viel viel kleiner als es in Ihrem Fall scheint). PDF-Dateien meiner Publikationen dazu sind auch online verfügbar.
Welches Spiel ist es? ungefähr 500 Kindknoten? Baumst du den Baum nach jedem Zug nicht von Grund auf neu? Eine 1 oder 2 Auswahl in Kind-Knoten kann ausreichen, wenn Knoten auf der obersten Ebene, die unmittelbar auf den Wurzelknoten folgen, genügend Kinds und Simulationen haben. "Soll ich einen anderen Algorithmus verwenden?" hängt sehr vom Spiel ab. MCTS ist schlecht für Schach, aber zum Beispiel großartig für GO. –