Journal Le jeu de la vie: conférence de Jean-Paul Delahaye

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
45
1
mai
2012

Je suppose que vous connaissez déjà Jean-Paul Delahaye via ses chroniques mensuelles dans le magazine "Pour la Science". C'est un spécialiste de la théorie de la complexité mais il touche également de nombreux autres domaines et notamment la théorie des automates cellulaires.

Ce journal n'a pour but que de signaler une conférence portant sur le jeu de la vie, la plus célèbre variante des automates cellulaires, et qui a été donnée par Jean-Paul Delahaye en mars dernier.
Le site de Lille1.tv propose de visionner la conférence au format flash mais, et c'est heureux, on peut également télécharger la vidéo dans divers formats (dont H264 et Theora).

J'ai trouvé cette conférence absolument fascinante. Je connaissais déjà un peu le jeu de la vie pour avoir lu divers articles de vulgarisation au fil des années, mais ici l'exposé est très vivant et se base sur les démonstrations visuelles des diverses configurations.
On découvre donc les "glisseurs" et les "lance-glisseurs", les "cendres", les "usines" et les "vaisseaux" (positifs ou négatifs). On parle également des problèmes ouverts qui sont parfois très simples (existe-il une configuration périodique de période 19 ?). Jean-Paul Delahaye nous montre des configurations absorbantes et des configurations qui remplissent le plan, des vaisseaux qui s'attaquent à coup de lance-glisseurs et d'autres qui fuient à des vitesses différentes.
La visite s'achève par une sorte de chef-d’oeuvre puisqu'il s'agit d'une configuration permettant de calculer, via la technique du crible d’Ératosthène, tous les nombres premiers !

En définitive, ce qu'on retient de cette vidéo, c'est que la complexité générée par cet automate cellulaire aux règles simplissimes est ahurissante. A partir de deux règles déterministes ultra-basiques c'est tout un monde chatoyant qui se dévoile petit à petit à l'aide des recherches théoriques et de l'exploration par ordinateur.
Bien entendu, même si la conférence en parle à peine, ce jeu de la vie à des implications philosophiques évidentes qui réjouissent l'athée que je suis. Comme dans la théorie de Darwin, on voit ici que du simple peut naitre le complexe et qu'il n'est nul besoin d'un "concepteur" pour expliquer la complexité qui nous entoure.

Le logiciel utilisé par Jean-Paul Delahaye se nomme "Golly" et c'est un logiciel libre sous licence GPL. Bien entendu je me suis empressé de l'installer depuis les dépôts de ma distribution (Debian Squeeze) et je fais joujou avec depuis des heures.
Je ne saurais trop vous conseiller de faire de même, ce ne sera pas du temps de perdu (sauf si vous avez à peine commencé à rédiger une news noyau et qu'on en est déjà à la rc-5).

  • # John Conway

    Posté par  (site web personnel) . Évalué à 7.

    Le jeu de la vie est en effet très sympa à voir mais aussi à coder.

    Ça ce fait très bien et très facilement. Dans l'idée :

    On se place dans une grille n * m.
    Chaque case est à l'état binaire, soit 1 pour vivant, soit 0 pour mort.

    On étudie alors le nombre de voisins vivants sur les huit possibles que possède chaque case.
    Il n'y a que deux règles :

    1) L'apparition de la vie n'est possible que s'il y a exactement trois voisins vivants autour d'une case morte.

    2) L'état de la case stagne à l'itération suivante s'il y a deux ou trois voisins vivants autour

    Tout le reste entraine la mort.

    Il y a plusieurs manière de coder et les plus simple ne sont pas forcement les plus efficaces, mais en gros il faut tableau de booléen en entrée et une sortie graphique avec des " " et des "*" sur la console.

    En tout cas, c'est un sujet que j'adore.

    La réalité, c'est ce qui continue d'exister quand on cesse d'y croire - Philip K. Dick

    • [^] # Re: John Conway

      Posté par  (Mastodon) . Évalué à 4.

      et Dieu vit dans le bug ? ;-)

    • [^] # Re: John Conway

      Posté par  (site web personnel) . Évalué à 4.

      C'est malin, à cause de ton commentaire je me suis mis à coder le jeu de la vie en HTML 5 !

      Bon, il me reste pas mal de choses à faire et à optimiser mais j'ai déjà un truc qui fonctionne bien sous Google Chrome ou Firefox en version récente et surtout on peut importer des milliers de modèles déjà existants sur le web dans divers formats et en sauvegarder des nouveaux dans la mémoire locale du navigateur (local storage). Voici le lien temporaire : http://share.infernal-quack.net/_temp/game_of_life.html

      L'association LinuxFr ne saurait être tenue responsable des propos légalement repréhensibles ou faisant allusion à l'évêque de Rome, au chef de l'Église catholique romaine ou au chef temporel de l'État du Vatican et se trouvant dans ce commentaire

      • [^] # Re: John Conway

        Posté par  (site web personnel) . Évalué à 3.

        Super idée ! Merci d'avoir mis ça à disposition.

        • [^] # Re: John Conway

          Posté par  (site web personnel) . Évalué à 2.

          Le disque dur de mon serveur Kimsufi ayant décidé de mourir aujourd'hui, j'ai migré le jeu de la vie sur mon compte Free. J'ai commencé à changer l’algorithme pour éviter de parcourir toute la grille et pour gérer les univers infini mais mon implémentation fait que c'est plus lent qu'avant. Il s'avère que l'émulation de tableaux associatifs avec des objets n'est pas idéal. Je compte repasser aux tableaux mais avec 4 tableaux selon la positivité ou non des coordonnées.

          Ancien algo assez rapide : http://shift.free.fr/game_of_life2.html
          Nouvel algo plus lent mais univers infini possible : http://shift.free.fr/game_of_life.html

          L'association LinuxFr ne saurait être tenue responsable des propos légalement repréhensibles ou faisant allusion à l'évêque de Rome, au chef de l'Église catholique romaine ou au chef temporel de l'État du Vatican et se trouvant dans ce commentaire

      • [^] # Re: John Conway

        Posté par  . Évalué à 2.

        Vieux souvenir.
        Je me souviens d'avoir programmé un jeu de la vie très simple vers 1978-80 et en BASIC. On y voyait déjà des perspectives intéressantes à cette partie de l'informatique sans pouvoir bien les définir.
        À l'époque on pensait surtout à des applications dans la robotique. Mais cette dernière a pris une autre direction tout en s'inspirant vaguement de ce jeu.
        Je vois que cela a beaucoup beaucoup évolué.

  • # "A new kind of science"

    Posté par  (site web personnel) . Évalué à 3.

    Cela me rappelle le livre au titre pompeux et au contenu très intéressant de Wolfram.

    Wolfram a tenté dans ce livre de construire une algèbre des automates cellulaires pour en découvrir les "nombres premiers". Il a découvert que cette liste était finie, et qu'elle en comptait 101.

    (Je possède une traduction en français du livre, qui a été autorisé par Wolfram. La diffusion de ce livre hors circuit de commerce ne le dérange pas)

    « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker

  • # Un super pédagogue

    Posté par  (site web personnel) . Évalué à 4.

    J'ai eu la chance d'avoir Jean-Paul Delahaye comme professeur et c'est un très bon pédagogue : ses cours sont passionnants, ils passent très vite, on y apprend plein de trucs et on en sort avec plein de questions en tête. Bref, une conférence à voir absolument :)

    • [^] # Re: Un super pédagogue

      Posté par  . Évalué à 2.

      J'ai eu un excellent prof de math en première E pendant l'année 1973/74, à Compiègne, qui s'appelait Delahaye, à coup sûr, Jean-Paul il me semble, et qui ressemblait au personnage sur la photo de la page Wikipédia. Mais c'est troublant : cette année-là Jean-Paul Delahaye avait juste une licence, et dans notre filière nous avions le privilège d'avoir des professeurs agrégés en math et en physique-chimie. Je ne sais pas dans quel genre de faille je suis tombé. Ontologique ? Spatio-temporelle ?

      /ma vie

  • # Triangle de Sierpiński

    Posté par  . Évalué à 2.

    Lorsque j'ai vu la génération du triangle de Sierpiński, ça m'a fait pensé à une autre conférence qui n'était pas sur le jeu de la vie, mais sur le triangle de Pascal dans lequel cette célèbre fractale se cache également : Quoi de neuf sur le Triangle de Pascal ?

    En tout cas, merci pour le lien, c'était très intéressant, et ça m'a donné envie de me replonger dans ce jeu que j'ai déjà programmé plusieurs fois pour le plaisir.

  • # Complexité

    Posté par  (site web personnel) . Évalué à -1.

    Un peu sur le même principe que le jeu de la vie, il existe le jeu de go. Des règles extrêmement simple qui génèrent un jeu extrêmement complexe !

    • [^] # Re: Complexité

      Posté par  . Évalué à 1.

      A noter que la complexité du jeu de Go s'exprime surtout par son plateau de jeu gigantesque (19 par 19).

      Dès que l'on réduit sa taille (vers 13 par 13, voire 7 par 7), les coups deviennent déterministes et l'on applique alors les joseki appris par coeur.

      • [^] # Re: Complexité

        Posté par  . Évalué à 2.

        Je suis pas sûr de comprendre comme la taille d'un problème peut le faire passer de déterministe à non déterministe.
        C'est par rapport à une capacité de calcul (humain ou ordinateur ?

    • [^] # Re: Complexité

      Posté par  . Évalué à 7.

      Pas grand chose à voir, le jeu de la vie (qui est mal nommé puisqu'on n'y joue pas) est un automate cellulaire, une fois la configuration de départ choisie le déroulement est strictement déterministe et ne fait plus intervenir l'utilisateur.

      Le go est un vrai jeu où deux adversaires s'affrontent et où, à moins de faire s'affronter deux algorithmes parfaitement déterministes, le coup suivant d'un joueur n'est pas connu à l'avance (bien que prévisible dans une certaine mesure).
      En mathématique cela relève de la théorie des jeux, qui est une branche assez différente de celle des automate cellulaires.

  • # Athée ?

    Posté par  . Évalué à 1.

    Justement, on peut y voir une interprétation d'une divinité sur un univers

    Les règles simples existent. Dieu est initiateur de l'impulsion originel. En l'occurence, l'utilisateur du jeu de la vie devient le Dieu de cet univers :).

    • [^] # Re: Athée ?

      Posté par  (site web personnel) . Évalué à 8.

      Je doute que beaucoup de croyants adhèrent à cette interprétation d'un Dieu qui se contente de définir les règles physiques initiales et puis qui laisse ensuite se dérouler l'histoire de l'Univers.
      Les religions postulent toute une divinité interventionniste à laquelle on peut s'adresser pour qu'elle agisse. Dire que Dieu est seulement "l'initiateur de l'impulsion originelle" c'est simplement rebaptiser les lois de la physique.

      • [^] # Re: Athée ?

        Posté par  (Mastodon) . Évalué à 2. Dernière modification le 02 mai 2012 à 14:19.

        (danke pour ce journal)

        rebaptiser les lois de la physique.

        ça, les religieux ne se sont pas gênés pour le faire, au fil de l'histoire. et suivis par une cohorte de scientifiques, d'ailleurs, qui assainaient les vérités du jour comme verités absolues. il y a même eu quelques morts célèbres, il me semble, parmi les scientifiques cherchant, et parfois remettant en cause le dogme. :-(

        Rebaptiser les lois des tables, c'est plus nouveau :-) : Soit remettre à jour la manière dont "on" perçoit, ou peut percevoir, Dieu, afin que cela colle avec les connaissances d'aujourd'hui. Mais c'est passionnant, parceque c'est aujourd'hui plus un moteur comme un autre, voire moins qu'un autre, pour avancer et (du moins, à mon niveau) se poser des questions. Il y a des gens passionnants qui posent cela très bien, en ce moment en biologie. Bref le croisement, la rencontre, de nombreuses discplines jusqu'alors séparés par des frontières purement théoriques (voir, auparavant, purement théologiques) est absolument passionnant. Même pour le péquin moyen : suivre les découvertes des frontières, des moments où telle échelle écrit elle même l'échelle suivante. Le jeu de la vie en est une illustration compréhensible :-)

      • [^] # Re: Athée ?

        Posté par  . Évalué à 4.

        Déjà, "croire" n'implique pas forcement adhérer à une religion ou l'un des grands courants religieux.

        Enfin, comme tu dis "un Dieu qui se contente de définir les règles physiques initiales et puis qui laisse ensuite se dérouler l'histoire de l'Univers." , cela a déjà été théoriser, cela s'appelle le deisme

        Pour l'interventionnisme, on peut l'envisager de plein de façon. soit il est omnipotent et il a déjà prévu une grand partie des événements, un peu comme un joueur de billard.
        Soit il(s) intervient(nent) sur le monde sans anticipation dans un but qui ne nous ai pas forcement connu.

        Bref, tout cela pour dire que "le jeu de la vie" ne prouve ni l'absence de dieu, ni leur(s) présence(s).

      • [^] # Re: Athée ?

        Posté par  (Mastodon) . Évalué à 4.

        Dire que Dieu est seulement "l'initiateur de l'impulsion originelle"

        TeX -> LaTeX -> LuaTex ?

        `

    • [^] # Re: Athée ?

      Posté par  . Évalué à 5.

      Bof, cherche pas de toute manière, ni la religion ni la science ne sont pas capable de répondre aux questions de base: "pourquoi y a t'il quelque chose plutôt que rien?", "comment ça a commencer?".

      Bon la religion prétend répondre à "comment ça a commencer?" (Dieu a crée tout), mais c'est juste une arnaque(comme le reste des "réponses" des religions) car on retombe sur "comment Dieu a été créer?".

      • [^] # Re: Athée ?

        Posté par  (Mastodon) . Évalué à 10.

        "comment Dieu a été créer?".

        Demande à Chuck Norris ?

        • [^] # Re: Athée ?

          Posté par  . Évalué à 6.

          On ne pose pas de question à Chuck Norris, c'est lui qui donne les réponses.

  • # Une implémentation documentée de HashLife en OCaml

    Posté par  . Évalué à 5.

    Si ça intéresse des gens, j'ai récemment écrit une implémentation de HashLife, un algorithme sophistiqué pour calculer l'état d'un jeu de la vie un grand nombre de générations dans le futur. Le code, en OCaml, est documenté à but pédagogique : c'était avant tout pour moi, pour bien comprendre l'algorithme, mais aussi pour pouvoir l'expliquer aux autres.

    La discussion autour du programme est là :
    http://progmod.org/forum/sujet/310/hashlife-explique-en-ocaml/

    Le code source directement:
    https://gitorious.org/hashlife-in-literate-ocaml/hashlife-in-literate-ocaml/blobs/master/hashlife.ml

    (En deux mots, l'idée de Hashlife est de compresser à la fois le temps et l'espace: au lieu de calculer seulement une géneŕation dans le futur, on calcule l'état dans 2N générations, et au lieu de recalculer à chaque endroit on essaie de reconnaître et partager les motifs spatiaux répétés.)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.