Le cycle hamiltonien au Snake : la stratégie mathématique pour remplir toute la grille
Peut-on gagner à Snake de manière garantie ? Peut-on remplir la totalité de la grille sans jamais se mordre la queue ? La réponse est oui, et elle repose sur un concept mathématique fascinant : le cycle hamiltonien. Derrière ce nom intimidant se cache une idée élégante qui transforme le jeu le plus simple au monde en un problème de théorie des graphes. Voici comment les mathématiques garantissent la victoire parfaite au Snake.
Qu’est-ce qu’un cycle hamiltonien ?
Un cycle hamiltonien est un concept issu de la théorie des graphes, la branche des mathématiques qui étudie les réseaux de points et de connexions. Imaginez un ensemble de points (appelés sommets) reliés entre eux par des lignes (appelées arêtes). Un cycle hamiltonien est un chemin qui passe par chaque sommet exactement une fois et revient au point de départ.
Le nom vient du mathématicien irlandais William Rowan Hamilton, qui a formalisé ce problème en 1857 avec son « jeu icosien », un casse-tête où il fallait trouver un chemin passant par les 20 sommets d’un dodécaèdre. Depuis, le problème hamiltonien est devenu l’un des plus étudiés en informatique théorique, car déterminer si un graphe quelconque possède un cycle hamiltonien est un problème NP-complet - autrement dit, il n’existe aucun algorithme rapide connu pour le résoudre dans le cas général.
Heureusement pour les joueurs de Snake, la grille rectangulaire du jeu est un cas particulier beaucoup plus simple. Sur une grille, trouver un cycle hamiltonien est non seulement possible, mais relativement facile.
La grille de Snake comme graphe
Pour appliquer le cycle hamiltonien au Snake, il faut d’abord voir la grille de jeu comme un graphe. Chaque case de la grille est un sommet, et deux cases adjacentes (horizontalement ou verticalement) sont reliées par une arête. Sur une grille de 10×10, cela donne 100 sommets et 180 arêtes.
Un cycle hamiltonien sur cette grille est donc un chemin fermé qui passe par chacune des 100 cases exactement une fois. Si le serpent suit ce chemin, il parcourra la totalité de la grille sans jamais passer deux fois au même endroit - et donc sans jamais se mordre la queue.
Le pattern en zigzag
Le cycle hamiltonien le plus simple sur une grille rectangulaire est le pattern en zigzag (aussi appelé « boustrophedon »). Le principe est le suivant :
- Parcourez la première colonne de haut en bas
- Déplacez-vous d’une case vers la droite
- Parcourez la deuxième colonne de bas en haut
- Déplacez-vous d’une case vers la droite
- Continuez en alternant jusqu’à la dernière colonne
- Revenez au point de départ en longeant le bord supérieur
Ce pattern simple crée un cycle qui passe par toutes les cases de la grille. C’est la base de la stratégie pour atteindre le score maximum. Le serpent n’a qu’à suivre ce chemin en boucle, ramassant les pommes au passage, et il finira inévitablement par remplir toute la grille.
La stratégie de base : suivre le cycle
La stratégie hamiltonienne au Snake est d’une simplicité désarmante : suivez le cycle, quoi qu’il arrive. Quelle que soit la position de la pomme, ne déviez pas du chemin prédéfini. Le serpent finira par atteindre la pomme en suivant le cycle, même si cela prend plus de temps que d’y aller directement.
Cette approche garantit plusieurs choses :
- Zéro risque de collision : puisque le cycle passe par chaque case exactement une fois, le serpent ne peut jamais se retrouver face à sa propre queue. La queue aura toujours quitté la case avant que la tête n’y revienne
- Toutes les pommes seront ramassées : peu importe où la pomme apparaît, le cycle finit par passer par cette case. La pomme sera ramassée en un tour de cycle au maximum
- La grille sera entièrement remplie : en ramassant chaque pomme, le serpent s’allonge d’une case. Après avoir ramassé toutes les pommes possibles, le serpent occupe toute la grille
Le problème de cette stratégie pure est sa lenteur. Sur une grille de 20×20, le cycle fait 400 cases. Si la pomme est juste derrière la tête du serpent dans le cycle, il faudra parcourir 399 cases pour l’atteindre. C’est mathématiquement garanti de fonctionner, mais c’est terriblement inefficace en termes de temps.
Les raccourcis : aller plus vite sans risque
Les joueurs et les programmeurs d’IA ont développé des optimisations du cycle hamiltonien qui permettent d’aller plus vite tout en conservant la garantie de sûreté. L’idée est de prendre des raccourcis par rapport au cycle de base, à condition que ces raccourcis ne compromettent pas la propriété fondamentale du cycle.
Le shortcutting
La technique du shortcutting consiste à couper à travers le cycle quand c’est sûr. Le principe est le suivant : à chaque pas, au lieu de suivre aveuglément le cycle, le serpent vérifie s’il peut sauter directement à une case plus avancée du cycle sans risque. La condition de sécurité est que la queue du serpent doit avoir déjà quitté toutes les cases entre la position actuelle et la destination du raccourci.
En pratique, cela signifie que le serpent peut couper à travers des zones déjà parcourues par sa queue, économisant parfois des dizaines de cases. Les secrets des meilleurs joueurs reposent souvent sur cette capacité à identifier les raccourcis sûrs.
Le perturbation de cycle
Une approche plus sophistiquée consiste à modifier dynamiquement le cycle en fonction de la position de la pomme. Au lieu de suivre un cycle fixe, l’algorithme maintient un cycle hamiltonien valide mais le déforme pour rapprocher la pomme de la tête du serpent. À chaque mouvement, le cycle est légèrement ajusté tout en restant hamiltonien, garantissant la sécurité.
Cette technique est plus complexe à implémenter mais produit des résultats spectaculaires : le serpent semble jouer de manière « intelligente », se dirigeant vers la pomme tout en évitant les pièges, alors qu’il suit en réalité un cycle mathématiquement garanti.
Le lien avec la théorie des graphes
Le cycle hamiltonien au Snake est un cas concret d’application de la théorie des graphes, une branche des mathématiques aux implications vastes. Le problème hamiltonien est étroitement lié à d’autres problèmes célèbres :
- Le problème du voyageur de commerce : trouver le plus court chemin passant par toutes les villes est essentiellement un problème hamiltonien avec une fonction de coût. C’est l’un des problèmes les plus étudiés en optimisation combinatoire
- Le chemin eulérien : cousin du chemin hamiltonien, il passe par chaque arête (et non chaque sommet) exactement une fois. C’est le problème des sept ponts de Königsberg résolu par Euler en 1736
- La coloration de graphe : déterminer le nombre minimum de couleurs nécessaires pour colorier un graphe sans que deux sommets adjacents aient la même couleur. Ce problème est lié aux cycles dans les graphes
Le Snake offre ainsi une porte d’entrée ludique vers des concepts mathématiques profonds. Pour ceux qui veulent aller plus loin, programmer son propre Snake est un excellent exercice pour comprendre ces concepts en les implémentant concrètement.
Pourquoi c’est la seule stratégie qui garantit de finir le jeu
Il est important de comprendre pourquoi le cycle hamiltonien est la seule approche qui garantit mathématiquement de remplir toute la grille. Toute autre stratégie - même très intelligente - comporte un risque non nul d’échec.
Considérons les alternatives :
- La stratégie gloutonne (aller directement vers la pomme) : elle fonctionne au début, mais quand le serpent s’allonge, elle mène inévitablement à des impasses où le serpent se retrouve piégé par son propre corps
- La stratégie A* (chemin le plus court avec évitement d’obstacles) : plus sophistiquée, elle évite les obstacles immédiats mais ne garantit pas qu’un chemin de retour existera après avoir mangé la pomme
- La stratégie par zones (diviser la grille en zones et les remplir une par une) : elle réduit les risques mais ne les élimine pas totalement, car la transition entre les zones peut créer des configurations piégeuses
Le cycle hamiltonien est le seul à offrir une preuve mathématique de complétude. Puisque le cycle passe par chaque case exactement une fois et revient au départ, et puisque la queue du serpent libère les cases dans l’ordre où la tête les a visitées, il ne peut jamais y avoir de collision. C’est un invariant mathématique qui tient quelle que soit la longueur du serpent.
Les IA de Snake basées sur Hamilton
Le cycle hamiltonien est devenu la pierre angulaire des IA de Snake les plus performantes. Sur YouTube et GitHub, des centaines de projets montrent des serpents contrôlés par ordinateur qui remplissent systématiquement toute la grille. Ces IA utilisent généralement une version optimisée du cycle hamiltonien, combinant la sécurité du cycle de base avec des raccourcis intelligents.
Les approches hybrides
Les IA les plus avancées combinent le cycle hamiltonien avec d’autres techniques :
- Hamilton + BFS : l’IA utilise un parcours en largeur (BFS) pour trouver la pomme rapidement, puis vérifie que le chemin choisi ne brise pas la propriété hamiltonienne. Si oui, elle prend le raccourci ; sinon, elle suit le cycle
- Hamilton + look-ahead : avant de prendre un raccourci, l’IA simule les N prochains mouvements pour vérifier qu’elle ne se retrouvera pas dans une impasse. Cette anticipation améliore considérablement la vitesse sans sacrifier la sécurité
- Hamilton adaptatif : le cycle est recalculé périodiquement en fonction de la position du serpent et de la pomme. Chaque nouveau cycle est hamiltonien, mais optimisé pour la situation courante
Les performances mesurées
Sur une grille classique de 20×20 (400 cases), les résultats sont éloquents :
- Cycle hamiltonien pur : 100 % de succès, mais lenteur extrême (plusieurs milliers de tours pour remplir la grille)
- Hamilton + shortcutting : 100 % de succès, vitesse multipliée par 3 à 5
- Hamilton adaptatif : 100 % de succès, vitesse multipliée par 8 à 10
- Stratégie gloutonne pure : environ 60 à 70 % de la grille remplie avant échec
- A* avec heuristique : environ 85 à 95 % de la grille remplie, mais jamais 100 % garanti
Ces chiffres illustrent clairement le compromis : le cycle hamiltonien est le seul à atteindre 100 % de manière garantie, au prix d’une vitesse moindre que les approches heuristiques.
Appliquer le concept à votre jeu
Suivre un cycle hamiltonien exact en jouant manuellement est difficile - voire impossible à haute vitesse. Mais le concept sous-jacent peut transformer votre manière de jouer :
- Pensez en boucles : plutôt que de foncer vers la pomme, essayez toujours de maintenir un chemin cyclique. Si vous pouvez revenir à votre point de départ sans croiser votre corps, vous êtes en sécurité
- Privilégiez les patterns répétitifs : les zigzags le long des murs sont une approximation du cycle hamiltonien. Ils ne sont pas optimaux mais ils réduisent considérablement le risque de collision
- Gardez toujours une route de fuite : avant de prendre un raccourci vers la pomme, vérifiez mentalement que vous pourrez revenir à votre pattern de base après l’avoir ramassée
- Remplissez méthodiquement : quand le serpent devient long, arrêtez de courir après la pomme et adoptez un parcours systématique de la grille. La pomme viendra à vous
Le cycle hamiltonien au Snake est bien plus qu’une curiosité mathématique : c’est la preuve que derrière le jeu le plus simple au monde se cache une richesse combinatoire fascinante. Que vous cherchiez à battre votre record, à programmer une IA imbattable, ou simplement à comprendre pourquoi les mathématiques sont belles, le cycle hamiltonien offre une réponse élégante à une question en apparence naïve : peut-on remplir toute la grille ? Oui, et voici exactement comment.