El juego perfecto de «Snake»: Algoritmos para dominar al clásico

Pocos youtubers explican los algoritmos y la inteligencia artificial como Code Bullet. Sus vídeos lo tienen todo: éxitos, fracasos, insultos, crisis emocionales y desafíos que empiezan simples y se vuelven gigantescos. Su último vídeo retoma un proyecto que ya había intentado meses atrás: conseguir que una inteligencia artificial aprenda a jugar Snake mediante Q-learning. Esta vez vuelve con intención de revancha, y aunque la “perfección” en sus vídeos hay que tomarla con cautela, el resultado es muy superior al anterior.

IA y videojuegos: un breve repaso

No es la primera vez que hablamos de inteligencias artificiales entrenadas para dominar juegos. El Deep-Q de Google se ha entrenado con títulos de Atari 2600, y en especial con pesadillas al nivel del Montezuma’s Revenge. Facebook ya participó con sus bots en torneos de StarCraft, y OpenAI logró victorias de alto perfil en DotA 2.

El desafío de Snake

El vínculo entre los videojuegos y las inteligencias artificiales solo se hará más fuerte, pero independientemente de la calidad de las partidas, no está de más aprender algo sobre lo que ocurre entre bastidores. Tomemos el caso de Snake: un juego sencillo para un humano, pero ¿qué necesitaría una inteligencia artificial para dominarlo por completo?

Code Bullet en YouTube decidió responder a esa pregunta… y creo que está un poco arrepentido. Después de sufrir con Q-learning en su primer vídeo a mediados de julio, regresó a la carga tirando todo su trabajo previo a la basura y empezando desde cero. Snake tiene cuatro comandos básicos: arriba, abajo, izquierda y derecha. Existe un muro en el perímetro del mapa, pero el propio cuerpo de la serpiente actúa como muro interno, con la dificultad extra de que se mueve. Al calcular la cantidad de caminos, el número aproximado es de 295 trillones de posibilidades… así que necesita algo diferente.

La primera idea fue priorizar los caminos que permiten a la serpiente acercarse a la comida en lugar de alejarse, con la ayuda del algoritmo A*, uno de los más populares en pathfinding… pero no funcionó. Al quedar atrapada, la serpiente simplemente dejó de moverse. La solución fue poner a A* de cabeza: en vez de buscar la ruta más corta, la serpiente toma la más larga, que en cierto modo es lo que deben hacer todos los jugadores de Snake cuando la serpiente se vuelve muy grande. A eso añadió otra condición: la serpiente siempre debe poder acceder al 80 por ciento de los bloques vacíos…

… y casi lo logró. Otro reinicio más, y así llegó al llamado «Ciclo de Hamilton», que interpreta el mapa de Snake como un circuito lleno de nodos que deben visitarse solo una vez y luego regresar al principio. Todo lo que debería hacer el nuevo algoritmo es generar ciclos de Hamilton y seguirlos al pie de la letra… pero eso es aburrido para Code Bullet, así que realizó un pequeño ajuste para que la serpiente tome atajos ocasionales. ¿Resultados? El primero fue un éxito, con una partida perfecta de Snake. El segundo terminó en fracaso por apenas dos bloques… aunque el mapa era enorme.