Les 100 niveaux de Bestioles en Cavale passés au crible d'un ordinateur
Dans Bestioles en Cavale, chaque bestiole glisse jusqu'au premier obstacle et doit rejoindre la porte de sa couleur. Les cent niveaux du mode solo n'ont pas été dessinés à la main : ils ont été tirés au hasard puis gardés seulement si un programme prouvait qu'ils avaient une solution. Nous avons repris ce travail avec le moteur du jeu, le fichier de règles qui tourne dans ton navigateur, et nous lui avons fait explorer toutes les suites de coups possibles de chaque niveau. Ce qu'il en ressort dit beaucoup sur la façon de les résoudre.
La méthode : essayer tout, dans l'ordre
Le programme fait une recherche en largeur. Il part de la position de départ, joue tous les coups possibles (chaque bestiole, dans chacune des quatre directions), note chaque situation obtenue, puis recommence depuis chacune d'elles. Une « situation », c'est tout ce qui compte pour la suite : la case de chaque bestiole, celles déjà rentrées, l'état des ponts et les planchers fragiles déjà effondrés. Une situation déjà vue n'est pas explorée deux fois, et un coup qui fait tomber une bestiole est écarté.
Comme les situations sont visitées par nombre de coups croissant, la première victoire trouvée est forcément la plus courte. Premier constat : sur les cent niveaux, le programme retrouve exactement la « solution courte » affichée pendant la partie en solo, celle qui sert de référence aux étoiles. Il n'existe aucun raccourci que le jeu aurait manqué.
Une bestiole de plus, et tout explose
Le chiffre le plus frappant est le nombre de situations atteignables, c'est-à-dire toutes celles que tu peux rencontrer en jouant n'importe comment depuis le départ. Le tableau donne la valeur médiane de chaque palier, à côté du nombre de situations que le programme passe en revue avant de tomber sur la première solution.
| Niveaux | Nouveauté | Bestioles | Solution courte | Atteignables | Vues avant la solution |
|---|---|---|---|---|---|
| 1 à 8 | glissade | 1 | 3 à 4 coups | 20 | 9 |
| 9 à 16 | flèches | 1 | 5 à 8 | 26 | 18 |
| 17 à 26 | deuxième bestiole | 2 | 6 à 9 | 1 857 | 505 |
| 27 à 38 | trous | 2 | 7 à 11 | 1 707 | 250 |
| 39 à 50 | téléporteurs | 2 | 8 à 12 | 1 556 | 603 |
| 51 à 62 | planchers fragiles | 2 | 8 à 13 | 5 928 | 940 |
| 63 à 74 | ponts à bascule | 2 | 9 à 14 | 10 404 | 1 151 |
| 75 à 86 | trois bestioles | 3 | 8 à 14 | plus d'un million | 15 389 |
| 87 à 96 | quatre bestioles | 4 | 8 à 11 | plus d'un million | 8 884 |
| 97 à 100 | tout combiné | 4 | 10 à 12 | plus d'un million | 12 946 |
Avec une seule bestiole, le plateau est minuscule pour un ordinateur : jamais plus de 31 situations. Une bestiole ne s'arrête qu'en butant sur quelque chose, donc elle n'occupe qu'une poignée de cases parmi les 49 ou 64 de la grille. Dès la deuxième, on passe le plus souvent à des milliers : chaque position de l'une se combine avec chaque position de l'autre, et surtout chacune crée de nouveaux points d'arrêt pour sa voisine. Les fragiles et les ponts multiplient encore le compte, parce qu'une même disposition des bestioles avec un plancher intact ou effondré, des ponts ouverts ou fermés, ce sont des situations différentes. Le record parmi les niveaux à deux bestioles est le 64, avec 110 247 situations.
À trois et quatre bestioles, nous avons arrêté de compter à un million : les 26 derniers niveaux dépassent tous ce plafond. Pourtant, il suffit au programme d'examiner au plus 28 066 situations pour trouver la solution la plus courte (niveau 79). Toute la difficulté est là : l'immense majorité des situations possibles ne mène nulle part d'utile, et le programme ne s'en sort que parce qu'il essaie méthodiquement les plus proches du départ.
Pourquoi ces casse-têtes sont durs, même pour une machine
Cette explosion n'est pas propre au jeu. Des chercheurs ont étudié des puzzles qui obéissent à la même règle : dans Ricochet Robots et Lunar Lockout, des pièces glissent jusqu'à buter contre un obstacle ou une autre pièce. Dans la version généralisée de Ricochet Robots (un plateau aussi grand qu'on veut, autant de pièces qu'on veut, et des obstacles fixes, comme les murs de nos niveaux), le problème qui consiste à amener une pièce donnée sur une case donnée est PSPACE-complet. Le résultat a été démontré en 2003 par Jeffrey Hartline et Ran Libeskind-Hadas (The computational complexity of motion planning, SIAM Review), et une preuve plus simple a été publiée en 2024 par Jose Balanza-Martinez, Angel Cantu, Robert Schweller et Tim Wylie (A Simple Proof that Ricochet Robots is PSPACE-Complete).
En clair, personne ne connaît de méthode qui reste rapide sur tous les plateaux quand ils grandissent, et en trouver une résoudrait une grande question ouverte de l'informatique. Ce résultat porte sur des plateaux arbitrairement grands : nos niveaux, qui ne dépassent pas 10 × 10, se résolvent en quelques secondes au plus. Mais il explique pourquoi la seule recette sûre est l'exploration, et pourquoi un humain, qui ne peut pas tester des milliers de situations, a besoin de raccourcis de raisonnement.
Les bestioles servent de butoirs, et souvent il n'y a pas le choix
Le conseil le plus répandu sur ce genre de jeu est d'utiliser une bestiole pour en arrêter une autre. Nous l'avons mesuré : le programme a refait toutes ses recherches en s'interdisant les coups qui s'arrêtent contre une autre bestiole (ou sur un téléporteur dont le jumeau est occupé).
- Sur les 84 niveaux à plusieurs bestioles, 34 deviennent impossibles sans butoir. Le premier est le niveau 20, le quatrième de la série à deux bestioles.
- Dans 15 autres, on peut s'en passer, mais il en coûte des coups : le niveau 33 se résout en 9 coups avec butoir, en 13 sans. Dans 6 de ces 15 niveaux (33, 40, 67, 79, 85 et 92), ce détour suffit à faire perdre la troisième étoile.
- Dans les 35 restants, la solution la plus courte n'a pas besoin de butoir.
Au total, les trois étoiles exigent un butoir dans 40 niveaux sur 100. Quand un niveau à plusieurs bestioles te résiste, la question à se poser n'est donc pas seulement « où va cette bestiole ? » mais « laquelle pourrait se placer pour l'arrêter au bon endroit ? ».
Les impasses : quand le plateau te piège
Le programme a aussi compté, pour les 74 niveaux à une ou deux bestioles où il a pu dresser la carte complète, les impasses : les situations d'où plus aucune suite de coups ne permet de gagner, même sans faire tomber personne. Dans les trois premiers paliers, elles sont rares : entre 2 et 6 % des situations en moyenne. Avec les trous et les téléporteurs, on monte à 12 à 16 %. Avec les planchers fragiles et les ponts, elles représentent en moyenne 46 % et 41 % des situations atteignables.
C'est logique : un plancher effondré ne revient jamais, et un pont mal basculé peut enfermer une bestiole. Le cas extrême est le niveau 70, où 52 832 situations sur 67 571 (78 %) sont des impasses. À l'inverse, 25 de ces 74 niveaux n'en ont aucune, dont le niveau 65, pourtant un niveau à ponts : tant qu'aucune bestiole ne tombe, tu pourras toujours y finir sans annuler.
La leçon pratique : dans un niveau à fragiles ou à ponts, ne joue pas « pour voir ». Le bouton Annuler défait le dernier coup sans pénalité, et il est fait pour ça. Les annulations ne comptent pas dans ton nombre de coups.
Partir de la porte
Autre chiffre parlant : le nombre de situations depuis lesquelles un seul coup suffit à gagner. Il est minuscule. Au niveau 37, une seule situation sur 933 est à un coup de la victoire. Au niveau 70, 12 sur 67 571. La fin d'une solution est presque toujours très contrainte, alors que le début laisse des dizaines de possibilités.
D'où une méthode qui imite le programme à l'envers : regarde d'abord la porte. Par quelles lignes ou colonnes une bestiole peut-elle y glisser ? Où doit-elle se trouver juste avant, et qu'est-ce qui l'arrêtera à cet endroit : un mur, de l'herbe, ou une camarade ? En remontant ainsi deux ou trois coups, tu réduis énormément le nombre de pistes à tester depuis le départ.
Le niveau le plus dur, selon la machine
Tout dépend de ce qu'on mesure. Par la longueur, ce sont les niveaux 74 et 86, avec 14 coups minimum. Par l'effort de recherche, c'est le 79 : seulement 9 coups, mais 28 066 situations à examiner avant de trouver la première solution. Et par la rareté des bonnes réponses, c'est le 38 : 11 coups, butoir obligatoire, 272 impasses sur 458 situations, et une seule suite de 11 coups qui gagne. C'est le seul niveau à plusieurs bestioles dans ce cas ; les 13 autres niveaux à solution courte unique sont tous à une bestiole. À l'opposé, le niveau 98 admet 36 360 suites optimales (deux suites qui jouent les mêmes coups dans un ordre différent comptent ici pour deux).
Ce que ça change pour tes étoiles
Trois étoiles demandent au plus 10 % de coups de plus que la solution courte, arrondi au coup supérieur. Comme toutes les solutions courtes font entre 3 et 14 coups, cela laisse un seul coup de marge dans 73 niveaux (jusqu'à 10 coups de solution courte) et deux coups dans les 27 autres. Autrement dit, un seul détour est permis sur la plupart des niveaux : trouver une solution ne suffit pas, il faut presque trouver la meilleure.
À retenir
- Commence par la porte : la fin d'une solution est très contrainte, le début beaucoup moins.
- Cherche les butoirs : dans 40 niveaux, les trois étoiles en dépendent, et dans 34 niveaux on ne gagne pas du tout sans.
- Méfie-toi des fragiles et des ponts : en moyenne, plus de 40 % des situations y sont des impasses. Annule plutôt que d'insister.
- Compte tes coups : la marge des trois étoiles est d'un coup sur 73 niveaux. La « solution courte » affichée pendant la partie te dit combien viser.
Pour te mesurer aux autres, le classement additionne les étoiles des cent niveaux, et le défi du jour te propose trois plateaux inédits, avec un seul essai (il faut un compte).
