Menu
in

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

Una pesadilla de código, y todo por una manzana…

Snake

Pocos youtubers explican a los algoritmos y la inteligencia artificial en general como Code Bullet. Sus vídeos lo tienen todo: Éxitos, fracasos, insultos, crisis emocionales, y desafíos simples que pasan a ser gigantescos. Su vídeo más reciente es una continuación del proyecto que publicó meses atrás, en el cual luchó para que una inteligencia artificial aprenda a jugar Snake vía Q-learning. Esta vez, vuelve al ataque buscando revancha, y aunque la «perfección» en los vídeos de Code Bullet debe ser tomada con pinzas, el resultado final es muy superior al anterior.

No es la primera vez que hablamos sobre 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 vínculo entre los videojuegos y las inteligencias artificiales sólo se hará más fuerte, pero independientemente de la calidad de las partidas, no es mala idea aprender un poco sobre el proceso en segundo plano. Tomemos el caso del Snake. Un juego más que simple si lo disfruta un humano, ¿pero qué necesitaría una inteligencia artificial para conquistarlo 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 comenzando desde cero. El 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… o sea que necesita algo diferente.

La primera idea fue priorizar aquellos caminos que le permiten a la serpiente acercarse a la comida en vez de alejarse con la ayuda del algoritmo A*, uno de los más populares en materia de pathfinding… pero no funcionó. Al quedar atrapada, la serpiente simplemente dejó de moverse. La solución para esto 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 agregó otra condición: La serpiente siempre debe ser capaz de 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 al mapa del Snake como un circuito lleno de nodos a los que tiene que visitar sólo una vez, y regresar al principio. Todo lo que debería hacer el nuevo algoritmo es generar ciclos de Hamilton y seguir cada uno 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.



Escrito por Lisandro Pardo

Leave a Reply