Alors que j'étais terrassé par un puissant rhume pendant le week-end de Pâques, j'ai réalisé cette page — que ce n'est même pas la peine d'aller voir si vous n'avez pas un navigateur Web moderne (je pense qu'il n'y a à peu près que les Firefox, Opera et peut-être certains Safari qui arriveront à l'afficher correctement ; notamment, si vous ne voyez pas s'afficher un rectangle gris avec des segments verts et marron, c'est qu'il vous manque le support SVG ou JavaScript — et si vous ne voyez même pas le titre correct, c'est que votre navigateur ne comprend pas le XHTLM). Avec beaucoup de clémence on pourrait qualifier ça de jeu (ou plutôt de time waster).
Vous incarnez Hercule, et votre but est de tuer l'hydre affichée sur la page. Celle-ci n'a, initialement, qu'une tête, au cou plus ou moins long (c'est-à dire reliée à son corps par l'intermédiaire de plusieurs segments, qui s'attachent en des nœuds), elle meurt quand elle n'a plus aucune tête, mais à chaque fois qu'on coupe une tête d'autres peuvent repousser selon des règles que je vais détailler. Pour jouer, Hercule n'a qu'à choisir la tête qu'il veut découper et cliquer dessus (il faut cliquer sur le gros point noir qui représente la tête) ; on ne peut couper qu'une tête, c'est-à-dire un nœud de l'hydre en bout de cou (qui n'a lui-même aucun descendant).
Les règles qui régissent la repousse des têtes dépendent du type de
cou auquel la tête coupée était attachée. Notre hydre a deux types de
segments : elle est plus puisante que l'hydre de Kirby-Paris qui n'en
a qu'un seul, les normaux
(mais si vous parvenez à terrasser
l'hydre, vous passerez forcément par un stade où elle aura été réduite
à cette version moins puissante).
- Les cous les moins embêtants sont les cous normaux (ils sont représentés en vert fin sur ma page). D'abord, si vous tranchez un cou normal qui est directement relié à la base de l'hydre (son corps, quoi), rien ne repousse — c'est d'ailleurs le seul cas où l'hydre n'a pas la posssibilité de se régénérer. Si vous tranchez un cou normal n'importe où ailleurs dans l'hydre, celle-ci a la possibilité de régénérer de nouvelles copies du nœud auquel ce cou était relié (le nœud « père » de la tête découpée) : c'est-à-dire reproduire non seulement le nœud lui-même et le segment qui le relie à son propre père (le « grand-père » de la tête découpée), mais aussi tous ses descendants (sauf le cou qui a été tranché, évidemment), et ce, en autant d'exemplaires que l'hydre le souhaite. Remarquez cependant que par cette opération l'hydre ne peut grandir qu'en largeur, jamais en hauteur.
- Les cous funestes (marron et épais sur ma page) sont beaucoup plus puissantes. Si vous tranchez un cou funeste, l'hydre a la faculté de régénérer, à la place de la tête tranchée, une copie d'un nœud situé plus près du corps de l'hydre. Précisément, on remonte depuis la tête tranchée vers le corps de l'hydre jusqu'à rencontrer un segment normal (et non funeste), et la totalité de la sous-hydre qui part de ce nœud pourra être reproduit à la place de la tête coupée. Mais il y a pire : l'hydre peut reproduire cela aussi profondément qu'elle le veut : à la place de la tête coupée apparaît une sous-hydre qui peut elle-même contenir une copie en abyme de la même sous-hydre et ainsi de suite jusqu'au niveau que l'hydre le souhaite. La seule bonne nouvelle, c'est que les copies sont attachées par des cous normaux (et non funestes).
Hum, voilà qui était un peu compliqué à dire, mais c'est en fait très simple et on comprend tout de suite les règles en jouant un peu avec mon programme. (Je vous invite à essayer, et si vous arrivez à exprimer les règles de façon plus concise et claire, faites-le moi savoir dans les commentaires !)
Par ailleurs, mon hydre est assez domestique : elle ne fait qu'un
usage très modéré de son droit à repousser des têtes (souvent elle ne
l'utilise même pas du tout), ne serait-ce que parce qu'il fallait bien
que l'écran ne déborde pas trop, et un petit peu de patience suffit
donc à la tuer (surtout si on ne choisit pas trop stupidement les
têtes à couper). On a peut-être l'impression que si l'hydre était un
peu plus méchante la tâche serait infinie (essayez par exemple de
faire une copie locale du fichier et de remplacer les lignes
271–272 par var prob = 1./rep; — m'est avis
que vous n'irez pas bien loin avec cette hydre-là) : que dire d'une
hydre qui se répliquerait dix fois à la première tête coupée (si les
règles lui permettent de se régénérer, bien sûr), cent à la suivante,
mille ensuite ? Sûrement il serait impossible pour Hercule de la
terrasser ! Ou peut-il y arriver en choisissant intelligemment les
têtes à couper ? Car même avec mon hydre bien gentille, il faut une
sacrée patience pour gagner en coupant, disons, toujours la tête la
plus à gauche.
Le résultat mathématique est surprenant :
Aussi méchante que soit l'hydre dans sa volonté de se reproduire,
aussi stupide que soit Hercule dans le choix des têtes à couper,
Hercule finit toujour par gagner
(en temps fini).
En temps fini
, ça ne veut pas dire rapidement
: si
l'hydre se reproduit dix fois puis cent fois puis mille fois et ainsi
de suite (ou même, en fait, une fois puis deux puis trois et ainsi de
suite), et si Hercule coupe à chaque fois la tête la plus à droite, il
faudra un nombre d'étapes tellement grand pour finir que
la fonction
d'Ackermann du nombre de particules dans l'univers, en
comparaison, c'est de la gnognote. Mais Hercule finit toujours par
gager, quelle que soit la mauvaise volonté qu'il y mette et quels que
soient les efforts de l'hydre pour faire sa mauvaise tête (pun
unintended) ; et ce n'est pas qu'un résultat probabiliste dépendant de
tel ou tel comportement de l'hydre : c'est un
résultat certain (ce qui est plus fort que de
probabilité 1
).
Je l'ai évoqué précédemment, ce résultat est lié à des grands ordinaux (pour cette hydre précise, c'est l'ordinal de Bachmann-Howard, dont j'ai déjà parlé). Je reviendrai sur l'aspect mathématique dans une entrée ultérieure : pour l'instant je laisse juste ça sous forme de petit jeu. Et je salue au passage les quelques navigateurs qui implémentent correctement l'affichage du SVG sous contrôle du DOM en JavaScript, parce que ça ne doit pas être ultra facile et ça rend ce genre de petites pages animées possible (et même agréable à écrire : en fait, JavaScript est un langage assez plaisant).