Le jeu parfait de « Snake » : des algorithmes pour dominer le classique

Peu de YouTubers expliquent les algorithmes et l'intelligence artificielle en général comme le fait Code Bullet. Ses vidéos ont tout : des succès, des échecs, des insultes, des crises émotionnelles et des défis simples qui deviennent gigantesques. Sa vidéo la plus récente est la suite d'un projet publié il y a quelques mois, dans lequel il s'efforçait de faire apprendre à une intelligence artificielle à jouer à Snake via le Q-learning. Cette fois, il revient à l'attaque pour prendre sa revanche, et même si la « perfection » dans les vidéos de Code Bullet doit être prise avec des pincettes, le résultat final est bien supérieur au précédent.

L'IA et les jeux vidéo

Il ne s'agit pas de la première fois que nous parlons d'intelligences artificielles entraînées à dominer des jeux. Le Deep-Q de Google s'est entraîné avec des titres d'Atari 2600, et en particulier avec des cauchemars au niveau du Montezuma's Revenge. Facebook a déjà participé avec ses bots à des tournois de StarCraft, et OpenAI a remporté des victoires très médiatisées sur DotA 2.

Le défi de Snake

Le lien entre les jeux vidéo et les intelligences artificielles ne fera que se renforcer, mais indépendamment de la qualité des parties, ce n'est pas une mauvaise idée d'apprendre un peu sur le processus en arrière-plan. Prenons le cas du Snake. Un jeu plus que simple si on le joue en humain, mais de quoi une intelligence artificielle aurait-elle besoin pour le conquérir complètement ?

La quête de la partie parfaite

Code Bullet en YouTube a décidé de répondre à cette question... et je pense qu'il le regrette un peu. Après avoir souffert avec le Q-learning dans sa première vidéo à la mi-juillet, il est revenu à la charge en jetant tout son travail précédent aux ordures et en recommençant de zéro. Le Snake a quatre commandes de base : haut, bas, gauche et droite. Il y a un mur sur le périmètre du terrain, mais le corps même du serpent agit comme un mur interne, avec la difficulté supplémentaire qu'il bouge. En calculant le nombre de chemins, le nombre approximatif est de 295 billions de possibilités... il lui faut donc quelque chose de différent.

La première idée était de prioriser les chemins qui permettent au serpent de se rapprocher de la nourriture au lieu de s'en éloigner, à l'aide de l'algorithme A*, l'un des plus populaires en matière de pathfinding... mais ça n'a pas fonctionné. Une fois piégé, le serpent s'est simplement arrêté de bouger. La solution a été de mettre A* à l'envers : au lieu de chercher le chemin le plus court, le serpent prend le plus long, ce qui est d'une certaine manière ce que tous les joueurs de Snake doivent faire lorsque le serpent devient très grand. À cela, il a ajouté une autre condition : le serpent doit toujours être capable d'accéder à 80 % des blocs vides...

… et il a presque réussi. Encore un redémarrage, et il est arrivé au fameux « cycle de Hamilton », qui interprète le terrain du Snake comme un circuit rempli de nœuds que le serpent doit visiter une seule fois et revenir au début. Tout ce que le nouvel algorithme devait faire était de générer des cycles de Hamilton et de les suivre à la lettre... mais c'est ennuyeux pour Code Bullet, alors il a fait un petit ajustement pour que le serpent prenne des raccourcis occasionnels. Résultats ? La première a été un succès, avec une partie parfaite de Snake. La seconde s'est soldée par un échec à deux blocs près... même si le terrain était énorme.