Ya sea que esté jugando al póquer contra un solo oponente o se encuentre en una guerra de ofertas por la compra de una casa con otro posible comprador, está operando en condiciones de información imperfecta. Usted sabe qué cartas tiene en el juego de póquer y también sabe cuánto puede pagar por encima del precio de venta de la casa, pero no conoce la mano de su oponente en el juego de cartas ni qué tan alto está dispuesto a llegar el otro comprador de la casa.
Un artículo escrito en coautoría por investigadores del MIT y presentado en abril en la Conferencia Internacional sobre Representaciones del Aprendizaje en Río de Janeiro no le dirá qué hacer en estas situaciones específicamente. Pero sí ofrece nuevos conocimientos sobre los llamados juegos de información imperfecta que involucran a dos concursantes enfrentándose en una competencia de “suma cero”, donde la ganancia de un jugador significa la pérdida del otro.
Los investigadores del MIT en el proyecto incluyen a Sobhan Mohammadpour, estudiante de doctorado en el Departamento de Ingeniería Eléctrica y Ciencias de la Computación (EECS) y el Laboratorio de Sistemas de Información y Decisión (LIDS) del MIT; y Gabriele Farina, profesora asistente en EECS e investigadora principal de LIDS. Otros coautores incluyen a Max Rudolph de la Universidad de Texas en Austin (UT), Nathan Lichtlé de la Universidad de California en Berkeley (UCB), Alexandre Bayen de UCB, J. Zico Kolter de la Universidad Carnegie Mellon (CMU), Amy X. Zhang ’11, MNG ’12 de UT; Eugene Vinitsky de la Universidad de Nueva York; y Samuel Sokota de CMU.
El nuevo trabajo se centra en algoritmos que podrían usarse para entrenar redes neuronales para participar en juegos de información imperfecta. La suposición, sostenida durante mucho tiempo en el campo, era que los algoritmos basados en los principios de la teoría de juegos, en este contexto, claramente superarían a una variedad de algoritmos de propósito general llamados métodos de gradiente de políticas, que comenzaron a usarse para la toma de decisiones en la década de 1990. El término “política” en este contexto significa básicamente estrategia, mientras que “gradiente” se refiere a un camino que conduce en la dirección del mayor cambio: hasta la cima (o la base) de una colina, por ejemplo. Se están utilizando métodos de gradiente de políticas para entrenar redes neuronales para que tomen decisiones que avancen (en pasos pequeños y secuenciales) hacia un objetivo particular (como alcanzar una cumbre, metafóricamente hablando), con ajustes continuos y correcciones de rumbo realizadas a lo largo del camino para acercar al agente al destino previsto.
Aunque los juegos estratégicos no estaban en la agenda original cuando se concibieron los métodos de gradiente de políticas a principios de la década de 1990, los autores del nuevo artículo todavía se preguntaban cómo podría funcionar esta clase de algoritmos en juegos de dos jugadores. Según Farina, estos métodos se vuelven más complicados de analizar en entornos de múltiples agentes. “Todavía hay una dirección en la que puedes avanzar para mejorar tus circunstancias, pero, debido a las acciones del otro jugador, esa dirección puede cambiar constantemente a lo largo del juego. Y esos cambios pueden ser rápidos”.
“Se daba prácticamente por sentado que los algoritmos especializados de la teoría de juegos eran el enfoque correcto para este entorno”, dice Sokota. “Nuestro estudio demostró que los métodos de gradiente de políticas pueden funcionar mejor que estos algoritmos especializados, y que los algoritmos especializados pueden no funcionar tan bien como la gente pensaba, lo que plantea una interesante pregunta sociológica sobre por qué esto pasó desapercibido durante tanto tiempo. Parte de la respuesta es que el campo no había realizado el trabajo de ingeniería necesario para evaluar rigurosamente los algoritmos, por lo que era difícil decir qué funcionaba y qué no”.
En consecuencia, una contribución importante de este trabajo ha sido proporcionar una manera imparcial de evaluar diferentes algoritmos que pueden enseñar a los agentes (es decir, redes neuronales) cómo competir en juegos de información imperfecta. “Estamos adoptando un enfoque diferente”, señala Rudolph. “A diferencia de muchos de los artículos publicados en este campo, no proponemos un nuevo algoritmo que pueda superar a otros algoritmos. Proponemos un punto de referencia que puede evaluar estos algoritmos”.
En pocas palabras, un punto de referencia consiste en software diseñado para calificar el desempeño de los algoritmos. “Lo que ofrecemos es un campo de pruebas, o un campo de juego, donde las personas pueden tomar sus algoritmos, entrenarlos para una tarea específica y ver qué tan bien lo hacen”, dice Farina.
El grupo calcula el desempeño de un jugador en términos de un concepto llamado explotabilidad, que mide qué tan bien se desempeña un jugador contra el “peor adversario”, explica Sokota. “En un juego como el póquer, este oponente no sabría cuál es mi mano, pero sí sabría cómo me comportaría en cualquier mano determinada”. Alcanzar un cero en esta escala implica un juego perfecto, mientras que una puntuación alta de explotabilidad indica un juego que está lejos de ser óptimo.
Se jugaron cinco juegos en experimentos llevados a cabo por el equipo: dos versiones de Phantom Tic-Tac-Toe, en el que los jugadores no pueden ver lo que ha hecho su oponente, junto con dos variantes de información imperfecta de un juego de mesa llamado Hex, y otro juego de engaño llamado Liar’s Dice.
El mayor desafío que enfrentaron los investigadores fue lograr que la medida de explotabilidad funcionara en juegos de este tamaño, que pueden incluir hasta 30 mil millones de estados. Un “estado” en este caso no son sólo todas las posiciones posibles del tablero, sino que también abarca toda la historia del juego, incluidos cada paso y paso en falso a lo largo del camino.
“Es como mirar dentro de una habitación oscura llena de objetos que no puedes ver”, dice Mohammadpour. “De alguna manera, es necesario descubrir dónde están estos objetos y exactamente cómo llegaron allí”. Investigadores anteriores, añade Mohammadpour, normalmente han utilizado la explotabilidad para juegos que son 100.000 veces más pequeños que los analizados en su estudio.
En los experimentos realizados en estos cinco juegos, las redes neuronales entrenadas con algoritmos de gradiente de políticas obtuvieron mejores (más bajas) puntuaciones de explotabilidad que las redes entrenadas con algoritmos basados en la teoría de juegos. En las competiciones cara a cara, que tuvieron lugar en la siguiente ronda, las redes entrenadas en gradientes de políticas volvieron a vencer a sus oponentes entrenados en teoría de juegos. “Esos resultados fueron tranquilizadores”, afirma Rudolph, “porque nos dan más confianza en nuestro enfoque de evaluación comparativa”.
El equipo ha puesto su software de evaluación comparativa a disposición de los usuarios de forma gratuita y cómoda de usar. “No se necesita una supercomputadora”, dice Mohammadpour. “Puedes ejecutarlo en una computadora portátil común y corriente. Y todo lo que tienes que hacer es agregar una sola línea de código a una colección de software de evaluación comparativa de uso común llamado OpenSpiel”.
Aunque sus experimentos involucraron algunos juegos bastante oscuros, a Farina le gustaría poner este trabajo en un contexto más amplio. “Hay que tener en cuenta que el término ‘juego’ realmente se aplica a cualquier interacción estratégica entre múltiples agentes”, afirma. “Así que las lecciones que aprendemos de esta investigación no se limitan de ninguna manera a los juegos recreativos”.
Vinitski está de acuerdo. “La información oculta es una propiedad muy importante del mundo”, afirma. “Abarca una variedad de cosas, incluidas operaciones militares, escenarios comerciales y negociaciones, todas las cuales se llevan a cabo en condiciones de información oculta. La idea de que podemos mejorar estos juegos sugiere que también podemos hacerlo mejor en estos otros entornos”.
Ian Gemp, científico informático y experto en teoría de juegos de Google DeepMind que no participó en este estudio, considera que estos resultados son alentadores. “Este trabajo sirve como un recordatorio convincente”, dice, “de que modernizar las herramientas clásicas [like policy gradient methods] sigue siendo un camino altamente productivo para resolver problemas estratégicos complejos”.