Búsqueda de árboles en Montecarlo

En informática , el algoritmo de búsqueda de árboles de Monte Carlo ( MCTS ) es un algoritmo de búsqueda heurística para algunos tipos de procesos de decisión , en particular los que se emplean en software que ejecuta juegos de mesa . En ese contexto, el MCTS se utiliza para resolver el árbol de juegos .

MCTS se combinó con redes neuronales en 2016 ^[1] y se ha utilizado en múltiples juegos de mesa como ajedrez , shogi , ^[2] damas , backgammon , contract bridge , go , scrabble y clobber ^[3], así como en videojuegos de estrategia por turnos (como la implementación de Total War: Rome II en la campaña de alto nivel de IA ^[4] ) y aplicaciones fuera de los juegos. ^[5]

Historia

Método de Monte Carlo

El método de Monte Carlo , que utiliza un muestreo aleatorio para problemas deterministas que son difíciles o imposibles de resolver utilizando otros enfoques, se remonta a la década de 1940. ^[6] En su tesis doctoral de 1987, Bruce Abramson combinó la búsqueda minimax con un modelo de resultado esperado basado en jugadas aleatorias de juego hasta el final, en lugar de la función de evaluación estática habitual . Abramson dijo que el modelo de resultado esperado "ha demostrado ser preciso, exacto, fácilmente estimable, eficientemente calculable e independiente del dominio". ^[7] Experimentó en profundidad con el tres en raya y luego con funciones de evaluación generadas por máquina para Otelo y ajedrez .

Estos métodos fueron luego explorados y aplicados exitosamente a la búsqueda heurística en el campo de la demostración automatizada de teoremas por W. Ertel, J. Schumann y C. Suttner en 1989, ^[8]^[9]^[10] mejorando así los tiempos de búsqueda exponencial de algoritmos de búsqueda no informados como por ejemplo la búsqueda en amplitud, la búsqueda en profundidad o la profundización iterativa .

En 1992, B. Brügmann lo empleó por primera vez en un programa de juego de Go . ^[11] En 2002, Chang et al. ^[12] propusieron la idea de "despliegue y retroceso recursivos" con opciones de muestreo "adaptativas" en su algoritmo de muestreo multietapa adaptativo (AMS) para el modelo de procesos de decisión de Markov . AMS fue el primer trabajo en explorar la idea de exploración y explotación basada en UCB en la construcción de árboles muestreados/simulados (Monte Carlo) y fue la semilla principal para UCT (árboles de confianza superior). ^[13]

Búsqueda de árboles de Monte Carlo (MCTS)

Clasificación de los mejores programas para jugar Go en el servidor KGS desde 2007. Desde 2006, todos los mejores programas utilizan la búsqueda de árbol de Monte Carlo. ^[14]

En 2006, inspirados por estos predecesores, ^[15] Rémi Coulom describió la aplicación del método Monte Carlo a la búsqueda en árboles de juego y acuñó el nombre de búsqueda en árboles de Monte Carlo, ^[16] L. Kocsis y Cs. Szepesvári desarrollaron el algoritmo UCT (límites de confianza superior aplicados a árboles), ^[17] y S. Gelly et al. implementaron UCT en su programa MoGo. ^[18] En 2008, MoGo alcanzó el nivel dan (maestro) en 9×9 Go, ^[19] y el programa Fuego comenzó a ganar contra fuertes jugadores amateurs en 9×9 Go. ^[20]

En enero de 2012, el programa Zen ganó 3:1 en una partida de Go en un tablero de 19x19 con un jugador amateur de 2 dan . ^[21] Google Deepmind desarrolló el programa AlphaGo , que en octubre de 2015 se convirtió en el primer programa de Go por computadora en vencer a un jugador profesional de Go humano sin handicaps en un tablero de tamaño completo de 19x19. ^[1]^[22]^[23] En marzo de 2016, AlphaGo recibió un nivel honorario de 9 dan (maestro) en Go 19x19 por derrotar a Lee Sedol en una partida de cinco juegos con un puntaje final de cuatro juegos a uno. ^[24] AlphaGo representa una mejora significativa con respecto a los programas de Go anteriores, así como un hito en el aprendizaje automático , ya que utiliza la búsqueda de árbol de Monte Carlo con redes neuronales artificiales (un método de aprendizaje profundo ) para la política (selección de movimientos) y el valor, lo que le otorga una eficiencia que supera ampliamente a los programas anteriores. ^[25]

El algoritmo MCTS también se ha utilizado en programas que ejecutan otros juegos de mesa (por ejemplo, Hex , ^[26] Havannah , ^[27] Game of the Amazons , ^[28] y Arimaa ^[29] ), videojuegos en tiempo real (por ejemplo, Ms. Pac-Man ^[30]^[31] y Fable Legends ^[32] ) y juegos no deterministas (como skat , ^[33] poker , ^[34] Magic: The Gathering , ^[35] o Settlers of Catan ^[36] ).

Principio de funcionamiento

El enfoque de MCTS se centra en el análisis de los movimientos más prometedores, ampliando el árbol de búsqueda en función de un muestreo aleatorio del espacio de búsqueda. La aplicación de la búsqueda del árbol de Monte Carlo en los juegos se basa en muchas repeticiones, también llamadas " roll-outs" . En cada repetición, el juego se juega hasta el final seleccionando movimientos al azar. El resultado final de cada repetición se utiliza para ponderar los nodos en el árbol de juego, de modo que haya más probabilidades de elegir los mejores nodos en las repeticiones futuras.

La forma más básica de utilizar los playouts es aplicar la misma cantidad de playouts después de cada movimiento legal del jugador actual y luego elegir el movimiento que condujo a la mayor cantidad de victorias. ^[11] La eficiencia de este método, llamado Búsqueda de partidas de Monte Carlo puro , a menudo aumenta con el tiempo a medida que se asignan más playouts a los movimientos que con frecuencia resultaron en la victoria del jugador actual según los playouts anteriores. Cada ronda de búsqueda de árbol de Monte Carlo consta de cuatro pasos: ^[37]

Selección : comience desde la raíz $R$ y seleccione nodos secundarios sucesivos hasta llegar a un nodo hoja $L.$ La raíz es el estado actual del juego y una hoja es cualquier nodo que tenga un hijo potencial desde el cual aún no se haya iniciado ninguna simulación (reproducción). La sección a continuación explica más sobre una forma de sesgar la elección de nodos secundarios que permite que el árbol de juego se expanda hacia los movimientos más prometedores, que es la esencia de la búsqueda en árboles de Monte Carlo.
Expansión : A menos que $L$ finalice el juego de manera decisiva (por ejemplo, victoria/derrota/empate) para cualquiera de los jugadores, crea uno (o más) nodos secundarios y elige el nodo $C$ de uno de ellos. Los nodos secundarios son cualquier movimiento válido desde la posición del juego definida por $L.$
Simulación : Completar una jugada aleatoria desde el nodo $C.$ Este paso a veces también se denomina jugada o lanzamiento. Una jugada puede ser tan simple como elegir movimientos aleatorios uniformes hasta que se decida la partida (por ejemplo, en ajedrez, la partida se gana, se pierde o se empata).
Retropropagación : utiliza el resultado de la reproducción para actualizar la información en los nodos en la ruta de $C$ a $R.$

Paso de búsqueda del árbol de Monte Carlo.

Este gráfico muestra los pasos que se deben seguir para tomar una decisión, y cada nodo muestra la proporción de victorias con respecto a las jugadas totales desde ese punto en el árbol de juego para el jugador que representa el nodo. ^[38] En el diagrama de selección, las negras están a punto de mover. El nodo raíz muestra que hay 11 victorias de las 21 jugadas para las blancas desde esta posición hasta el momento. Complementa el total de 10/21 victorias negras que se muestran a lo largo de los tres nodos negros debajo de él, cada uno de los cuales representa un posible movimiento de las negras. Tenga en cuenta que este gráfico no sigue el algoritmo UCT que se describe a continuación.

Si las blancas pierden la simulación, todos los nodos a lo largo de la selección incrementan su conteo de simulación (el denominador), pero entre ellos solo los nodos negros reciben el crédito de victorias (el numerador). Si, en cambio, las blancas ganan, todos los nodos a lo largo de la selección incrementarían su conteo de simulación, pero entre ellos solo los nodos blancos reciben el crédito de victorias. En los juegos en los que es posible el empate, un empate hace que el numerador tanto para las negras como para las blancas se incremente en 0,5 y el denominador en 1. Esto garantiza que, durante la selección, las opciones de cada jugador se expandan hacia los movimientos más prometedores para ese jugador, lo que refleja el objetivo de cada jugador de maximizar el valor de su movimiento.

Las rondas de búsqueda se repiten mientras se mantiene el tiempo asignado a una jugada. Luego, se elige como respuesta final la jugada con más simulaciones realizadas (es decir, la de mayor denominador).

Búsqueda de juegos de Monte Carlo puro

Este procedimiento básico se puede aplicar a cualquier juego cuyas posiciones necesariamente tengan un número finito de movimientos y una longitud finita. Para cada posición, se determinan todos los movimientos posibles: se juegan k juegos aleatorios hasta el final y se registran las puntuaciones. Se elige el movimiento que lleva a la mejor puntuación. Los empates se resuelven mediante lanzamientos justos de moneda . La búsqueda de juegos de Monte Carlo pura da como resultado un juego fuerte en varios juegos con elementos aleatorios, como en el juego EinStein würfelt nicht! . Converge al juego óptimo (ya que k tiende a infinito) en juegos de llenado de tablero con orden de turno aleatorio, por ejemplo en el juego Hex con orden de turno aleatorio. ^[39] AlphaZero de DeepMind reemplaza el paso de simulación con una evaluación basada en una red neuronal. ^[2]

Exploración y explotación

La principal dificultad en la selección de nodos secundarios es mantener cierto equilibrio entre la explotación de variantes profundas después de movimientos con alta tasa de victorias promedio y la exploración de movimientos con pocas simulaciones. La primera fórmula para equilibrar la explotación y la exploración en juegos, llamada UCT ( Upper Confidence Bound 1 applied to trees ), fue introducida por Levente Kocsis y Csaba Szepesvári. ^[17] UCT se basa en la fórmula UCB1 derivada por Auer, Cesa-Bianchi y Fischer ^[40] y el algoritmo probablemente convergente AMS (Adaptive Multi-stage Sampling) aplicado por primera vez a modelos de toma de decisiones de múltiples etapas (específicamente, Markov Decision Processes ) por Chang, Fu, Hu y Marcus. ^[12] Kocsis y Szepesvári recomiendan elegir en cada nodo del árbol de juego el movimiento para el cual la expresión tiene el valor más alto. En esta fórmula: ${\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}$

$w i$ representa el número de victorias del nodo considerado después delmovimiento $i$
$n i$ representa el número de simulaciones para el nodo considerado después delmovimiento $i$
$N i$ representa el número total de simulaciones después del $i$ -ésimo movimiento ejecutado por el nodo padre del considerado
$c$ es el parámetro de exploración, teóricamente igual a $\sqrt 2$ ; en la práctica, generalmente se elige empíricamente

El primer componente de la fórmula anterior corresponde a la explotación; es alto para movimientos con una alta tasa de victorias promedio. El segundo componente corresponde a la exploración; es alto para movimientos con pocas simulaciones.

La mayoría de las implementaciones contemporáneas de la búsqueda de árboles de Monte Carlo se basan en alguna variante de UCT que remonta sus raíces al algoritmo de optimización de simulación AMS para estimar la función de valor en procesos de decisión de Markov de horizonte finito (MDP) introducido por Chang et al. ^[12] (2005) en Operations Research . (AMS fue el primer trabajo en explorar la idea de exploración y explotación basada en UCB en la construcción de árboles muestreados/simulados (Monte Carlo) y fue la semilla principal para UCT. ^[13] )

Ventajas y desventajas

Aunque se ha demostrado que la evaluación de movimientos en la búsqueda de árbol de Monte Carlo converge a minimax cuando se utiliza UCT, ^[17]^[41] la versión básica de la búsqueda de árbol de Monte Carlo converge solo en los llamados juegos "Monte Carlo Perfectos". ^[42] Sin embargo, la búsqueda de árbol de Monte Carlo ofrece ventajas significativas sobre la poda alfa-beta y algoritmos similares que minimizan el espacio de búsqueda.

En particular, la búsqueda pura mediante árboles de Monte Carlo no necesita una función de evaluación explícita . Simplemente, la implementación de la mecánica del juego es suficiente para explorar el espacio de búsqueda (es decir, la generación de movimientos permitidos en una posición dada y las condiciones de fin del juego). Como tal, la búsqueda mediante árboles de Monte Carlo se puede emplear en juegos sin una teoría desarrollada o en juegos en general .

El árbol de juego en la búsqueda de árboles de Monte Carlo crece de forma asimétrica a medida que el método se concentra en los subárboles más prometedores. Por lo tanto, ^{[ dudoso – discutir ]} , logra mejores resultados que los algoritmos clásicos en juegos con un alto factor de ramificación .

Una desventaja es que en ciertas posiciones, puede haber movimientos que parecen superficialmente fuertes, pero que en realidad conducen a una pérdida a través de una línea de juego sutil. Tales "estados de trampa" requieren un análisis exhaustivo para ser manejados correctamente, particularmente cuando se juega contra un jugador experto; sin embargo, MCTS puede no "ver" tales líneas debido a su política de expansión selectiva de nodos. ^[43]^[44] Se cree que esto puede haber sido parte de la razón de la derrota de AlphaGo en su cuarto juego contra Lee Sedol . En esencia, la búsqueda intenta podar secuencias que son menos relevantes. En algunos casos, una jugada puede conducir a una línea de juego muy específica que es significativa, pero que se pasa por alto cuando se poda el árbol, y este resultado, por lo tanto, está "fuera del radar de búsqueda". ^[45]

Mejoras

Se han propuesto varias modificaciones del método básico de búsqueda de árboles de Monte Carlo para acortar el tiempo de búsqueda. Algunas emplean conocimientos especializados específicos del dominio, otras no.

La búsqueda en árbol de Monte Carlo puede utilizar jugadas ligeras o pesadas . Las jugadas ligeras consisten en movimientos aleatorios, mientras que las jugadas pesadas aplican varias heurísticas para influir en la elección de movimientos. ^[46] Estas heurísticas pueden emplear los resultados de jugadas anteriores (por ejemplo, la heurística de la última respuesta buena ^[47] ) o el conocimiento experto de un juego determinado. Por ejemplo, en muchos programas de juego de Go, ciertos patrones de piedras en una parte del tablero influyen en la probabilidad de moverse a esa área. ^[18] Paradójicamente, jugar de forma subóptima en las simulaciones a veces hace que un programa de búsqueda en árbol de Monte Carlo juegue mejor en general. ^[48]

Patrones de *hane* (piedras que rodean al oponente) utilizados en los playouts del programa MoGo. Es ventajoso tanto para las negras como para las blancas colocar una piedra en la casilla del medio, excepto en el patrón más a la derecha, donde favorece solo a las negras. ^[18]

El conocimiento específico del dominio puede emplearse al construir el árbol de juego para ayudar a la explotación de algunas variantes. Uno de estos métodos asigna valores previos distintos de cero al número de simulaciones ganadas y jugadas al crear cada nodo hijo, lo que conduce a tasas de victoria promedio artificialmente elevadas o reducidas que hacen que el nodo sea elegido con mayor o menor frecuencia, respectivamente, en el paso de selección. ^[49] Un método relacionado, llamado sesgo progresivo , consiste en agregar a la fórmula UCB1 un elemento, donde $b$ $i$ es una puntuación heurística del $i$ -ésimo movimiento. ^[37] ${\frac {b_{i}}{n_{i}}}$

La búsqueda básica en árbol de Monte Carlo recopila suficiente información para encontrar los movimientos más prometedores solo después de muchas rondas; hasta entonces, sus movimientos son esencialmente aleatorios. Esta fase exploratoria puede reducirse significativamente en una cierta clase de juegos utilizando RAVE ( Rapid Action Value Estimation ). ^[49] En estos juegos, las permutaciones de una secuencia de movimientos conducen a la misma posición. Por lo general, son juegos de mesa en los que un movimiento implica la colocación de una pieza o una piedra en el tablero. En tales juegos, el valor de cada movimiento a menudo solo está ligeramente influenciado por otros movimientos.

$En RAVE, para un nodo N$ del árbol de juego , sus nodos secundarios $C i$ almacenan no solo las estadísticas de victorias en las jugadas iniciadas en el nodo $N,$ sino también las estadísticas de victorias en todas las jugadas iniciadas en el nodo $N$ y por debajo de él, si contienen el movimiento $i$ (también cuando el movimiento se jugó en el árbol, entre el nodo $N$ y una jugada). De esta manera, el contenido de los nodos del árbol se ve influenciado no solo por los movimientos jugados inmediatamente en una posición dada, sino también por los mismos movimientos jugados más tarde.

RAVE en el ejemplo del tres en raya. En los nodos rojos, las estadísticas de RAVE se actualizarán después de la simulación b1-a2-b3.

Al utilizar RAVE, el paso de selección selecciona el nodo para el cual la fórmula UCB1 modificada tiene el valor más alto. En esta fórmula, y representan el número de jugadas ganadas que contienen el movimiento $i$ y el número de todas las jugadas que contienen el movimiento $i$ , y la función debe ser cercana a uno y a cero para $n$ relativamente pequeño y relativamente grande $i$ y , respectivamente. Una de las muchas fórmulas para , propuesta por D. Silver, ^[50] dice que en posiciones equilibradas se puede tomar , donde $b$ es una constante elegida empíricamente. $(1-\beta (n_{i},{\tilde {n}}_{i})){\frac {w_{i}}{n_{i}}}+\beta (n_{i},{\tilde {n}}_{i}){\frac {{\tilde {w}}_{i}}{{\tilde {n}}_{i}}}+c{\sqrt {\frac {\ln t}{n_{i}}}}$ ${\tilde {w}}_{i}$ ${\tilde {n}}_{i}$ $\beta(n_{i},{\tilde {n}}_{i})$ ${\tilde {n}}_{i}$ $\beta(n_{i},{\tilde {n}}_{i})$ $\beta (n_{i},{\tilde {n}}_{i})={\frac {{\tilde {n}}_{i}}{n_{i}+{\tilde {n}}_{i}+4b^{2}n_{i}{\tilde {n}}_{i}}}$

Las heurísticas utilizadas en la búsqueda de árboles de Monte Carlo suelen requerir muchos parámetros. Existen métodos automatizados para ajustar los parámetros a fin de maximizar la tasa de éxito. ^[51]

La búsqueda en árbol de Monte Carlo puede ser ejecutada simultáneamente por varios subprocesos o procesos . Existen varios métodos fundamentalmente diferentes para su ejecución paralela : ^[52]

Paralelización de hojas , es decir, ejecución paralela de muchas reproducciones desde una hoja del árbol del juego.
Paralelización de raíces , es decir, construir árboles de juego independientes en paralelo y realizar el movimiento basándose en las ramas de nivel raíz de todos estos árboles.
Paralelización de árboles , es decir, construcción paralela del mismo árbol de juego, protegiendo los datos de escrituras simultáneas ya sea con un mutex global , con más mutex o con sincronización no bloqueante . ^[53]

Véase también

AlphaGo , un programa Go que utiliza búsqueda de árbol de Monte Carlo, aprendizaje de refuerzo y aprendizaje profundo .
AlphaGo Zero , un programa Go actualizado que utiliza búsqueda de árbol de Monte Carlo, aprendizaje de refuerzo y aprendizaje profundo .
AlphaZero , una versión generalizada de AlphaGo Zero que utiliza búsqueda de árbol de Monte Carlo, aprendizaje de refuerzo y aprendizaje profundo .
Leela Chess Zero , una implementación de software libre de los métodos de AlphaZero para ajedrez, que actualmente se encuentra entre los programas líderes para jugar al ajedrez.

Referencias

^ ab Silver, David ; Huang, Aja ; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya ; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 de enero de 2016). "Dominar el juego de Go con redes neuronales profundas y búsqueda de árboles". Nature . 529 (7587): 484–489. Código Bibliográfico :2016Natur.529..484S. doi :10.1038/nature16961. Código IATA : 10 ...
^ ab Silver, David (2017). "Dominar el ajedrez y el shogi mediante el juego autónomo con un algoritmo de aprendizaje por refuerzo general". arXiv : 1712.01815v1 [cs.AI].
^ Rajkumar, Prahalad. "Un estudio de las técnicas de Montecarlo en los juegos" (PDF) . cs.umd.edu . Archivado (PDF) desde el original el 7 de abril de 2023.
^ "Búsqueda de árboles de Montecarlo en la campaña de IA de TOTAL WAR: ROME II". AI Game Dev . Archivado desde el original el 13 de marzo de 2017. Consultado el 25 de febrero de 2017 .
^ Kemmerling, Marco; Lütticke, Daniel; Schmitt, Robert H. (1 de enero de 2024). "Más allá de los juegos: una revisión sistemática de aplicaciones de búsqueda de árboles neuronales de Monte Carlo". Inteligencia Aplicada . 54 (1): 1020–1046. arXiv : 2303.08060 . doi :10.1007/s10489-023-05240-w. ISSN 1573-7497.
^ Nicholas, Metropolis; Stanislaw, Ulam (1949). "El método de Monte Carlo". Revista de la Asociación Estadounidense de Estadística . 44 (247): 335–341. doi :10.1080/01621459.1949.10483310. PMID 18139350.
^ Abramson, Bruce (1987). The Expected-Outcome Model of Two-Player Games (PDF) . Informe técnico, Departamento de Ciencias de la Computación, Universidad de Columbia . Consultado el 23 de diciembre de 2013 .
^ Wolfgang Ertel; Juan Schumann; Christian Suttner (1989). "Aprendizaje de heurística para un demostrador de teoremas mediante propagación hacia atrás". En J. Retti; K. Leidlmair (eds.). 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208, págs. 87-95 . Saltador. Archivado desde el original el 15 de abril de 2021 . Consultado el 14 de agosto de 2016 .
^ Christian Suttner; Wolfgang Ertel (1990). "Adquisición automática de heurísticas de guía de búsqueda". CADE90, 10.ª Conferencia Internacional sobre Deducción Automatizada, págs. 470-484. LNAI 449. Springer. Archivado desde el original el 2021-04-15 . Consultado el 2016-08-14 .
^ Christian Suttner; Wolfgang Ertel (1991). "Uso de redes de retropropagación para guiar la búsqueda de un demostrador de teoremas". Revista de investigación y aplicaciones de redes neuronales . 2 (1): 3–16. Archivado desde el original el 15 de abril de 2021 . Consultado el 14 de agosto de 2016 .
^ ab Brügmann, Bernd (1993). Monte Carlo Go (PDF) . Informe técnico, Departamento de Física, Universidad de Syracuse.
^ abc Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marcus, Steven I. (2005). "Un algoritmo de muestreo adaptativo para resolver procesos de decisión de Markov" (PDF) . Investigación de operaciones . 53 : 126–139. doi :10.1287/opre.1040.0145. hdl : 1903/6264 . Archivado desde el original (PDF) el 2021-04-20 . Consultado el 2016-02-25 .
^ ab Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). "Alphago de Google DeepMind: el papel no anunciado de la investigación de laboratorio en el logro pionero". OR/MS Today . 45 (5): 24–29.
^ "Biblioteca del Sensei: KGSBotRatings" (PDF) . Archivado desde el original el 25 de junio de 2009. Consultado el 3 de mayo de 2012 .
^ Rémi Coulom (2008). "La revolución de Montecarlo en Go" (PDF) . Simposio franco-japonés sobre las fronteras de la ciencia .
^ Rémi Coulom (2007). "Selectividad eficiente y operadores de respaldo en la búsqueda de árboles de Montecarlo". Computers and Games, 5.ª conferencia internacional, CG 2006, Turín, Italia, 29-31 de mayo de 2006. Documentos revisados . H. Jaap van den Herik, Paolo Ciancarini, HHLM Donkers (eds.). Springer. págs. 72-83. CiteSeerX 10.1.1.81.6817 . ISBN. 978-3-540-75537-1.
^ abc Kocsis, Levente; Szepesvári, Csaba (2006). "Bandit based Monte-Carlo Planning". En Fürnkranz, Johannes; Scheffer, Tobias; Spiliopoulou, Myra (eds.). Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlín, Alemania, 18-22 de septiembre de 2006, Actas . Lecture Notes in Computer Science. Vol. 4212. Springer. págs. 282-293. CiteSeerX 10.1.1.102.1296 . doi :10.1007/11871842_29. ISBN . 3-540-45375-X.
^ abc Sylvain Gelly; Yizao Wang; Rémi Munos; Olivier Teytaud (noviembre de 2006). Modificación de UCT con patrones en Monte-Carlo Go (PDF) . Informe técnico, INRIA.
^ Chang-Shing Lee; Mei-Hui Wang; Guillaume Chaslot; Jean-Baptiste Hoock; Arpad Rimmel; Olivier Teytaud; Shang-Rong Tsai; Shun-Chin Hsu; Tzung-Pei Hong (2009). "La inteligencia computacional de MoGo revelada en los torneos de Go por computadora de Taiwán" (PDF) . Transacciones IEEE sobre inteligencia computacional e IA en juegos . 1 (1): 73–89. CiteSeerX 10.1.1.470.6018 . doi :10.1109/tciaig.2009.2018703. S2CID 15266518.
^ Markus Enzenberger; Martin Mūller (2008). Fuego: un marco de código abierto para juegos de mesa y un motor Go basado en la búsqueda de árboles de Monte Carlo (PDF) . Informe técnico, Universidad de Alberta.
^ "El Shodan Go Bet" . Consultado el 2 de mayo de 2012 .
^ "Blog de investigación: AlphaGo: cómo dominar el antiguo juego de Go con aprendizaje automático". Blog de investigación de Google . 27 de enero de 2016.
^ "Google logra un gran avance en inteligencia artificial al vencer al campeón Go". BBC News . 27 de enero de 2016.
^ "Partido 1 - Desafío Google DeepMind: Lee Sedol contra AlphaGo". Youtube . 9 de marzo de 2016.
^ "La inteligencia artificial AlphaGo de Google arrasa con el campeón europeo de Go". ZDNet . 28 de enero de 2016.
^ Broderick Arneson; Ryan Hayward; Philip Henderson (junio de 2009). "MoHex gana el torneo Hex" (PDF) . Revista ICGA . 32 (2): 114–116. doi :10.3233/ICG-2009-32218.
^ Timo Ewalds (2011). Jugando y resolviendo Havannah (PDF) . Tesis de maestría, Universidad de Alberta.
^ Richard J. Lorentz (2008). "Amazons Discover Monte-Carlo". Computers and Games, 6th International Conference, CG 2008, Beijing, China, 29 de septiembre – 1 de octubre de 2008. Actas . H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark HM Winands (eds.). Springer. págs. 13–24. ISBN. 978-3-540-87607-6.
^ Tomáš Kozelek (2009). Métodos de MCTS y el juego Arimaa (PDF) . Tesis de maestría, Universidad Carolina de Praga.
^ Xiaocong Gan; Yun Bao; Zhangang Han (diciembre de 2011). "Método de búsqueda en tiempo real en un juego no determinista: Ms. Pac-Man". ICGA Journal . 34 (4): 209–222. doi :10.3233/ICG-2011-34404.
^ Tom Pepels; Mark HM Winands; Marc Lanctot (septiembre de 2014). "Búsqueda de árbol de Monte Carlo en tiempo real en Ms Pac-Man". IEEE Transactions on Computational Intelligence and AI in Games . 6 (3): 245–257. doi : 10.1109/tciaig.2013.2291577 .
^ Mountain, Gwaredd (2015). "Planificación táctica y MCTS en tiempo real en Fable Legends". Archivado desde el original el 8 de junio de 2019. Consultado el 8 de junio de 2019. ... implementamos un enfoque basado en simulación, que implicó modelar el juego y usar MCTS para buscar el espacio de plan potencial. En general, esto funcionó bien, ...
^ Michael Buro; Jeffrey Richard Long; Timothy Furtak; Nathan R. Sturtevant (2009). "Mejora de la evaluación, inferencia y búsqueda de estados en juegos de cartas basados en trucos". IJCAI 2009, Actas de la 21.ª Conferencia conjunta internacional sobre inteligencia artificial, Pasadena, California, EE. UU., 11-17 de julio de 2009. Craig Boutilier (ed.). págs. 1407-1413. CiteSeerX 10.1.1.150.3077 .
^ Jonathan Rubin; Ian Watson (abril de 2011). "Computer poker: A review". Inteligencia artificial . 175 (5–6): 958–987. doi : 10.1016/j.artint.2010.12.005 .
^ CD Ward; PI Cowling (2009). "Búsqueda de Monte Carlo aplicada a la selección de cartas en Magic: The Gathering" (PDF) . Actas de la 5.ª conferencia internacional sobre inteligencia computacional y juegos de CIG'09 . IEEE Press. Archivado desde el original (PDF) el 28 de mayo de 2016.
^ István Szita; Guillaume Chaslot; Pieter Spronck (2010). "Búsqueda de árboles de Montecarlo en Los colonos de Catán" (PDF) . En Jaap Van Den Herik; Pieter Spronck (eds.). Advances in Computer Games, 12.ª Conferencia Internacional, ACG 2009, Pamplona, España, 11-13 de mayo de 2009. Documentos revisados . Springer. págs. 21-32. ISBN. 978-3-642-12992-6Archivado desde el original (PDF) el 4 de marzo de 2016. Consultado el 30 de noviembre de 2015 .
^ ab GMJB Chaslot; MHM Winands; JWHM Uiterwijk; HJ van den Herik; B. Bouzy (2008). "Estrategias progresivas para la búsqueda en árboles de Montecarlo" (PDF) . Nuevas matemáticas y computación natural . 4 (3): 343–359. doi :10.1142/s1793005708001094.
^ Bradberry, Jeff (7 de septiembre de 2015). "Introducción a la búsqueda de árboles de Monte Carlo".
^ Peres, Yuval; Schramm, Oded; Sheffield, Scott; Wilson, David B. (2006). "Random-Turn Hex y otros juegos de selección". arXiv : math/0508580 .
^ Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). "Análisis de tiempo finito del problema del bandido multiarmado". Aprendizaje automático . 47 (2/3): 235–256. doi : 10.1023/a:1013689704352 . S2CID 207609497.
^ Browne, Cameron B.; Powley, Edward; Whitehouse, Daniel; Lucas, Simon M.; Cowling, Peter I.; Rohlfshagen, Philipp; Tavener, Stephen; Perez, Diego; Samothrakis, Spyridon; Colton, Simon (2012). "Un estudio de los métodos de búsqueda de árboles de Monte Carlo". Transacciones IEEE sobre inteligencia computacional e IA en juegos . 4 (1): 1–43. doi :10.1109/tciaig.2012.2186810. ISSN 1943-068X.
^ Althöfer, Ingo (2012). "Sobre los juegos de llenado de tablero con orden de turno aleatorio y perfección de Monte Carlo". Avances en juegos de computadora . Apuntes de clase en informática. Vol. 7168. págs. 258–269. doi :10.1007/978-3-642-31866-5_22. ISBN 978-3-642-31865-8.
^ Ramanujan, Raghuram; Sabharwal, Ashish; Selman, Bart (mayo de 2010). "Sobre espacios de búsqueda adversarial y planificación basada en muestreo". ICAPS '10: Actas de la Vigésima Conferencia Internacional sobre Planificación y Programación Automatizadas . Icaps'10: 242–245.
^ Ramanujan, Raghuram; Selman, Bart (marzo de 2011). "Compensaciones en la planificación adversarial basada en muestreo". Actas de la Conferencia internacional sobre planificación y programación automatizadas . 21 (1): 202–209. doi : 10.1609/icaps.v21i1.13472 . S2CID : 45147586.
^ "Lee Sedol derrota a AlphaGo en una remontada magistral - Juego 4". Go Game Guru. Archivado desde el original el 2016-11-16 . Consultado el 2017-07-04 .
^ Świechowski, M.; Mańdziuk, J., "Autoadaptación de estrategias de juego en el juego en general" (2010), IEEE Transactions on Computational Intelligence and AI in Games , vol: 6(4), págs. 367-381, doi :10.1109/TCIAIG.2013.2275163, https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729
^ Drake, Peter (diciembre de 2009). "La política de última respuesta válida para Montecarlo Go". ICGA Journal . 32 (4): 221–227. doi :10.3233/ICG-2009-32404.
^ Seth Pellegrino; Peter Drake (2010). "Investigación de los efectos de la fuerza de reproducción en Monte-Carlo Go". Actas de la Conferencia Internacional sobre Inteligencia Artificial de 2010, ICAI 2010, 12 al 15 de julio de 2010, Las Vegas, Nevada, EE. UU . Hamid R. Arabnia, David de la Fuente, Elena B. Kozerenko, José Angel Olivas, Rui Chang, Peter M. LaMonica, Raymond A. Liuzzi, Ashu MG Solo (eds.). Prensa CSREA. págs. 1015-1018. ISBN 978-1-60132-148-0.
^ ab Gelly, Sylvain; Silver, David (2007). "Combinación de conocimiento en línea y fuera de línea en UCT" (PDF) . Aprendizaje automático, Actas de la vigésimo cuarta conferencia internacional (ICML 2007), Corvallis, Oregón, EE. UU., 20-24 de junio de 2007. Zoubin Ghahramani (ed.). ACM. págs. 273-280. ISBN 978-1-59593-793-3. Archivado desde el original (PDF) el 28 de agosto de 2017.
^ David Silver (2009). Aprendizaje por refuerzo y búsqueda basada en simulación en Go por computadora (PDF) . Tesis doctoral, Universidad de Alberta.
^ Rémi Coulom . "CLOP: Optimización local segura para el ajuste de parámetros de caja negra ruidosa". ACG 2011: 13.ª conferencia sobre avances en los juegos de ordenador, Tilburg (Países Bajos), del 20 al 22 de noviembre .
^ Guillaume MJ-B. Chaslot, Mark HM Winands, Jaap van den Herik (2008). "Búsqueda paralela en árboles de Montecarlo" (PDF) . Computers and Games, 6.ª conferencia internacional, CG 2008, Pekín, China, 29 de septiembre – 1 de octubre de 2008. Actas . H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark HM Winands (eds.). Springer. págs. 60–71. ISBN. 978-3-540-87607-6.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
^ Markus Enzenberger; Martin Müller (2010). "Un algoritmo de búsqueda de árbol de Montecarlo multiproceso sin bloqueo". En Jaap Van Den Herik; Pieter Spronck (eds.). Advances in Computer Games: 12th International Conference, ACG 2009, Pamplona, España, 11-13 de mayo de 2009, Documentos revisados . Springer. págs. 14-20. CiteSeerX 10.1.1.161.1984 . ISBN 978-3-642-12992-6.

Bibliografía

Cameron Browne; Edward Powley; Daniel Whitehouse; Simon Lucas; Peter I. Cowling; Philipp Rohlfshagen; Stephen Tavener; Diego Pérez; Spyridon Samothrakis; Simon Colton (marzo de 2012). "Un estudio de los métodos de búsqueda de árboles de Monte Carlo". Transacciones IEEE sobre inteligencia computacional e IA en juegos . 4 (1): 1–43. CiteSeerX 10.1.1.297.3086 . doi :10.1109/tciaig.2012.2186810. S2CID 9316331.
Maciej Świechowski; Konrad Godlewski; Bartosz Sawicki; Jacek Mańdziuk (julio de 2022). "Monte Carlo Tree Search: una revisión de modificaciones y aplicaciones recientes". Revisión de la inteligencia artificial de Springer Nature . 56 (3): 497–2562 (66 páginas). arXiv : 2103.04931 . doi :10.1007/s10462-022-10228-y. S2CID 232147848.

Enlaces externos

Guía para principiantes sobre la búsqueda de árboles en Montecarlo