David Madore's WebLog: Une hydre à combattre : première partie (petit jeu informatique)

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #1537 [older|newer] / Entrée #1537 [précédente|suivante]:

(jeudi)

Une hydre à combattre : première partie (petit jeu informatique)

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).

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).

↑Entry #1537 [older|newer] / ↑Entrée #1537 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées