Ich schreibe einen verteilten Go / Gomoku Bot.
Grundsätzlich geht es darum, die Baumsuche auf viele Computer zu verteilen. Mit grundlegenden Baumsuchalgorithmen wie DFS wäre das sehr einfach, da ich den Suchraum einfach in Teilbäume unterteilen könnte. Obwohl ich lieber etwas effizienteres hätte, wie Mini-Max mit Alpha-Beta-Beschneidung - aber nach meinem Verständnis ist es ziemlich sinnlos ohne jegliche Art von gemeinsamem Speicher. Also bin ich irgendwie festgefahren.
Irgendwelche Ideen, welchen Algorithmus könnte ich verwenden, der effizient ist und leicht verteilt werden kann? Und was noch wichtiger ist: Wo finde ich einen (Pseudo-) Code dafür oder vielleicht eine Implementierung?
Danke,
Sie müssen sich über die Monte-Carlo-Baumsuche informieren, nicht weil es einfacher zu verteilen ist (es ist weder einfacher noch schwieriger als eine andere Baumsuche), sondern weil es der Stand der Technik ist und die Leute an dem Problem arbeiten Arbeiten an verteilter Version dieses Algorithmus.
Wenn Sie sich die Mühe machen, einen verteilten Algorithmus zu erstellen, gibt es keinen Grund, mit einem kleineren zu beginnen. Wenn Sie keinen verteilenden Algorithmus aus pädagogischen Gründen machen, in diesem Fall, gehen Sie voran, es wird etwas sehr Aufklärendes im Experiment geben, einen Basisalgorithmus zu verteilen und zu sehen, dass er schlechter abschneidet als der nicht verteilte Algorithmus nach dem Stand der Technik :)
Die MoGo Homepage
Siehe den Abschnitt "Neueste Entwicklungen" auf der Wikipedia-Seite auf dem Computer .
DDS * und ABDADA sind 2 verteilte / parallele Minimax-Algorithmen. Eine gewisse Kommunikation ist notwendig, aber dies könnte durch Weiterleiten bestimmter Ergebnisse an den Controller erfolgen.
Der einfachere Ansatz, den Sie erwähnt haben, wäre etwas wie Map-Reduzierung mit verschiedenen Suchbaum-Wurzeln.
Als @ Pascal Cuoq erwähnt zu Recht , Monte-Carlo-Baumsuche ist der Stand der Technik in Go.
Hier finden Sie eine gute Erklärung von MoGos Suchalgorithmus und wie dieser parallelisiert wird:
Knoten, die mit besseren Ergebnissen spielen, die auf Zufallsspielen basieren, werden tiefer erforscht. Bei jedem Schritt wird ein Blattknoten für eine einlagige Erweiterung ausgewählt. Dies könnte verteilt werden, indem jede Maschine ein anderes Blatt zum Erweitern auswählt.
Einen guten Überblick über die Monte-Carlo-Suche gibt es hier:
Tags und Links algorithm language-agnostic distributed parallel-processing tree-search