Le jeu de la vie
Je vais vous présenter la notion d'automate cellulaire
en vous présentant un automate cellulaire bi-dimensionnel très simple
appelé "Jeu de la vie"
Voici une simulation du jeu de la vie nommée "Mini-Life.nlogo"
que vous pouvez télécharger
de notre page "Course Materials"
Je vais détailler ce qu'est le "Jeu de la vie"
qui n'est pas un jeu du tout
mais, pour l'instant,
laissez-moi vous montrer le type de motifs qui peuvent être créés.
Nous avons ici une grille de cellules
dans lequelles chaque cercle blanc est une cellule
Le cercle peut être coloré soit en blanc ou soit en noir
En cliquant sur "randomize" on obtient 12% de cercles noirs au hasard
Chaque cellule suit une règle simple de comportement
qui consiste à prendre en compte
son environnement local
et à chaque pas de temps toutes les cellules
changent de couleur
selon des règles très simples.
Cliquons sur Go et voyons ce qu'il se passe
cela se stabilise selon une structure simple
après avoir été très complexe
Maintenant modifions le pourcentage de noir à 50%
on clique sur "setup" pour réinitialiser l'écran
sur "randomize" pour générer une nouvelle cnofiguration
ayant 50% de cecles noirs
puis "go" pour lancer la simulation.
On observe un comportement compliqué qui
se simplifie finalement
Voilà
Maintenant retournons aux diapositives
et analysons ce que l'on vient de voir
Le 'Jeu de la vie" constitue un exemple
d'une large classe de modèles appelés "Automates cellulaires"
qui sont une idéalisation
des modèles de systèmes complexes
Ce sont de grands réseaux de composants simples
dont les cellules sont ici les composants
et la partie réseau est la connexion
avec les cellules voisines ou éventuellement lointaines
La communication entre les composants est limitée
les composants communiquent directement avec leurs voisins
il n'y a pas de contrôle central
il n'y a aucune cellule chargée d'une autre cellule
et de plus, comme on peut le voir sur l'exemple du jeu de la vie
on peut obtenir des évolutions complexes
à partir de règles très simples
et, comme on pourra le voir plus tard
les automates cellulaires ont la possiblité
d'effectuer des traitements sophistiqués
de l'information et de calcul
Ils peuvent aussi évoluer au moyen d'Algorithmes Génétiques
Ainsi, comme on peut le voir
les automates cellulaires recouvrent
plusieurs des sujets que nous avons déjà étudiés
allant de la dynamique à l'infomation
et aux algorithmes génétiques
qui mis ensembles constituent
un modèle de système complexe
Maintenant un peu de terminologie
le singulier est "automate cellulaire"
c'est à dire un élément du modèle
en abrégé CA
le pluriel est "automates cellulaires" c'est le modèle
dont l'abrégé est quelquefois CA mais j'utiliserai
pour éviter toute ambiguité
CAs avec un "s" minuscule
Quant à la prononciation
ici en Amérique l'accent tonique est sur "TO"
mais dans d'autres pays dont l'Angleterre
l'accent tonique est sur "MA"
un participant Anglais peut me corriger si je me trompe.
Donc le "Jeu de la vie" est le modèle d'automate cellulaire
le plus célèbre au monde
comme le l'ai indiqué,
mais plutôt un objet de calcul mathématique
plublié en 1970 par le mathématicien Anglais John Conway
il a été très largement diffusé
en particulier au début
dans la rubrique "Jeux mathématiques" de Martin Gardner
du "Scientific American"
La raison pour laquelle John Conway l'a appelé "Vie"
a été inspiré par les modèles
de John von Neumann sur les processus
ressemblant à la vie dans les automates cellulaires
dont on parlera un peu plus loin
Rapidement, ce dont Conway traite,
ce sont de systèmes simples qui montrent l'émergence et
l'auto-organisation
le "Jeu de la vie" est ce sur quoi il est arrivé
Comme je vous l'ai montré précedemment
le "Jeu de la vie" est joué ou se joue
sur une grille de cellules
ici les cellules sont représentées
par des cercles noirs ou blancs
une cellule noire est dite "vivante"
et une cellule blanche est dite "morte"
c'est la terminologie de Conway
Chaque cellule vit au milieu d'un voisinnage
constitué de la cellule elle même au centre
et de 8 voisines.
Le "monde" ne s'arrête pas au bords de la grille
mais par exemple pour cette cellule de gauche,
sa voisine de gauche est celle du bord droit
et pour celle-ci, au sud sa voisine se situe au sommet (nord)
Voici les règles auxquelles chaque cellule obéit :
la 1ère règle est qu'une cellule vivante
c'est-à-dire une cellule noire
reste vivante au pas de temps suivant
seulement si 2 ou 3 voisines sont vivantes
sinon elle meurt
Une cellule morte redevient vivante
au pas de temps suivant
seulement si 3 voisines exactement sont vivantes
Ce sont les règles auxquelles toutes les cellules obéissent
De plus, toutes les cellules sont mises à jour simultanément
selon des pas de temps discrets
Nous allons voir comment cela fonctionne dans une minute
Voici ce à quoi cela ressemble dans notre modèles Netlogo
"Mini-Life.nlogo"
Nous voyons que les cellules colorées en vert
sont celles qui resteront en vie ou ressuciteront
au prochain pas de temps
celle-ci, au milieu
possède 2 voisines vivantes donc elle reste en vie
celle-ci est morte
mais elle a 3 voisines noires
donc elle va ressuciter au prochain pas de temps
les autres n'ont pas de assez de voisines vivantes
leur permettant de rester en vie ou de ressuciter
Donc voici le résultat au pas de temps suivant
dans ce petit carré de 9 cellules
Testez votre compréhension dans ce petit "quizz"
Ce "quizz" a 3 questions
dans chaque question vous avez une grille 5 par 5 du jeu de la vie
considérez que les grilles sont continues d'un bord à l'autre
la question est :
quel est l'état de la cellule centrale
pointée par la flèche rouge
au pas de temps suivant
Donc, essayez de répondre et consultez le résultat sur la vidéo suivante