O jogo perfeito de «Snake»: algoritmos para dominar o clássico

Poucos youtubers explicam algoritmos e inteligência artificial em geral como Code Bullet. Seus vídeos têm de tudo: sucessos, fracassos, insultos, crises emocionais e desafios simples que se tornam gigantescos. Seu vídeo mais recente é a continuação do projeto que publicou meses atrás, no qual ele lutou para que uma inteligência artificial aprenda a jogar Snake via Q-learning. Desta vez, ele volta ao ataque em busca de revanche e, embora a “perfeição” nos vídeos do Code Bullet deva ser encarada com cautela, o resultado final é muito superior ao anterior.

Não é a primeira vez que falamos sobre inteligências artificiais treinadas para dominar jogos. O Deep-Q do Google foi treinado com títulos de Atari 2600, e especialmente com pesadelos do nível do Montezuma’s Revenge. O Facebook já participou com seus bots em torneios de StarCraft, e a OpenAI conseguiu vitórias de alto perfil em DotA 2.

O vínculo entre os videogames e as inteligências artificiais só ficará mais forte, mas independentemente da qualidade das partidas, não é má ideia aprender um pouco sobre o processo nos bastidores. Tomemos o caso do Snake. Um jogo mais que simples se um humano o joga, mas o que uma inteligência artificial precisaria para conquistá-lo por completo?

Code Bullet no YouTube decidiu responder a essa pergunta... e acho que ele está um pouco arrependido. Depois de sofrer com Q-learning em seu primeiro vídeo em meados de julho, ele voltou à carga jogando todo o trabalho anterior no lixo e começando do zero. O Snake tem quatro comandos básicos: cima, baixo, esquerda e direita. Existe uma parede no perímetro do mapa, mas o próprio corpo da serpente age como parede interna, com a dificuldade extra de que ele se move. Ao calcular a quantidade de caminhos, o número aproximado é de 295 trilhões de possibilidades... ou seja, ele precisa de algo diferente. A primeira ideia foi priorizar os caminhos que permitem à serpente se aproximar da comida em vez de se afastar com a ajuda do algoritmo A*, um dos mais populares em matéria de pathfinding... mas não funcionou. Ao ficar presa, a serpente simplesmente parou de se mover. A solução foi virar o A* de cabeça para baixo: em vez de buscar a rota mais curta, a serpente pega a mais longa, que de certa forma é o que todos os jogadores de Snake devem fazer quando a serpente fica muito grande. A isso ele adicionou outra condição: a serpente deve sempre ser capaz de acessar 80 por cento dos blocos vazios...

… e quase conseguiu. Mais um reinício, e assim chegou ao chamado «Ciclo de Hamilton», que interpreta o mapa do Snake como um circuito cheio de nós que devem ser visitados apenas uma vez, e voltar ao início. Tudo o que o novo algoritmo deveria fazer é gerar ciclos de Hamilton e seguir cada um à risca... mas isso é chato para o Code Bullet, então ele fez um pequeno ajuste para que a serpente pegue atalhos ocasionais. Resultados? O primeiro foi um sucesso, com uma partida perfeita de Snake. O segundo terminou em fracasso por apenas dois blocos... embora o mapa fosse enorme.