Búsqueda en árbol de Monte Carlo
Etapa 3 · Del auge experto al giro estadístico (1980–2011) › Aprendizaje por refuerzo
- Linaje
- Datos y aprendizaje
- Tipo
- Formulación
Quién
MTA SZTAKI
Qué ocurrió
El francés Rémi Coulom presenta en el congreso Computers and Games de Turín la búsqueda en árbol de Monte Carlo, y su programa Crazy Stone gana el torneo de go en tablero de 9 × 9 de la Olimpiada de computadores. En septiembre, los húngaros Levente Kocsis y Csaba Szepesvári publican UCT, su versión con garantías teóricas.
Qué aportó
Un programa evalúa las jugadas jugando miles de partidas al azar hasta el final, sin necesidad de una función de evaluación escrita a mano. Hace avanzar el go por computador y es una de las dos piezas de AlphaGo.
Desarrollo
El ajedrez se había resuelto con búsqueda alfa-beta y una buena función de evaluación, pero en el go esa receta fallaba: hay muchas más jugadas posibles en cada turno y nadie sabía escribir una fórmula fiable para decir quién va ganando. En 2006 los mejores programas de go jugaban como aficionados flojos.
La alternativa era evaluar una posición jugando desde ella muchas partidas con jugadas al azar y contar cuántas se ganan. Bernd Brügmann lo había probado en el go en los años noventa. Coulom combinó esas simulaciones con un árbol de búsqueda que crece de forma selectiva: dedica más simulaciones a las jugadas que parecen prometedoras sin abandonar del todo las demás. Así nació el nombre de búsqueda en árbol de Monte Carlo.
Kocsis y Szepesvári, del instituto de informática de la Academia Húngara de Ciencias, resolvieron cómo repartir las simulaciones con una fórmula tomada del problema de las máquinas tragaperras, que equilibra explorar jugadas nuevas y aprovechar las buenas, y demostraron que el método converge a la mejor jugada. Su algoritmo, UCT, se adoptó enseguida, por ejemplo en el programa MoGo.
En pocos años los programas de go pasaron al nivel de maestro en el tablero pequeño. En 2015, AlphaGo combinó esta búsqueda con redes neuronales que eligen y evalúan las jugadas.
Lleva a
AlphaGo vence a Fan Hui (5 de octubre de 2015)
Influencia directa documentada
AlphaGo combina la búsqueda en árbol de Monte Carlo con redes de política y de valor; el artículo cita los trabajos de Coulom y de Kocsis y Szepesvári
Hilos que pasan por aquí
- Máquinas contra campeones (paso 5 de 7)
Bibliografía
Fuente original
- Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Computers and Games 2006, Lecture Notes in Computer Science 4630, pp. 72-83 (se abre en una pestaña nueva). Rémi Coulom, 2006
- Bandit Based Monte-Carlo Planning. ECML 2006, Lecture Notes in Computer Science 4212, pp. 282-293 (se abre en una pestaña nueva). Levente Kocsis y Csaba Szepesvári, 2006
Cómo citar
«Búsqueda en árbol de Monte Carlo». En La historia de la IA, revisión del 13 de noviembre de 2026. https://thehistoryofai.com/es/hito/busqueda-arbol-monte-carlo
Última revisión de esta ficha: 13 de noviembre de 2026.