David Madore's WebLog: 2008-03

This WebLog is bilingual, some entries are in English and others are in French. A few of them have a version in either language. Other than that, the French entries are not translations of the English ones or vice versa. Of course, if you understand only English, the English entries ought to be quite understandable without reading the French ones.

Ce WebLog est bilingue, certaines entrées sont en anglais et d'autres sont en français. Quelques-unes ont une version dans chaque langue. À part ça, les entrées en français ne sont pas des traductions de celles en anglais ou vice versa. Bien sûr, si vous ne comprenez que le français, les entrées en français devraient être assez compréhensibles sans lire celles en anglais.

Note that the first entry comes last! / Notez que la première entrée vient en dernier !

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

Entries published in March 2008 / Entrées publiées en mars 2008:

(vendredi)

Annonce de congrès

L'édition d'il y a deux ans ayant été un grand succès, nous avons décidé de rééditer cette année — mardi, pour être exact — un congrès en l'honneur de Sophie Germain et à l'occasion de son anniversaire. L'annonce du congrès se trouve ici, et nous espérons vous y voir nombreux.

Note : la deadline pour les propositions d'exposés est fixée à une date indéterminée : il est donc encore temps d'écrire aux organisateurs si vous pensez pouvoir intervenir sur le thème proposé, n'hésitez pas à nous écrire.

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

(dimanche)

Un peu plus d'IPv6

En prévision de la fin d'Internet version 4[#], annoncée pour dans un peu moins de trois ans, et puisque les Dédibox proposent enfin une connectivité IPv6, j'ai enfin décidé de publier les adresses v6 du serveur (qui marchaient depuis un moment, mais qui n'étaient pas employées). Histoire de voir, entre autre, si les gens les contactent : d'ailleurs, depuis hier soir, il y a huit heureux gagnants qui ont gagné un point geek++ pour être venus ici en transports modernes : deux personnes avec des adresses 6to4 en 2002:xyzt:uvws::xyzt:uvws dont un par un smartphone, et six freenautes[#2] (un avec une adresse en 2a01:5d8::/32 qui est l'ancien système de numérotation de Free et les autres en 2a01:e30::/28 qui est leur nouveau système de numérotation).

C'est un peu stupide de dire si vous n'arrivez pas à lire ces lignes, faites-moi signe, mais je vais quand même le dire… Donc, si vous constatez un problème particulier qui serait apparu depuis hier soir, dites-le moi.

[#] Précisons pour ceux qui ne sont pas au courant : la version du protocole Internet que presque tout le monde utilise presque tout le temps (par exemple, c'est très probablement votre cas quand vous consultez Google ou Wikipedia) est la version 4 (nonobstant son nom, on pourrait dire que c'est la première), et elle ne prévoit que quatre milliards d'adresses IP possibles. Il n'y a pas encore quatre milliards d'ordinateurs connectés à Internet, mais on perd forcément pas mal d'espace dans la façon dont on alloue ces adresses (car il faut attribuer des blocs entiers à des fournisseurs d'accès, on ne va pas le faire IP par IP), si bien qu'on arrive maintenant à court. Autour de fin 2010 ou début 2011, l'autorité suprême qui alloue les adresses (l'IANA) n'en aura plus à déléguer, et à peine un an plus tard les différents groupements régionaux de fournisseurs d'accès n'en auront plus non plus. La version 6 du protocole (il n'y a pas vraiment eu de version 5), qui prévoit différentes améliorations dont beaucoup plus d'adresses (on dit parfois spectaculairement qu'il y en a 340282366920938463463374607431768211456 au lieu de 4294967296, mais ce nombre n'a pas beaucoup de sens vu que ce sont des bits qu'on attribue plutôt que des adresses), a été définie il y a une douzaine d'années et est — très lentement — en cours d'adoption. Tous les différents systèmes d'exploitation modernes sont maintenant compatibles IPv6, ainsi que beaucoup de logiciels ; les fournisseurs d'accès commencent timidement à s'y mettre, les sites Web expérimentent, mais il reste encore beaucoup de chemin à faire (mon pipotron me souffle qu'il ne doit même pas y avoir 0.001% du Web qui soit accessible en IPv6).
Pour savoir simplement si vous avez une connectivité IPv6, essayez de vous connecter à IPv6.org et on vous dira soit you are using IPv6 soit you are using IPv4 selon le cas ; vous pouvez aussi aller sur la page du projet Kame et voir si la tortue est animée (auquel cas vous utilisez IPv6) ; ou encore, essayer de vous connecter à ipv6.google.com.

[#2] Ce chiffre ne me surprend pas : je pense que Free a fait énormément de bien à l'utilisation d'IPv6 en l'activant sur ses réseaux.

(mardi)

Remarques sur le mode de scrutin

Il n'est pas fréquent que je dise du bien d'un mode de scrutin qui est utilisé dans la vie réelle, mais celui qui sert à élire les conseillers municipaux (donc, indirectement, les maires) me semble globalement bon : il s'agit d'un scrutin à la proportionnelle, avec prime à la majorité pour garantir que la stabilité de l'exécutif municipal. Je trouve que cette prime à la majorité (50%, surtout que c'est arrondi à l'entier supérieur) est un peu excessive, cependant : une prime de 25% comme c'est le cas pour les régionales suffirait à assurer une majorité des sièges dès que la liste arrivée en tête a au moins 33% des voix, ce qui doit être à peu près tout le temps le cas (il faudrait une quadrangulaire bien serrée pour faire moins) ; peut-être qu'une prime de 33% serait un compromis. Quoi qu'il en soit, le principe est que la liste ayant obtenu le plus de voix se voit attribuer d'emblée un certain nombre de sièges et que les autres sont répartis à la proportionnelle (entre toutes les listes, y compris celle qui a déjà eu la prime en question). En détails :

On procède à un premier tour de scrutin. Si aucune liste n'obtient la majorité absolue à ce premier tour (c'est-à-dire strictement plus que la moitié des suffrages exprimés), on procède à un second tour de scrutin : pour maintenir sa liste au second tour, il faut avoir recueilli au moins 10% des suffrages exprimés ; les listes ayant obtenu moins de 10% mais au moins 5% des suffrages exprimés peuvent fusionner avec une autre liste (cette fusion est libre, et si elle a lieu l'ordre des candidats peut changer ; en revanche, il n'est pas permis que certains candidats d'une liste du premier tour fusionnent avec une certaine liste et d'autres avec une autre).

Une fois le ou les tours de scrutins effectués, on attribue la moitié des sièges à la liste ayant obtenu le plus de voix : la moitié est arrondue à l'entier supérieur s'il y a au moins cinq sièges à pourvoir, à l'entier inférieur s'il y en a trois ou moins. Pour attribuer le reste des sièges, on écarte les listes qui ont obtenu moins de 5% des voix et on attribue entre toutes les autres listes (y compris celle qui a eu la prime à la majorité) les sièges à la proportionnelle avec la méthode de la plus forte moyenne.

La méthode de la plus forte moyenne (de d'Hondt) signifie qu'on donne d'emblée à chaque liste un nombre de sièges proportionnel à son nombre de voix, arrondi à l'entier inférieur, puis on attribue chaque siège restant à pourvoir selon la règle « bayesienne » suivante : on divise le nombre de voix de chaque liste par un de plus que le nombre de sièges qu'elle a déjà obtenus (de ceux qui sont attribués à la proportionnelle, évidemment !), et la liste qui a le plus grand quotient obtient le siège (ce qui signifie que pour le siège suivant son quotient sera plus petit, évidemment).

Les sièges sont attribués dans l'ordre des listes (donc le premier de la liste aura un siège dès que la liste en reçoit un, le second sera servi en deuxième, etc., et — puisque les listes sont de même longueur que le nombre de sièges à pourvoir — le dernier n'aura de siège que si la liste obtient tous les sièges).

Le maire est ensuite élu par le conseil municipal en son sein.

S'agissant de Paris, Lyon et Marseille, les choses sont plus compliquées car les élections sont sectorisées : les listes sont déposées dans un secteur (qui correspond à un arrondissement dans le cas de Paris et Lyon, à deux arrondissements dans le cas de Marseille), et elles servent à la fois à élire les conseillers municipaux (appelés conseillers de Paris dans le cas de Paris) et les conseillers d'arrondissement du secteur. Chaque liste comporte un nombre de noms égal au nombre de conseillers municipaux plus d'arrondissement attribués au secteur (les conseillers municipaux élus dans le secteur siègent au conseil d'arrondissement, mais on ne les appelle pas conseillers d'arrondissement : le Club Contexte vous remercie de votre attention !). On répartit de la même façon (à la proportionnelle avec prime à la majorité comme expliqué ci-dessus) les conseillers municipaux pour le secteur et les conseillers d'arrondissement[#] : les premiers candidats des listes deviennent conseillers municipaux et les suivants deviennent conseillers d'arrondissement.

Le conseil municipal élit en son sein le maire de la ville, les conseils d'arrondissement élisent les maires d'arrondissement parmi les conseillers municipaux pour le secteur.

Quels que soient les détails mineurs, je trouve que c'est un bon système, et je serais très favorable à ce que l'Assemblée nationale soit élue selon le même mécanisme : disons, un scrutin à la proportionnelle avec prime à la majorité dans chaque région, et on regroupe tout ça en une seule assemblée : ça combinerait les mérites du scrutin à la proportionnelle pure (permettre aux petits partis d'être un peu représentés, éviter que les députés cultivent trop « leur » circonscription au détriment de la représentation nationale) avec certains de ceux du scrutin majoritaire par circonscription[#2] (avoir un minimum d'assise territoriale, et favoriser la formation des majorités stables). Le collège électoral qui élit le président des États-Unis serait aussi bien moins absurde s'il était formé selon ce principe (avoir un semblant de proportionnelle dans chaque état au lieu d'attribuer tous les grands électeurs à l'unique candidat arrivé en tête pour l'État[#3]).

Il y a cependant un point sur lequel on pourrait nettement améliorer le système proportionnel tel qu'il est utilisé en France, c'est qu'au lieu d'élire bêtement les conseillers dans l'ordre des listes, on pourrait utiliser un des divers systèmes qui permettent d'améliorer les choses par rapport à ça — c'est-à-dire d'éviter que l'ordre d'élection soit fixé par la hiérarchie d'un parti mais de donner aux électeurs un poids là-dedans. Le système du vote unique transférable a l'air d'avoir des vertus intéressantes, mais il est sans doute difficile à appliquer en pratique, et je ne suis pas sûr de voir quel système proportionnel il devient si on fixe des listes toutes disjointes (ni s'il y a un système de ce genre qui donne exactement le système proportionnel par la méthode des plus fortes moyennes si on l'applique à des listes fixées).

[#] Une question un peu byzantine est de savoir si on attribue les sièges séparément pour les conseillers municipaux et les conseillers uniquement d'arrondissement ou bien ensemble pour le conseil d'arrondissement (composé des deux). Cela peut faire une différence pour des raisons d'arrondi. Et il se trouve que la différence a effectivement lieu dans le 2e arrondissement de Paris : les 3 conseillers de Paris pour l'arrondissement sont acquis à la liste d'union de la gauche qui a obtenu 68.34% des suffrages obtenus, et selon qu'on procède ensuite à l'élection des 10 conseillers d'arrondissement au sens strict ou bien qu'on considère que ces 3 conseillers font déjà partie d'une élection de 13=3+10 personnes en bloc, cela donne à l'unique liste adverse soit 1 seul conseiller d'arrondissement (attribué à la proportionnelle sur les 5←10 sièges qui le sont) soit 2 (attribués à la proportionnelle sur les 6←13 sièges qui le sont). D'après les chiffres du ministère de l'intérieur, c'est la première solution qui est la bonne puisqu'ils ne donnent qu'un conseiller d'arrondissement à la liste Lekieffre : i.e., on élit successivement, et avec les mêmes proportions, les conseillers de Paris pour l'arrondissement et les conseillers d'arrondissement au sens strict. J'aimerais bien savoir qui a dû se gratter la tête pour décider pour décider quelle était l'interprétation correcte de la phrase absolument sibylline du Code électoral ! J'aimerais aussi savoir si c'était expressément voulu ou si personne ne s'est posé la question ; en tout cas, ce n'était certainement pas le bon choix : le mode d'élection proportionnel à la plus forte moyenne a des propriétés mathématiques intéressantes et sympathiques (pas de paradoxe de l'Alabama) notamment si, justement, on considère une élection comme emboîtée dans une autre (par exemple, on pourrait élire à la proprotionnelle, simultanément, le présidium d'une assemblée et le reste de l'assemblée, en commençant par pourvoir les sièges du présidium : ce serait une erreur de procéder à deux scrutins séparés, il faudrait continuer à pourvoir les sièges avec les moyennes déjà calculées — et l'élection simultanée du conseil de Paris et des conseils d'arrondissement sont le cas d'école d'application de ces propriétés). Mais bon, il faut reconnaître que ça fait peu souvent une différence.

[#2] On pourrait aussi à cet égard parler du système allemand (Sie haben zwei Stimmen) ; mais les petits malicieux pourraient faire remarquer que celui-ci combine les inconvénients du système proportionnel (les répartitions des sièges sont, in fine, proportionnelles, donc il peut très bien ne pas y avoir de majorité — d'ailleurs…) et du système majoritaire par circonscription (puisque les élus du Bundestag qui ont mandat direct dépendent bien de leur circonscription). Le système allemand avec une prime à la majorité serait peut-être un système raisonnable ; mais en fait, la stabilité ministérielle allemande a surtout l'air de venir du fait que les motions de censure doivent être constructives (i.e., rassembler les voix autour d'un nouveau nom de chancelier).

[#3] Les États-Unis sont particulièrement peu friands de scrutins de listes et, par conséquent, de représentation proportionnelle. Pourtant, il y a un domaine où ils ont effectivement une représentation proportionnelle : c'est entre les États à la Chambre des Représentants (pour fixer le nombre de sièges de chaque État à partir des chiffres du recensement). Avec un système différent de celui qui est employé en France, cependant, qui, pour dire les choses grossièrement, privilégie plutôt l'absence de distorsions entre les États que la qualité de la représentation d'ensemble.

(dimanche)

J'apprends à compter jusqu'à ψ(εΩ+1) et à dompter les hydres

Si j'ai été silencieux pendant deux semaines c'est qu'aussitôt abandonné le nim épicé j'ai été saisi d'une autre obnubilation intellectuelle (et qui me revient périodiquement[#]), c'est celle des ordinaux dénombrables : j'avais déjà écrit des articles de vulgarisation à ce sujet (celui-ci il y a très longtemps et celui-ci il y a un peu moins longtemps, le premier ayant même été traduit en chinois[#2] ; et j'ai beaucoup contribué à l'article de Wikipédia en anglais), cette fois je me suis intéressé aux notations ordinales — c'est-à-dire, en gros, la façon de donner un nom aux (plus petits des) ordinaux dénombrables, en essayant d'aller le plus loin possible, tout en sachant très bien qu'on ne pourra pas atteindre tous les ordinaux dénombrables (ni même tous les ordinaux récursifs). Et j'ai produit les jolis dessins que voici[#3] et surtout ce texte explicatif dont je vais dire un peu plus.

[Ajout : voir une entrée ultérieure, qui peut servir d'introduction à la suite.]

Quand on entend parler des ordinaux pour la première fois, on entend parler de ω, de ωω, de ωωω, et souvent de la limite de tout ça, qui est ε0 (qui le plus petit ordinal vérifiant ωξ = ξ, c'est-à-dire le plus petit point fixe de ξ↦ωξ). Manipuler les ordinaux jusqu'à ε0 (pour les ajouter, les multiplier ou les exponentier) est facile si on travaille en forme normale de Cantor (c'est-à-dire, informellement, en base ω) itérée pour les exposants ; à partir de ε0 ça devient un chouïa plus compliqué parce qu'il y a des égalités qui ne sautent pas immédiatement aux yeux (comme le fait que ωε0+1 = ε0·ω), mais on finit par s'y habituer. Le problème est plutôt de monter aussi loin que possible : si ε1 est la prochaine solution de ωξ = ξ, et ainsi de suite, jusqu'où ira-t-on ? On pourrait appeller ζ0 la limite de la suite ε0, εε0, εεε0, c'est-à-dire le premier point fixe de ξ↦εξ, on peut continuer à jouer ainsi avec les lettres grecques qui énumèrent les points fixes les unes des autres, si bien qu'on finit par avoir besoin d'un alphabet grec transfini : c'est ce qu'on appelle le schéma φ de Veblen (à deux variables, pour commencer), chaque rang énumérant les points fixes du rang précédent. Seulement, on arrive à court de ce schéma aussi lorsqu'on tombe sur la première lettre grecque qui est, pour ainsi dire, son propre rang dans l'alphabet. C'est cet ordinal (toujours dénombrable, bien sûr) qu'on appelle l'ordinal de Feferman-Schütte (et c'est la limite des ordinaux pour lesquels le schéma de Veblen à deux variables fournit des notations).

(dimanche)

Le jeu de nim épicé

Je disais récemment que les idées scientifiques ont tendance à ressembler aux tamagotchis : on commence à les élever et rapidement elles vous accaparent l'esprit en demandant sans arrêt votre attention.

Je réfléchissais à la théorie combinatoire[#] des jeux quand je suis tombé sur l'idée du jeu suivant (qui a certainement déjà été décrit et étudié, mais il est difficile de trouver sous quel nom), que j'appellerai le jeu de nim épicé.

Tout d'abord je rappelle ce qu'est le jeu de nim usuel : il s'agit d'un jeu (impartial, à connaissance complète, à deux joueurs) extrêmement simple, dans lequel l'état du jeu est donné par un certain nombre de lignes de bâtonnets (ou quelconques autres jetons : tas de pièces, rangées d'alumettes, ce que vous voudrez ; il en existe aussi des avatars un petit peu moins évidents où, par exemple, on avance des pions sur un échiquier sans avoir le droit de les reculer). Seul compte le nombre de bâtonnets présent sur chaque ligne (il n'y a pas d'ordre, pas de structure supplémentaire). La règle du jeu est simplissime : les joueurs jouent tour à tour et chacun, quand c'est son tour, peut et doit retirer des bâtonnets situés sur une ligne — il doit en retirer au moins un et peut en retirer autant qu'il veut, y compris vider (et donc supprimer) la ligne, mais il ne peut en un tour retirer des bâtonnets que d'une seule ligne (de son choix). Normalement, le joueur qui ne peut plus jouer a perdu (i.e., celui qui retire le dernier bâtonnet a gagné, puisque son adversaire est dans l'impossibilité de jouer) : en fait, la version misère, où celui qui retire le dernier bâtonnet perd, est peut-être plus commune pour le jeu de nim, mais elle est en fait très semblable[#2] et moins intéressante mathématiquement.

Dans n'importe quel jeu de ce genre (i.e., un jeu impartial, à connaissance complète, à deux joueurs, et qui termine toujours en temps fini sur le gain d'un des joueurs avec par convention perte du joueur qui ne peut plus jouer), l'un des deux joueurs a forcément une stratégie gagnante. En fait, on peut définir deux sortes de positions du jeu : les positions dites nulles[#3] — qui sont celles à partir desquelles le second joueur a une stratégie gagnante —, et les autres (généralement les plus nombreuses). La définition (récursive !) est qu'une position nulle est une position qui ne conduit qu'à des positions non nulles (y compris si elle ne conduit à rien du tout, car alors le joueur qui vient de jouer à gagné) et, a contrario, une position non nulle est une position qui conduit à au moins une position nulle. La stratégie gagnante consiste à jouer, autant que c'est possible, pour mettre le jeu dans une position nulle (auquel cas le joueur adverse sera obligé de jouer pour aller dans une position non nulle, donc on sera assuré de pouvoir jouer vers une position nulle, et ainsi de suite : comme on peut toujours gagner, on ne peut pas perdre). Connaître la stratégie gagnante revient donc à identifier les positions nulles (pour pouvoir jouer vers elles).

Dans le cas du jeu de nim, elles ont une description mathématiquement simple : sont nulles les positions telles que le « ou exclusif » du nombre de bâtonnets de chaque ligne (écrits en binaire) soit nul. Par exemple, la position de départ habituelle, (1,3,5,7) (ce qui signifie : un bâtonnet sur une ligne, trois sur une autre, cinq sur une troisième, et sept sur la dernière ligne) est nulle car 001⊕011⊕101⊕111=000 : cela signifie qu'au jeu de nim usuel, à partir de cette position, le joueur qui ne commence pas peut gagner le jeu à coup sûr (par exemple, si le premier joueur retire deux bâtonnets de la dernière ligne, c'est-à-dire joue vers (1,3,5,5), position non nulle, on répondra vers (1,1,5,5), position nulle, et il est d'ailleurs clair qu'on a alors une stratégie gagnante en reproduisant les coups d'une paire de lignes (1,5) sur l'autre).

J'en viens donc au jeu de nim épicé : la différence avec le jeu nim normal est qu'il existe deux sortes de lignes, des lignes épicées et des lignes normales (ou fades). La règle du jeu est la même (on peut retirer autant de bâtonnets qu'on veut, mais d'une ligne seulement) avec la seule différence que lorsqu'un joueur retire des bâtonnets d'une ligne épicée, son adversaire ne peut pas en faire autant au coup immédiatement après (il doit retirer des bâtonnets d'une ligne fade — et s'il n'en reste aucun, il a perdu). Autrement dit, on ne peut consommer deux coups de suite des bâtonnets épicés. Une position du jeu est déterminée par le nombre de bâtonnets dans les lignes de chaque sorte (je les écrirai en commençant par les lignes fades) et par le fait que le coup immédiatement précédet ait été épicé ou non.

Exemple : en commençant sur (1,2,11;4;4), c'est-à-dire qu'il y a trois lignes fades avec 1, 2 et 11 bâtonnets, et deux lignes épicées avec 4 bâtonnets chacune, le premier joueur pourrait jouer vers (1,2,5;4;4), le second joueur répliquerait avec (1,2,5;4,2)H (le H, comme hot signifiant qu'on vient de jouer épicé, donc que le coup suivant sera forcément fade), le premier joueur tenterait maladroitement (1,2,3;4,2), ce à quoi on rétorquera (1,2,3;2,2)H, et une tentative désespérée vers (1,2,1;2,2) provoquera inévitablement la réplique (1,2,1;2)H, et il n'y a plus de doute sur qui a gagné.

La question à cent zorkmids est donc : quelles sont les positions nulles du jeu de nim épicé ? Peut-on les décrire de façon synthétique comme pour le jeu de nim usuel ?

Je n'ai que des réponses partielles à cette question. Je peux facilement faire produire à mon ordinateur des tables gigantesques de positions nulles, mais ensuite trouver la logique ressemble à un test d'intelligence. Et si c'est un test d'intelligence, j'ai échoué : j'ai trouvé beaucoup de motifs partiels, mais aucune decription complète.

Il est clair que si le nombre total de bâtonnets épicés est strictement supérieur au nombre total de bâtonnets fades (et que la position n'est pas chaude, i.e., qu'on peut jouer épicé), alors la position est non nulle : en effet, le premier joueur a la stratégie gagnante consistant à manger les épices, c'est-à-dire retirer un quelconque bâtonnet épicé, auquel cas son adversaire devra en retirer un fade, puis le premier joueur retire de nouveau un épicé, et ainsi de suite jusqu'à épuisement des fades auquel moment le second joueur perd. Dans « beaucoup » de cas, une position nulle s'obtient en complétant une telle position jusqu'à ce que le nombre total de bâtonnets fades égale le nombre total d'épicés : notamment, s'il y a une seule ligne fade, il est facile de voir que la condition de nullité est précisément que le nombre de bâtonnets de cette ligne soit égal au nombre total de bâtonnets épicés ; il en va de même si les épicés sont dans des lignes d'un seul bâtonnet chacune (i.e., de nouveau, quelle que soit la répartition des fades, la condition de nullité sera que les fades soient aussi nombreux que les épicés). Mais parfois, il faut plus de fades : par exemple, s'il y a exactement deux lignes de fades dont une avec un seul bâtonnet, la condition de nullité est que le nombre total de fades soit deux de plus que le nombre total d'épicés si toutes les lignes épicées ont un nombre pair de bâtonnets (alors que c'est égalité s'il y a une ligne épicée avec un nombre impair de bâtonnets) — je sais le démontrer, mais je ne sais pas le généraliser correctement. Je ne sais pas « expliquer » de façon satisfaisante le fait que (2,9;6,4) ou (3,8;6,4) ou (1,2,8;6,4) (et pas (2,8;6,4) ou (2,n;6,4) pour un quelconque autre n) soient des positions nulles. C'est mystérieux : je cherche encore le motif, mais je commence à douter de son existence…

Évidemment, le jeu de nim se prête à quantité d'autres variations (on pourrait interdire de reprendre des bâtonnets de la ligne qui vient d'être diminuée, ou bien seulement pour certaines lignes, ou avoir plusieurs sortes d'épices, que sais-je encore…). Mais celle-ci m'est venue à l'esprit dans le cours d'une réflexion plus générale, alors maintenant elle m'obsède.

[#] Le terme combinatoire est là pour insister sur le fait qu'il ne s'agit pas de la théorie des jeux dans le sens où on l'entend d'habitude (jeux à la von Neumann, équilibres de Nash, tout ça) mais de jeux à information complète. Pour la bible sur le sujet, voir le très exotique Winning Ways de Berlekamp, Conway et Guy. On peut dire que c'est Conway qui a inventé la théorie combinatoire des jeux partiaux, la théorie combinatoire des jeux impartiaux — théorie de Sprague-Grundy, par exemple — est plus ancienne.

[#2] Pour jouer à la version misère, si on connaît la stratégie optimale de la version normale du nim décrite plus loin, il suffit de jouer comme pour la version normale sauf lorsqu'on ne va laisser que des lignes avec (zéro ou) un bâtonnet : à ce moment-là on en laisse un de moins (ou un de plus).

[#3] Le choix du mot nul, pour les jeux où le second joueur a une stratégie gagnante, pourra sembler bizarre. L'explication est que si on fait la somme d'un tel jeu et d'un jeu G quelconque — la somme étant à comprendre au sens où chaque joueur peut jouer dans une composante quelconque de la somme — alors la somme en question a la même caractéristique que le jeu G. Ou encore, les positions nulles sont celles dont la fonction de Grundy est nulle.

Continue to older entries. / Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2017 Jan 2017 Feb 2017
2016 Jan 2016 Feb 2016 Mar 2016 Apr 2016 May 2016 Jun 2016 Jul 2016 Aug 2016 Sep 2016 Oct 2016 Nov 2016 Dec 2016
2015 Jan 2015 Feb 2015 Mar 2015 Apr 2015 May 2015 Jun 2015 Jul 2015 Aug 2015 Sep 2015 Oct 2015 Nov 2015 Dec 2015
2014 Jan 2014 Feb 2014 Mar 2014 Apr 2014 May 2014 Jun 2014 Jul 2014 Aug 2014 Sep 2014 Oct 2014 Nov 2014 Dec 2014
2013 Jan 2013 Feb 2013 Mar 2013 Apr 2013 May 2013 Jun 2013 Jul 2013 Aug 2013 Sep 2013 Oct 2013 Nov 2013 Dec 2013
2012 Jan 2012 Feb 2012 Mar 2012 Apr 2012 May 2012 Jun 2012 Jul 2012 Aug 2012 Sep 2012 Oct 2012 Nov 2012 Dec 2012
2011 Jan 2011 Feb 2011 Mar 2011 Apr 2011 May 2011 Jun 2011 Jul 2011 Aug 2011 Sep 2011 Oct 2011 Nov 2011 Dec 2011
2010 Jan 2010 Feb 2010 Mar 2010 Apr 2010 May 2010 Jun 2010 Jul 2010 Aug 2010 Sep 2010 Oct 2010 Nov 2010 Dec 2010
2009 Jan 2009 Feb 2009 Mar 2009 Apr 2009 May 2009 Jun 2009 Jul 2009 Aug 2009 Sep 2009 Oct 2009 Nov 2009 Dec 2009
2008 Jan 2008 Feb 2008 Mar 2008 Apr 2008 May 2008 Jun 2008 Jul 2008 Aug 2008 Sep 2008 Oct 2008 Nov 2008 Dec 2008
2007 Jan 2007 Feb 2007 Mar 2007 Apr 2007 May 2007 Jun 2007 Jul 2007 Aug 2007 Sep 2007 Oct 2007 Nov 2007 Dec 2007
2006 Jan 2006 Feb 2006 Mar 2006 Apr 2006 May 2006 Jun 2006 Jul 2006 Aug 2006 Sep 2006 Oct 2006 Nov 2006 Dec 2006
2005 Jan 2005 Feb 2005 Mar 2005 Apr 2005 May 2005 Jun 2005 Jul 2005 Aug 2005 Sep 2005 Oct 2005 Nov 2005 Dec 2005
2004 Jan 2004 Feb 2004 Mar 2004 Apr 2004 May 2004 Jun 2004 Jul 2004 Aug 2004 Sep 2004 Oct 2004 Nov 2004 Dec 2004
2003 May 2003 Jun 2003 Jul 2003 Aug 2003 Sep 2003 Oct 2003 Nov 2003 Dec 2003