Le jeu de la vie
Malgré des règles très simples, le jeu de la vie permet le développement de motifs extrêmement complexes.
| Sommaire |
Règles
En préambule, il faut préciser que le jeu de la vie n'est pas vraiment un jeu au sens ludique, puisque il ne nécessite aucun joueur ; il s'agit d'un automate cellulaire, un modèle où chaque état conduit mécaniquement à l'état suivant à partir de règles pré-établies.
Le jeu se déroule sur une grille à deux dimensions, théoriquement infinie (mais de longueur et de largeur finies et plus ou moins grandes dans la pratique), dont les cases — qu'on appelle des « cellules », par analogie avec les cellules vivantes — peuvent prendre deux états distincts : « vivantes » ou « mortes ».
À chaque étape, l'évolution d'une cellule est entièrement déterminée par l'état de ses huit voisines de la façon suivante :
- Une cellule morte possédant exactement trois voisines vivantes devient vivante (elle naît).
- Une cellule vivante possédant deux ou trois voisines vivantes le reste, sinon elle meurt.
Ainsi, la configuration Image manquante
Gol-blinker1.png
Image:Gol-blinker1.png
donne au tour suivant la configuration Image manquante
Gol-blinker2.png
Image:Gol-blinker2.png
qui redonne ensuite la première.
On peut également formuler cette évolution ainsi :
- Image manquanteSi une cellule a exactement trois voisines vivantes, elle est vivante à l'étape suivante. C'est le cas de la cellule verte dans la configuration de gauche.
Gol-born.png
- Image manquanteSi une cellule a exactement deux voisines vivantes, elle reste dans son état actuel à l'étape suivante. Dans le cas de la configuration de gauche, la cellule située entre les deux cellules vivantes reste morte à l'étape suivante.
Gol-nochange.png
- Image manquanteSi une cellule a moins de deux ou plus de trois voisines vivantes, elle est morte à l'étape suivante. C'est le cas de la cellule rouge dans la configuration de gauche.
Gol-dead.png
Afin de représenter le processus, les cellules vivantes sont généralement représentées colorées sur la grille, sur un fond de cellules mortes incolores.
Histoire
Le Jeu de la vie fut inventé par John Horton Conway en 1970, alors qu'il était professeur de mathématiques à l'université de Cambridge, au Royaume-Uni. À l'origine, John Conway y jouait à la main, en utilisant un plateau de go pour grille et des jetons de go pour matérialiser les cellules vivantes.
Le jeu de la vie connu sa permière apparition vraiment publique lorsque Martin Gardner le détailla dans sa rubrique Mathematical Games (« Jeux mathématiques ») de l'édition d'octobre 1970 du magazine Scientific American[1].
D'après Gardner, Conway expérimenta plusieurs jeux de règles concernant la naissance, la mort et la survie d'une cellule avant d'en choisir un où la population des cellules n'explose pas (ce qui arrive souvent lorsque les conditions de naissances sont moins strictes) mais où des structures intéressantes apparaissent cependant facilement.
Peu après cette publication, plusieurs structures intéressantes furent découvertes, comme le « planeur », un motif qui se décale en diagonale toutes les 4 générations, ou divers « canons » qui génèrent un flux sans fin de planeurs. Ces possibilités augmentèrent l'intérêt pour le jeu de la vie. De plus, arrivant à une époque où une nouvelle génération de mini-ordinateurs meilleur marché fut commercialisée, ce qui permettait de tester des structures pendant la nuit, lorsque personne d'autre ne les utilisait, sa popularité augmenta d'autant.
Vers la fin des années 1980, la puissance des ordinateurs fut suffisante pour permettre la création de programmes de recherche de structures automatiques efficaces; couplés au développement massif d'Internet, ils conduisirent à un renouveau dans la production de structures intéressantes.
Au bout du compte, le jeu de la vie assura plus d'intérêt du grand public (entre autres grâce à divers économiseurs d’écran) pour les automates cellulaires que, par exemple, tous les travaux de E. F. Codd, spécialiste reconnu du domaine et auteur de l'ouvrage de référence Cellular automata (1968)[2].
Structures
Des structures, constituées de plusieurs cellules, peuvent apparaître dans l'univers ; les plus classiques sont :
- Les structures stables
- Les structures périodiques, ou oscillateurs
- Les vaisseaux
Il existe également d'autres structures, qui n'apparaîssent pas spontanément dans l'univers de jeu :
- Les puffeurs
- Les canons
- Les jardins d'Éden
Structures stables
Gol-block.png
Les structures stables (en anglais still life) sont des ensembles de cellules ayant stoppé toute évolution : elles sont dans un état stationnaire et n'évoluent plus tant qu'aucun élément perturbateur n'apparaît dans leur voisinage.
Oscillateurs
Gol-toad.gif
Les oscillateurs (en anglais ) se transforment de manière cyclique, en revétant plusieurs formes différentes avant de retrouver leur état initial. Des figures de ce type sont très nombreuses : on en connaît actuellement des centaines.
Elles peuvent apparaître relativement facilement dans l'univers de jeu par l'évolution spontanée de « graines » beaucoup plus simples.
Vaisseaux
Gol-glider.gif
Les vaisseaux — ou navires — (en anglais spaceships, « vaisseaux spatiaux ») sont des structures capables, après un certain nombre de générations, de produire une copie d'elles-même, mais décalée dans l'univers du jeu.
Le déplacement d'un vaisseau qui, après N étapes, retrouve sa configuration initiale déplacée de A cases horizontalement et de B cases verticalement est noté A - B. L'existence de vaisseaux de type A - B pour A et B quelconques a été démontrée, mais on ne connaît actuellement que deux grands types de vaisseaux :
- Des vaisseaux de type transversal, c'est-à-dire A = 0 ou B = 0.
- Des vaisseaux de type diagonal, avec A = ± B.
On prouve également qu'un vaisseau de type A - B a nécessairement une période N ≥ 2(A+B).
On sait construire des vaisseaux de taille et de période aussi grandes que souhaitées, en utilisant des séries de composants.
Puffeurs
Les puffeurs (de l'anglais puffer, « générateur de fumée ») sont des configurations qui se déplacent en laissant derrière elles une traînée constituée de débris.
Canons
Gol-gun.gif
Les canons, ou lanceurs, ou encore lances-navires (en anglais guns) sont capables de produire des vaisseaux, à un rythme variable (toutes les 15, 23, 30 ou 360 générations par exemple, ou bien de manière apparemment imprévisible pour les lance-navires aléatoires).
De telles structures peuvent être créées à partir de puffeurs que l'on modifie afin que les débris s'agencent sous forme de navires.
Jardins d'Éden
Un jardin d'Éden est une configuration sans passé possible : aucune configuration ne donne à l'étape suivante un jardin d'Éden.
Questions mathématiques
Certaines propriétés du jeu de la vie on pu être démontrées, en particulier :
- La croissance d'une configuration est au maximum en t2.
- L'existence de portes logiques ET, OU, NON (on ne connaît jusqu'à présent aucune configuration de ce type).
Computabilité
Malgré sa simplicité, ce jeu est une machine de Turing universelle : il est possible de calculer tout algorithme pourvu que la grille soit suffisamment grande et les conditions initiales correctes.
Variantes
Il existe des variantes du jeu de la vie, basées sur des règles de voisinage légèrement différentes.
Voir aussi
Liens internes
- Wikipédia:Projet, Jeu de la vie
- Automate, en particulier automate cellulaire.
- John von Neumann.
- Machine de Turing.
Liens externes
- Mirek's Cellebration, pour faire tourner des automates cellulaires.
Bibliographie
[1] Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game « life », Scientific American n°223 (Octobre 1970), p. 120-123 [2] E. F. Codd, Cellular Automata, New York Academic Press (1968)