Vignette Gauche Vignette Droite
Image Bandeau Supérieur

Le jeu de la vie
émergence et complexité

L'algorithme de Conway et le Jeu de la Vie

On ne présente plus le Jeu de la vie, nom donné à l'automate cellulaire mis au point par le mathématicien anglais John Horton CONWAY, et rendu publique par Martin GARDNER en 1970 dans la Revue Scientific American*. J. H. Conway avait conçu cet algorithme pour illustrer des problèmes de complexité et d'auto-reproduction de systèmes logico-mathématiques. 

▼ Pourquoi un tel succès pour cet algorithme ?

La motivation de son inventeur, J.H. Conway, s'inscrivait dans la suite de travaux de mathématiciens (John von Neumann, Stanislaw Ulam) qui s'intéressaient aux systèmes logiques capables de se reproduire (capables de "s'auto-répliquer" : une reproduction non sexuée). A plus long terme, la question visait celle de l'auto-organisation de systèmes vivants… et donc de l'origine de la vie.

Dans le même temps les ordinateurs "personnels" se répandaient, d'abord dans le milieu scientifique, puis à tous les niveaux de la gestion et de l'administration… Que de machines disponibles à temps perdu pour des utilisateurs fascinés par leurs prouesses !

Enfin l'algorithme de Conway est simple… donc facile à programmer, alors que l'on forme des milliers de jeunes programmeurs. Et les figures qu'il produit sont complexes, imprévisibles, et donc fascinantes par leur évolutivité mystérieuse…
Vers le haut

▼ Quelques images.

Les deux images ci-dessous montrent un Canon à planeurs de Gosper (Gosper Glider Gun) qui vient tout juste de libérer un Planeur (Glider) : cette configuration émet un planeur toutes les 30 générations.

Exemple d'un Gosper Glider Gun sous algorithme de Conway Exemple de Vaisseaux sous algorithme de Conway Smart
• L'image de gauche montre les pions qui composent le Gosper Glider dans leur aspect habituel avec l'algorithme de Conway.
• L'image de droite montre la même configuration sous une version modifiée de l'algorithme que j'ai appelée Conway Smart : elle rend visible la direction des cases qui, à la génération précédente, ont provoqué l'apparition ou la survie des pions actuels.

Les 3 groupes de pions présents sur les images ci-dessous sont des Vaisseaux : Ces groupes ont la propriétés de se déplacer de 2 cases horizontalement toutes les 4 générations.

Exemple de Vaisseaux sous algorithme de Conway Exemple de Vaisseaux sous algorithme de Conway Smart
• L'image de gauche montre les Vaisseaux dans leur forme standard.
• L'image de droite les montre sous la variante Conway_Smart. Les cases occupées par un point jaune sont des cases maintenant vides mais qui étaient occupées à la génération précédente.
Exemple d'un Gosper Glider Gun sous algorithme de Conway
Exemple d'un Gosper Glider Gun sous algorithme de Conway Smart
Exemple de Vaisseaux sous algorithme de Conway
Exemple de Vaisseaux sous algorithme de Conway Smart
▲ Vers le haut

▼ De nombreux sites sur Internet publient des informations sur cet automate cellulaire et son histoire.

Je signale en particulier :

→ J'ajoute que l'on peut aussi trouver sur Internet des programmes de Jeu de la vie, beaucoup plus puissant que Biogame (voir : http://fr.wikibooks.org/ wiki/ Automate_cellulaire/ Logiciels). Ces programmes sont capables de gérer des grilles de plusieurs millions de cases, et avec des performances prodigieuses. Certains d'entre eux permettent aussi de créer diverses variantes d'automates cellulaires…

Biogame ne peut aucunement prétendre à rivaliser avec de tels logiciels. La spécialité de Biogame tient à son mode de programmation particulier, qui permet la création et la modification d'algorithmes "à la volée" depuis le logiciel lui-même à l'aide de son Tableau Algorithmique (ce Tableau et ses Opérateurs servent bien sûr aussi à la création d'algorithme originaux).
Vers le haut

▼ Pour mémoire voici la définition de l'algorithme de Conway.

  • On dispose d'une grille orthogonale à "voisinage 8" (formée de cases carrées pour lesquelles on compte 8 cases voisines). Ces cases peuvent être à l'état 0 (case dite "vide") ou à l'état 1 (case dite "occupée par un pion").
  • Toute case vide devient occupée si elle a 3 cases voisines occupées, sinon elle reste inchangée.
  • Toute case occupée le reste si elle a 2 ou 3 cases voisines occupées, sinon elle devient vide.

On fait démarrer l'algorithme à partir d'une grille comprenant un amas de cases occupées plus ou moins chaotique, et l'on assiste alors à leur évolution. Dans certains cas, les cases occupées se rassemblent en figures plus ou moins stables ou périodiques. On parle de groupes ou de regroupements de pions, de configurations ou patterns qui forment des figures à l'évolution typique. Bien sûr l'intérêt est de choisir habilement les configurations dont l'évolution présentera des propriété particulières…

Conformément à l'esprit de BioGame, je parle de "pions" pour désigner les cases occupées de la grille. On tend à dire que les pions se déplacent : ça n'est évidemment qu'une une façon de parler qui désigne le sentiment de mouvement qui accompagne les transformations des cases tantôt vides tantôt occupées.
Vers le haut

▼ Les regroupements de pions caractéristiques du Jeu de la Vie.

Les cases occupées forment des "regroupements" en "figures" (pattern) caractéristiques. Je parlerai aussi de "configurations" de pions…

Voici rapidement les grands types de regroupements qui apparaissent dans le Jeu de la vie (d'après wikipedia, qui donne plus de détail) :

  • Les Structures Stables : ce sont les regroupements de pions qui restent figés tant que des modifications des cases de leur voisinage ne viennent pas les atteindre
  • Les Oscillateurs (ou structures périodiques) : ce sont des regroupements qui se transforment et qui finissent par retrouver leur état antérieur : le nombre de cycles nécessaires pour retrouver l'état initial désigne la périodicité de l'oscillateur
  • Les Vaisseaux : non seulement ces structures sont périodiques, mais elles se déplacent (en diagonale, ou en axe vertical/horizontal). Le Vaisseau le plus répandu est le planeur, il ne comprend que 5 cases et se déplace en oblique sur une période de 4 cycles.
    On peut utiliser les vaisseaux comme un "signal" qui part à destination d'une autre structure qui va en être affectée.
  • Les Puffeurs (ou Fumeurs) : Il s'agit encore de structures périodiques, mais elles ont la particularité de laisser derrières divers débris à l'évolution apparemment chaotique.
  • Les Canons : ce sont des structures périodiques qui émettent des vaisseaux (le plus souvent des planeurs) Le Gosper Glider est un des plus connu : il émet un planeur tous les 30 cycles
    Miracle : il existe aussi un ensemble de 8 planeurs qui en se rencontrant construisent un Gosper Glider : on appelle ça un "Gun Synthetiseur"…

Vers le haut

▼ Quelques caractéristiques générales.

Notons d'abord que l'algorithme de CONWAY est convergent : des regroupements différents peuvent aboutir à un regroupement identique. A l'inverse, un regroupement donné, ne peut avoir qu'une seule descendance possible. Ainsi l'algorithme de CONWAY est déterministe : pour une figure donnée, il n'existe qu'une évolution possible (aucun facteur supplémentaire ne peut en influencer le devenir… en dehors de l'interaction avec d'autres figures, mais cette interaction est elle-même strictement déterminée).

A l'inverse l'algorithme de CONWAY n'est pas réversible : il n'existe pas de moyen permettant à partir d'un regroupement de pions de "remonter" à celui qui l'a produit. Et pour cause, puisque que plusieurs regroupements peuvent produire un même résultat. Plus encore : il existe des regroupements de pions qui ne peuvent résulter d'aucun regroupement préexistant : on les appelle des Jardins d’Éden. Prouver des tels regroupement n'a rien d'évident…

Les différents "destins" possibles pour un regroupement quelconque de pions se résument aux suivants : soit disparition, soit formation d'une structure stable, figée ou périodique, soit fragmentation en plusieurs éléments formés d'éléments figés ou périodiques. Parmi cette dernière possibilité existe le cas de la formation d'un groupe périodique émettant des éléments qui s'en éloignent indéfiniment, débris chaotiques ou vaisseaux. Une telle formation est périodique par son noyau, mais infiniment non-périodique, non identique à elle-même, si l'on y inclut les éléments qui s'en détachent.

Ajoutons enfin qu'il n'existe pas de moyen de calculer quel sera l'état de la grille dans n générations, sauf lorsque l'on est en présence de ces figures qui se répètent de façon périodique. En dehors ces cas, nous avons ici l'illustration d'une évolutivité parfaitement déterminée et pourtant imprévisible.

Le cas d'une formation périodique émettant des vaisseaux est particulier : dans l'absolu cette formation est non périodique, mais comme les vaisseaux le sont, son évolution est calculable (comme combinaison de 2 systèmes périodiques). On peut calculer l'état de l'ensemble dans n générations alors même que cet état n'a encore jamais eu lieu, et ne se reproduira jamais ensuite… Pas mal non ?

A vrai dire, la calculabilité de tout phénomène se tient entre déterminisme et imprévisibilité. C'est sur cette frange qu'une science est possible. Le caractère cyclique d'un phénomène, sa périodicité, constitue le moyen essentiel de prévoir son avenir. Ainsi l'étude des phénomènes célestes, astrologie et astronomie, est à l'origine des sciences dans les civilisations anciennes et a imposé la nécessité des mathématiques. Dans la "vraie vie", les phénomènes non périodiques ont pu être étudiés dès lors qu'on parvenait à les reproduire, et à en extraire les déterminations qui les rendaient calculables. C'est après avoir appris à répéter à l'identique, que se constituent les sciences expérimentales.

La non-réversibilité de l'algorithme de CONWAY est aussi compatible avec l'idée que cet algorithme produit du désordre : on a "perdu de l'information, puisque, à partir d'une configuration donnée, on ne peut pas reconstituer son passé… Du coup quand finissent par se former des configurations stables, on les perçoit plutôt comme des reliquats appauvris de configurations passées (des "cendres").

Peut-on concevoir des configurations qui ne perdraient pas d'information et qui, tout en se transformant, préservent leur stabilité en retrouvant périodiquement une forme identique ? De telles configurations paraissent être organisées puisqu'elles "savent" retrouver leur états antérieur; elles font figure d'exception, et leur mouvement parait doté de "sens".

C'est en combinant de telles figures organisées qu'ont été conçue des systèmes complexes aux propriétés remarquables.
Vers le haut

▼ Propriétés émergentes.

Lorsque des regroupements de pions présentent une certaine stabilité, leur comportement spécifique donne le sentiment de leur autonomie. On parle alors de propriétés émergentes pour désigner le surgissement de ces comportements caractéristiques mais inattendus. L'interaction maîtrisée de plusieurs regroupements, en particulier à l'aide de canons émetteurs de vaisseaux, suggère alors une sorte de physique émergente propre à l'espace du Jeu de la Vie.

Viennent alors des questions :

  • Les transformations de certaines regroupements de pions pourraient-ils représenter des opérations logico-mathématiques ? (en les assimilant à des codes émettant des signaux "oui" ou "non", valant pour des "bits" d'information)
  • Certains de ces regroupements seraient-ils capables de se reproduire en se restituant dans l'état de leur ancêtre et donc avec ses propriétés initiales ?
  • Existerait-il un regroupement qui serait un constructeur universel, et qui en lisant une chaîne de codes, pourrait construire à la demande n'importe quel regroupement de pions ? Un tel constructeur serait-il capable de se répliquer lui-même ? La création mathématique d'un tel constructeur universel, fut l'entreprise du mathématicien John von Neumann, puis de E. F. Codd.

    WIKIPEDIA nous annonce : En 2010, Gemini, le tout premier constructeur universel du jeu de la vie, a été découvert. Cette immense figure fait 4 217 807 cellules sur 4 220 191. En avançant, cette figure crée une copie d'elle-même en détruisant la précédente. L'opération prend environ 34 millions de générations. Comme Gemini se déplace et ne laisse rien derrière lui, c'est aussi un vaisseau. C'est d'ailleurs le premier vaisseau à se déplacer obliquement, c'est-à-dire ni orthogonalement, ni diagonalement. 

  • Enfin de telles configurations stables seraient-elles capables de s'auto-réparer ? Cette propriété est aussi une des grandes caractéristiques des systèmes vivants… seulement dans une certaine mesure, on le sait.

Vers le haut

----------
* « The fantastic combinations of John Conway's new solitaire game "life" », Scientific American 223, october 1970 
Il semble qu'une version de cet article soit accessible à l'adresse suivante : http://fr.scribd.com/doc/75545612/Martin-Gardner-Wheels-Life-and-Other-Mathematical-Amusements-The-Game-of-Life-Part-1