Game Over

La revista Science publica este mes (aunque la noticia es de hace un par) un articulo sobre la resolucion matematica del juego de las Damas.

Los informáticos de la Universidad de Alberta llevan trabajando en el programa, llamado Chinook desde 1989, aunque entonces tenía un objetivo más modesto: conseguir ganar el campeonato del mundo de damas. La primera participación de Chinook en el campeonato fue en 1992, pero no logró ganarlo. Sin embargo, en 1994 ganó el campeonato (la primera vez que un programa ganó un “campeonato humano” en cualquier juego de inteligencia).

Con la ayuda de jugadores expertos, los informáticos programaron una serie de reglas heurísticas con las que el programa decidía qué movimiento realizar en cada posición. Durante años han utilizado múltiples computadoras (50 de media, 200 en los picos de trabajo) para calcular todas las posibilidades, estimar los movimientos más eficaces, perfeccionar las reglas y aumentar su número.

Finalmente, han conseguido el objetivo último: Chinook no puede perder. Ya ni siquiera le hacen falta reglas heurísticas: su base de datos contiene el mejor movimiento en cualquier posición. Por lo que si su oponente juega a la perfección, lo más que puede conseguir es acabar en tablas, empatarle, Chinook no puede, nunca jamás, perder una partida. Dicho de otra manera: las damas han sido “resueltas” como juego.

El mismo grupo de gente desarrollo posteriormente un programa que juega al poker, Polaris, y que se enfrentó a dos jugadores profesionales en Vancouver, Canadá, en el marco de la conferencia anual de la Asociación para el Avance de la Inteligencia Artificial.

Es claro que el desafio es mucho mayor dadas las caracteristicas del juego, entender como funciona un “bluff” o que capacidad de “imitación” tienen los humanos es lo complicado (de hecho ese es el secreto de un buen jugador) ya que, gran parte se basa en como hacerle creer a tu oponente que las cartas que el no puede ver son mejores que las que tenés en realidad o, en muchos casos, que son malas cartas y que siga apostando para lograr un “all in” y ganarle.

El concurso tuvo que ser adaptado para alojar la computadora. Para contrarrestar la suerte, un factor donimanate en el póker, los jugadores humanos fueron puestos en diferentes cuartos. La mano repartida fue exactamente la misma para los dos jugadores.

A diferencia de los programas de ajedrez, que requieren mucho uso de memoria para determinar cada movimiento posible, el software de póker de Polaris está precomputado en gran parte, estuvo funcionando por semanas antes del partido para construir una serie de agentes llamados "bots" que tienen diferentes personalidades o estilos de juego, pasando de un estilo agresivo al pasivo.

El equipo de la Universidad de Alberta modeló 10 diferentes bots antes de la competencia y utilizaron un simple programa en los dos primeros rounds. En el tercer round, los investigadores utilizaron un programa más sofisticado con un programa de "entrenamiento" monitoreando el rendimiento de los tres bots y luego moviéndolos hacia arriba y abajo de la línea como si fueren jugadores de fútbol.

Los resultados se pueden ver dia a dia aca: http://poker.cs.ualberta.ca/ y se ve claramente que si bien le dieron por ganado a los humanos el desafio, solo un dia lograron ganarle los dos a la maquina y hubo un empate tecnico en otro, es decir, estuvo bastante bien la maquinita.

Vayan dejando de jugar al poker online y en las maquinas de los casinos.

Y repasando esto de batallas contra las malditas maquinas, una mencion de honor a modo de homenaje a uno de los mas grandes, Garry Kasparov.

En 1989 le gano a Deep Tought (IBM) en 41 movimientos. En 1996 le gano (4-2) a Deep Blue, un monstruo de 32 procesadores masivamente paralelos del RS/6000 SP que pesaba tonelada y media y calculaba 100 millones de movimientos por segundo, contra los dos que puede calcular un cerebro humano. Al año siguiente, contra la version mejorada de Deep Blue (200 millones de movimientos por segundo) finalmente perdio 3 y medio a 2 y medio. Curiosamente, IBM desmantelo la maquina y no acepto jugar la gran final. Garry jugo dos partidos mas contra otro programa israeli (Deep Fritz) y empato ambos, en 2000 y 2003.

Gracias Garry, por ayudarme a seguir creyendo que somos nosotros los que gobernamos. Por suerte vuelve Terminator.