Principios básicos de la búsqueda de grafos Monte Carlo
- La búsqueda de árboles Monte Carlo (MCTS) puede aplicarse a un grafo dirigido en lugar de un árbol como "búsqueda de grafos Monte Carlo" ("MCGS"), pero a veces se considera difícil de implementar.
- La bibliografía académica existente sigue la explicación "estándar" de MCTS para árboles, por lo que resulta difícil entender conceptualmente cómo generalizarla a grafos.
- Este documento presenta una explicación considerada más intuitiva, esencialmente equivalente pero más limpia, y deriva desde principios básicos por qué la búsqueda en grafos debe funcionar de esta manera.
Introducción / contexto
- En la búsqueda de árboles de juego u otras aplicaciones de búsqueda en árboles, es posible encontrar múltiples secuencias de jugadas o acciones que conducen al mismo estado.
- Por ejemplo, en ajedrez,
1. d4 d5 2. Nf3 lleva a la misma posición que 1. Nf3 d5 2. d4.
- Cuando este tipo de situaciones es posible en un juego, la cantidad de casos posibles crece geométricamente con la profundidad de búsqueda, haciendo que la búsqueda profunda sea más costosa de lo necesario.
- Idealmente, se quiere que estas ramas de búsqueda compartan el cálculo.
- Sin embargo, una implementación estándar de MCTS trata el juego como un árbol ramificado y vuelve a explorar de forma ineficiente posiciones duplicadas dentro del árbol.
Explicación habitual de MCTS: árbol de estadísticas en ejecución
- MCTS suele describirse como un algoritmo que rastrea estadísticas en ejecución de los playouts que pasan por los nodos de un árbol.
- Cada nodo representa un único estado del juego y rastrea el conteo de visitas (N) y el promedio acumulado (Q) de los valores de utilidad muestreados por los playouts.
- Una sola iteración o playout de MCTS consiste en descender por el árbol muestreando la siguiente acción a explorar, expandir el árbol al llegar a un estado nuevo, estimar la utilidad U del nuevo estado y luego volver a subir por el árbol incrementando N en cada nodo y actualizando el promedio Q con la nueva utilidad muestreada U.
¿Qué sale mal en un grafo?
- Si el algoritmo anterior se aplica tal cual a un grafo acíclico dirigido en lugar de un árbol, el algoritmo puede volverse incorrecto.
- Esto se debe a que MCTS suele explicarse en términos de estadísticas en ejecución de playouts como una extensión de métodos basados en multi-armed bandits.
- Czech, Korus y Kersting resolvieron este problema y llegaron a un algoritmo sólido, pero existe un método alternativo para abordar MCTS desde la perspectiva del aprendizaje de políticas en línea.
- En esta explicación alternativa, la generalización a grafos surge de manera relativamente natural.
Replantear MCTS como optimización regularizada de políticas
- Cuando MCTS actualiza estadísticas en distintos nodos, en realidad está ejecutando una forma de aprendizaje de políticas en línea.
- La distribución de visitas de MCTS representa aproximadamente una política "posterior" que mejora gradualmente la política previa P de la red neuronal para maximizar la utilidad esperada.
Cómo realizar correctamente la búsqueda de grafos Monte Carlo
- Todos los problemas que surgen al extender MCTS a grafos provienen de asumir únicamente visitas al nodo hijo desde nodos padre.
- La teoría garantiza que los conteos acumulados de acciones seleccionadas por PUCT proporcionan una política posterior que aproxima la política optimizada π, por lo que eso es lo que debe rastrearse.
- Si se usa la interpretación de que el valor Q reportado por un nodo es el valor esperado de la política posterior, puede aplicarse la fórmula recursiva de Q sin tener que tratar cómo calcular cada playout individual.
Discusión sobre decisiones de implementación
- El algoritmo presentado en este documento es muy similar al de Czech, Korus y Kersting, pero hay algunas decisiones de implementación y algunas diferencias menores.
- Existen varias formas de optar por la simplicidad de implementación, como estrategias para reducir lo "desactualizado" de los valores Q o usar actualizaciones iguales en lugar de graduales.
Opinión de GN⁺
- Este artículo puede resultar interesante para personas interesadas en inteligencia artificial y teoría de juegos, ya que presenta la complejidad de la búsqueda de grafos Monte Carlo (MCGS) y un nuevo enfoque para entenderla.
- Algoritmos como MCTS desempeñan un papel importante en juegos de estrategia complejos como el ajedrez o el go, y contribuyen al desarrollo de inteligencia artificial para estos juegos.
- Sin embargo, el contenido tratado en este artículo puede ser algo difícil para ingenieros de software de nivel inicial y requiere conocimientos teóricos previos.
- Entre los puntos a considerar al implementar MCGS está cómo equilibrar la eficiencia y la precisión del algoritmo, lo cual puede influir mucho en el rendimiento dentro de entornos de juego reales.
- Un proyecto o producto con funciones similares es AlphaZero de DeepMind, que alcanzó un nivel superior al de los mejores humanos en ajedrez, go y shogi.
1 comentarios
Opiniones en Hacker News
La exploración de grafos es necesaria para avanzar en el razonamiento de la inteligencia artificial, y los LLM simples van a fallar. El enlace incluye muchas buenas referencias, entre ellas el hashing de Zobrist para tableros de juego. Hay que encontrar un buen hashing para descripciones de estado basadas en lenguaje para que la exploración de grafos no explote computacionalmente. Buenas lecturas sobre búsqueda en árboles son 'Thinking Fast and Slow' y 'Teaching Large Language Models to Reason with Reinforcement Learning', que comparan el enfoque de MCTS con otras estrategias actuales de RL.
Reconocí de inmediato, desde la URL de HN, al genial desarrollador de KataGo. Sus publicaciones en Reddit como cbaduk son consistentemente excelentes.
Respecto al nombre "Monte-Carlo Tree Search", los lectores deberían notar que en el algoritmo mencionado no hay nada de "Monte-Carlo" y que es completamente determinista. Es raro que MCTS normalmente se implemente de forma determinista. Yo había asumido que había aleatoriedad en el muestreo.
El paper mencionado había pasado totalmente fuera de mi radar cuando estudiaba MCTS. Va a ser muy divertido probar esta modificación en la próxima oportunidad.
Conocimientos previos: