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 .
Clase | Algoritmo de búsqueda |
---|
MCTS se combinó con redes neuronales en 2016 para Computer Go . [1] Se ha utilizado en otros juegos de mesa como ajedrez y shogi , [2] juegos con información incompleta como bridge [3] y póquer , [4] así como en videojuegos de estrategia por turnos (como Total Guerra: Implementación de Roma II en la campaña de alto nivel AI [5] ).
Historia
Método Monte Carlo
El método de Monte Carlo , que utiliza la aleatoriedad para problemas deterministas que son difíciles o imposibles de resolver con otros enfoques, se remonta a la década de 1940. En su tesis de doctorado de 1987, Bruce Abramson combinó la búsqueda minimax con un modelo de resultado esperado basado en jugadas aleatorias hasta el final, en lugar de la función de evaluación estática habitual . Abramson dijo que el modelo de resultados esperados "ha demostrado ser preciso, exacto, fácilmente estimable, eficientemente calculable e independiente del dominio". [6] Experimentó en profundidad con Tic-tac-toe y luego con funciones de evaluación generadas por máquina para Othello y Chess .
Estos métodos fueron luego 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 exponenciales de 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 Go-playing . [10] En 2002, Chang et al. [11] propuso la idea de "despliegue recursivo y retroceso" 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 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 (Upper Confidence Trees). [12]
Búsqueda de árboles de Montecarlo (MCTS)
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 juego 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 árboles), [16] y S. Gelly et al. implementó UCT en su programa MoGo. [17] En 2008, MoGo alcanzó el nivel de 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 de Go humano profesional sin desventajas en un tablero de 19x19 de tamaño completo. [1] [21] [22] En marzo de 2016, AlphaGo recibió un nivel honorario de 9 dan (maestro) en 19 × 19 Go por derrotar a Lee Sedol en un partido de cinco juegos con una puntuación final de cuatro juegos a uno. [23] AlphaGo representa una mejora significativa con respecto a los programas anteriores de Go, así como un hito en el aprendizaje automático, ya que utiliza la búsqueda de árboles 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 gran eficiencia. superando los 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] póquer , [4] Magic: The Gathering , [33] o Settlers of Catan [34] ) .
Principio de funcionamiento
El enfoque de MCTS está en el análisis de los movimientos más prometedores, expandiendo el árbol de búsqueda basado 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 lanzamientos . En cada playout, el juego se juega hasta el final seleccionando movimientos al azar. El resultado final del juego de cada juego se usa para ponderar los nodos en el árbol del juego para que sea más probable que se elijan mejores nodos en juegos futuros.
La forma más básica de usar playouts es aplicar el mismo número de playouts después de cada movimiento legal del jugador actual, luego elegir el movimiento que condujo a la mayor cantidad de victorias. [10] La eficiencia de este método, llamado Pure Monte Carlo Game Search, a menudo aumenta con el tiempo a medida que se asignan más jugadas a los movimientos que frecuentemente han dado como resultado la victoria del jugador actual según las jugadas anteriores. Cada ronda de búsqueda de árboles de Monte Carlo consta de cuatro pasos: [35]
- Selección : comience desde la raíz R y seleccione los nodos secundarios sucesivos hasta que se alcance un nodo hoja L. La raíz es el estado actual del juego y una hoja es cualquier nodo que tenga un hijo potencial a partir 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 los nodos secundarios que permite que el árbol del juego se expanda hacia los movimientos más prometedores, que es la esencia de la búsqueda del árbol de Monte Carlo.
- Expansión : A menos que L termine el juego de manera decisiva (por ejemplo, ganar / perder / empatar) para cualquiera de los jugadores, cree uno (o más) nodos secundarios y elija el nodo C de uno de ellos. Los nodos hijos son los movimientos válidos desde la posición de partida definida por L .
- Simulación : Complete una reproducción aleatoria desde el nodo C . Este paso a veces también se denomina reproducción o lanzamiento. Un playout puede ser tan simple como elegir movimientos aleatorios uniformes hasta que se decida el juego (por ejemplo, en el ajedrez, el juego se gana, se pierde o se empata).
- Retropropagación : Use el resultado de la reproducción a la información de actualización en los nodos en el camino desde C a R .
Este gráfico muestra los pasos involucrados en una decisión, y cada nodo muestra la proporción de victorias con respecto al total de playouts desde ese punto en el árbol del juego para el jugador que representa el nodo. [36] 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 jugadas para las blancas desde esta posición. Complementa el total de 10/21 victorias negras que se muestran a lo largo de los tres nodos negros debajo, cada uno de los cuales representa un posible movimiento negro.
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 fueron acreditados con victorias (el numerador). Si, en cambio, el blanco gana, 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 ganancias. En los juegos donde es posible empatar, un empate hace que el numerador para blanco y 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 el objetivo de cada jugador para maximizar el valor de su movimiento.
Las rondas de búsqueda se repiten mientras quede el tiempo asignado a un movimiento. A continuación, se elige como respuesta final la jugada con más simulaciones realizadas (es decir, el denominador más alto).
Búsqueda pura de juegos de Monte Carlo
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 factibles: k se juegan juegos aleatorios hasta el final y se registran las puntuaciones. Se elige el movimiento que conduzca a la mejor puntuación. Los lazos se rompen con buenos lanzamientos de monedas. 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 al infinito) en juegos de mesa con orden de turno aleatorio, por ejemplo, en Hex con orden de turno aleatorio. [37] 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 para seleccionar nodos secundarios es mantener cierto equilibrio entre la explotación de variantes profundas después de movimientos con una tasa de ganancia promedio alta 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 aplicado a los árboles ), fue introducida por Levente Kocsis y Csaba Szepesvári . [16] UCT se basa en la fórmula UCB1 derivada por Auer, Cesa-Bianchi y Fischer [38] y el algoritmo AMS (muestreo adaptativo multietapa) convergente comprobable que se aplicó por primera vez a modelos de toma de decisiones de varias etapas (específicamente, Markov Procesos de decisión ) por Chang, Fu, Hu y Marcus. [11] Kocsis y Szepesvári recomiendan elegir en cada nodo del árbol de juego el movimiento para el que la expresióntiene el valor más alto. En esta fórmula:
- 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 √ 2 ; en la práctica, generalmente elegido empíricamente
El primer componente de la fórmula anterior corresponde a la explotación; es alto para movimientos con un promedio de victorias alto. 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 operativa . (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. [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 , [39] la versión básica de la búsqueda de árbol de Monte Carlo converge sólo en los llamados juegos "Monte Carlo Perfect". [40] 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 . La simple 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 determinada y las condiciones del final 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 ] logra mejores resultados que los algoritmos clásicos en juegos con un factor de ramificación alto .
Una desventaja es que, en una posición crítica contra un jugador experto, puede haber una sola rama que lleve a una pérdida. Debido a que esto no se encuentra fácilmente al azar, es posible que la búsqueda no lo "vea" y no lo tenga en cuenta. 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, por lo tanto, este resultado está "fuera del radar de búsqueda". [41]
Mejoras
Se han propuesto varias modificaciones del método básico de búsqueda de árbol de Monte Carlo para acortar el tiempo de búsqueda. Algunos emplean conocimientos de expertos específicos del dominio, otros no.
La búsqueda de árboles de Monte Carlo puede usar 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. [42] Estas heurísticas pueden emplear los resultados de jugadas anteriores (por ejemplo, la heurística de la última buena respuesta [43] ) o el conocimiento experto de un juego dado. Por ejemplo, en muchos programas de Go-playing, ciertos patrones de piedras en una parte del tablero influyen en la probabilidad de moverse a esa área. [17] Paradójicamente, jugar de manera subóptima en las simulaciones a veces hace que un programa de búsqueda de árboles de Monte Carlo juegue más fuerte en general. [44]
Se pueden emplear conocimientos específicos de dominio al construir el árbol del juego para ayudar a la explotación de algunas variantes. Uno de estos métodos asigna a priori distintos de cero al número de simulaciones ganadas y jugadas al crear cada nodo hijo, lo que conduce a tasas de ganancia promedio elevadas o reducidas artificialmente que hacen que el nodo se elija con más o menos frecuencia, respectivamente, en el paso de selección. [45] Un método relacionado, llamado sesgo progresivo , consiste en agregar a la fórmula UCB1 unelemento, donde b i es una puntuación heurística del i -ésimo movimiento. [35]
La búsqueda básica del á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 determinada clase de juegos utilizando RAVE ( Estimación de valor de acción rápida ). [45] 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 está solo ligeramente influenciado por otros movimientos.
En RAVE, para un nodo de árbol de juego dado N , sus nodos secundarios C i 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 se jugó el movimiento en el árbol, entre el nodo N y un playout). De esta manera, el contenido de los nodos del árbol se ve influenciado no solo por los movimientos que se juegan inmediatamente en una posición determinada, sino también por los mismos movimientos que se juegan más tarde.
Cuando se usa 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 elLa función debe ser cercana a uno y a cero para n i y relativamente pequeños y relativamente grandes., respectivamente. Una de las muchas fórmulas para, propuesto por D. Silver, [46] dice que en posiciones equilibradas uno puede tomar, donde b es una constante elegida empíricamente.
Las heurísticas utilizadas en la búsqueda de árboles de Monte Carlo a menudo requieren muchos parámetros. Existen métodos automatizados para ajustar los parámetros y maximizar la tasa de ganancias. [47]
La búsqueda de árbol de Monte Carlo puede ser ejecutada simultáneamente por muchos subprocesos o procesos . Existen varios métodos fundamentalmente diferentes de su ejecución paralela : [48]
- Paralelización de hojas , es decir, ejecución paralela de muchos playouts de una hoja del árbol del juego.
- Paralelización de raíces , es decir, construir árboles de juego independientes en paralelo y hacer el movimiento basándose en las ramas al nivel de la 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 uno, mutex global , con más mutex o con sincronización sin bloqueo . [49]
Ver también
- AlphaGo , un programa de 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 la búsqueda de árboles de Monte Carlo, el aprendizaje por refuerzo y el aprendizaje profundo .
- Leela Chess Zero , una implementación de software libre de los métodos de AlphaZero para el ajedrez, que actualmente se encuentra entre los principales programas de juego de ajedrez.
Referencias
- ^ a b 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". Naturaleza . 529 (7587): 484–489. Código Bib : 2016Natur.529..484S . doi : 10.1038 / nature16961 . ISSN 0028-0836 . PMID 26819042 . S2CID 515925 .
- ^ a b Plata, David (2017). "Dominar el ajedrez y el shogi por auto-juego con un algoritmo de aprendizaje de refuerzo general". arXiv : 1712.01815v1 [ cs.AI ].
- ^ Stuart J. Russell , Peter Norvig (2009). Inteligencia artificial: un enfoque moderno (3ª ed.). Prentice Hall .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ a b Jonathan Rubin; Ian Watson (abril de 2011). "Computer poker: una revisión" (PDF) . Inteligencia artificial . 175 (5–6): 958–987. doi : 10.1016 / j.artint.2010.12.005 . Archivado desde el original (PDF) el 13 de agosto de 2012.
- ^ "Búsqueda de árboles de Monte-Carlo en TOTAL WAR: Campaña AI 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 .
- ^ Abramson, Bruce (1987). El modelo de resultados esperados 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; Johann Schumann; Christian Suttner (1989). "Aprendizaje heurístico para un demostrador de teoremas usando retropropagación". . En J. Retti; K. Leidlmair (eds.). 5. Österreichische Artificial-Intelligence-Tagung. Informatik-Fachberichte 208, págs. 87-95 . Saltador.
- ^ Christian Suttner; Wolfgang Ertel (1990). "Adquisición automática de heurísticas de guía de búsqueda". . CADE90, 10º Int. Conf. sobre la deducción automatizada.pp. 470-484. LNAI 449 . Saltador.
- ^ 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.
- ^ a b Brügmann, Bernd (1993). Monte Carlo Go (PDF) . Informe técnico, Departamento de Física, Universidad de Syracuse.
- ^ a b c Chang, Hyeong Soo; Fu, Michael C .; Hu, Jiaqiao; Marcus, Steven I. (2005). "Un algoritmo de muestreo adaptativo para resolver los procesos de decisión de Markov" (PDF) . Investigación operativa . 53 : 126-139. doi : 10.1287 / opre.1040.0145 . hdl : 1903/6264 .
- ^ a b Hyeong Soo Chang; Michael Fu; Jiaqiao Hu; Steven I. Marcus (2016). "Alphago de Google DeepMind: papel desconocido de OR en el logro innovador" . OR / MS hoy . 45 (5): 24-29.
- ^ "Biblioteca de Sensei: KGSBotRatings" . Consultado el 3 de mayo de 2012 .
- ^ Rémi Coulom (2008). "La revolución de Montecarlo en marcha" (PDF) . Simposio sobre las fronteras de la ciencia entre Japón y Francia .
- ^ Rémi Coulom (2007). "Operadores eficientes de selectividad y respaldo en la búsqueda de árboles de Monte-Carlo". Computers and Games, 5th International Conference, CG 2006, Turín, Italia, 29 al 31 de mayo de 2006. Revised Papers . 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.
- ^ a b Kocsis, Levente; Szepesvári, Csaba (2006). "Planificación de Montecarlo basada en bandidos". En Fürnkranz, Johannes; Scheffer, Tobias; 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 en Ciencias de la Computación. 4212 . Saltador. págs. 282-293. CiteSeerX 10.1.1.102.1296 . doi : 10.1007 / 11871842_29 . ISBN 3-540-45375-X.
- ^ a b c 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 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 Go Engine 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: Dominar el antiguo juego de Go con aprendizaje automático" . Blog de investigación de Google . 27 de enero de 2016.
- ^ "Google logra el 'avance' de la IA al vencer al campeón de Go" . BBC News . 27 de enero de 2016.
- ^ "Partido 1 - Partido desafío de Google DeepMind: Lee Sedol vs AlphaGo" . Youtube . 9 de marzo de 2016.
- ^ "Google AlphaGo AI limpia arrasa 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). "Amazonas Descubre Montecarlo". Computadoras y juegos, 6ª 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 Charles de Praga.
- ^ Xiaocong Gan; Yun Bao; 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 IA 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" . 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 del plan potencial. En general, esto funcionó bien, ...
- ^ Michael Buro; Jeffrey Richard Long; Timothy Furtak; Nathan R. Sturtevant (2009). "Mejora de la evaluación de estado, la inferencia y la búsqueda en juegos de cartas basados en trucos". IJCAI 2009, Actas de la 21ª 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 .
- ^ CD Ward; PI Cowling (2009). "Búsqueda de Monte Carlo aplicada a la selección de cartas en Magic: The Gathering" (PDF) . CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games . 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, XII Congreso Internacional, ACG 2009, Pamplona, España, 11 al 13 de mayo de 2009. Revised Papers . Saltador. págs. 21–32. ISBN 978-3-642-12992-6.
- ^ a b GMJB Chaslot; MHM Winands; JWHM Uiterwijk; HJ van den Herik; B. Bouzy (2008). "Estrategias progresivas para la búsqueda de árboles de Monte-Carlo" (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 : matemáticas / 0508580 .
- ^ Auer, Peter; Cesa-Bianchi, Nicolò; Fischer, Paul (2002). "Análisis en tiempo finito del problema del bandido multiarmado" . Aprendizaje automático . 47 (2/3): 235–256. doi : 10.1023 / a: 1013689704352 . S2CID 207609497 .
- ^ Bouzy, Bruno. "Computer Go anticuado vs Monte-Carlo Go" (PDF) . Simposio del IEEE sobre juegos e inteligencia computacional, del 1 al 5 de abril de 2007, Hilton Hawaiian Village, Honolulu, Hawaii .
- ^ Althöfer, Ingo (2012). "Juegos de relleno de tablero con orden de giro aleatorio y perfección de Montecarlo". Avances en juegos de computadora . Apuntes de conferencias en Ciencias de la Computación. 7168 . págs. 258-269. doi : 10.1007 / 978-3-642-31866-5_22 . ISBN 978-3-642-31865-8.
- ^ "Lee Sedol derrota a AlphaGo en una remontada magistral - Juego 4" . Go Game Guru. 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 el juego general" (2010), IEEE Transactions on Computational Intelligence and AI in Games , vol: 6 (4), pp. 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 Playout en Monte-Carlo Go". Actas de la Conferencia Internacional de 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.
- ^ a b Gelly, Sylvain; Plata, David (2007). "Combinación de conocimientos en línea y fuera de línea en UCT" (PDF) . Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, 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 Computer Go (PDF) . Tesis de doctorado, Universidad de Alberta.
- ^ Rémi Coulom . "CLOP: Optimización local segura para ajuste de parámetros de caja negra ruidosa" . ACG 2011: Conferencia Advances in Computer Games 13, Tilburg, Países Bajos, 20-22 de noviembre .
- ^ Guillaume MJ-B. Chaslot, Mark HM Winands, Jaap van den Herik (2008). "Búsqueda de árboles de Montecarlo en paralelo" (PDF) . Computadoras y juegos, 6ª 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.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Markus Enzenberger; Martin Müller (2010). "Un algoritmo de búsqueda de árbol Monte-Carlo multiproceso sin bloqueo". 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, Revised Papers . Saltador. pp. 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). "Una encuesta de 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 .
enlaces externos
- Guía para principiantes de la búsqueda de árboles de Montecarlo