¿Cómo funciona la "búsqueda de Montecarlo"?

16

He escuchado sobre este concepto en una publicación de Reddit sobre Alpha Go. Traté de leer el artículo y el artículo, pero no pude entender el algoritmo.

Entonces, ¿alguien puede dar una explicación fácil de entender sobre cómo funciona el algoritmo de búsqueda de Montecarlo y cómo se está utilizando para construir bots de IA que juegan juegos?

gaming monte-carlo-tree-search Dawny33
fuente
Se puede encontrar una buena descripción del algoritmo MCTS en: https://towardsdatascience.com/monte-carlo-tree-search-in-reinforcement-learning-b97d3e743d0f .
nbro

Respuestas:

13

El método de Monte Carlo es un enfoque en el que genera una gran cantidad de valores aleatorios o simulaciones y forma algún tipo de conlusiones basadas en los patrones generales, como las medias y las variaciones.

Como ejemplo, podría usarlo para pronósticos meteorológicos . Predecir el clima a largo plazo es bastante difícil, porque es un sistema caótico donde pequeños cambios pueden conducir a resultados muy diferentes. Con los métodos de Monte Carlo, puede ejecutar una gran cantidad de simulaciones, cada una con cambios atmosféricos ligeramente diferentes. Luego puede analizar los resultados y, por ejemplo, calcular la probabilidad de lluvia en un día determinado en función de cuántas simulaciones terminaron con lluvia.

En cuanto al uso de Monte Carlo en Alpha Go, parecen estar usando el llamado Monte Carlo Tree Search . En este enfoque, haces un árbol de movimientos posibles, algunas vueltas hacia el futuro e intentas encontrar la mejor secuencia. Sin embargo, dado que la cantidad de movimientos posibles en el juego de go es muy grande, no podrás explorar mucho más adelante. Esto significa que algunos de los movimientos que se ven bien ahora podrían resultar ser malos más adelante.

Entonces, en Monte Carlo Tree Search, eliges una secuencia prometedora de movimientos y ejecutas una o más simulaciones de cómo podría proceder el juego desde ese punto. Luego puede usar los resultados de esa simulación para tener una mejor idea de cuán buena es realmente esa secuencia específica de movimientos y actualizar el árbol en consecuencia. Repita según sea necesario hasta que encuentre un buen movimiento.

Si desea obtener más información o mirar algunas ilustraciones, encontré un artículo interesante sobre el tema: C. Browne et al., A Survey of Monte Carlo Tree Search Methods ( repositorio abierto / enlace permanente (pago )

Acechador desencantado
fuente
Entonces, ¿qué hace básicamente monte carlo en alphago es crear estrategias a largo plazo, considerando diferentes combinaciones de movimientos, en lugar de al revés (elija una estrategia y luego los movimientos para lograrla)?
Diego Antonio Rosario Palomino
No se menciona el elemento clave del enfoque de Monte Carlo, que es el elemento estocástico integrado en la selección de movimientos disponibles para investigar. Tampoco se mencionó el intercambio de exactitud para lograr un procesamiento más ágil. Esos son los dos aspectos más importantes y están ausentes de la respuesta. En cambio, se mencionó "gran número de valores aleatorios o simulaciones", cuando es un número menor de simulaciones de factores pseudoaleatorios (una búsqueda menos exhaustiva) que es característico de la convergencia de Monte Carlo.
FauChristian