Un algoritmo aprende a jugar al Stratego como un humano experto

La empresa brit¨¢nica DeepMind, propiedad de Google desde 2014, ha conseguido desarrollar un algoritmo capaz de jugar como un humano experto a Stratego, un popular juego de mesa. Seg¨²n detalla un equipo de investigadores de la compa?¨ªa en un art¨ªculo que se publica hoy en la revista Science, DeepNash (as¨ª se ha bautizado a la herramienta) se ha colocado entre los tres mejores jugadores del portal Gravon especializado en partidas online de este juego. Se trata de un hito debido a la alta complejidad del juego, que combina elementos de estrategia, de intuici¨®n (los jugadores no tienen toda la informaci¨®n necesaria para trazar planes perfectos) e incluso de farol. Los autores del estudio creen que el algoritmo podr¨ªa tener aplicaciones en ¨¢mbitos como la optimizaci¨®n autom¨¢tica de tr¨¢fico.

Comercializado por Jumbo desde los a?os sesenta del siglo pasado, aunque inventado antes de la Primera Guerra Mundial, Stratego era uno de los pocos juegos de mesa ic¨®nicos que todav¨ªa no dominaba la inteligencia artificial. Este juego de estrategia se caracteriza por un reto doble: requiere de pensamiento estrat¨¦gico a largo plazo, como el ajedrez, pero tambi¨¦n se necesita gestionar informaci¨®n imperfecta, como en el p¨®quer, porque las fichas del contrincante empiezan cubiertas y se van revelando seg¨²n avanza la partida. Esta singularidad lo convierte en un juego m¨¢s complejo que Go, el milenario juego asi¨¢tico cuyo tablero permite que las fichas se dispongan en m¨¢s combinaciones distintas que ¨¢tomos hay en el universo. Tambi¨¦n hace que para ganar se requiera m¨¢s astucia que en el p¨®quer, donde tampoco se conocen las cartas del contrincante y se necesita tanto intuici¨®n como conocimientos matem¨¢ticos.

Los simuladores de juegos han funcionado hist¨®ricamente como un buen term¨®metro para medir la efectividad de los programas inform¨¢ticos. Ofrecen un entorno controlado con reglas precisas en los que las herramientas pueden desarrollar sus capacidades y donde es sencillo medir su ¨¦xito: basta con ver si ganan o no la partida. Es un banco de pruebas perfecto para estudiar c¨®mo los humanos y las m¨¢quinas desarrollan y ejecutan estrategias ganadoras. De ah¨ª que DeepMind se haya fijado en Stratego, un reto may¨²sculo para la m¨¢quina dada la falta de informaci¨®n que debe de gestionar durante la partida.

DeepMind tiene un gran historial en este campo, habiendo desarrollado herramientas punteras para superar al hombre en juegos complejos de estrategia a largo plazo con informaci¨®n perfecta, como Go (con AphaGo), pero tambi¨¦n en videojuegos de informaci¨®n imperfecta, como StarCraft (con AlphaStar). Nadie hab¨ªa conseguido hasta ahora desarrollar una herramienta capaz de jugar a Stratego al mismo nivel que un humano experto. No es por casualidad: el juego cuenta con 10??? posibles disposiciones, lo que supera tanto al p¨®quer Texas Hold¡¯em, un juego de informaci¨®n imperfecta (cada uno conoce solo las cartas de su mano y las que se van jugando) muy estudiado, con 10??? estados, como a Go, el milenario juego asi¨¢tico, que tiene 10??? opciones.

Por otra parte, cualquier movimiento que se haga en el primer turno implica pensar 10?? posibles parejas de configuraciones de fichas. En el p¨®quer son 10?. Los juegos de informaci¨®n perfecta no tienen ese problema, porque las fichas est¨¢n a la vista.

Estas dos complejidades particulares hacen que no se pueda aprovechar investigaciones previas para abordar un simulador de juego para Stratego. Por eso, el equipo de DeepMind ha desarrollado un algoritmo de aprendizaje reforzado que aplica modelos te¨®ricos basados en el equilibrio de Nash, un teorema del famoso matem¨¢tico estadounidense especialista en la teor¨ªa de juegos. La herramienta no trata de predecir los posibles movimientos del contrincante, que es la aproximaci¨®n habitual en los simuladores de juegos, porque el ¨¢rbol de posibilidades de la partida reci¨¦n iniciada es casi inabarcable, sino que establece su propia estrategia y luego la va adaptando sobre la marcha.

¡°Nuestro art¨ªculo muestra c¨®mo DeepNash puede ser aplicado en situaciones de incertidumbre y equilibrar exitosamente sus acciones para ayudar a resolver problemas complejos¡±, explica Julien Perolat, autor principal del estudio. El cient¨ªfico y sus colegas creen que R-NaD, el algoritmo detr¨¢s de DeepNash, puede ser de utilidad para desarrollar nuevas aplicaciones de inteligencia artificial que impliquen la interacci¨®n con muchos seres humanos con distintos objetivos, lo que comporta que el sistema tenga falta de informaci¨®n sobre lo que va a ocurrir.

La optimizaci¨®n a gran escala de la gesti¨®n del tr¨¢fico para reducir los tiempos de los viajes y las emisiones de gases asociadas se antoja como una buena aplicaci¨®n, escriben Perolat y sus compa?eros en Science.

C¨®mo se juega a Stratego

Stratego vive una segunda juventud gracias a internet. El popular juego de mesa se ha pasado ahora a foros como Gravon, donde jugadores de todo el mundo se miden entre s¨ª en tensas partidas online.

En Stratego se enfrentan dos jugadores por turnos, que disponen en su lado del tablero 40 fichas con distintos atributos. El objetivo es capturar la bandera del contrincante o dejar sin fichas m¨®viles al contrario. Para ello, los jugadores avanzan por turnos con sus fichas m¨®viles, que pueden ser de diez tipos, correspondi¨¦ndose con los rangos militares y con especialistas como minadores, exploradores o esp¨ªas. Cada vez que una ficha entra en contacto con otra del contrincante, ambas se exponen. La que resulte vencedora, por ser de mayor rango o por sus habilidades especiales, se queda en el tablero; la perdedora se retira del juego.

El algoritmo de DeepNash es capaz de desarrollar estrategias impredecibles y de ejecutar movimientos equivalentes de forma aparentemente aleatoria. Todo ello encaminado a confundir al contrincante y que este no pueda sacar conclusiones sobre el estilo de juego de la m¨¢quina. En una de las partidas rese?adas en el art¨ªculo, por ejemplo, sacrific¨® dos piezas importantes para localizar las de mayor rango del oponente. Eso le dej¨® en desventaja material, pero el algoritmo entendi¨® que tener informaci¨®n sobre la localizaci¨®n de las mejores piezas del contrincante le daba unas probabilidades de ¨¦xito del 70%. Al final gan¨® esa partida. En otra ocasi¨®n, jug¨® un farol, persiguiendo con una pieza de muy bajo rango a otra de alto, lo que llev¨® a que el adversario se convenciera de que jugaba con el 10 (mariscal) y sacara al esp¨ªa (S), una ficha estrat¨¦gica que perdi¨® frente a un explorador (2).

¡°El nivel de juego de DeepNash me sorprendi¨®. Nunca hab¨ªa visto que una m¨¢quina fuera capa de jugar a Stratego como un humano experimentado. Tras jugar yo mismo contra DeepNash, no me extra?¨® que m¨¢s tarde llegara a colocarse en el top-3 del ranking de Gravon. Creo que lo har¨ªa muy bien si le dejasen participar en el Campeonato Mundial¡±, dice Vincent de Boer, coautor del art¨ªculo de Science y antiguo campe¨®n del mundo de Stratego.

Puedes seguir a EL PA?S TECNOLOG?A en Facebook y Twitter o apuntarte aqu¨ª para recibir nuestra newsletter semanal.