poda alfa beta distribuida

19

Estoy buscando un algoritmo eficiente que me permita procesar el árbol de búsqueda minimax para ajedrez con poda alfa-beta en una arquitectura distribuida. Los algoritmos que he encontrado (PVS, YBWC, DTS, ver más abajo) son bastante antiguos (1990 es el último). Supongo que ha habido muchos avances sustanciales desde entonces. ¿Cuál es el estándar actual en este campo?

Además, indíqueme la explicación de un idiota sobre DTS, ya que no puedo entenderlo por los trabajos de investigación que he leído.

Los algoritmos mencionados anteriormente:

  • PVS: división de variación de principio
  • YBWC: concepto de Young Brothers Wait
  • DTS: división dinámica de árboles

son todos se discuten aquí .

algorithms distributed-systems board-games wirate
fuente
Tal vez esta es una lectura interesante: chessbase.com/newsdetail.asp?newsid=8047
Alex ten Brink
2
Bueno, este es un problema (paralelizar la búsqueda de minimax o cualquiera de sus variantes) particularmente difícil. En un artículo publicado este año por Richard Korf titulado "Retos de investigación en búsqueda combinatoria", se puede leer lo siguiente: "La búsqueda [...] minimax con poda alfa-beta, ha sido notoriamente difícil de paralelizar", dudo sinceramente hay un algoritmo que lo hace siempre eficiente ...
Carlos Linares López
Entonces, teniendo en cuenta que soy un estudiante de informática de 4to semestre muy humilde, ¿debería optar por un algoritmo serializado o tratar de esperar una aceleración sub-lineal aceptable?
wirate
Perdón por el retraso en mi respuesta, esto pasó completamente desapercibido en mi bandeja de entrada. De hecho, esperaría que los ahorros finales dependan completamente de la distribución de los puntajes asignados por su función de evaluación a las hojas del árbol de búsqueda. En general, no hay garantías de que un algoritmo de búsqueda distribuido funcione significativamente mejor que un algoritmo de búsqueda alfa-beta serializado. Por lo tanto, definitivamente elegiría una versión serializada de él probando tantas mejoras como sea posible (movimientos de pedidos, tablas de transposición, etc.)
Carlos Linares López
He tenido cierto éxito con la alfa-beta paralela (básicamente como se describe en la página wiki a la que se vinculó).
Jeremy List

Respuestas:

3

Sí, la teoría ha avanzado significativamente y algo debido a la literatura de análisis de ajedrez y a las técnicas generales de programación paralela. Aquí hay algunas referencias más recientes sobre poda alfa beta (ajedrez) sobre grupos distribuidos / paralelismo. También parte de la literatura de ajedrez computacional distribuida temprana es anterior a muchos patrones básicos de diseño paralelo y puede conceptualizarse dentro de ese marco.

La idea básica detrás de DTS es que los árboles de búsqueda se distribuyen entre los nodos computacionales en función de la complejidad del movimiento / diseño. Los procesadores no utilizados que "finalizan antes de tiempo" pueden hacer un trabajo adicional más allá de una asignación inicial que puede distribuirse de la manera más uniforme posible inicialmente pero que resultará desigual. por lo tanto, es básicamente una especie de cola de "equilibrio de carga" y "productor / consumidor" , o también similar a la programación de trabajos.

Este procesador inactivo transmite (usando memoria compartida) que está inactivo y está disponible para "ayudar" a cualquier otro procesador a terminar de buscar en su árbol. Los procesadores ocupados recopilan los datos del "estado del árbol" y los almacenan en la memoria compartida para que el procesador inactivo los examine. Este procesador inactivo analiza estos datos y decide cuál (si alguno) de los procesadores ocupados parece tener un árbol que es lo suficientemente complicado como para que sea eficiente ayudar con la búsqueda. Si se encuentra tal posición, el procesador inactivo informa al procesador que posee ese nodo de esto y ellos "unen" fuerzas.

vzn
fuente