Inspirado no vídeo "Algoritmo INVENCÍVEL dominando o jogo da cobrinha (SNAKE)" do canal Universo Programado, implementei o jogo Snake na linguagem C++11 usando a biblioteca gráfica SDL2, e apliquei o algoritmo apresentado. A ideia dele é proibir alguns movimentos da cobrinha de modo a garantir que sempre haja um caminho até a cauda para que ela nunca se prenda e nunca perca o jogo.
O vídeo também apresenta as seguintes otimizações:
- Escolher entre duas direções usando a distância euclidiana até o alimento.
- Escolher entre duas direções usando Dijkstra (algoritmo de pathfinding).
- Obrigar a cobrinha a não deixar lacunas no tabuleiro.
Esse algoritmo, apenas com a primeira otimização, conseguiu zerar o jogo em 100% das vez com 25 mil passos, em média. Compararado ao algoritmo de Monte Carlo, esse algoritmo consegue terminar o jogo em menos passos e consegue jogar em tabuleiros maiores sem necessitar de mais processamento. O ponto fraco desse algoritmo é que ele não funciona em tabuleiros de tamanho ímpar (9x5 por exemplo).
É necessário que você tenha a biblioteca SDL2 instalada. No Ubuntu (e derivados), você pode usar o seguinte comando:
sudo apt install libsdl2-dev -y
Para compilar com o g++, use o seguinte comando:
g++ -std=c++11 main.cpp -lSDL2 -o snake
Espaço para acelerar o jogo.
Enter para reiniciar o jogo.
Esc para perder o jogo.