¿Algoritmos de Computer Go aplicados a otros juegos?

Recientemente, los programas de Computer Go pudieron competir con los humanos utilizando los árboles de búsqueda de Monte-Carlo:

Un programa go de Monte Carlo (MC) juega juegos aleatorios y evalúa fácilmente la posición del terminal (ganador o perdido). Un programa de MC busca movimientos que tengan altas tasas de ganancia, calculadas a partir de jugar al menos unos cientos de juegos aleatorios.

(Esta es una descripción muy simplificada. En la práctica, uno desea explorar ramas interesantes con mayor prioridad, por lo que la aleatoriedad debe controlarse de alguna manera utilizando los resultados recopilados. Para jugar a un nivel razonable, aún deben realizarse varios millones de juegos aleatorios. jugado. Pero, con suerte, es bastante rápido para jugar al azar...)

Siento que se podrían "abordar" muchos más juegos usando este método, y eso podría incluir tal vez la gran mayoría de los juegos de mesa...

Dos preguntas:

  • ¿Se ha aplicado ya el método de Montecarlo a otros juegos? (¿Hay implementaciones concretas disponibles?)

  • ¿Para qué tipo de juegos, entre aquellos que tienen reglas claramente establecidas y no se basan en una comunicación compleja entre los jugadores, se puede esperar que este método falle?

Respuestas (3)

¿Se ha aplicado ya el método de Montecarlo a otros juegos? (¿Hay implementaciones concretas disponibles?

Sí. Este trabajo de posgrado podría ser de su interés. Cubre Backgammon, Bridge, Go, Scrabble y Clobber.

¿Para qué tipo de juegos, entre aquellos que tienen reglas claramente establecidas y no se basan en una comunicación compleja entre los jugadores, se puede esperar que este método falle?

En realidad, los métodos de Monte Carlo no funcionan muy bien con los juegos finales en general. Encontrará que muchas implementaciones de computadora que usan métodos de Monte Carlo emplean diferentes algoritmos cuando juegan el final del juego.

  • MAVEN usa algoritmos de búsqueda B* durante el final del juego (no más fichas para dibujar).
  • MoGo usa patrones 3x3 para ayudar a identificar movimientos "interesantes", y Upper Confidence aplicado a Trees (UCT) para ayudar a eliminar los movimientos aleatorios menos óptimos de la consideración y acelerar la búsqueda.

Si bien los métodos de Monte Carlo son una herramienta útil para jugar juegos de mesa, no son una solución perfecta. Los programas Computer Go que usan MCTS aún no pueden vencer a los mejores jugadores en tableros de 19x19 sin desventajas significativas. Los programas de Computer Bridge no son rival para los jugadores expertos. Los métodos de Monte Carlo solo se acercarán al juego perfecto con un tiempo/espacio infinito.

+1 con accesorios adicionales para cubrir una variedad de juegos. Estoy impresionado de que la búsqueda de Monte Carlo haya funcionado bien para TD-Gammon.
Honestamente, no sé si el método de Monte Carlo está lo suficientemente bien definido como para distinguir un algoritmo MCTS, de un algoritmo de implementación, de una red neuronal, etc. Creo que la lista de juegos podría ser incluso mucho más larga, pero el OP solo quería saber si existen.
¿De dónde sacaste que MoGo usa bases de datos de finales? No hay tal cosa en Go. ¿Te refieres a bases de datos para movimientos de apertura (que de hecho se agregaron en algunas otras IA de MC)?
google.com/… Ups, tienes razón. MoGo usa patrones 3x3 para hacer movimientos más interesantes en general en lugar del enfoque aleatorio MC, esto no es específicamente para finales. Mi punto general sigue en pie, los métodos MC no son buenos en los juegos finales.

Primero, uno necesita entender las diferencias entre Chess y Go desde el punto de vista de la complejidad del juego. A continuación, uno debe comprender las diferencias entre los dos tipos de algoritmos de IA y por qué uno funciona para Chess y el otro no.

Tanto el ajedrez como el Go son juegos de información perfectos sin elementos estocásticos . Esto significa que siempre puede ver el estado completo del juego, y no hay posibilidad ni suerte involucradas (no hay dados para tirar, no hay sorteos de cartas desafortunados).

La diferencia entre los juegos se puede resumir en el número de movimientos posibles en cada turno (número de decisiones o elecciones) y la duración del juego. Me estoy saltando un análisis más formal de los tamaños de los árboles de búsqueda, los tamaños de los espacios de estado, etc., para proporcionar una comprensión más intuitiva de las diferencias.

Para el ajedrez, el número promedio de movimientos posibles en un punto típico del juego es de unos 30 movimientos diferentes. Un juego típico dura alrededor de 40 movimientos. Para Go, hay alrededor de 250 opciones por movimiento y el juego dura alrededor de 150 movimientos.

Lo que esto significa es que hay mucha, mucha más evaluación de posibles movimientos, mucho más lejos en el futuro con Go que con Ajedrez.

Sin embargo, lo que hace posible que los humanos jueguen es que en Go las piezas son todas iguales, podemos apuntar a patrones en lugar de posiciones.

Una IA de ajedrez tradicional usa algo llamado Función de evaluación que usa atajos (como asignar más puntos a las reinas que a los peones) para evaluar un tablero y decir que el estado del juego es mejor o peor para un jugador que para el otro. Con Go, es muy difícil llegar a una función de evaluación, ya que las piezas son las mismas y el territorio no está grabado hasta casi el final del juego. Esta es la razón por la cual el enfoque tradicional de ajedrez-IA para Go ha fallado, los espacios de decisión y estado más grandes son imposibles de podar, por lo que la búsqueda es ineficaz.

Ahora, demos la vuelta al problema y veamos por qué usar Monte Carlo en el ajedrez podría ser una mala idea. Dado que el juego aleatorio no distingue entre 'movimientos buenos' y 'movimientos malos', la gran mayoría de los juegos aleatorios explorarán árboles de juego obviamente malos. Por ejemplo, sacrificar tu reina sin obtener ninguna ventaja, o hacerla vulnerable y que el oponente no la explote. Se obtiene poca información promediando los resultados de los malos movimientos individuales. Este tipo de IA funcionará, pero requeriría mucho más cálculo que el enfoque evaluativo habitual.

En resumen, mucho más de ganar/perder es evidente al mirar las piezas en Ajedrez que en Go.

Entonces, ¿por qué Monte Carlo funciona para Go (es decir, puede vencer a los humanos)? Funciona porque tanto los humanos como las computadoras son muy malos para jugar Go (en comparación con el juego perfecto teórico). El muestreo de juego aleatorio de Monte Carlo funciona porque no es necesario un mayor nivel de comprensión de los patrones que el que se puede obtener de una manera computacionalmente eficiente.

Entonces, ¿cómo se comparan otros juegos de mesa? Hagámonos estas preguntas:

  1. ¿Se puede evaluar fácilmente la situación de la junta?
  2. ¿Cuántas decisiones/movimientos son posibles en cada turno?
  3. ¿Cuántas decisiones se deben tomar en un juego típico?
  4. ¿Qué tan predecibles son los resultados de cada movimiento?

La mayoría de los juegos de mesa mostrarán características que los acercarán mucho más al ajedrez que Go para las primeras 3 preguntas. Esto es muy sugerente de que una IA de estilo de ajedrez será más fácil, más rápida y más efectiva.

Dado que el #4 es diferente tanto para Chess como para Go, veamos cómo afecta a los dos algoritmos.

Si tuviéramos un factor aleatorio, digamos, sacar una carta de una pila de 60, cada decisión de sacar una carta dividirá el juego en 60 resultados posibles. Dependiendo de lo que dibujen otros jugadores, sus elecciones cambiarán, lo que nuevamente nos coloca en la posición de muestrear muchos estados que son altamente improbables o imposibles (argumentando en contra de Monte Carlo). Mientras tanto, se puede escribir fácilmente una función de evaluación para dar valores a cada carta (combinada con el estado del tablero).

No he visto Monte Carlo aplicado a otras IA de juegos de mesa, y las anteriores son algunas de las razones. Esas son también las razones por las que se espera que falle. Cuando falla, puede fallar espectacularmente porque está haciendo movimientos tontos y obviamente malos porque los resultados 'aleatorios' de las muestras resultaron ser irracionales en las futuras elecciones aleatorias.

Si quieres leer más, te sugiero estos sitios:

http://aaai.org/AITopics/

http://beej.us/blog/data/monte-carlo-método-juego-ai/

http://www.aihorizon.com/essays/chessai/intro.htm

Creo que la pregunta original presupone que está utilizando algún tipo de función de evaluación estática para podar el árbol de búsqueda (incompleto) utilizado por el método de Monte Carlo, al igual que lo hace con una búsqueda más convencional (según la cláusula sobre ramas "interesantes" ). Entonces, el problema principal para un juego como el ajedrez se convierte en "¿Cuánto se deteriora el juego de la IA cuando tomas una muestra de Monte Carlo en lugar de explorar todas las ramas de manera determinista?"
Lo siento, no estoy de acuerdo con la mayoría de las cosas que afirmas, y tu segundo enlace (el único que parece relevante para esta pregunta) no considera los árboles de búsqueda de Monte Carlo (ver el último párrafo).
Por cierto, ¿su conclusión es que los árboles de búsqueda de MC no se ajustan al ajedrez ni a la mayoría de los juegos de mesa?
@StéphaneGimenez "No estoy de acuerdo con la mayoría de las cosas que dices" es bastante vago, en mi opinión.
@NealTibrewala Tu ejemplo de dibujo de cartas no tiene sentido para mí. Puede tener en cuenta eventos probabilísticos al realizar una búsqueda basada en árboles. (Aunque, según mis conocimientos universitarios ligeramente anticuados, la IA más exitosa para un juego que incorpora un elemento de azar aún se basa en el aprendizaje automático ).
@Alex, lo sé, me gustaría agregar comentarios explícitos pronto e intentar encontrar algunas referencias para respaldarlos, pero tomaría algo de espacio.
Hice algunas ediciones (principalmente errores tipográficos y formateo). Su punto sobre la evaluación del tablero es bueno y tiene sentido, pero no veo cómo el problema de explorar árboles de "movimientos malos obvios y tontos" es mejor en Go que en ajedrez. Proporcionalmente, apostaría a que hay más malas movidas en un punto dado en un juego de Go que en un juego de ajedrez. Aunque quizás en el ajedrez las consecuencias de una sola jugada algo mala pueden ser más inmediatas e irreversibles que en el Go.
Todos, excelentes comentarios. @shujaa, por ejemplo, una vez que pierdes un cierto número de piezas, la pérdida es casi inevitable. Sin embargo, el juego aleatorio no mostrará eso, ya que es probable que el otro lado pierda dos 'al azar'. Estas certezas son suficientes para que el Ajedrez esté siendo 'resuelto' debido a la casi certeza de ciertas valoraciones. " games.slashdot.org/story/12/04/02/2043240/… "
@StéphaneGimenez Lamento que no esté de acuerdo. Mi afirmación es que MC Search solo es necesario en Go debido a la dificultad de crear una función de evaluación útil. La mayoría de los otros juegos de mesa no tienen la complejidad de Go y son funciones de evaluación fáciles de escribir. Por lo tanto, no es necesario crear una IA basada en MC, y hacerlo sería innecesariamente largo y costoso de ejecutar (aunque sería más fácil de 'escribir').
... ¿por qué esta respuesta habla tanto de ajedrez? ¿Quién dijo algo sobre ajedrez?
@Neal. Con MC puede mejorar cualquier función de evaluación buena o parcialmente precisa. En Go, sucede que no necesita ninguna función de evaluación (simplemente terminar aleatoriamente es suficiente). Pero nada impide usar una función de evaluación después de cierta profundidad en el árbol de búsqueda de MC (ejemplo: dama + torre contra nada es una victoria). El algoritmo puede entonces converger más rápido, pero nada garantiza que convergerá a la jugada perfecta.
@NealTibrewala Eso tiene sentido, tal vez podría editar su respuesta para que los problemas de evaluación de Go se presenten como un punto principal. Tal como está, no mencionas eso hasta el sexto párrafo.
@BlueRaja-DannyPflughoeft: La pregunta es (1) si MC se ha hecho con otros juegos y (2) dónde fallaría. Así que está bien que esta respuesta considere el ajedrez.

Ok, investigué un poco. Citando este artículo :

En los últimos años, surgieron varias técnicas basadas en Monte-Carlo en el campo de los juegos de computadora. Ya se han aplicado con éxito a muchos juegos, incluidos POKER (Billings et al. 2002) y SCRABBLE (Sheppard 2002). Monte-Carlo Tree Search (MCTS), una técnica basada en Monte-Carlo que se estableció por primera vez en 2006, se implementa en los programas GO mejor calificados. Estos programas derrotaron por primera vez a los jugadores profesionales de GO en el tablero de 9 × 9. Sin embargo, la técnica no es específica de GO o de los juegos de mesa clásicos, sino que se puede generalizar fácilmente a los juegos de mesa oa los videojuegos modernos. Además, su implementación es bastante sencilla. En la demostración propuesta, ilustraremos que MCTS se puede aplicar de manera efectiva a

  1. juegos de mesa clásicos (como GO)
  2. juegos de mesa modernos (como SETTLERS OF CATAN), y
  3. videojuegos (como el juego SPRING RTS).

Entonces, parece que ya se aplicó a algunos otros juegos. Y mencionan implementaciones explícitas, pero no proporcionan enlaces a ellas.

Yo llamaría a 9 x 9 un éxito muy limitado. Estás reduciendo severamente el factor de ramificación asociado con cada movimiento en comparación con el tablero completo de 19 x 19.
Estuve presente en la sala de la primera victoria oficial de 9x9 contra un profesional de MoGo, y fue hace como 3 o 4 años. Ahora están a solo 4 o 5 piedras de los mejores profesionales en 19x19 . A su vez, un profesional afirmó una vez que estaba a tres piedras del juego perfecto (y desde el punto de vista de un jugador de go, es plausible).
Algo de esto se reduce a la definición de "fracaso". La IA de MC Catan jugará 'bien' y puede vencer a otras IA, pero afirman que es solo un "oponente desafiante", lo que implica que todavía es posible que los humanos ganen. En general, cualquier búsqueda de MC requiere que los buenos y los malos movimientos estén en una proporción bastante razonable. Dicho de otra manera, hay un límite superior de cuán buena puede ser una IA basada en MC, que una IA de poda clásica puede superar (en casos no degenerados).
@Neal: Por supuesto, todavía es posible que los humanos ganen Catan. Incluso si la computadora pudiera jugar perfectamente , los humanos, incluso los principiantes, podrían vencerla un porcentaje decente del tiempo. Esto se debe a la gran cantidad de posibilidades inherentes a Catán. Lo mismo ocurre con el póquer, el bridge, el cribbage, etc. No ocurre lo mismo con los juegos de información perfecta como el ajedrez o el go; una computadora que jugó perfectamente siempre podría garantizar una victoria/empate jugando como el lado ventajoso.
¿Algoritmos de Computer Go aplicados a otros juegos?
RespuestasAquíPolítica de privacidad1y, 0v