Jeu de la vie de Conway · The Last Codex

Le Jeu de la vie de John Conway fait évoluer des cellules vivantes ou mortes sur un quadrillage. La même règle locale, appliquée partout en même temps, suffit à produire des motifs stables, des oscillations et des déplacements. On peut en suivre les générations avec des pions aussi bien qu’avec un ordinateur.

Ce que c’est

Le Jeu de la vie est un automate cellulaire conçu par le mathématicien John Horton Conway : un ensemble de cellules dont l’état change suivant une règle commune. Chaque case d’un quadrillage carré est soit vivante, soit morte ; une configuration initiale détermine les générations suivantes. Les mots « naissance » et « mort » désignent ici des changements d’état, dans un modèle mathématique inspiré par l’évolution de populations.

Il n’y a aucun déplacement de pion décidé pendant l’évolution : après le choix du motif initial, on applique la règle à chaque génération. Un plateau avec des pions permet de suivre ce calcul à la main ; un ordinateur en facilite l’exploration lorsque les motifs deviennent grands. Le support ne change pas la règle.

Comment ça marche

Une ardoise encadrée posée sur un plancher, quadrillée à la craie en trois rangées de trois cases : un pion sur la case centrale, les huit cases qui l’entourent coloriées en bleu, et un bâton de craie à côté Les diagonales comptent autant que les cases qui partagent un côté.

Chaque cellule possède huit voisines : quatre par un côté et quatre par un coin. La cellule examinée ne fait pas partie de ce compte. Une cellule morte devient vivante si elle a exactement trois voisines vivantes. Une cellule vivante reste vivante si elle en a deux ou trois ; elle meurt dans tous les autres cas. On peut résumer ces conditions par B3/S23 : B indique la naissance avec trois voisines, S la survie avec deux ou trois.

Tous les comptages utilisent l’état de la génération de départ, puis toutes les modifications prennent effet simultanément. Une cellule qui vient de naître ne contribue donc pas aux autres naissances de ce même passage. Modifier les cases au fur et à mesure du comptage ne respecte pas cette évolution synchrone.

La grille théorique s’étend à l’infini dans le plan. Sur un plateau limité, il faut choisir comment traiter les bords ; pour les exemples ci-dessous, on conserve un environnement mort autour des motifs, sans raccorder les côtés opposés. Le carré visible va de zéro à six sur chaque axe, avec les abscisses vers la droite et les ordonnées vers le bas. Les cellules hors de cette fenêtre sont mortes ; les motifs calculés restent à distance de ses bords.

Comment faire

Pour exécuter la règle à la main, préparer un quadrillage et des pions, ou dessiner les cellules sur du papier quadrillé. Conserver la configuration de départ pendant tout le comptage ; reporter le résultat sur une seconde grille avant de passer à la génération suivante. Ce second relevé permet d’appliquer en une seule fois les naissances et les morts calculées depuis le même état. Les pions et le papier sont des supports possibles ; l’automate reste la règle qui relie les configurations.

Trois petites ardoises sur un banc bas, reliées par des flèches à la craie : trois pions en ligne horizontale, puis verticale, puis de nouveau horizontale Un même motif revient après deux générations, sans se déplacer.

Commencer avec des cellules vivantes aux coordonnées (2, 3), (3, 3) et (4, 3), toutes les autres étant mortes. Les extrémités n’ont chacune qu’une voisine vivante et meurent ; la cellule centrale en a deux et survit. Les cases (3, 2) et (3, 4) ont chacune trois voisines vivantes et naissent. La génération suivante contient donc exactement (3, 2), (3, 3) et (3, 4). Au passage suivant, on retrouve exactement (2, 3), (3, 3) et (4, 3). Ce clignotant a une période de deux générations ; sa population reste de trois cellules.

Essayer séparément le bloc formé par (2, 2), (3, 2), (2, 3) et (3, 3). Chacune de ses quatre cellules a trois voisines vivantes ; aucune case extérieure n’en a trois. Le bloc reste donc identique à la génération suivante. Un motif inchangé est appelé motif stable. Un motif qui revient cycliquement est un oscillateur. Ces deux essais permettent de contrôler le comptage des diagonales et l’application simultanée de la règle, avant d’explorer d’autres configurations.

Histoire et évolution

Les automates cellulaires précèdent le Jeu de la vie : von Neumann figure parmi les premiers chercheurs à les étudier, et ces modèles sont explorés au début des années 1950. Cette famille comprend des grilles, des états et des voisinages différents ; elle ne se confond pas avec la règle particulière de Conway.

Cinq grilles de six cases sur six tracées à la craie sur une longue ardoise encadrée posée sur un banc et reliées par des flèches, chacune portant cinq pions ; la forme change d’une grille à l’autre et revient sur la dernière, décalée d’une case vers le bas et d’une case vers la droite L’article de Gardner décrivait déjà des configurations mobiles.

Conway choisit ses règles après une longue expérimentation. Martin Gardner présente son Jeu de la vie dans la rubrique « Mathematical Games » de Scientific American, dans le numéro d’octobre 1970. L’article décrit déjà une pratique avec des pions, la naissance et la survie selon le voisinage, ainsi que des configurations stables, oscillantes ou mobiles. Il rapporte aussi l’emploi d’un ordinateur PDP-7 pour explorer des évolutions longues, avec un programme de M. J. T. Guy et S. R. Bourne.

Le calcul informatique étend ensuite l’étude des motifs et des constructions. Des règles voisines, comme HighLife, constituent d’autres automates, et non une modification implicite du Jeu de la vie de Conway.