Le Jeu de Vie imaginé par John Conway en 1970 est un automate cellulaire célebrissime pour au moins deux raisons:
-
Un "canon à planeurs"
A partir de règles toutes simples, le jeu de la vie génère une “vie” artificielle étrangement complexe et imprévisible, posant toutes sortes de questions intéressantes
- Le Jeu de la Vie étant très facile à programmer, des générations d’étudiants ont codé des programmes “Life” dans tous les langages imaginables.
Après une flambée d’intérêt dans les années 1980 où on a même vu apparaitre des processeurs spécialisés dans l’exécution d’automates cellulaires, le soufflé est retombé dans la décennie suivante car la simulation de grands automates demandait beaucoup de puissance de calcul et de mémoire.
Mais comme nous l’apprend Jean-Paul Delahaye dans le dernier “Pour la Science” [1], il y a du nouveau. En 2005 est apparu “Golly“, un logiciel Open Source utilisant ”Hashlife“, un algorithme accélérant le calcul des automates cellulaires d’une manière phénoménale. Hashlife a été imaginé en 1984 déjà par Bill Gosper [3], un des premiers “hacker” du Xerox Park de Palo Alto. Mais pour une étrange raison, ce n’est qu’en 2004 Tomas Rokicki l’a implanté en C et décrit dans un article intitulé “un algorithme pour compresser le temps et l’espace” [2].
Hashlife combine en effet deux techniques de programmation :
- une partition de l’espace qui permet d’une part d’ignorer les grandes zones de cellules vides et d’autre part de reconnaitre les copies identiques de groupes de cellules
- la “Mémoization“, qui consiste à mémoriser des résultats précédemment calculés afin de les restituer immédiatement lorsque la même situation se représente.
Ainsi, hashlife ne calcule qu’une seule fois l’évolution d’un groupe de cellules qui serait présent à des milliers d’exemplaires dispersés sur un immense jeu de la vie, et n’a besoin de mémoire que pour stocker chacune des étapes d’un cycle au lieu de millions de cellules.
Hashlife parvient ainsi à calculer des milliers de générations par seconde de “Jeux de la Vie” comportant 10^50 cellules sur un PC ordinaire doté de 10^9 octets de mémoire !
Voici par exemple “Golly” en action sur le “breeder”, la première structure générant un nombre de cellules augmentant comme le carré du nombre de générations :
On voit comment un groupe de “fusées” se déplace vers la droite en générant des “canons à planeurs”. En quelques secondes, 400′000 générations ont été calculées (même pas à vitesse maximale) , générant 160 millions de cellules actives.
Cette vitesse permet de visualiser confortablement d’autres structures extraordinaires découvertes récemment, comme les “métacellules”:
On voit ici un tableau de 15×15 métacellules, dont chacune se comporte comme une cellule du Jeu de la Vie ! En 30′000 générations environ, chaque métacellule compte le nombre de ses voisins “vivants” et devient elle-même vivante en se remplissant de planeurs en suivant la règle de Conway !
Le “Jeu de la Vie” est donc capable d’exécuter un programme jouant au “Jeu de la Vie”. Mais quels autres programmes peut-il exécuter ? On connait depuis 1984 des structures calculant les nombres premiers, et d’autres “écrivant” en clair comme celle-ci :
Mais en 2000, Paul Rendell a réussi a créer une ”Machine du Turing” en Jeu de la Vie [3], ce qui signifie que ce petit jeu aux règles extraordinairement simple est capable, avec une astucieuse programmation, de réaliser toutes les opérations d’un ordinateur usuel.
Outre le jeu de la Vie, Golly peut exécuter d’autres automates cellulaires en utilisant le fantastique algorithme Hashlife, notamment Wireworld, un système simulant les circuits électroniques digitaux.
“Hashlife” est bien un algorithme qui compresse l’espace et le temps, comme le dit Rokicki, et il est même d’un usage assez général. Je ne serais pas étonné s’il trouvait prochainement des applications “sérieuses”, en simulation notamment.
J’adore les rubriques de Jean-Paul Delahaye dans “Pour la Science”. Surtout celle du mois prochain…
Références:
- Jean-Paul Delahaye “Le royaume du Jeu de la vie“, Pour la Science, avril 2009, p. 86-91
- Tomas G. Rokicki “An Algorithm for Compressing Space and Time“, Dr. Dobbs Journal, avril 2006
- William Gosper ”Exploiting Regularities in Large Cellular Spaces”, 1984, Physica D. Nonlinear Phenomena, Vol 10, pp. 75-80
- Paul Rendell “ a Turing Machine implemented in Conway’s Game of Life“, 2000
- Paul Callahan “Wonders of Math : What is the Game of Life?” sur Math.com
- Game of Life News, un blog dédié aux nouvelles découvertes sur le Jeu de la Vie
- Un “Jeu de la Vie” en Java, utilisant l’algorithme Hashlife implanté dans ce langage, en open source.
- David Bau “Python Curses Life“, une implantation (simplifiée) de Hashlife en Python