¿Cómo funciona la inteligencia artificial campeona de GO?

El juego de Go es milenario. Sus reglas son simples. Dos jugadores, se disputan el control de un tablero cuadriculado de 19x19. Para eso utilizan piedras blancas y negras que van colocando en las intersecciones de la cuadricula. Las piedras van delimitando áreas de control. Encerrar las piedras del rival las elimina del tablero. Al final del juego aquel jugador que controla más espacio es el ganador.

Basándose en reglas simples, el juego tiene un complejidad estratégica importante. Donde ubicar cada piedra para maximizar el control de áreas de tablero (ubicándolas esparcidas) y al mismo tiempo cómo protegerlas del encierro (ubicándolas conectadas) requiere una planificación rigurosa y estudiada.

Existen 361 intersecciones en un tablero en las que se puede colocar la primera piedra. El contrincante tiene 360 opciones restantes. Una partida de Go dura en promedio 200 movimientos. En conclusión, la variedad de juegos diferentes es astronómica. No es extraño entonces que habiendose terminado la supremacía del ser humano en el ajedrez (DeepBlue en 1997), el próximo hito fuese este complejo juego. Pasaron cerca de 20 años y Google lo logró. AlphaGo - inteligencia artificial construida para jugar al Go - derrotó a Lee Sedol jugador profesional y top 5 actual de los mejores jugadores del mundo. Cómo hizo? Qué tan inteligente es?

El enfrentamiento realizado entre el 8 y 15 de Mayo del 2016 terminó en un triunfo de la inteligencia artificial de Google DeepMind 4 a 1. Lee Sedol se mostraba antes del enfrentamiento confiado en tener un resultado ampliamente diferente. En varias entrevistas preveía un resultado diametrálmente opuesto. Ningún programa de computación había logrado ganarle a un jugador profesional. Algunos auguraban que no sería posible por al menos en una década más. El poder computacional y los algoritmos de AlphaGo demostraron ser suficiente. Qué lo hace diferente a los programas anteriores?

Ciertamente algo que debe ponderarse es el poder de procesamiento de AlphaGo. El programa de google contaba como plataforma el Cloud computing de Google con su gran cantidad de servidores. Según informan sus creadores para la competencia contaron con 1920 procesadores standard y 280 procesadores gráficos (los cuales hoy día se utilizan para realizar también operaciones matemáticas). Este poder de cálculo le da las herramientas para analizar con más profundidad una situación de juego dada. Pero aun con toda esa disponibilidad no le resulta suficiente sin los mecanismos algorítmicos adecuados.

A simple vista lo que parece un juego sencillo no lo es. Se estiman que existen 10¹⁷⁰ combinaciones posibles de juegos de Go. Si se toman un promedio de 250 opciones de acción en cada movida del juego y se tiene en cuenta la cantidad promedio de jugadas por partido es evidente que un programa que intente resolver por fuerza bruta no es adecuado. Por fuerza bruta se entiende intentar analizar todas las acciones posibles y sus consecuencias armando un árbol completo desde la situación inicial hasta la finalizacion de todos los posibles fines de partido.

El uso de un algoritmo como minimax con una cantidad acotada de niveles de profundidad es una opción. El mismo se utilizo en Deep Blue el programa de ajedrez que venció por primera vez al numero 1 de ajedrez. El problema de esta aproximación es que al ser juegos más largos que el ajedrez y con muchas más ramificaciones la elección de una próxima jugadas muchas veces termina siendo inadecuada. Una posición que parece ser ventajosa en un momento puede conducir a un resultado negativo varias jugadas después. Los constructores de AlphaGo decidieron seleccionar otra aproximación: El árbol de búsqueda Monte Carlo.

Pasos del algoritmo de búsqueda Monte Carlo

La idea atrás de árbol de búsqueda Monte Carlo es realizar la mayor cantidad posible de simulaciones, en este caso, de juegos completos de Go y mantener registrador por cada estado pasado cuantas veces llevaron a la victoria y cuantas a la derrota. Se puede separar el método en 4 pasos. El primer paso es recorrer el árbol existente con los conocimientos previos hasta llegar a un nodo hoja (selección). El segundo paso es expander en varios subnodos hijos (Expansión). El tercer paso es tomar uno de esos nodos hijos y realizar una simulación seleccionando acciones al azar hasta finalizar el juego y ver si termina en victoria o derrota. El último paso es llevar el resultado a las estadísticas de los nodos del árbol por lo que paso. De esa forma realizando muchas pasadas se podrá observar aquellos nodos que nos llevaron a más victorias. En el límite, con la similación muy grande de casos el resultado obtenido converge a la solución óptima. Obviamene volvemos al problema inicial, no es posible acercarnos con el poder computacional actual a esa cantidad de simulaciones.

La clave, entonces es lograr intentar restringir la selección de aquellos caminos que se descubren más promisorios a medida que más circuitos del algoritmo se van realizando. Aunque se debe dejar lugar a la exploración de nuevos caminos dando lugar al descubrimiento de mejores soluciones. Además una forma de refinar la efectividad del método es no dejando totalmente al azar la fase de simulación, sino seleccionar las que parezcan más promisorias. En algunos programas se utilizaron heurísticas basadas en reglas obtenidas mediante el análisis del juego de expertos. En el caso de AlphaGo la solución fue diferente y muy interesante.

Los jugadores de Go suelen dar nombres a diferentes formaciones típicas que se arman durante una partida. Algunas formas son consideradas beneficiosas y otras no. Esta idea llevó a pensar a algunos desarrolladores que el análisis de los patrones de juego eran indispensables para una inteligencia artificial que juegue bien al Go. La capacidad de "ver" el tablero y determinar si una configuración de piedras es promisoria o no cobra vital importancia. Algunos esfuerzos de programar teniendo en cuenta esto se toparon con problemas de escala. Se tendían a encontrar configuraciones pequeñas que no tenían en cuenta todo el tablero (un ejemplo el paper de 2007 "Reinforcement Learning of Local Shape in the Game of Go").

AlphaGo utiliza una técnica para la detección de patrones dentro de todo el tablero que se está utilizando con éxito para encontrar estructuras dentro de imágenes. Conocidas como redes neuronales convolucionales, son estructuras que imitan a las neuronas en la corteza visual primaria de un cerebro biológico. Estas redes se pueden entrenar utilizando un volumen de datos de entrenamiento indicando para cada configuración particular cual es la salida esperada. El programa de Google utiliza 3 redes, una llamada red de valores y la otras dos redes de políticas. La primera toma como entrada el estado general del tablero (qué posiciones están ocupadas y por qué jugador) y retorna una evaluación general de que porcentaje de probabilidad tiene de ganar cada jugador. La segunda también recibe como parámetro el estado tablero y retorna como resultado el detalle de cada posible posición a seleccionar con la probabilidad de que un buen jugador de Go en esa misma situación la elija. Las dos versiones diferentes de las redes de políticas se diferencian en que la segunda es una reducción de la primera que se utiliza para las simulaciones de Monte Carlo (en este caso se requería más velocidad en la respuesta).

AlphaGo para cada jugada comienza utilizando la red de política para determinar que acciones son las mas beneficiosa. Luego por cada una de ellas determina mediante la red de valor que probabilidad de ganar obtendría con seleccionar esa posición. Para reforzar ese valor realiza la búsqueda de Monte Carlo. La red de política reducida la utiliza dentro del árbol de busqueda para seleccionar aquellas movidas a analizar en el paso de selección.

En su paper Mastering the Game of Go with Deep Neural Networks and Tree Search los autores detras de AlphaGo explican con más detalles todos los procesos. Cabe destacar que el entrenamiento de la red neuronal lo realizaron mediante un procedimiento que tomó como entrada 30 millones de posiciones jugadas por expertos. Luego mediante sucesivos juegos simulados entre las computadora y versiones modificadas de si misma generaron más set de entrenamiento con los que refinaron algunos procesos del programa. Con eso lograron predecir la próxima jugada que realizaría un experto un 57% de las veces (la marca anterior era un 44%).

Estos últimos detalles no son menores. Para que todo esto funcione hacen falta grandes volúmenes de información disponible. Además contar con ambientes controlados para ejecutar gran cantidad de simulaciones con el objetivo de entrenar a la inteligencia artificial. No obstante eso no siempre es posible. Veremos qué pasa cuando estas dos premisas faltan: El auto autónomo y el chatbot de mente "juvenil"

Algunas artículos con mayor detalle:

• Google Deepmind's AlphaGo: How it works
  
• How AlphaGo Works
• Win or lose, a computer program’s contest against a professional Go player is another milestone in AI