Eventuali suggerimenti dell'algoritmo di ricerca ad albero paralleli distribuiti?

Question

Sto scrivendo un bot Go/Gomoku distribuito.

Fondamentalmente il punto è di distribuire la ricerca dell'albero su molti computer. Con algoritmi di ricerca ad albero di base come DFS questo sarebbe molto semplice, dato che potrei semplicemente suddividere lo spazio di ricerca in sottoalberi. Anche se preferirei avere qualcosa di più efficiente, come mini-max con potatura alfa-beta, ma dalla mia comprensione è piuttosto inutile senza alcun tipo di memoria condivisa. Quindi sono piuttosto bloccato.

Qualche idea su quale algoritmo potrei usare che sia efficiente e distribuito facilmente? E, ancora più importante, dove posso trovare qualche codice (pseudo) per esso o forse l'implementazione?

Grazie,

Answer 1

è necessario leggere fino in merito a Monte Carlo albero di ricerca, non perché è intrinsecamente più facile da distribuire (non è né più facile né più difficile di un altro albero di ricerca), ma perché è lo stato dell'arte e che le persone che lavorano al problema stanno lavorando su una versione distribuita di tale algoritmo.

Se si ha intenzione di creare un algoritmo distribuito, non c'è motivo di iniziare con un altro. A meno che non si stia realizzando un algoritmo distribuito per ragioni educative, nel qual caso, andare avanti, ci sarà qualcosa di profondamente educativo nell'esperimento di distribuire un algoritmo di base e vederlo funzionare peggio dell'algoritmo avanzato non distribuito :)

Some slides

il MoGo homepage

vedere la sezione "recenti sviluppi" nel Wikipedia page on computer go.

Answer 2

DDS* e ABDADA sono 2 distribuiti algoritmi minimax/paralleli. Alcune comunicazioni sono necessarie, ma ciò potrebbe essere fatto riportando determinati risultati al controller.

L'approccio più semplice, come hai detto, sarebbe qualcosa come la riduzione della mappa con diverse radici di ricerca.

Come @Pascal Cuoq rightly mentions, la Ricerca di alberi Monte Carlo è lo stato dell'arte in Go.

Qui trovi una buona spiegazione di algoritmo di ricerca di MoGo e come la sua parallelizzati:

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

nodi che stanno giocando con i risultati migliori sulla base di riproduzione casuale sono più profondamente esplorati. Ad ogni passo viene selezionato un nodo foglia per un'espansione monostrato. Questo potrebbe essere distribuito avendo ciascuna macchina scegliere una foglia diversa da espandere.

una buona panoramica del Monte Carlo di ricerca albero è qui:

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

Answer 3

Prova mappa Riduci approccio. Ad esempio, vedere

Breadth-First Search (BFS) & MapReduce