6388ce129963208649083b0e Stratego Header 02 Hd.png

DeepNash aprende a jugar Stratego desde cero combinando teoría de juegos y RL profunda sin modelos

Los sistemas de inteligencia artificial (IA) para juegos han avanzado a una nueva frontera. Stratego, el clásico juego de mesa que es más complejo que el ajedrez y el Go, y más astuto que el póquer, ya se ha dominado. Publicado en ciencianosotros presentamos ProfundoNashun agente de IA que aprendió el juego desde cero hasta un nivel humano experto jugando contra sí mismo.

DeepNash utiliza un enfoque novedoso, basado en la teoría de juegos y el aprendizaje por refuerzo profundo sin modelos. Su estilo de juego converge hacia un equilibrio de Nash, lo que significa que su juego es muy difícil de explotar para un oponente. De hecho, es tan difícil que DeepNash ha alcanzado el top tres de todos los tiempos entre los expertos humanos en la plataforma Stratego en línea más grande del mundo, Gravon.

Históricamente, los juegos de mesa han sido una medida del progreso en el campo de la IA, permitiéndonos estudiar cómo los humanos y las máquinas desarrollan y ejecutan estrategias en un entorno controlado. A diferencia del ajedrez y el Go, Stratego es un juego de información imperfecta: los jugadores no pueden observar directamente las identidades de las piezas de su oponente.

Esta complejidad ha significado que otros sistemas Stratego basados ​​en IA hayan tenido dificultades para ir más allá del nivel amateur. También significa que una técnica de IA muy exitosa llamada “búsqueda de árbol de juegos”, utilizada anteriormente para dominar muchos juegos de información perfecta, no es lo suficientemente escalable para Stratego. Por esta razón, DeepNash va mucho más allá de la búsqueda en el árbol de juegos.

El valor de dominar Stratego va más allá de los juegos. En cumplimiento de nuestra misión de resolver inteligencia para hacer avanzar la ciencia y beneficiar a la humanidad, necesitamos construir sistemas avanzados de IA que puedan operar en situaciones complejas del mundo real con información limitada de otros agentes y personas. Nuestro artículo muestra cómo DeepNash se puede aplicar en situaciones de incertidumbre y equilibrar con éxito los resultados para ayudar a resolver problemas complejos.

Conociendo Stratego

Stratego es un juego por turnos de capturar la bandera. Es un juego de engaños y tácticas, de recopilación de información y maniobras sutiles. Y es un juego de suma cero, por lo que cualquier ganancia de un jugador representa una pérdida de la misma magnitud para su oponente.

Stratego es un desafío para la IA, en parte porque es un juego de información imperfecta. Ambos jugadores comienzan organizando sus 40 piezas de juego en la formación inicial que quieran, inicialmente ocultas entre sí cuando comienza el juego. Dado que ambos jugadores no tienen acceso al mismo conocimiento, necesitan equilibrar todos los resultados posibles al tomar una decisión, lo que proporciona un punto de referencia desafiante para estudiar las interacciones estratégicas. Los tipos de piezas y sus clasificaciones se muestran a continuación.

Izquierda: La clasificación de piezas. En las batallas, las piezas de mayor rango ganan, excepto la 10 (Mariscal) que pierde cuando es atacada por un Espía, y las Bombas siempre ganan excepto cuando son capturadas por un Minero.
Medio: Una posible formación inicial. Observe cómo la bandera está guardada de forma segura en la parte trasera, flanqueada por bombas protectoras. Las dos áreas de color azul pálido son “lagos” y nunca se ingresa a ellas.
Bien: Un juego en juego, que muestra al Espía de Azul capturando al 10 de Rojo.

La información se gana con esfuerzo en Stratego. La identidad de la pieza de un oponente normalmente se revela sólo cuando se encuentra con el otro jugador en el campo de batalla. Esto contrasta marcadamente con los juegos de información perfecta como el ajedrez o el Go, en los que ambos jugadores conocen la ubicación y la identidad de cada pieza.

Los enfoques de aprendizaje automático que funcionan tan bien en juegos de información perfecta, como DeepMind alfacero, no se transfieren fácilmente a Stratego. La necesidad de tomar decisiones con información imperfecta y la posibilidad de farolear hacen que Stratego se parezca más al póquer Texas Hold’em y requiere una capacidad humana señalada una vez por el escritor estadounidense Jack London: “La vida no siempre es una cuestión de mantener buenas cartas, pero a veces, jugar bien una mala mano”.

Sin embargo, las técnicas de IA que funcionan tan bien en juegos como Texas Hold’em no se transfieren a Stratego debido a la gran duración del juego: a menudo cientos de movimientos antes de que un jugador gane. El razonamiento en Stratego debe realizarse sobre una gran cantidad de acciones secuenciales sin una idea obvia de cómo cada acción contribuye al resultado final.

Finalmente, el número de estados posibles del juego (expresados ​​como “complejidad del árbol del juego”) está fuera del gráfico en comparación con el ajedrez, el Go y el póquer, lo que lo hace increíblemente difícil de resolver. Esto es lo que nos entusiasmó de Stratego y la razón por la que ha representado un desafío durante décadas para la comunidad de IA.

La escala de las diferencias entre ajedrez, póquer, Go y Stratego.

Buscando un equilibrio

DeepNash emplea un enfoque novedoso basado en una combinación de teoría de juegos y aprendizaje por refuerzo profundo sin modelos. “Sin modelo” significa que DeepNash no intenta modelar explícitamente el estado de juego privado de su oponente durante el juego. En particular, en las primeras etapas del juego, cuando DeepNash sabe poco sobre las piezas de su oponente, tal modelado sería ineficaz, si no imposible.

Y debido a que la complejidad del árbol de juegos de Stratego es tan vasta, DeepNash no puede emplear un enfoque incondicional de juegos basados ​​en IA: la búsqueda en el árbol de Monte Carlo. La búsqueda de árboles ha sido un ingrediente clave de muchos logros históricos en IA para juegos de mesa menos complejos y póquer.

En cambio, DeepNash funciona con una nueva idea algorítmica de teoría de juegos que llamamos Dinámica de Nash regularizada (R-NaD). Trabajando a una escala incomparable, R-NaD dirige el comportamiento de aprendizaje de DeepNash hacia lo que se conoce como equilibrio de Nash (profundice en los detalles técnicos en nuestro periódico).

El comportamiento de juego que da como resultado un equilibrio de Nash no se puede explotar con el tiempo. Si una persona o máquina jugara Stratego perfectamente inexplotable, la peor tasa de victorias que podrían lograr sería del 50%, y sólo si se enfrentaran a un oponente igualmente perfecto.

En partidos contra los mejores robots de Stratego, incluidos varios ganadores del Campeonato Mundial de Computer Stratego, la tasa de victorias de DeepNash superó el 97% y frecuentemente fue del 100%. Contra los mejores jugadores humanos expertos en la plataforma de juegos Gravon, DeepNash logró una tasa de victorias del 84%, lo que le valió un ranking entre los tres primeros de todos los tiempos.

Esperar lo inesperado

Para lograr estos resultados, DeepNash demostró algunos comportamientos notables tanto durante su fase inicial de implementación de piezas como en la fase de juego. Para resultar difícil de explotar, DeepNash desarrolló una estrategia impredecible. Esto significa crear despliegues iniciales lo suficientemente variados como para evitar que su oponente detecte patrones a lo largo de una serie de juegos. Y durante la fase de juego, DeepNash realiza una selección aleatoria entre acciones aparentemente equivalentes para evitar tendencias explotables.

Los jugadores de Stratego se esfuerzan por ser impredecibles, por lo que es valioso mantener la información oculta. DeepNash demuestra cómo valora la información de maneras bastante sorprendentes. En el siguiente ejemplo, contra un jugador humano, DeepNash (azul) sacrificó, entre otras piezas, un 7 (Mayor) y un 8 (Coronel) al principio del juego y como resultado pudo localizar el 10 (Mariscal) del oponente. 9 (General), un 8 y dos 7.

En esta situación inicial del juego, DeepNash (azul) ya ha localizado muchas de las piezas más poderosas de su oponente, mientras mantiene en secreto sus propias piezas clave.

Estos esfuerzos dejaron a DeepNash en una desventaja material significativa; perdió un 7 y un 8 mientras que su oponente humano conservó todas sus piezas del puesto 7 y superiores. Sin embargo, al tener información sólida sobre los altos mandos de su oponente, DeepNash evaluó sus posibilidades de ganar en un 70% y ganó.

El arte del farol

Como en el póquer, un buen jugador de Stratego a veces debe representar fuerza, incluso cuando es débil. DeepNash aprendió una variedad de tácticas de farol. En el siguiente ejemplo, DeepNash usa un 2 (un Explorador débil, desconocido para su oponente) como si fuera una pieza de alto rango, persiguiendo el 8 conocido de su oponente. El oponente humano decide que lo más probable es que su perseguidor sea un 10, y así intenta para atraerlo a una emboscada de su espía. Esta táctica de DeepNash, arriesgando sólo una pieza menor, logra eliminar y eliminar al Spy de su oponente, una pieza crítica.

El jugador humano (rojo) está convencido de que la pieza desconocida que persigue su 8 debe ser el 10 de DeepNash (nota: DeepNash ya había perdido su único 9).

Obtenga más información viendo estos cuatro vídeos de partidas completas jugadas por DeepNash contra expertos humanos (anónimos): Juego 1, Juego 2, Juego 3, Juego 4.

“Me sorprendió el nivel de juego de DeepNash. Nunca había oído hablar de un jugador artificial de Stratego que se acercara al nivel necesario para ganar un partido contra un jugador humano experimentado. Pero después de jugar contra DeepNash, no me sorprendió el ranking entre los 3 primeros que logró más tarde en la plataforma Gravon. Supongo que le iría muy bien si se le permitiera participar en el Campeonato Mundial humano”.

– Vincent de Boer, coautor del artículo y ex campeón mundial de Stratego

Direcciones futuras

Si bien desarrollamos DeepNash para el mundo altamente definido de Stratego, nuestro novedoso método R-NaD se puede aplicar directamente a otros juegos de suma cero para dos jugadores con información perfecta o imperfecta. R-NaD tiene el potencial de generalizarse mucho más allá de las configuraciones de juegos de dos jugadores para abordar problemas del mundo real a gran escala, que a menudo se caracterizan por información imperfecta y espacios de estado astronómicos.

También esperamos que R-NaD pueda ayudar a desbloquear nuevas aplicaciones de IA en dominios que cuentan con una gran cantidad de participantes humanos o de IA con diferentes objetivos que podrían no tener información sobre las intenciones de otros o lo que ocurre en su entorno, como en los grandes Optimización a gran escala de la gestión del tráfico para reducir los tiempos de viaje de los conductores y las emisiones asociadas de los vehículos.

Al crear un sistema de IA generalizable y robusto frente a la incertidumbre, esperamos llevar las capacidades de resolución de problemas de la IA a nuestro mundo inherentemente impredecible.

Obtenga más información sobre DeepNash leyendo nuestro artículo en ciencia.

Para los investigadores interesados ​​en probar R-NaD o trabajar con nuestro método recientemente propuesto, hemos abierto el código fuente nuestro codigo.