Les origines du Jeu de la vie
Origines
Automates
Jeu de la vie
Genèse
Règles
Voisinage utile
"Blinkers"
Jardins d'Éden
Navires
Canons...
"Breeders"
Machines
Métacellules
Documents
Automates cellulaires
Dès 1947, celui-ci entreprit des recherches dont le but était de proposer un modèle théorique de machines auto-réplicatrices. Ces travaux reçurent une nouvelle impulsion en 1951 avec la contribution de Stanislaw Ulam. L'objectif fut atteint, mais au prix d'une complexité très élevée. Les cellules de l'automate de Von Neumann pouvaient occuper 29 états. La génération initiale comptait plus de 200 000 cellules. La preuve théorique, de plus de 100 pages, n'a été publiée qu'après la mort de son auteur, en 1957.Un automate cellulaire consiste [1] :
- en un réseau bidimensionnel (généralement plan [2]) de réceptacles (cases) accueillant des cellules qui peuvent se trouver dans un certain nombre d'états ;
- en un ensemble de règles qui régissent le passage d'une génération de cellules à la suivante.
Les règles de transition d'une génération à la suivante prennent en compte
- l'état d'une cellule, ainsi que ceux de ses voisines [3] ;
- l'occupation des cases voisines [3] d'une cellule donnée.
Le Jeu de la vie de J. Conway
L'invention du Jeu de la vie est le résultat d'une tentative (fructueuse) de simplification de l'automate de Von Neumann. Publié en 1970 dans la chronique du Scientific American alors tenue par Martin Gardner, ce "jeu à zéro joueur" [5] a instantanément connu un succès foudroyant. Deux raisons principales à cela :
- il est très facile d'y "jouer" (du papier et un crayon suffisent, même si ce n'est pas la méthode la plus rapide) ;
- il est apparu en même temps que les mini-ordinateurs commençaient à se répandre dans le milieu professionnel -- et on ne compte pas [6] le temps de calcul "emprunté" par les employés à leur entreprise pour faire tourner des programmes de Jeu de la vie ! ...
- il a rapidement montré une richesse et une profondeur étonnantes par rapport à sa simplicité.
La "genèse" : l'invention des règles
Les règles du Jeu de la vie ne doivent rien au hasard. Dès 1968, John Conway a
effectué de nombreuses expériences, tantôt à la main (!), tantôt à l'aide d'un mini-ordinateur DEC PDP-7 (qui venait de sortir).
<<
- Il ne devrait pas y avoir de configurations initiales pour lesquelles on puisse prouver simplement que la population croisse indéfiniment.
- Il
devrait y avoir des configurations initiales pour lesquelles,
apparemment, la population s'accroît effectivement indéfiniment.
- Il devrait y avoir des configuration initiales qui
croissent et évoluent pendant un temps considérable avant de s'achever
de trois manières possibles :
- s'éteindre complètement (de surpopulation ou de raréfaction) ;
- s'établir en une configuration stable demeurant inchangée par la suite ;
- entrer dans une phase oscillatoire de période 2 ou plus.
Ces essais intensifs ont débouché sur un ensemble de règles concises mais fructueuses.
Les règles du Jeu
L' univers du jeu de la vie est un quadrillage (théoriquement infini)
à mailles carrées. Les cases sont
occupées (ou non) par des cellules en nombre fini. Le voisinage
d'une cellule comporte ses huit cases adjacentes : par un côté, mais
aussi par un coin. Ce sont les "x" sur le schéma suivant :
Les cellules naissent, survivent ou meurent (disparaissent) d'une génération à l'autre selon les règles suivantes :
- une cellule naît dans une case vide voisine d'exactement trois cellules (une bien curieuse sexualité) ;
- une cellule ayant zéro ou une voisine vivante meurt
(d'isolement...), de même qu'une cellule possédant quatre voisines ou
plus (surpopulation...) ;
- une cellule avec deux ou trois voisines survit à la prochaine génération.
| survie si 2 ou 3 voisines |
| naissance si 3 voisines |
... en 10 mots !
Voisinage utile
Ces règles ont une conséquence importante. Deux cellules distantes [7] de deux cases ou plus à la génération N ne peuvent interagir sur la génération N+1, n'étant pas voisines communes d'une quelconque troisième.Ceci conduit à la notion de voisinage utile d'une (partie de) configuration. Le voisinage utile est l'ensemble des cases [8] qui participent effectivement à la détermination de la génération suivante. Au Jeu de la vie, seules comptent les cases situées une unité au plus d'une cellule vivante. Si notre configuration est contenue dans un certain rectangle n×p, les cases hors du rectangle (n+2)×(p+2) qui le "borde" ne jouent aucun rôle dans la détermination de la génération suivante.
Nous verrons plus loin les conséquences de cette simple remarque.
Notes
[1] en 1ère approximation -- cette présentation intuitive demande à être formalisée pour l'étude théorique, voir p. ex. ici.
[2] mais pourquoi pas une sphère, ou un tore ? Des essais ont été effectués pour l'adapter à ces surfaces.[3] Les états possible et la définition des voisines dépendent de l'automate cellulaire considéré.
[4] La sphère à cornes, c'est lui !
[5] zero-player game, selon l'expression de J. Conway lui-même
[6] mais on estime à plusieurs millions de dollars !
[7] horizontalement, verticalement ou diagonalement : cela ne fait pas de différence dans le Jeu de la vie. On y utilise la norme || . ||∞ !
[8] vides ou non -- cas d'une naissance