Le Jeu de vie imaginé par John Conway en 1970 est un automate cellulaire célébrissime 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 de 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
- [altmetric doi= »10.1016/0167-2789(84)90251-3″ float= »right »]William Gosper « Exploiting Regularities in Large Cellular Spaces », 1984, Physica D. Nonlinear Phenomena, Vol 10, pp. 75-80 DOI : 10.1016/0167-2789(84)90251-3
- 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
10 commentaires sur “la Résurrection du Jeu de la Vie”
David vient d’expliquer tout ça en vidéo :
Hello,
Je découvre Golly seulement maintenant alors que je connais le jeu de la vie depuis les années 80. Bluffé ! Bravo à votre blog.
comment programmer sous golly? Y a t il un site ou un tutoriel pour apprendre à programmer?
merci.
Bravo également pour la qualité de cet article ! J’avais implémenté hashlife en C en 2008 et juste pour illustrer la puissance de l’algorithme voici les résultats du calcul à la génération 2^4096 du pattern breeder http://www.ericweisstein.com/encyclopedias/life/Breeder.html
Temps de calcul 3.5 secondes
Nombre initial de cellules: 4060
Nombre de cellules à la génération 2^4096: 1.42×10^2464
Une fois sauvegardé sur disque, la taille du fichier contenant le pattern final est de 10 Mo.
A titre de comparaison, un algo conventionnel sur le même pattern et dans le même temps irai à peine jusqu’à la 1000ème génération…
Coucou,
Déjà bravo pour la qualité de ce blog.
J’avais auparavant travaillé sur Conway et consorts, donc j’ai foncé sur Golly pendant mes heures de pause.
Je suis en train de regarder un mobile donc la vitesse de déplacement de manière exponentielle … très amusant …
donc la vitesse de déplacement ? AUGMENTE ?de manière exponentielle ??? Wow ! où on le trouve celui-là ?
Bonjour, je vais profiter de ce commentaires pour plusieurs choses :
Je suis arrivé sur votre site vers 5h du matin, là il est 8 heures…. ça en dit pas mal 🙂
C’est tout simplement génial, bon à cause de tout ça j’ai du aussi passer plus de 30 min sur wikipedia, (et me suis dit une fois de plus que j’aurais jamais le niveau en math pour comprendre wikipedia.)
Ensuite, à propos du jeux de la vie, j’avais découvert ça il y a environ 5 ans, et j’ai trouvé que c’était tout simplement extraordinaire, puis, pour un bref exposé récent, je suis retourné me documenter et j’ai téléchargé Golly.
Quand j’ai vu la forme de base permettant de faire défiler des lettres, WOW je suis tout simplement resté scotché pendant 20 min à admirer la « construction » de ces lettres.
C’était encore plus beau que j’avais programmé un basique jeux de la vie, et quand j’ai vu à quel vitesse et sur une si grande taille il pouvait être exécuté avec un bon algorithme…
Bref, à cause de ça, ma religion est l’émergence, persuadé que nous vivons dans un monde avec des règles relativement simple d’où sorte des choses imprévu mais logique.
Je suis content d’avoir pu vous retenir plus de quelques secondes sur ce blog.
A mon sens, la puissance de Golly permet effectivement l’ émergence d’un second niveau de complexité dans le Jeu de la Vie : on peut combiner des structures simples comme les planeurs, les canons, les miroirs etc pour former des structures effectuant des calculs, et même assembler ces structures pour former un processeur programmable. C’est très spectaculaire parce que le fonctionnement est visible et d’apparence « vivant », mais fondamentalement on reste au même niveau de complexité qu’un ordinateur « normal » (=machine de Turing).
Notre monde est peut-être bien régi par des règles relativement simples, mais il semblerait qu’elles diffèrent selon le niveau d’organisation, ou du moins l’échelle. Les particules fondamentales jouent un jeu de hasard quasiment pur avec des règles incompréhensibles à notre niveau. Elles ont peut-être parfois le droit de remonter le temps ou de surgir du néant (en paires particule/antiparticule). Une fois assemblées en atomes, le hasard joue un rôle moindre, le déterminisme s’installe progressivement dans les lois de la chimie et devient dominant pour les objets solides du grain de sable jusqu’aux astres.
A mon sens le vivant se situe juste à la frontière entre l’échelle du petit où le hasard joue encore un rôle (en permettant en particulier l’Evolution) et l’échelle du grand où le déterminisme nous permet de percevoir une « logique », une continuité dans l’univers.
Pour simuler ceci, il faudrait un « Jeu de la Vie » probabiliste, dans lequel des cellules pourraient naitre ou disparaitre sans briser le fonctionnement d’une structure complexe, mais qui pourrait éventuellement donner naissance à une structure encore plus complexe. Vaste programme…
Hello et merci pour cet article tout à fait passionnant. Le jeu de la vie qui joue u jeu de la vie m’a tout particulièrement bluffé.
Une petite question : tu as l’air de dire que c’est grâce à Paul Rendell qu’on sait que le jeu de la vie permet de construire une machine universelle. Mais, si je ne m’abuse, Conway avait déjà prouvé ça il y a longtemps, non ?
Mais sans doute n’avait-il pas pu, avec les moyens techniques de l’époque construire la dite machine ?
Oui, c’est juste et ça m’avait échappé : selon la Wikipedia Conway et ses étudiants avaient montré qu’on pouvait construire une machine de Turing avec environ 10^13 cellules. C’était peut être en simulant des portes logiques comme décrit sur cette page que je viens de trouver.
Paul Rendell en a fait une avec 36’549 cellules seulement. Chapeau.