Búsqueda de árboles de Montecarlo

En informática , la búsqueda de árbol de Monte Carlo ( MCTS ) es un algoritmo de búsqueda heurística para algunos tipos de procesos de decisión , sobre todo los empleados en software que juega juegos de mesa . En ese contexto, MCTS se utiliza para resolver el árbol del juego .

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 juegos por turnos. -Videojuegos de estrategia (como la implementación de Total War: Rome II en la campaña de alto nivel AI ^[4] ).

Historia

Método Montecarlo

El método Monte Carlo , que utiliza un muestreo aleatorio para problemas deterministas difíciles o imposibles de resolver mediante otros enfoques, se remonta a la década de 1940. ^[5] En su tesis doctoral de 1987, Bruce Abramson combinó la búsqueda minimax con un modelo de resultado esperado basado en repeticiones aleatorias del 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". ^[6] Experimentó en profundidad con el tres en raya y luego con funciones de evaluación generadas por máquinas para Otelo y el ajedrez .

Estos métodos fueron posteriormente explorados y aplicados con éxito 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, ^[7]^[8]^[9] , mejorando así los tiempos de búsqueda exponencial de personas no informadas. algoritmos de búsqueda como, por ejemplo, búsqueda en amplitud, búsqueda en profundidad o profundización iterativa .

En 1992 B. Brügmann lo utilizó por primera vez en un programa de juego de Go . ^[10] En 2002, Chang et al. ^[11] propusieron la idea de "despliegue y retroceso recursivo" con opciones de muestreo "adaptativas" en su algoritmo de muestreo adaptativo de múltiples etapas (AMS) para el modelo de procesos de decisión de Markov . AMS fue el primer trabajo que exploró 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 de UCT (Upper Confidence Trees). ^[12]

Búsqueda de árboles de Montecarlo (MCTS)

La clasificación de los mejores programas de Go-play en el servidor KGS desde 2007. Desde 2006, todos los mejores programas utilizan la búsqueda de árbol de Monte Carlo. ^[13]

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

En enero de 2012, el programa Zen ganó 3:1 en un partido de Go en un tablero de 19×19 con un jugador amateur de 2 dan . ^[20] Google Deepmind desarrolló el programa AlphaGo , que en octubre de 2015 se convirtió en el primer programa Computer Go en vencer a un jugador humano profesional de Go sin desventajas en un tablero de tamaño completo de 19x19. ^[1]^[21]^[22] En marzo de 2016, AlphaGo recibió un nivel honorario de 9-dan (maestro) en Go 19 × 19 por derrotar a Lee Sedol en una partida de cinco juegos con una puntuación final de cuatro juegos a uno. ^[23] AlphaGo representa una mejora significativa con respecto a los programas 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 políticas (selección de movimientos) y valor, lo que le otorga una eficiencia mucho mayor. superando programas anteriores. ^[24]

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

Principio de funcionamiento

El objetivo de MCTS está en el análisis de los movimientos más prometedores, ampliando el árbol de búsqueda basándose en un muestreo aleatorio del espacio de búsqueda. La aplicación de la búsqueda de árboles de Monte Carlo en los juegos se basa en muchos playouts, también llamados roll-outs . En cada playout, el juego se juega hasta el final seleccionando movimientos al azar. El resultado final del juego de cada playout se utiliza para ponderar los nodos en el árbol del juego, de modo que sea más probable que se elijan mejores nodos en futuros playouts.

La forma más básica de utilizar los playouts es aplicar el mismo número de playouts después de cada movimiento legal del jugador actual y luego elegir el movimiento que generó la mayor cantidad de victorias. ^[10] La eficiencia de este método, llamado búsqueda de juegos Pure Monte Carlo , a menudo aumenta con el tiempo a medida que se asignan más reproducciones a los movimientos que frecuentemente han resultado en la victoria del jugador actual según las reproducciones anteriores. Cada ronda de búsqueda de árboles de Monte Carlo consta de cuatro pasos: ^[36]

Selección : comience desde la raíz $R$ y seleccione nodos secundarios sucesivos hasta alcanzar un nodo hoja $L.$ La raíz es el estado actual del juego y una hoja es cualquier nodo que tiene un hijo potencial del cual aún no se ha iniciado ninguna simulación (reproducción). La siguiente sección dice 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 de árbol de Monte Carlo.
Expansión : a menos que $L$ termine el juego de manera decisiva (por ejemplo, gane/pierda/empate) para cualquiera de los jugadores, cree uno (o más) nodos secundarios y elija 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 : Completa una reproducción aleatoria desde el nodo $C.$ Este paso a veces también se denomina reproducción o implementación. Una playout puede ser tan simple como elegir movimientos aleatorios uniformes hasta que se decida la partida (por ejemplo, en el ajedrez, la partida se gana, se pierde o se empata).
Propagación hacia atrás : utilice el resultado de la reproducción para actualizar la información en los nodos en la ruta de $C$ a $R.$

Paso de la búsqueda de árboles de Montecarlo.

Este gráfico muestra los pasos involucrados en una decisión, y cada nodo muestra la proporción de victorias y playouts totales desde ese punto en el árbol del juego para el jugador que representa el nodo. ^[37] En el diagrama de Selección, el negro está a punto de moverse. El nodo raíz muestra que hasta ahora hay 11 victorias de 21 eliminatorias para las blancas desde esta posición. Complementa el total de victorias de las negras 10/21 que se muestran a lo largo de los tres nodos negros debajo, 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 el blanco pierde la simulación, todos los nodos a lo largo de la selección incrementaron su recuento de simulación (el denominador), pero entre ellos solo los nodos negros obtuvieron victorias (el numerador). Si, en cambio, gana el blanco, todos los nodos a lo largo de la selección seguirían incrementando su recuento de simulación, pero entre ellos solo los nodos blancos recibirían las victorias. En juegos donde es posible empatar, un empate hace que el numerador tanto para blanco como para negro se incremente en 0,5 y el denominador en 1. Esto asegura que durante la selección, las opciones de cada jugador se expandan hacia los movimientos más prometedores para ese jugador, lo que refleja la objetivo de cada jugador de maximizar el valor de su movimiento.

Las rondas de búsqueda se repiten mientras quede el tiempo asignado a un movimiento. Luego, se elige como respuesta final el movimiento con más simulaciones realizadas (es decir, el denominador más alto).

Pura búsqueda de juegos de Montecarlo

Este procedimiento básico se puede aplicar a cualquier juego cuyas posiciones tengan necesariamente un número finito de movimientos y una duración 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 conduce a la mejor puntuación. Los empates se rompen lanzando una moneda al aire . Pure Monte Carlo Game Search 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. ^[38] 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 a la hora de seleccionar nodos secundarios es mantener cierto equilibrio entre la explotación de variantes profundas después de movimientos con una alta tasa de ganancia promedio y la exploración de movimientos con pocas simulaciones. La primera fórmula para equilibrar la explotación y la exploración en los juegos, llamada UCT ( Upper Confidence Bound 1 aplicada a los árboles ), fue introducida por Levente Kocsis y Csaba Szepesvári. ^[16] UCT se basa en la fórmula UCB1 derivada de Auer, Cesa-Bianchi y Fischer ^[39] 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 Procesos de decisión ) de Chang, Fu, Hu y Marcus. ^[11] 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 para el nodo considerado después del $i$ -ésimo movimiento
$n i$ representa el número de simulaciones para el nodo considerado después del $i$ -ésimo movimiento
$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 tasa de ganancia promedio alta. 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 tiene sus raíces en el algoritmo de optimización de simulación AMS para estimar la función de valor en los procesos de decisión de Markov (MDP) de horizonte finito introducidos por Chang et al. ^[11] (2005) en Investigación de Operaciones . (AMS fue el primer trabajo que exploró 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 de UCT. ^[12] )

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 usa UCT, ^[16]^[40] la versión básica de la búsqueda de árbol de Monte Carlo converge sólo en los llamados juegos "Monte Carlo Perfect". ^[41] Sin embargo, la búsqueda de árboles 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 de árboles de Monte Carlo no necesita una función de evaluación explícita . Simplemente implementar 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 determinada y las condiciones de fin del juego). Como tal, la búsqueda de á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 asimétricamente 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 determinadas posiciones puede haber movimientos que parezcan superficialmente fuertes, pero que en realidad conducen a una pérdida a través de una línea de juego sutil. Estos "estados trampa" requieren un análisis exhaustivo para poder manejarlos correctamente, especialmente cuando se juega contra un jugador experto; sin embargo, es posible que MCTS no "vea" dichas líneas debido a su política de expansión selectiva de nodos. ^[42]^[43] Se cree que esto puede haber sido parte del motivo 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, por lo tanto, este resultado está "fuera del radar de búsqueda". ^[44]

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. Algunos emplean conocimientos expertos en un dominio específico, otros no.

La búsqueda de árboles de Monte Carlo puede utilizar playouts ligeros o pesados . Los playouts ligeros consisten en movimientos aleatorios, mientras que los playouts pesados aplican varias heurísticas para influir en la elección de los movimientos. ^[45] Estas heurísticas pueden emplear los resultados de playouts anteriores (por ejemplo, la heurística de la última buena respuesta ^[46] ) 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 hacia esa área. ^[17] Paradójicamente, jugar de manera subóptima en simulaciones a veces hace que un programa de búsqueda de árboles de Monte Carlo funcione mejor en general. ^[47]

Patrones de *hane* (piedras circundantes del oponente) utilizados en las reproducciones del programa MoGo. Es ventajoso tanto para el blanco como para el negro colocar una piedra en el cuadrado del medio, excepto en el patrón más a la derecha donde favorece únicamente al negro. ^[17]

Se pueden emplear conocimientos específicos del dominio al construir el árbol del juego para ayudar a explotar 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 secundario, lo que genera tasas de ganancia promedio aumentadas o reducidas artificialmente que hacen que el nodo se elija con mayor o menor frecuencia, respectivamente, en el paso de selección. ^[48] Un método relacionado, llamado sesgo progresivo , consiste en agregar a la fórmula UCB1 un elemento, donde $bi$ es una puntuación heurística del $i$ $-$ ésimo movimiento. ^[36] ${\frac {b_{i}}{n_{i}}}$

La búsqueda básica en el árbol de Monte Carlo recopila suficiente información para encontrar los movimientos más prometedores sólo después de muchas rondas; hasta entonces sus movimientos son esencialmente aleatorios. Esta fase exploratoria puede reducirse significativamente en una determinada clase de juegos utilizando RAVE ( Estimación del valor de acción rápida ). ^[48] En estos juegos, las permutaciones de una secuencia de movimientos conducen a la misma posición. Normalmente, 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 está sólo ligeramente influenciado por otros movimientos.

En RAVE, para un nodo $N$ determinado del árbol de juegos , sus nodos secundarios $Ci$ almacenan no solo las estadísticas de victorias en los playouts iniciados en el nodo $N$ , sino también las estadísticas de victorias en todos los playouts iniciados en el nodo $N y$ $debajo$ de él, si contienen movimiento. $i$ (también cuando la jugada se realizó en el árbol, entre el nodo $N$ y un playout). De esta manera, el contenido de los nodos del árbol se ve influenciado no sólo por los movimientos realizados inmediatamente en una posición determinada, sino también por los mismos movimientos realizados posteriormente.

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

Cuando se utiliza 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 representa el número de playouts ganados que contienen el movimiento $i$ y el número de todos los playouts que contienen el movimiento $i$ , y la función debe estar cerca de uno y de cero para $n$ $i$ y relativamente pequeños y relativamente grandes , respectivamente. Una de las muchas fórmulas para , propuesta por D. Silver, ^[49] 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 para maximizar la tasa de ganancias. ^[50]

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

Paralelización de hojas , es decir, ejecución paralela de muchas reproducciones desde una hoja del árbol de juego.
Paralelización de raíces , es decir, construir árboles de juego independientes en paralelo y realizar el movimiento basándose en las ramas a nivel de raíz de todos estos árboles.
Paralelización de árbol , 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 sin bloqueo . ^[52]

Ver también

AlphaGo , un programa Go que utiliza la búsqueda de árboles de Monte Carlo, el aprendizaje por refuerzo y el aprendizaje profundo .
AlphaGo Zero , un programa Go actualizado que utiliza la búsqueda de árboles de Monte Carlo, el aprendizaje por refuerzo y el aprendizaje profundo .
AlphaZero , una versión generalizada de AlphaGo Zero que utiliza búsqueda de árbol de Monte Carlo, aprendizaje por refuerzo y aprendizaje profundo .
Leela Chess Zero , una implementación de software libre de los métodos de ajedrez de AlphaZero, que actualmente se encuentra entre los principales programas de ajedrez.

Referencias

^ ab Plata, David ; Huang, Aja ; Maddison, Chris J.; Guez, Arturo; Sifré, Laurent; Driessche, George van den; Schrittwieser, Julián; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, Juan; Kalchbrenner, Nal; Sutskever, Ilya ; Lillicrap, Timoteo; Lixiviación, 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". Naturaleza . 529 (7587): 484–489. Código Bib :2016Natur.529..484S. doi : 10.1038/naturaleza16961. ISSN 0028-0836. PMID 26819042. S2CID 515925.
^ ab Plata, 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 TOTAL WAR: IA de la campaña de ROME II". Desarrollador de juegos de IA . Archivado desde el original el 13 de marzo de 2017 . Consultado el 25 de febrero de 2017 .
^ Nicolás, Metrópolis; Estanislao, Ulam (1949). "El método montecarlo". Revista de la Asociación Estadounidense de Estadística . 44 (247): 335–341. doi :10.1080/01621459.1949.10483310. PMID 18139350.
^ Abramson, Bruce (1987). El modelo de resultado esperado de los juegos de dos jugadores (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 orientadoras de búsqueda". CADE90, 10° Int. Conf. en Deducción Automatizada.pp. 470-484. LNAI 449 . Saltador. Archivado desde el original el 15 de abril de 2021 . Consultado el 14 de agosto de 2016 .
^ 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). Montecarlo Ir (PDF) . Informe técnico, Departamento de Física, Universidad de Syracuse.
^ abc Chang, Hyeong Soo; Fu, Michael C.; Hu, Jiaqiao; Marco, Steven I. (2005). "Un algoritmo de muestreo adaptativo para resolver procesos de decisión de Markov" (PDF) . La 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 25 de febrero de 2016 .
^ ab Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). "Alphago de Google DeepMind: el papel poco anunciado de OR en el logro pionero". OR/MS hoy . 45 (5): 24-29.
^ "Biblioteca de 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 japonés-francés sobre las fronteras de la ciencia .
^ Rémi Coulom (2007). "Operadores de respaldo y selectividad eficiente en la búsqueda de árboles de Montecarlo". Computadoras y juegos, Quinta Conferencia Internacional, CG 2006, Turín, Italia, 29 al 31 de mayo de 2006. Artículos revisados . H. Jaap van den Herik, Paolo Ciancarini, HHLM Donkers (eds.). Saltador. págs. 72–83. CiteSeerX 10.1.1.81.6817 . ISBN 978-3-540-75537-1.
^ abc Kocsis, Levente; Szepesvári, Csaba (2006). "Planificación de Montecarlo basada en bandidos". En Fürnkranz, Johannes; Scheffer, Tobías; Spiliopoulou, Myra (eds.). Aprendizaje automático: ECML 2006, 17ª Conferencia europea sobre aprendizaje automático, Berlín, Alemania, 18 al 22 de septiembre de 2006, Actas . Apuntes de conferencias sobre informática. vol. 4212. Saltador. 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 Computer Go de Taiwán" (PDF) . Transacciones IEEE sobre inteligencia computacional e inteligencia artificial 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 motor Go basado en la búsqueda de árboles de Monte Carlo (PDF) . Informe técnico, Universidad de Alberta.
^ "La apuesta Shodan Go" . Consultado el 2 de mayo de 2012 .
^ "Blog de investigación: AlphaGo: 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 IA al vencer al campeón de Go". Noticias de la BBC . 27 de enero de 2016.
^ "Partido 1 - Partido del desafío Google DeepMind: Lee Sedol vs AlphaGo". YouTube . 9 de marzo de 2016.
^ "Google AlphaGo AI 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). "Las Amazonas descubren Montecarlo". Computadoras y juegos, Sexta Conferencia Internacional, 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.). Saltador. 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; Yunbao; Zhangang Han (diciembre de 2011). "Método de búsqueda en tiempo real en un juego no determinista: Sra. Pac-Man". Revista ICGA . 34 (4): 209–222. doi :10.3233/ICG-2011-34404.
^ Tom Pepels; Mark HM Winands; Marc Lanctot (septiembre de 2014). "Búsqueda de árboles de Monte Carlo en tiempo real en Ms Pac-Man". Transacciones IEEE sobre inteligencia computacional e inteligencia artificial en juegos . 6 (3): 245–257. doi : 10.1109/tciaig.2013.2291577 .
^ Montaña, 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 potencial del plan. En general, esto funcionó bien,...
^ Michael Buro; Jeffrey Richard largo; Timoteo 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 XXI Conferencia Internacional Conjunta sobre Inteligencia Artificial, Pasadena, California, EE. UU., 11 al 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). "Póquer por computadora: una revisión". Inteligencia artificial . 175 (5–6): 958–987. doi : 10.1016/j.artint.2010.12.005 .
^ Sala de CD; PI Carenado (2009). "Búsqueda de Montecarlo aplicada a la selección de cartas en Magic: The Gathering" (PDF) . CIG'09 Actas de la quinta conferencia internacional sobre juegos e inteligencia computacional . Prensa IEEE. 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, 12th International Conference, ACG 2009, Pamplona, España, 11 al 13 de mayo de 2009. Artículos revisados . Saltador. págs. 21-32. ISBN 978-3-642-12992-6. Archivado 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 de árboles en 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 Montecarlo".
^ Peres, Yuval; Schramm, Oded; Sheffield, Scott; Wilson, David B. (2006). "Random-Turn Hex y otros juegos de selección". arXiv : matemáticas/0508580 .
^ Auer, Pedro; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). "Análisis en tiempo finito del problema de los bandidos multiarmados". Aprendizaje automático . 47 (2/3): 235–256. doi : 10.1023/a:1013689704352 . S2CID 207609497.
^ Browne, Cameron B.; Powley, Eduardo; Casa Blanca, Daniel; Lucas, Simón M.; Carenado, Peter I.; Rohlfshagen, Philipp; Tavener, Stephen; Pérez, Diego; Samotrakis, Espiridón; Colton, Simón (2012). "Un estudio de los métodos de búsqueda de árboles de Montecarlo". Transacciones IEEE sobre inteligencia computacional e inteligencia artificial en juegos . 4 (1): 1–43. doi :10.1109/tciaig.2012.2186810. ISSN 1943-068X.
^ Althöfer, Ingo (2012). "Juegos de llenado en el tablero con orden de turno aleatorio y perfección de Monte Carlo". Avances en juegos de computadora . Apuntes de conferencias sobre 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 adversarios 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 adversa basada en muestreo". ICAPS '11: 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". Vaya gurú del juego. Archivado desde el original el 16 de noviembre de 2016 . Consultado el 4 de julio de 2017 .
^ Świechowski, M.; Mańdziuk, J., "Autoadaptación de estrategias de juego en juegos generales" (2010), IEEE Transactions on Computational Intelligence and AI in Games , vol: 6(4), págs. 367-381, doi :10.1109/TCIAIG. 2013.2275163, http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6571225&isnumber=4804729
^ Drake, Peter (diciembre de 2009). "La política de última buena respuesta para Monte-Carlo Go". Revista ICGA . 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; Plata, David (2007). "Combinación de conocimientos online y offline en la UCT" (PDF) . Aprendizaje automático, Actas de la vigésima cuarta conferencia internacional (ICML 2007), Corvallis, Oregon, EE. UU., 20 al 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 plata (2009). Aprendizaje por refuerzo y búsqueda basada en simulación en Computer Go (PDF) . Tesis doctoral, Universidad de Alberta.
^ Rémi Coulom . "CLOP: optimización local segura para un ajuste de parámetros ruidoso de caja negra". ACG 2011: Conferencia Advances in Computer Games 13, Tilburg, Países Bajos, 20 al 22 de noviembre .
^ Guillaume MJ-B. Chaslot, Mark HM Winands, Jaap van den Herik (2008). "Búsqueda paralela de árboles en Montecarlo" (PDF) . Computadoras y juegos, Sexta Conferencia Internacional, 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.). Saltador. págs. 60–71. ISBN 978-3-540-87607-6.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
^ Markus Enzenberger; Martín Müller (2010). "Un algoritmo de búsqueda de árboles de Monte-Carlo multiproceso sin bloqueo". En Jaap Van Den Herik; Pieter Spronck (eds.). Avances en juegos de computadora: XII Conferencia Internacional, ACG 2009, Pamplona, España, 11 al 13 de mayo de 2009, artículos revisados . Saltador. págs. 14-20. CiteSeerX 10.1.1.161.1984 . ISBN 978-3-642-12992-6.

Bibliografía

Cameron Browne; Edward Powley; Daniel Whitehouse; Simón Lucas; Pedro I. Carenado; Philipp Rohlfshagen; Stephen Tavener; Diego Pérez; Espiridón Samotrakis; Simon Colton (marzo de 2012). "Un estudio de los métodos de búsqueda de árboles de Montecarlo". Transacciones IEEE sobre inteligencia computacional e inteligencia artificial 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