El éxito de AlphaGo en 2016 y sus sucesores, que vimos en un artículo anterior, puso de manifiesto que era posible crear programas que acabaran aprendiendo a jugar mejor que cualquier ser humano, partiendo sólo de las reglas básicas de juego, a base de jugar consigo mismo, para cualquier tipo de juego de dos jugadores con información perfecta. Es decir, aquellos en los que el objetivo del adversario es ganarte y su estrategia es clara, las reglas son iguales para ambos y conocidas y se dispone de la misma información que el adversario y éste quiere “comerte” piezas y mejorar su posición sobre el tablero.

¿Cuál sería pues la nueva frontera de la Inteligencia Artificial (IA) en 2017? Esta frontera era el Póker. Este juego es un reto mucho más difícil ya que requiere que el Sistema de IA tome decisiones extremadamente complicadas basada en información incompleta mientras tiene que lidiar con los faroles, el juego lento y otras estratagemas.

En enero de 2017, el sistema de IA Libratus de la Universidad Carnegie Mellon, fue capaz de ganar al póker, modalidad Head’s up, Texas Hold’em sin límite, a un grupo de cuatro profesionales. En total entre todos ellos, jugaron un total de 120.000 manos, jugados en el casino Rivers en Pittsburgh, durante 20 días. La modalidad Head’s Up (dos jugadores) sin límite Hold’em es extremadamente compleja con más de 10160 conjuntos de información distintos. Cada conjunto está caracterizado por el curso del juego en la manera en que es percibido por el jugador que tiene el turno de juego. Como en el caso del Go, el número de posibilidades muchísimo más grande que el número de átomos del universo.

Recreación del sistema Libratus jugado a Texas Hold’em

En Texas Hold’em sin límite a cada jugador se le reparten dos cartas que no pueden ver hasta el final de la mano. Tras una ronda de apuestas a ciegas, denominada” “Pre-Flop”, los jugadores que no se hayan retirado verán las tres primeras cartas comunitarias o “Flop”, seguido de una ronda de apuestas. Vuelve a sacarse otra carta descubierta comunitaria (el turn) y comienza una nueva ronda de apuestas. Finalmente se saca una última carta comunitaria descubierta (el river), y hay una ronda final de apuestas.  Finalmente, si fuera necesario se muestran las cartas para dirimir al ganador entre los jugadores que todavía estén en la mano. Se pueden hacer combinaciones para la mano con las 5 cartas comunitarias y las 2 de cada jugador para establecer el ganador.

A diferencia de otros juegos, Libratus ganó y lo hizo de forma clara, pero no consiguió capacidades sobrehumanas como había sucedido en el ajedrez, el Go o en Jeopardy!. Aun así, destrozó los mejores registros de los jugadores profesionales, con 14,7 apuestas grandes a ciegas (big blinds) ganadas cada 100 manos, con una significación estadística del 99,98%, esto es, que la probabilidad de que los humanos jugaran mejor que Libratus habiendo perdido una tasa de apuesta grandes a ciegas como la anterior, está entre el 0,0001% en el caso del límite inferior de la desviación estándar y 0,54%, en el caso del límite superior. Es decir, que simple y llanamente, Libratus es un mejor jugador de póker que sus oponentes humanos.

Pero, ¿qué tiene realmente el póker que lo hace tan difícil para una IA?

Pues, en primer lugar, no hay un único movimiento óptimo y además un sistema de IA que juegue al póker tiene que aleatorizar sus acciones para que sus oponentes no estén seguros de cuando va de farol. Si siempre vas de farol no eres un buen jugador, y sin nunca vas de farol tampoco.

Si un movimiento es bueno o no, depende de cosas que no se pueden observar, por lo tanto, hay una incertidumbre asociada en la toma de decisiones que hace que ésta sea más complicada que en el caso del Go, a pesar de tener un nivel de complejidad similar en cuanto al número (casi infinito) de posiciones a considerar.

Lo extraordinario de Libratus es que no tiene una estrategia definida, sino que el algoritmo calcula la estrategia usando un superordenador del centro de supercomputación de Pittsburgh, llamado Bridges para calcular lo que piensa que es una buena estrategia. Bridges tiene 274 terabytes of RAM, es unas 30.000 veces más rápido que un ordenador de sobremesa y cuesta 9,65 millones de dólares.

Como vamos a ver un poco más adelante en este artículo, Libratus ejecuta muy bien la estrategia calculada y aún es mejor a la hora de mejorar una estrategia sobre la marcha, según pueda ir variando la estrategia del adversario.

Una de las claves de su éxito viene de su uso de la teoría de juegos, cuya aplicación se pensaba hasta hace poco que no estaba al alcance de un sistema de IA. Libratus sustituye la intuición humana, intentando encontrar la estrategia perfecta para jugar al póker, aquella que en el largo plazo le permitirá ganar a todos sus adversarios. A esta estrategia se la conoce como el equilibrio de Nash y fue probada por John Nash lo que le valió el premio Nobel de Economía en 1994. Para el lector interesado en profundizar en este punto John Nash fue inmortalizado cinematográficamente por Russell Crowe en 2001, en la película A Beautiful Mind (“Una mente maravillosa”).

La estrategia que alcanza el equilibrio de Nash es aquella situación en la cual todos los jugadores han puesto en práctica una estrategia que maximiza sus ganancias dadas las estrategias de los otros. Consecuentemente, ningún jugador tiene ningún incentivo para modificar individualmente su estrategia, por eso se llama equilibrio. En palabras sencillas, implica seguir una mezcla de agallas, “lectura” de los oponentes e intuición, el perfecto jugador de póker. Libratus ha encontrado un método más rápido para encontrar el equilibrio de Nash que la simple “fuerza bruta” de probar todas las posibilidades. Si evaluáramos una situación de juego por segundo, nos llevaría más de 10 billones de años recorrerlas todas.

Aunque se puede demostrar que para un juego como el póker existe siempre una estrategia que conduzca al equilibrio de Nash, no existe ninguna garantía que esta estrategia sea única (puede haber más de una) o que ésta sea fácil de encontrar. Para los juegos de suma cero como el póker (esto es, si uno gana los demás pierden) se puede resolver en un tiempo finito (conocido como polimonial), pero el gigantesco número de posibles combinaciones obliga a buscar en el espacio de posibles soluciones de forma muy inteligente, para hacerlo en un tiempo razonable. Para lograrlo, Libratus divide el problema del póker en tres módulos:

  1. El que crea y resuelve por adelantado una abstracción del juego: para ello abstrae el estado del juego agrupando las apuestas (por ejemplo, apuestas con diferencias de menos de 10$) y otras acciones parecidas referidas a combinaciones de cartas (por ejemplo, “As y 5” frente a “As y 6”) en lo que denomina un “plan de acción“ (blueprint).

Este plan de acción le permite reducir muchos órdenes de magnitud en número de estados del juego. A partir de ahí aplica una serie de algoritmos de “complejidad lineal” (es decir, computables en un tiempo razonable) para resolver el equilibrio de Nash, lo que le permite obtener como resultado un “subjuego” aproximado, es decir, la parte restante del juego (descontando las manos ya jugadas y las apuestas realizadas) sin tener que enumerar todas las posibles combinaciones (lo que se conoce como las hojas del árbol del juego).

  1. El que le permite solucionar el subjuego restante de forma “segura” y recurrente: esto es más difícil de lo que parece porque en un juego de información imperfecta los posibles subárboles a examinar no son independientes entre sí, por lo que no se puede resolver el subárbol aisladamente.

Es necesario un método “seguro” que permita que el oponente pueda modificar su estrategia sobre la marcha (no asumir que ésta va a ser fija) y que asegure que para cualquier posible situación que la nueva estrategia no sea peor que la estrategia actual. Libratus usa un nuevo método para hacer esto, que es tan bueno que mereció el premio al mejor paper académico de 2017 en el campo de la IA. Y es recurrente porque con cada fase de la mano se poda el subárbol y se vuelve a calcular sobre el nuevo árbol (más pequeño).

  1. El último módulo que implementa Libratus es la característica de automejora: mientras sus adversarios humanos descansan, Libratus busca las acciones más frecuentes que se han quedado fuera del plan de acción y calcula sus soluciones completas. De esta manera, conforme va jugando manos, se hace cada vez más difícil engañar a Libratus porque sólo ha resuelto una versión aproximada del juego.

Por todo esto que he expuesto, no es de extrañar que la modalidad de Head’s up, Texas Hold’em con límite en las apuestas,se considera solucionado desde 2015, ya es un problema mucho más pequeño y sólo tiene 1013 puntos de decisión. Exactamente igual que sucede con los finales de partida en el ajedrez. Están resueltos todos los finales de partida de 5 piezas y casi todos los de 6 piezas, porque su complejidad computacional es mucho menor. Por ello, en esta parte los sistemas de IA son “implacables” y mejores que cualquier gran maestro humano.

Por el contrario, en el caso del póker, modalidades con varios jugadores, o más complejas como la modalidad Omaha, todavía continúan siendo un reto. Aunque dado el incremento exponencial de la velocidad de los ordenadores y la mejora constante de los algoritmos de búsqueda, esto puede significar sólo unos pocos años más.

Pero el impacto real de todo esto es que no hace falta que superen a los mejores jugadores o que el juego esté resuelto de una forma teórica, sino que sean mejores que el jugador promedio y, de hecho, ya lo son. De la misma manera, en el ajedrez, la primera vez que un ordenador alcanzó el nivel ELO de maestro fue en 1981, 16 años antes de que derrotara al campeón del mundo Gary Kasparov y que ya examinamos en otro artículo.  Mucho antes ya ganaban a casi todo el mundo. En el póker estamos en un punto medio entre esos dos hitos del ajedrez.

La otra variable a tener en cuenta es cuándo la mejora de la velocidad computacional, los algoritmos y la reducción de los costes de los circuitos integrados, permitirán tener versiones más simples (pero aún muy potentes) en nuestros teléfonos móviles u otros dispositivos al alcance de cualquiera. Y todo indica, como demuestra Ray Kurzweil, que esto sucederá mucho antes de lo que pensamos.

La importancia de este sistema es que se presta muy bien a ser usado en aplicaciones del mundo real con información incompleta y errónea, como en el ámbito de los negocios, estrategia militar, ciberseguridad, medicina, el guiado automático de taxis autónomos y la planificación de acciones en robots. Y cuando estas aplicaciones bajen al terreno del consumo diario, pueden suponer,  que el los procesos de negociación de salarios o en el establecimiento de los precios de las cosas, no estén sólo seres humanos encima de la mesa.

Una vez más es de esperar que vayamos viendo poco a poco en forma de aplicaciones reales en estos y otros campos, las consecuencias de que un sistema de IA haya aprendido a “desplumarnos”.

¡Feliz año 2020 para todos!

 

Posted by santiago

Deja un comentario