AccueilTurfu

Il arrive (presque) à finir Snake en codant son IA

Publié le

par Benjamin Bruel

Un snake pour les gouverner tous et dans les ténèbres les lier.

Connaissez-vous Code Bullet ? C’est la chaîne YouTube des amateurs de code, de hacks, de "fuuuuck" et d’intros barrées.

Très récemment, le vidéaste américain à la tête de PC, nommé Evan dans la vraie vie, s’est attaqué au problème Snake, ce jeu auquel les plus de 20 ans ont tous joué, devenu populaire sur téléphone portable avec le Nokia 3310 et consorts.

Dans une vidéo publiée il y a déjà quelques mois, Code Bullet se met en quête du système d’intelligence artificielle parfait pour battre Snake – entendre, créer un serpent capable de remplir toutes les cases du jeu, d’avaler tous les points carrés sans se heurter avec sa propre queue qui grandit à chaque carré avalé. Un exploit hautement complexe.

De trois manières différentes, Code Bullet essaie de coder l’algorithme parfait. En utilisant A* d’abord, un algorithme de recherche de chemin et de planification, qui calcule le meilleur chemin, mais qui abandonne rapidement (littéralement, mais prosaïquement) face au problème suivant : le chemin ne peut être fait directement, à cause de la queue qui ne cesse de grandir et des murs qui ne s’élargissent pas. Fail.

Deuxième idée : avec l’ajout d’une règle forçant le serpent à avoir toujours accès à 80 % des blocs vides, Code Bullet essaie d’éviter qu’il se percute lui-même. Fail encore, malgré les progrès.

Il recommence à zéro. Il explique, sans vergogne, avoir volé tout le code à un homme nommé John Tapsell, qui a tout simplement hacké un Nokia pour tripoter Snake. En gros, l’idée utilisée est celle d’un problème mathématique nommé chemin hamiltonien : le serpent va passer par tous les blocs (vides) de la carte, une fois et une seule, pour constamment rejoindre le bout de sa queue.

Voilà : même si vous n’en avez pas grand-chose à faire, de Snake, vous aurez appris l’existence d’une théorie mathématique.


Snake vous fascine autant que nous ? Dites-le nous à hellokonbinitechno@konbini.com.

À voir aussi sur techno :