Un paso más de la inteligencia artificial en los videojuegos: AlphaGo (I)

2 junio, 2016

Cada vez más la inteligencia artificial se está abriendo paso en el mundo de los videojuegos, convertíendose en un elemento clave en el diseño de cualquier videojuego. La evolución de los algoritmos de aprendizaje, tales como las redes neuronales convolucionales, están permitiendo que se mejoren algoritmos clásicos como el reinforcement learning, que se basan en premiar las acciones que han dado un buen resultado, de forma que el jugador controlado por el ordenador se vaya aprendiendo automáticamente qué acciones le son más beneficiosas en el momento de tomar alguna decisión.

La integración de las redes neuronales convolucionales con los algoritmos de reinforcement learning ha dado lugar a las técnicas que hoy en día se conocen como deep reinforcement learning. Prueba de la revolución que están suponiendo es la existencia de un equipo de Google llamado Google DeepMind, que tiene como objetivo construir algoritmos que son capaces de aprender por ellos mismos a partir de los datos originales. Una prueba de su éxito ha sido el desarrollo de AlphaGo, el primer programa informático que consigue derrotar un jugador de Go profesional. Lo hizo en Octubre de 2015 derrotando por 5-0 al campeón europeo Fan Hui y, más recientemente, en Marzo de 2016 derrotando por 4-1 a Lee Sedol, quien es considerado el mejor jugador del mundo. Y quizás os preguntaréis: ¿Qué tiene de especial el juego Go respecto otros juegos clásicos como el ajedrez en el que ya se había conseguido que un programa informático derrotara un jugador profesional?

human_vs_alphago
Dibujo obtenido de [3] por Cai Meng. Usado bajo condiciones de fair use.

 

Pues bien, hay dos elementos diferenciales que hacen de Go un juego mucho más complejo que el ajedrez. En esta entrada nos centraremos en el primer de ellos, el factor de ramificación o branching factor. Este factor representa el número posible de acciones que un jugador puede llevar a cabo en una situación de juego. Por ejemplo, en el juego 3 en raya, en el primer turno se tiene un branching factor 9 ya que hay 9 casillas en las que el jugador puede colocar su pieza, en la segundo turno el branching factor es de 8, y así sucesivamente. En un juego tan simple como el 3 de raya es fácil imaginar un ordenador desarrollar un árbol en el que simula todas las situaciones posibles de juego antes de decidir cuál será su próximo movimiento. Y digo que es fácil imaginar no únicamente porque el branching factor va disminuyendo sino también porque la profundidad del árbol está limitada por los 9 turnos máximos del juego. En cada turno, el ordenador decidirá realizar un movimiento que le permita llegar a un estado final (partida terminada) en el que obtenga un resultado óptimo (ganar si es posible, empatar si no hay opción de ganar, o perder si ninguna opción le permite ni siquiera empatar). Es lo que se conoce como algoritmo minimax.

En el caso del ajedrez, la cosa se complica un poco más. Aquí, el branching factor va a depender de la situación de la partida en la que nos encontremos, pero está calculado que el valor promedio del branching factor es 35. Esto significa que, en promedio, cada jugador puede realizar 35 movimientos distintos en cada turno. Esto conlleva que desarrollar un árbol para decidir que la siguiente jugada ya no es tan sencillo, ya que cada posible movimiento da lugar a 35 posibles movimientos y así sucesivamente, creciendo el número de nodos del árbol a examinar de forma exponencial. Además, la profundidad del árbol también es mayor que en caso del 3 en raya, siendo 40 el número promedio de turnos en una partida de ajedrez. Desarrollar todo el árbol tanto en amplitud (35 posibles movimientos en promedio) como en profundidad (40 jugadas en promedio) es bastante prohibitivo, motivo por ello se suelen usar funciones heurísticas para no tener que desarrollar todo el árbol en profundidad sinó solamente hasta un cierto nivel de profundidad. Pero, si no se llega a un estado final (un nodo terminal del árbol que representa una partida acabada), ¿cómo se evalúa ese nodo? ¿cómo se sabe si llegar a ese estado intermiedo es bueno? La respuesta es definiendo una función heurística, que estime qué bueno el estado de la partida al que llegaríamos. Una forma sería, en el caso del ajedrez, dando un valor distinto a cada pieza en función del tipo de pieza (peón, alfil, torre, reina, etc.) y sumando el valor de las piezas y comparándolo con las del adversario. En este caso, daríamos valores mayores a las piezas que son más importantes (rey y reina) y valores menores a las de menor importancia (peón).

Analizado en detalle el ajedrez, vamos a centrarnos ahora en el Go, para ver la complejidad a la que nos enfrentamos en este caso. El branching factor promedio es 250, lo que significa que, en promedio, un jugador puede elegir entre 250 movimientos distintos en cada jugada, cuyo valor es considerablemente mayor a los 35 posibles movimientos del ajedrez. Además, el número promedio de jugadas es 200, mucho mayor que los 40 del ajedrez. Pero la mayor complejidad de Go no radica en el branching factor y el número de jugadas, sinó en la complejidad de estimar una función heurística que permita valorar cualquier estado intermedio de la partida. Veremos en la siguiente entrada cómo el equipo de AlphaGo se enfrentó a este problema…

Referencias

[1] https://googleblog.blogspot.com.es/2016/01/alphago-machine-learning-game-go.html

[2] Silver, David, et al. «Mastering the game of Go with deep neural networks and tree search.» Nature 529.7587 (2016): 484-489.

[3] http://www.chinadaily.com.cn/opinion/cartoon/2016-03/10/content_23808231.htm

 

(Visited 22 times, 1 visits today)
Autor / Autora
Carles Ventura Royo
Comentarios
Deja un comentario