viernes, 9 de enero de 2015

Un algoritmo informático se convierte en el mejor jugador de póquer del mundo

http://www.madrimasd.org/informacionidi/noticias/noticia.asp?id=62555&origen=notiweb&dia_suplemento=viernes


Un algoritmo informático se convierte en el mejor jugador de póquer del mundo

Pero, por complejos que sean, en estos juegos todo se resume a conocer las reglas y poder de computación (mental o artificial) para simular todas las posibles estrategias. Con el póquer la cosa se complica. Interviene el azar, y los jugadores no tienen toda la información, ya que el rival esconde sus cartas. Sin embargo, incluso en esa situación de incertidumbre, un nuevo algoritmo ha sido capaz de resolver el juego hasta el punto de que ningún jugador humano o máquina podrá ganarle la partida, según una investigación que se publica en la revista Science.

Desde mediados del siglo pasado, con pioneros de la computación moderna como Alan Turing, la inteligencia artificial (IA) siempre ha usado juegos para probar sus teorías. Como dice el profesor del departamento de informática de laUniversidad de Alberta (Canadá), Mike Johanson, "para los investigadores de la inteligencia artificial, con cualquier juego, hay dos grandes hitos: la primera vez que un programa informático derrota a un campeón humano y la primera vez que un programa resuelve el juego creando una estrategia matemáticamente perfecta e imbatible, de modo que nunca más pierda con cualquier oponente, humano o máquina, aunque este lo sepa todo del programa".

Eso es lo que ha conseguido CFR+, un algoritmo desarrollado por un equipo de investigadores de la universidad canadiense entre los que está Johanson. Un algoritmo matemático es un conjunto de reglas a seguir durante pasos sucesivos. En la Wikipedia hay un ejemplo gráfico muy sencillo y que también se puede encontrar al final de cualquier manual de instrucciones: Punto de partida, la lámpara no funciona. Paso 1, ¿está enchufada? Si no lo está, enchufar. Si lo está, paso 2, ¿está fundido el foco? Si lo está, reemplazarlo y, si no lo está, paso 3, comprar una nueva lámpara. El problema con el póquer es que las posibles situaciones son casi astronómicas: 319 billones de posibilidades.

Al menos, esos son los conjuntos de información posibles en la versión del póquer descubierto con dos jugadores llamada Texas hold 'em, la más popular y la que se juega en los campeonatos mundiales de este juego de cartas. Aquí, el juego se inicia con el reparto de dos cartas boca abajo para cada jugador. Apuestan, y el que da las cartas saca tres boca arriba con las que tienen que jugar ambos. Si los dos vuelven a apostar se saca una cuarta y hasta una quinta carta. Solo al final del juego, si los dos han apostado, se descubren sus dos cartas. Esta modalidad del póker, que se puede jugar con o sin límite en la apuesta, es mucho más complicada para una máquina que otros tipos de juegos. En el caso de las damas o Connect-4 (versión del tres en raya ampliado a cuatro), se trata de juegos con información completa donde no hay margen para el azar y los jugadores pueden ver todas las piezas y saben todas las reglas.

"El póquer es todo lo contrario. Incluye el azar aleatorio de las cartas que te tocan y también cuenta con una información imperfecta, ya que no podemos ver las cartas que tiene el rival", recuerda Johanson. Su algoritmo puede contra el azar, la falta de información y hasta el faroleo. "Ahora es imposible para cualquier rival humano o informático derrotarle, aunque el oponente lo sepa todo del programa, su código fuente, la estrategia que usará, todo salvo las dos cartas que esconde", añade.

En realidad, el algoritmo no es aún perfecto, puede que el humano le gane alguna mano. "Sin embargo, aún usando la contra estrategia perfecta para vencerle, si alguien se pasara toda su vida jugando al póquer contra nuestro programa, jugando 200 partidas a la hora, 12 horas al día, los siete días de la semana durante 70 años, unos 660 millones de partidas, no tendría la certeza estadística de que le va a gana", sostiene el investigador canadiense. Y retan a cualquiera, ya sea humano o máquina a intentarlo. Han habilitado una página donde se puede jugar al póquer con CFR+.

Este mismo equipo de investigadores es el responsable de Polaris, el primer programa informático que ganó a un profesional del póquer en los campeonatos mundiales de 2008. Pero entonces era imperfecto, el humano ganó algunas partidas. Es decir, podía ganar la mayoría de las veces pero no había resuelto el juego encontrando siempre la mejor estrategia para ganar. Es más, el algoritmo en que se apoyaba, una versión previa de CFR, habría necesitado disponer de 523 terabytes (TB) de memoria y unos 10.000 años de procesamiento medido en tiempo de uso de un procesador para resolver matemáticamente todas las jugadas del Texas hold 'em. Con CFR+, han conseguido un algoritmo manejable que reduce el juego en subpartidas y que solo necesita 32 gigabytes (GB) de memoria RAM, 11 TB de espacio y apenas 900 años de tiempo de procesamiento. Con 200 nodos de 24 procesadores cada uno, en apenas dos meses, tiene la estrategia imbatible.

Por fortuna, el algoritmo aún tiene sus limitaciones. Está diseñado para el póquer donde hay límite en las apuestas. Además, CFR+ puede vencer a los humanos, pero uno a uno. En el póquer a varias bandas, ya no sería invencible, por ahora.

Autor:   Miguel Ángel Criado
Publicar un comentario en la entrada