Irgendwelche Vorschläge für verteilte parallele Baumsuchalgorithmen?

Question

Ich schreibe einen verteilten Go/Gomoku Bot.

Im Grunde 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 ohne jegliche Art von gemeinsamem Speicher ziemlich sinnlos. Also bin ich irgendwie festgefahren.

Irgendwelche Ideen welchen Algorithmus könnte ich verwenden, der effizient ist und leicht verteilt? Und noch wichtiger, wo kann ich einen (Pseudo-) Code dafür oder vielleicht Implementierung finden?

Danke,

Answer 1

Sie müssen sich über Monte Carlo Baumsuche lesen, nicht weil es von Natur aus einfacher zu verteilen (es ist weder leichter noch schwieriger als eine andere Baumsuche), aber weil es der Stand der Technik ist und die Leute, die an dem Problem arbeiten, an der verteilten Version dieses Algorithmus arbeiten.

Wenn Sie sich die Mühe machen, einen verteilten Algorithmus zu erstellen, gibt es keinen Grund, mit einem kleineren Algorithmus 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 :)

Some slides

die MoGo homepage

Siehe "jüngsten Entwicklungen" in der Wikipedia page on computer go.

Answer 2

DDS* und ABDADA sind 2 verteilt/Parallel-Minimax-Algorithmen. Einige Kommunikation ist notwendig, aber dies könnte durch Weiterleiten bestimmter Ergebnisse an den Controller erfolgen.

Der einfachere Ansatz, wie Sie erwähnt haben, wäre so etwas wie Map reduzieren mit verschiedenen Suchbaumwurzeln.

Als @Pascal Cuoq rightly mentions, Monte Carlo Tree Search ist der Stand der Technik in Go.

Hier finden Sie eine gute Erklärung von MoGo-Suchalgorithmus finden können und wie seine parallelisiert:

http://www.lri.fr/~gelly/paper/nips_exploration_exploitation_mogo.pdf

Knoten, die basierend auf der Zufallswiedergabe mit besseren Ergebnissen spielen geführt werden tiefer erforscht. Bei jedem Schritt wird ein Blattknoten für eine einlagige Erweiterung ausgewählt. Dies könnte dadurch verteilt werden, dass jede Maschine ein anderes Blatt zum Erweitern auswählt.

eine gute Übersicht über die carlo Baumsuche monte hier ist:

http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf

Answer 3

Versuch Karte Reduzieren Ansatz. Zum Beispiel

Breadth-First Search (BFS) & MapReduce