Accueil

  

LE JEU DE LA VIE
 


SOMMAIRE
 


Introduction
Règles du jeu
Les formes de base
Propriétés
Logiciels
Prototypes
 

 

Introduction
 


Les origines du fameux « jeu de la vie » (Game of Life) :
 

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...
 



 


Les principaux acteurs à l’origine du « jeu de la vie » :
 
 
Johannes Von NEUMANN
américain
1903-1957
 
John Horton CONWAY
Anglais
1937-

D'origine hongroise, professeur à l'université de Berlin, il s'installe aux Etats Unis afin d'échapper au régime nazi (1933) et fut professeur à Princeton.

Travaux fondamentaux en mécanique quantique, en algèbre et en topologie (espaces de Hilbert, opérateurs dans un tel espace : algèbres de Von Neumann), en théorie des ensembles (modification, avec Bernays, des axiomes de Zermelo).

Théorie des ensembles et entiers naturels : En collaboration avec Morgensten, il crée la théorie des jeux (Theory of games and economic behavior, 1944).

Le mot "jeu" doit être compris en tant que "stratégie". Cette théorie s'applique aux problèmes économiques ou militaires. Il apporta ainsi une importante contribution à la cybernétique (fonctionnement des automates, intelligence artificielle) dont l'initiateur fut, à la même époque, le mathématicien américain Norbert Wiener (1894-1964).

En France, cette nouvelle branche des mathématiques, où intervient le calcul des probabilités, sera étudiée par Borel.

Von Neumann est aussi à l'origine des méthodes probabilistes, dite de Monte Carlo (rappelant les jeux de hasard) employées là où les méthodes classiques d' yse numérique s'avèrent inefficaces.

Notion de recherche opérationnelle, théorie des jeux, systémique : Von Neumann est considéré comme le père des ordinateurs modernes (architecture von Neumann) mais aussi comme celui de la première bombe atomique, laquelle n'a pu voir le jour qu'après de longs et complexes calculs des premiers computers (ordinateurs) américains.

Elève brillant, John Conway se passionna dès son enfance pour le calcul et la magie des nombres, en un mot : l'arithmétique.

Etudiant à Cambridge, il se spécialisa en théorie des nombres sous la houlette d’ Harold Davenport (mathématicien anglais, 1907-1969) et fut maître de conférence à l'université de Cambridge (1964) puis professeur (1983).

Il enseigne actuellement à l'université de Princeton. Sémillant pédagogue et vulgarisateur des mathématiques, il a publié (souvent en collaboration avec son complice Richard K. Guy, professeur à Calgary, Canada) de nombreux livres destinés à tous les publics.

Cherchant à résoudre un difficile problème dans un groupe de symétries d'un espace abstrait, Conway se trouve confronté aux groupes sporadiques et découvre (1968) l'un des trois qui porte désormais son nom. Il en exhibera deux autres et contribuera à leur classement que l'on pense être définitif (1982) : 26 sont aujourd'hui dénombrés.

D'apparence ludique, mais en fait fort complexe, est la théorie des noeuds, se rattachant à la topologie, et à laquelle Conway s'intéressa très tôt.
 
 


 
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.34E154 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.
 
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- 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

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 !)
 
 


 

Les formes de base


On trouve différentes formes,
dont voici quelque exemples :

A- Les formes stables ;
B- Les graines de pulsar ;
C- Les pulsars :
D- Les oscillateurs ;
E- Les vaisseaux :
F- Les planeurs ;
G- Les canons ;
H- Les mangeurs.

 

 


A- Les formes stables
 
Le « bloc »…un exemple de forme stable, qui ne varie pas au fur et à mesure des générations :

 
D’autre exemples de formes stables, ayant les mêmes caractéristiques que le bloc :
 



 


B- 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 » !
 



 


C- 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.



 


D- Les oscillateurs
 
Ce sont des structures périodiques, qui reprennent leur forme après 2 itérations.

Voici quelque mples :



 


E- 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 :

 



 


F- Les planeurs
 
C’est 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. La preuve qu’une forme élémentaire peut naître, mourir… mais aussi se mouvoir.

 



 


G- Les canons
 
Le canon est né d’un défi lancé par Conway aux passionnés du jeu de la vie, et que releva une équipe d’universitaires. Il est constitué de 2 navettes centrales qui oscillent entre 2 blocs. Résultat : le canon produit un planeur toutes les 30 itérations. Les canons sont de véritables « créateurs » de matière.



 


H- Les mangeurs
 

Contrairement aux canons (créateurs de structures), le mangeur dévore celles qui ont le malheur de passer à portée des 3 cellules de sa tête, constituant son « hameçon ».

Voici l’exemple atroce d’un planeur se faisant gober :



 

Propriétés


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

 
1- Vitesse limite des vaisseaux
2- Croissance infinie
3- Irréversibilité
4- Jardin d’Eden
5- Indécidabilité

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.

Plusieurs propriétés :
C est la vitesse maximale (strictement) d'un vaisseau (on la note ainsi par ogie avec la vitesse de la lumière).

Si un vaisseau se déplaçe de A cases horizontalement et de B cases verticalement en une période, cette période doit être au moins 2*(A+B).
 

Il existe des structures dont l’effectif croît indéfiniment.

Exemples du « remplisseur de plan » (spacefiller) ou encore du « canon à glisseurs » (glider gun)


=> Le remplisseur de plan :

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 :

Jardins d'Eden (structures pour lesquelles il n'existe pas d'antécédent)

Il existe des structures Jardin d'Eden pour le Jeu de La Vie. 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, et Guy, (ainsi que dans d'autres ouvrages) : elle se fonde sur des arguments de dénombrement.

Cela 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.



 

Logiciels


Voici les logiciels que l'on peut utiliser pour "jouer" au Jeu de la Vie :
 
LIFE
WINLIFE
(celui que j'utilise)
W-LIFE
GET A LIFE
LIFELAB
X-LIFE
DB-LIFE
PC (Dos, Windows)
PC (Dos, Windows)
PC (Dos, Windows)
PC (Dos, Windows)
MacOS
Unix
Unix


Retrouvez ces logiciels et téléchargez-les par ce lien :

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

 

 



 

Prototypes


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

 
PROTOTYPE
TYPE DE PROTOTYPE
GRAPH
NOMBRE DE
GÉNÉRATIONS
VITESSE
X
VITESSE
Y
POPULATION
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