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

f3et (2008-03-31T12:40:25Z)

Relire les règles. Mais c'est vrai que ça parait absurde, à première vue. Remarquer quand même que les têtes reliées au corps ne se régénèrent pas, et que dans de nombreux cas, les têtes que l'hydre engendrent sont plus près du corps que celles coupées, donc déjà pour celles-là, on voit par récurrence qu'elles finiront par donner naissance à un nombre (certes énorme, mais fini) de têtes définitivement mortes

Daniel (2008-03-31T07:24:53Z)

Pardon pour cette question naïve sans doute, mais je vois mal comment on peut être certain qu'Hercule peut gagner de manière certaine.
Chaque coup qu'il porte réduit de 1 le nombre de têtes de l'hydre, donc, si l'hydre choisi de régénérer, disons, deux têtes à chaque fois, à chaque coup porté l'hydre a une tête de plus, non ?! Comment ce nombre peut-il alors être porté à 0 ??

Fork (2008-03-28T22:26:52Z)

→ Ruxor
Je ne sais pas si ça te fera plaisir, mais c'est juste pour signaler que j'ai posté un lien vers la page de l'hydre sur le forum de mon école, et plusieurs personnes sont allé y jouer :)

Ruxor (2008-03-28T18:29:43Z)

Touriste → C'est une bonne question, et j'ai des réponses mais seulement partielles. Disons qu'on peut définir des stratégies meilleures que d'autres contre une hydre “méchante”. Je compte en parler dans une prochaine entrée où j'évoquerai les mathématiques de ce jeu, mais à toute configuration de l'hydre on peut définir deux ordinaux assez naturels, l'un correspondant à un Hercule qui veut en finir aussi lentement que possible, l'autre — plus petit — à un Hercule qui veut en finir aussi vite que possible (l'ordinal lent sera donc défini comme le plus petit ordinal strictement supérieur aux ordinaux lents de toutes les hydres résultant d'une croissance quelconque à partir d'un coup possible d'Hercule, tandis que pour l'ordinal rapide on prendra le min sur les coups d'Hercule au lieu du max) ; en termes Conwayiens, l'ordinal lent correspond à la valeur du jeu si l'hydre et Hercule coopèrent, alors que l'ordinal rapide correspond à sa valeur s'ils sont adversaires. L'ordinal lent peut monter jusqu'à l'ordinal de Bachmann-Howard (sans l'atteindre) et si je ne m'abuse on obtient une stratégie lente en coupant systématiquement la tête la plus à gauche ; l'ordinal rapide, lui, je n'ai pas encore bien calculé jusqu'à combien il montait (peut-être ε0, mais je n'en suis pas du tout sûr) et il a l'air de s'atteindre avec des stratégies où, effectivement, Hercule coupe plutôt les branches d'en haut en premier (mais il faut aussi couper les funestes en premier donc c'est un poil plus compliqué que ça à expliquer). En fait, à toute stratégie de découpe bien définie on pourrait associer un ordinal pour chaque hydre (et un ordinal limite de ça), qui serait quelque part entre l'ordinal rapide et l'ordinal lent.

Maintenant, mon implémentation d'hydre a aussi des faiblesses qui lui sont propres. Par exemple, comme elle rechigne à produire trop de têtes, on peut facilement la tromper en lui faisant en produire beaucoup qui soient faciles à couper puis en coupant des branches beaucoup plus puissantes, pour ainsi dire anesthésiées par les nombreuses têtes faciles.

Touriste (2008-03-28T18:05:22Z)

Question à l'énoncé un peu approximatif (dont la réponse est peut-être prévue dans l'entrée à venir expliquant où se cache l'ordinal) : existe-t-il pour le joueur une stratégie "optimale" en un sens raisonnable ? (J'ai du mal à voir quel peut être ce sens compte tenu du hasard qui intervient dans les choix de l'hydre).

Les tactiques qui donnent des temps de combat nettement plus courts sur le jeu concret que tu proposes sont elles "meilleures" en un sens ou un autre pour le jeu théoriue, ou sont-elles fortement liées au fait que la bête de cette implémentation reste très timide en matière de renouvellement de têtes ?

Ruxor (2008-03-28T15:56:06Z)

nameornick → Non, les règles de l'hydre dont on parle, là, sont une invention moderne (Kirby et Paris pour les segments normaux, Buchholz légèrement modifié par moi pour les segments funestes). L'hydre qu'aurait terrassée Hercule dans la légende grecque, rien ne dit comment ses têtes repoussaient et encore moins s'il y aurait eu un résultat de finitude (et probablement pas, car si à chaque tête qu'Hercule coupe deux nouvelles repoussent ben c'est mal parti).

Pour la licence du code, je viens d'ajouter des commentaires disant que c'est du domaine public. Ne pas hésiter à le recopier, donc, si on a besoin d'un générateur ARC4 en JavaScript ou bien d'exemples d'utilisation du DOM SVG.

J'ai aussi ajouté une feature de jeu automatique, qui coupe toujours la tête la plus à gauche.

Raoul → Je ne sais pas à quoi peut être dû ce problème, et comme je n'ai pas Safari pour tester il m'est difficile de le corriger. Si un expert JavaScript ayant Safari sous la main peut regarder…

PB → C'est plutôt normal d'être surpris, en fait, parce que si l'hydre est forcément battue elle peut quand même rendre le temps pour la battre aussi long qu'elle veut (mais toujours fini). Pour rendre cette affirmation précise, il faut, justement, des ordinaux.

Laurent (2008-03-28T14:02:38Z)

42!
Oups, pardon… ;-)

iPidiblue du côté de l'hydre (2008-03-28T12:22:42Z)

Requiem pour une hydre soumise à autant de combats et à autant de valeureux guerriers !

DH (2008-03-28T11:42:10Z)

95 !

Raoul (2008-03-28T10:45:04Z)

138 coups, mais en fin de partie, impossible de quitter la page, tout clic ou commande clavier se traduit par un bong sonore, et reste sans effet. Obligé de forcer à quitter Safari.

nameornick (2008-03-28T10:04:37Z)

Question historique: les grecs avaient-ils intuité ce résultat de finititude? Je veux dire ont-ils conservé cette légende parce que ça parassait forcément faisable, ou au contraire parce que ça paraissait vraiment infaisable pour un mortel qui n'a qu'un temps fini court?

Par ailleurs ton code n'as aucune licence, doit-on comprendre que c'est dans le domaine public? C'est l'usage pour le javascript que tout un chacun peut lire de tout façon?

DH (2008-03-28T08:39:53Z)

136 ! ;-) J'ai utilisé la stratégie de Linca, et l'hydre a été assez gentille avec moi.

Feature request :
* Un bouton "Undo"
* Une table de hi-scores ailleurs que dans les commentaires ;-)

PB (2008-03-28T06:31:42Z)

Ok, donc je n'ai rien compris, je relis les règles du jeu :-)

jö (2008-03-28T02:08:11Z)

914 mais j'ai oublié de noter le nombre de segments de départ.

Ruxor (2008-03-27T23:07:15Z)

PB → Non, c'est bien *toujours*, pas juste avec probabilité 1. D'ailleurs, il n'y a pas de probabilités en jeu (enfin, il y a dans mon implémentation de l'hydre, mais il n'y en a pas dans le problème). *Quels que soient* les choix faits par l'hydre et *quels que soient* les choix faits par Hercule, l'hydre meurt toujours en temps fini.

PB (2008-03-27T21:59:21Z)

"Hercule finit toujour par gagner"

Je ne suis pas sûr de comprendre : il y a bien des probabilités ici ? Faut-il comprendre qu'Hercule finit *presque* toujour par gagner ?

Linca (2008-03-27T20:33:54Z)

371…

je commencerai plutôt par les têtes non funestes, d'abord, et en enlevant celles où le père n'a pas trop d'enfants

Fork (2008-03-27T17:34:23Z)

J'ai battu mon premier hydre en 928 coups (ouf!)
Par contre je suis pas sur d'avoir joué de façon optimale, faudra que je réfléchisse un peu avant d'y rejouer (je me suis borné à couper les têtes les plus hautes possibles, et les coups funestes en cas d'égalité de hauteur).


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: 47657a


Recent comments