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.