Accueil


Loisirs

   

Le jeu de la vie

 

Faire écrire le scénario de la vie par un ordinateur, est-ce bien sérieux ? En tout cas, cela démarre comme un jeu ! Et l'on finit par un hallucinant zoo d’automates, d’anges, de mortels, d’errants…

1- Introduction

Faire écrire le scénario de la vie par un ordinateur, est-ce bien sérieux ? En tout cas, ça démarre comme un jeu ! Et ça finit par un hallucinant zoo d’automates, d’anges, de mortels, d’errants, …

Le mathématicien américain d’origine hongroise John Von Neumann est un vrai génie dont les travaux ont, entre autres, jeté les bases de l’informatique. Il se pose beaucoup de questions dans les années 1950, notamment sur les automates autoreproducteurs (pouvant reproduire une exacte copie d’eux-mêmes)

Un autre mathématicien, Stanislas Ulam (polonais), lui suggère la méthode décisive. Il veut créer sur des ordinateurs des jeux capables d’inventer des formes géométriques.

L’univers de Von Neumann commence ainsi par un damier où les cases, baptisées cellules, peuvent revêtir 2 états : éteint/allumé.

C’est John Conway, sur une idée de Von Neumann, l’inventeur du célèbre jeu de la vie (1970) : jeu à un joueur dont l'objectif est la survie et la croissance d'une population représentée par des jetons sur un quadrillage dont les cases sont des cellules tant au sens biologique que topographique...
 

2- Les règles du jeu

Le monde du « Jeu de la vie » est un plan infini quadrillé, dont chaque case est, soit occupée par une cellule, soit vide.

Chaque case possède huit voisines, placées tout autour d’elle.
D’une génération à l’autre, des naissances et des décès s’y déroulent mécaniquement selon la règle simpliste de Conway :

Pour un automate 2D à 2 états avec voisinage de 8, il y a 2^2^9 = 1.34^154 fonctions de transitions différentes possibles ! Pour expliciter chacune de ces fonctions, il faudrait décrire l'état de sortie correspondant à chacune des 512 configurations de voisinage. La fonction de transition du Jeu de la Vie se résume en fait à des méta-règles qui regroupent à elles-seules les 512 configurations.
 

 

2.1- Principe de naissance :
Si une case est vide et que trois de ses voisines sont occupées, alors une naissance s’y produit (étrange ité!)

2.2- Principe de stase :
Si une case est occupée, la survie n’y est possible que si deux ou trois cases voisines sont occupées

2.3- Principe de mort :
Si une case est entourée de 0 ou 1 voisine occupée, la case est vide à la génération suivante (mort par isolement).
Si une case est entourée de 3 voisines occupées et plus, la case est vide à la génération suivante (mort par surpopulation).

Ces règles, choisies parce qu’elles sont assez naturelles (la vie nécessite déjà de la vie, mais trop de vie provoque l’étouffement) et qu’elles engendrent un monde inattendu, ont dépassé toutes les espérances de son créateur.

Le système est le plus souvent simulé sur un ordinateur et de nombreux logiciels sont disponibles pour cela.

Il faut tout de même savoir que dans les premières années du Jeu de la Vie, les simulations informatisées étaient peu courantes et les premiers résultats furent trouvés à la main ! Le tableau dans lequel se joue le Jeu de la Vie (qu'on appelle parfois plan de Conway) est en théorie infini.

Vous l'aurez compris, le Jeu de la Vie n'est pas vraiment un jeu, il consiste simplement à choisir la configuration de départ et à observer...ce qui peut paraitre un peu maigre mais qui est en fait tout sauf ennuyeux !

Le principal intérêt de ce jeu est qu'il permet, à partir de règles simples, de faire émerger des phénomènes complexes. Cet automate cellulaire en deux dimensions (car c'est à cette ensemble d'objets qu'appartient le Jeu de la Vie) est considéré comme une référence par les chercheurs s'interessant à la vie artificielle car il montre que des règles très simples peuvent permettre de mettre en évidence des fonctionements non triviaux, et pouvant simuler la richesse et la diversité de la vie (même si personne ne prétendra que le Jeu de la Vie est aussi riche que la vie ! ).

 

3- Les formes de base
A peine a-t-on commencé de jouer au jeu de la vie que l'on peut déjà distinguer des formes plus ou moins durables dans le temps. On peut les classer en différentes "espèces".

3.1- Les formes stables

Le "bloc" est un exemple de forme stable, qui ne varie pas au fur et à mesure des générations. Il reste comme "gelé" à jamais, ou jusqu'à ce qu'une forme mobile vienne le "déranger" :

 

D'autres formes stables existent. Quelques exemples :

                                                  

 

 

3.2- Les graines de pulsar

On trouve 3 grands types de graines de pulsar, permettant d'engendrer, juste avec leur petit nombre de cellules, de vrais "géants" :

                                                                     

 

3.3- Les pulsars

Ce sont de véritables « géants », oscillant entre 3 phases de 48, 56 et 72 cellules.

Le plus remarquable est que cette forme gigantesque et durable est le fruit de la croissance de l’une des 3 graines vues précédemment.

Ce sont de véritables "géants", oscillant entre 3 phases de 48, 56 et 72 cellules. Le plus remarquable est que cette forme gigantesque et durable est le fruit de la croissance de l'une des 3 graines de pulsar vues ci-dessus.

 

3.4- Les oscillateurs

Ce sont des structures périodiques, qui reprennent leur forme après 2 itérations. Exemples :

 

3.5- Les vaisseaux

Ce sont des structures animées, qui se déplacent horizontalement dans l'espace de jeu. Leur déplacement s'effectue en 4 étapes. Voici les 3 types de vaisseaux :

 

3.6- Les planeurs

Ils adoptent une forme particulière de vaisseau. Elle est simplement composée de 5 cellules dans chacun des 4 stades de son évolution.

C'est une structure animée qui se déplace en diagonale dans l'univers du jeu, donnant la preuve qu'une forme élémentaire peut naître, mourir... mais aussi se mouvoir.

 

3.7- Les canons

Les canons sont nés d'un défi lancé par Conway aux passionnés du jeu de la vie, et que releva une équipe d'universitaires. Ils sont constitués de 2 navettes centrales qui oscillent entre 2 blocs. Le canon produit alors un planeur toutes les 30 itérations. Les canons sont de véritables "créateurs" de matière.

 

3.8- Les mangeurs

Contrairement aux canons, qui sont créateurs de structures, les mangeurs quant à eux dévorent celles qui ont le malheur de passer à portée des 3 cellules de sa tête, constituant en quelque sorte sont "hameçon". Voici l'exemple d'un planeur se faisant "gober" :

 

4- Les propriétés

Il est possible d'avancer 5 propriétés dans le jeu de la vie :

 

4.1- Vitesse limite des vaisseaux

Il existe des structures appelées vaisseaux (spaceships) ou encore navires ayant la propriété de se déplacer.

Voici une définition plus précise : un vaisseau est une structure finie (de cellules vivantes) qui, après un certain nombre de générations réapparait, mais translatée dans une certaine direction (et avec une distance non nulle).

Le plus petit nombre de générations au bout desquelles elle réapparait translatée est sa période.

On définit la vitesse d'un vaisseau par la distance de translation (mesurée par la longueur du plus court chemin entre deux cellules : deux cellules adjacentes (cote à cote ou en diagonale) étant distantes de 1) divisée par la période. La vitesse d'une cellule par génération est notée usuellement "C".

Autres caractéristique :
- C est la vitesse maximale (strictement) d'un vaisseau (on la note ainsi par analogie avec la vitesse de la lumière).
- Si un vaisseau se déplace de A cases horizontalement et de B cases verticalement en une période, cette période doit être au moins 2*(A+B).

 

4.2- Croissance infinie

Il existe des structures dont l'effectif croît indéfiniment. Exemples en sont donnés par le "remplisseur de plan" (spacefiller) ou encore le "canon à glisseurs" (glider gun). Voici un exemple de remplisseur de plan :

 

4.3- Irréversibilité

L'automate cellulaire de Conway est irréversible. Cela signifie qu'il n'est pas possible de proposer des règles permettant de déduire d'une configuration son état à la génération précédente.

En effet, d'une part il existe des structures ayant plusieurs antécédents possibles, d'autre part il en existe aussi n'ayant pas d'antécédent. Il est donc impossible de "repasser le film en arrière". La démonstration de la non-unicité des antécédents est assez triviale : il n'est pas difficile de trouver 2 antécédents possibles à une même structure. Par exemple :

 

4.4- Jardin d'Eden

Le Jardin d'Eden est une structure par laquelle il n'existe pas d'antécédent.

Cela n'est à priori pas si étonnant, en effet, puisqu'il existe des structures finies ayant plusieurs antécédents et que le nombre de structures s'inscrivant dans un rectangle donné est limité, il paraît naturel que d'autres n'en aient aucun.

Une démonstration se trouve dans "Winning Ways (for your Mathematical Plays)" par Berlekamp-Conway-Guy (ainsi que dans d'autres ouvrages). Elle se fonde sur des arguments de dénombrement.

 

4.5- Indécidabilité

Cette propriété signifie qu'il n'existe aucun procédé général de calcul (ou algorithme) capable de prédire comment va évoluer à long terme (on dit aussi "asymptotiquement") une structure quelconque du jeu de la vie.

Par exemple, il n'existe pas d'algorithme permettant de répondre, dans un temps fini et pour toutes les structures du jeu de la vie, à la question "Cette structure va-t-elle croître indéfiniment ?".

Dès lors, on ne peut espérer répondre à ces questions qu'en examinant des cas particuliers, ou en ayant recourt à la simulation (pour laquelle rien ne garantit d'obtenir une réponse dans un temps fini).

La démonstration de cette propriété n'est pas triviale !

 

5- Les logiciels

Plusieurs logiciels permettent de "jouer" au jeu de la vie :
- "Life" (Windows)
- "Winlife (Windows), celui que j'utilise
- "Wlife" (Windows)
- "Get a life" (Windows)
- "Life Lab" (Mac)
- "X-Life" (Linux)
- "DB-Life" (Linux)

Ils sont téléchargeables sur internet, et notamment à ce lien :

http://t0m.free.fr/jdlv/jdlv_logiciel.htm#PC

 

Le format standard des fichiers permettant de décrire une structure est indiqué ci-dessous. L'extension est ".LIF" :

 

 

6- Les prototypes

Voici les principaux prototypes, leur graph et leurs propriétés :

PROTOTYPE
TYPE DE PROTOTYPE
GRAPH
NOMBRE DE
GÉNÉRATIONS
(cycles de transformation)

VITESSE X
(déplacements axe des X)

VITESSE Y
(déplacements axe des Y)

POPULATION
(nombre de cellules)
TRADUCTION
ANGLAISE

Bloc

STABLE

0
0
0
4

Block

Bateau

STABLE

0
0
0
5

Boat

Péniche

STABLE

0
0
0
6

Barge

Péniche longue

STABLE

0
0
0
8

Long barge

Porte-avions

STABLE
 

0
0
0
6

Aircraft carrier

Ruche

STABLE

0
0
0
6

Beehive

Flâneur

STABLE

0
0
0
7

Loaf

Bi-flâneur

STABLE

0
0
0
14

Biloaf

Bateau long

STABLE

0
0
0
7

Long boat

Navire long

STABLE

0
0
0
8

Long ship

Etang

STABLE

0
0
0
8

Pond

Navire

STABLE

0
0
0
6

Ship

Serpent

STABLE

0
0
0
6

Snake

Serpent long

STABLE

0
0
0
7

Long snake

Mangeur

STABLE

0
0
0
7

Eater

Crapaud

OSCILLATEUR

2
0
0
6

Toad

Pentadecathlon

OSCILLATEUR

15
0
0
12

Pentadecathlon

Clignotant

OSCILLATEUR

2
0
0
3

Blinker

Phare

OSCILLATEUR

2
0
0
8

Beacon

Planeur

VAISSEAU

4
1
1
5

Glider

Vaisseau léger

VAISSEAU

4
2
0
9

Small ship

Vaisseau moyen

VAISSEAU

4
2
0
11

Medium Ship

Vaisseau lourd

VAISSEAU

4
2
0
13

Large ship

Canon à planeurs

CANON

30
23
58
45

Glider gun

Canon à planeurs P46

CANON

46
2
0
56

P46 glider gun

 

7- Sources d'information

- Le site de Thomas MORIN : http://t0m.free.fr/jdlv
- La page de Wikipedia : http://fr.wikipedia.org/wiki/Jeu_de_la_vie
- Le site "Jeux et mathématiques" de D. LEGLAND : http://www.dlegland.fr/maths/life/life.html
- Le blog de Jean-Michel CORNU : http://www.cornu.eu.org/news/le-jeu-de-la-vie-et-l-emergence-de-la-complexite