Jeu de la vie - Définition
La liste des auteurs de cet article est disponible ici.
Calculabilité
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.
Questions mathématiques
Certaines propriétés du jeu de la vie ont pu être démontrées, en particulier :
- La croissance d’une configuration est au maximum en t².
- L’existence de portes logiques , , .
- Le comportement asymptotique d’une structure du jeu de la vie est indécidable.
Variantes
Il existe des variantes du jeu de la vie, basées sur des règles de voisinage légèrement différentes (par exemple HighLife).
Bibliographie
- Martin Gardner, Mathematical Games. The fantastic combinations of John Conway’s new solitaire game « life », Scientific American no 223 (Octobre 1970), p. 120-123
- E. F. Codd, Cellular Automata, New York Academic Press (1968)
Simulation
Il existe un très grand nombre de programmes informatiques qui simulent le Jeu de la Vie. Certains sont écrits en Java ou JavaScript, ce qui permet de les inclure dans une page web. La plupart de ces simulateurs sont cependant assez inefficaces car ils représentent le « terrain de jeu » par un tableau bi-dimensionnel et se contentent de faire évoluer les cellules en suivant les règles de Conway.
En 1980, Bill Gosper a créé Hashlife, un algorithme de simultation beaucoup plus efficace, permettant de manipuler des millions de cellules sur des millions de générations en des temps très courts. Cet algorithme reposait sur une idée différente : en effet si l’on considère une portion de l’espace du jeu relativement isolée de ses voisines, il est possible de la faire « tourner » pendant un certain nombre n de générations, puis de simplement mémoriser le résultat. Si la configuration de départ se reproduit ailleurs, on pourra alors « sauter » directement n générations pour cette partie du jeu. Ce nouvel algorithme faisait donc « tourner » différentes portions de l’espace à des vitesses différentes, et se débrouillait pour préserver la cohérence aux bordures de chaque région ainsi simulée. Il faisait appel à une table de hachage pour mémoriser et retrouver rapidement des configurations locales.
Depuis 2008, de nombreux programmes (dont le plus connu est Golly) intègrent cet algorithme dans une interface graphique. Ils ont permis de créer des configurations énormes et très ingénieuses et de suivre leur évolution, insufflant une nouvelle dynamique dans l’étude déjà très riche de cet automate cellulaire.
