¿Alguna sugerencia distribuida de algoritmo de búsqueda en árbol paralelo?

Question

Escribo un bot distribuido de Go/Gomoku.

Básicamente el punto es distribuir la búsqueda de árbol en muchas computadoras. Con algoritmos básicos de búsqueda de árboles como DFS, esto sería muy simple, ya que podría simplemente dividir el espacio de búsqueda en subárboles. Aunque preferiría tener algo más eficiente, como mini-max con poda alfa-beta, pero desde mi punto de vista es bastante inútil sin ningún tipo de memoria compartida. Así que estoy algo atrapado.

¿Alguna idea de qué algoritmo podría usar que sea eficiente y se distribuya fácilmente? Y más importante aún, ¿dónde puedo encontrar algún código (pseudo) para ello o tal vez su implementación?

Gracias,

Answer 1

Necesitas leer acerca de Monte Carlo árbol de búsqueda, no porque sea intrínsecamente más fáciles de distribuir (que no es ni más fácil ni más difícil que otra búsqueda en árbol), sino porque es el estado del arte y las personas que trabajan en el problema están trabajando en la versión distribuida de ese algoritmo.

Si se toma la molestia de hacer un algoritmo distribuido, no hay ninguna razón para comenzar con uno menor. A menos que esté haciendo un algoritmo distribuido por razones educativas, en cuyo caso, continúe, habrá algo profundamente educativo en el experimento de distribuir un algoritmo básico y verlo funcionar peor que el algoritmo de última generación no distribuido. :)

Some slides

el MoGo homepage

Consulte la sección "acontecimientos recientes" en el Wikipedia page on computer go.

Answer 2

DDS* y ABDADA son 2 distribuidos algoritmos minimax/paralelas. Algunas comunicaciones son necesarias, pero esto se puede hacer transmitiendo ciertos resultados al controlador.

El enfoque más fácil como lo mencionó sería algo así como reducir el mapa con diferentes raíces de árbol de búsqueda.

Como @Pascal Cuoq rightly mentions, Monte Carlo Tree Search es el estado de la técnica en Go.

Aquí usted puede encontrar una buena explicación del algoritmo de búsqueda de MoGo y cómo su paralelizados:

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

nodos que están jugando a cabo con mejores resultados basados ​​en la reproducción aleatoria se exploran más profundamente. En cada paso, se selecciona un nodo hoja para una expansión de una capa. Esto podría distribuirse haciendo que cada máquina elija una hoja diferente para expandir.

una buena visión general del carlo árbol de búsqueda Monte está aquí:

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

Answer 3

Probar mapa Reduce el enfoque. Por ejemplo, ver

Breadth-First Search (BFS) & MapReduce