Le jeu de la vie

 

Le jeu de la vie a été créé par J. Conway, un mathématicien anglais, dans les années 70. Il a été popularisé par Martin Gardner dans ses rendez vous mensuels du journal "Pour la sciences".

Grace à l'apparition des premiers ordinateurs personnels, beaucoup se sont passionnés pour ces expériences de biologie virtuelle.

Les règles.
Des exemples pour comprendre.
Faire fonctionner le programme.
Commentaires sur le programme.
Quelques colonies intéressantes
Conclusion.


Les règles

Ce jeu consiste à observer l'évolution de colonies de cellules virtuelles qui vivent, se reproduisent, et meurent sur un quadrillage rectangulaire suivant des règles précises.
Avant d'énoncer ces règles, précisons que chaque case du quadrillage rectangulaire contient une cellule ou n'en contient pas. On définit le voisinage d'une case (ou de la cellule qui y est contenue) comme étant l'ensemble des 8 cases qui l'entourent. Autrement dit deux cases sont voisines si elles ont au moins un sommet commun.

Par exemple le voisinage de la case "c" est constitué des 8 cases colorées.

Dans ce jeu, il faut décrire la génération 0, c'est à dire que l'on choisit la composition de la première colonie. Par exemple on peut décider que la génération 0 est constituée des 5 cellules disposées sur un quadrillage comme dans l'exemple ci dessous.

A la génération 0 succède la génération 1, grâce aux 4 règles suivantes :

1-Les cellules qui ont moins de deux cellules voisines à la génération 0 sont mortes d'isolement à la génération 1.

2- Les cellules qui ont plus de trois cellules voisines à la génération 0 sont mortes d'étouffement à la génération 1.

3- Si une case vide a trois cellules voisines exactement à la génération 0, alors dans cette case, naît une cellule à la génération 1.

4-Une cellule qui a 2 ou 3 voisines à la génération 0, reste vivante à la génération 1.

Les règles d'évolution de la génération 1 à la génération 2 sont les mêmes, et plus généralement de la génération n à la génération n+1, et ceci pour tout entier naturel n.


Des exemples pour comprendre

exemple 1: "Le clignotant"

génération 0.

A la génération suivante, les 2 cellules extrèmes vont mourir d'isolement, celle du centre va vivre. Au dessus et au dessous de la cellule centrale, il y a 2 cases vides, qui ont 3 cellules voisines, et dans lesquelles va naitre une cellule.(voir génération 1)

génération 1.

La situation est symétrique.

génération 2.

Identique à la génération 0.

On obtient donc un processus périodique.

génération 3.

On retrouve la génération 1.

Cette colonie est nommé "le clignotant".

exemple 2: "feu de navigation"

génération 0

Toutes les cellules survivent à la génération 1, car elles ont 2 ou 3 voisines. Chaque case occupée par des points ont 3 cellules voisines. Dans chacune de ces 3 cases va donc naitre une cellule à la génération 1.

génération 1

1 cellule a 6 voisines, une autre en a 5, et 2 en ont 4. Ces 2 cellules vont mourir d'étouffement. Par contre les 3cases occupées par des points ont exactement 3 cellules voisines, donc à la prochaine génération, il va naître une cellule dans chacune de ces 3 cases.

génération 2

4 cellules vont mourir d'isolement, car elles n'ont qu'une voisine. Une cellule continue à vivre, et dans les cases marquées d'un point va naitre une cellule à la prochaine génération.

génération 4

La colonie va continuer d'évoluer.Chercher les générations suivantes à l'aide de papier-crayon-gomme ou avec le programme sur Excel décrit plus loin.

On peut ainsi tester différentes générations 0 et observer comment elles évoluent. Certaines meurent rapidement, d'autres se stabilisent ou deviennent périodiques, d'autres se développent ou se déplacent à travers le quadrillage. Les simulations se font très rapidemment avec un ordinateur, en prenant par exemple comme support une feuille de calcul. Faire le programme sous EXCEL en utilisant le visual basic est assez amusant. Je propose donc un programme que vous pourrez surement améliorer. Il peut être téléchargé et il est également commenté un peu plus bas.


Faire fonctionner le programme

Télécharger le fichier "jeu de la vie".

Ouvrir ce fichier avec EXCEL.

Sur la feuille " jeu de la vie" du classeur :
1) mettre des" X" dans les cases qui contiennent des cellules qui composent la génération 0. C'est vous qui choisissez ces cases. Vous pouvez également copier-coller des colonies qui se trouvent sur la feuille "exemples colonies".
2) aller dans le menu Outils-Macro-Macro(cliquer sur le deuxième Macro), une fenêtre s'ouvre, cliquer sur "programme principal" puis sur éxécuter.

Le programme se met en route pour 100(on peut modifier le paramètre "longueur"directement dans le programme) générations et vous pouvez alors voir évoluer le processus.
Lorsque la 100ème génération est terminée, le programme s'arrête. Vous pouvez également modifier le paramètre "dimension" dans le programme. Ce paramètre est le côté du carré sur lequel se déroule le processus. Plus il est grand plus le nombre de cases soumises au calcul est grand et moins la succession des générations se fait rapidemment. De toute façon, le paramètre dimension ne peut dépasser 255 qui est le nombre de colonnes sur une page. Pour beaucoup d'ordinateurs, dimension = 150 est déjà très grand, et le programme peut planter. Il faut faire des essais.

En sélectionnant avec la souris, la zone qui contient les cellules, vous pouvez les effacer en faisant apparaitre le menu supprimer avec un clic droit de souris. Il est aussi possible de sélectionner toutes les cases de la feuille en cliquant sur le coin en haut à gauche de la page ( ligne0, colonne 0). Pour rendre blanche la feuille avant de démarrer, on utilise le pot de peinture. On peut également faire varier le nombre de cases qui apparait sur l'écran en jouant sur la fonction zoom de excel(100% , 75% , 50% ou même 25%)

Pour changer certains paramètres, faites apparaitre le programme, en allant dans le menu Outils-Macro-Visual Basic editor (ou Alt F11) ou encore Outils-Macro-Macro-modifier.
Pour revenir à la feuille de calcul, cliquer sur la croix à gauche dans la barre des taches(ou Alt F11).
Vous pouvez interrompre le programme à n'importe quel moment en appuyant sur Esc. Cliquer ensuite sur déboguage, ce qui vous envoie dans la feuille du programme, et cliquer sur le petit carré(réinitialiser).



Commentaires sur le programme

Dim longueur, couleur1, couleur2 As Single
Const dimension As Single = 100
Dim generation1(1 To dimension, 1 To dimension) As Single
Dim generation2(1 To dimension, 1 To dimension) As Single

Cette partie du programme déclare les variables. longueur désigne le nombre de générations qui seront observées. longueur est fixé à 100 dans le sous programme init, mais on peut changer cette valeur directement dans le programme. dimension est une constante qui désigne le côté du carré quadrillé sur lequel le processus évolutionniste se déroule. Elle est fixée à 100 mais vous pouvez changer sa valeur si certaines colonies de cellules se développent beaucoup. dimension est déclarée comme constante, ce qui signifie que l'éxécution du programme ne peut changer sa valeur. generation1 et generation2 sont des tableaux de (dimension x dimension) entiers qui sont 1 ou 0 suivant qu'une case contient ou non une cellule. Si les générations de cellules dépassent la partie de la feuille d'Excel composée du quadrillage formé des dimension premières lignes et dimension premières colonnes, les lois de reproduction ne s'appliquent plus.
couleur1 est le numéro de la couleur des cases occupées par des cellules et couleur2 celle du fond.

Sub init()
couleur1 = 3
couleur2 = 6
longueur = 300
Cells(65, 3).Value = "/"
Cells(65, 4).Value = longueur
For i = 2 To dimension - 1
For j = 2 To dimension - 1
Cells(i, j).Interior.ColorIndex = couleur2
If Cells(i, j).Value = "X" Then
Cells(i, j).Interior.ColorIndex = couleur1
generation1(i, j) = 1
End If
If Cells(i, j).Value = "" Then generation1(i, j) = 0
Next j
Next i
End Sub

Sub init est le sous programme d'initialisation des paramètres et de lecture de la génération 1. C'est le sous programme qui est appelé en premier par le programme principal.
Les paramètres "dimension" , "longueur", couleur1, couleur2 sont initialisés et leurs valeurs peuvent donc facilement être modifiées par n'importe quel utilisateur, directement dans le programme.
Les 2 lignes suivantes permettent de rappeler la valeur du paramètre longueur dans la cellule qui se situe au croisement de la ligne 65 et de la colonne 3. C'est pratique lorsqu'on observe l' évolution de la colonie.
La double boucle suivante permet d'initialiser le tableau generation1, par lecture de la feuille de calcul dans laquelle vous aurez précisé la génération d'origine en plaçant des "x" dans les cellules choisies, puis de colorier le damier.

Function voisinage(i, j) As Single
r = 0
For ligne = i - 1 To i + 1
For colonne = j - 1 To j + 1
r = r + generation1(ligne, colonne)
Next colonne
Next ligne
r = r - generation1(i, j)
voisinage = r
End Function

Cette fonction voisinage compte le nombre de cellules autour de la case de coordonnées (i,j). C'est le compteur r, initialisé à 0 au début du compte qui rend la valeur . La double boucle examine 9 cases, fait la somme de leurs valeurs, et la 8ème ligne soustrait la valeur de la case centrale qui ne fait pas partie de son propre voisinage. Le paramètre voisinage prend la valeur de ce compteur et cette valeur est rendue au sous programme évolution, car c'est lui qui avait appelé cette fonction .

Sub basculement()
For i = 1 To dimension
For j = 1 To dimension
generation2(i, j) = generation1(i, j)
Next j
Next i


Le sous programme basculement sert à initialiser les données de generation2 avec celles de generation1. generation2 sera modifiée à nouveau avec le sous programme évolution ou les règles de vie seront appliquées.

Sub evolution()
For i = 2 To dimension - 1
For j = 2 To dimension - 1

If generation2(i, j) = 1 And (voisinage(i, j) < 2 Or voisinage(i, j) > 3) Then generation2(i, j) = 0
If generation2(i, j) = 0 And voisinage(i, j) = 3 Then generation2(i, j) = 1

Next j
Next i
End Sub

Le programme basculement a entré les données de generation1 dans le tableau generation2, et le sous programme évolution met en application les règles de vie et de mort énoncées dans le paragraphe "règles" et modifie alors le tableau generation2 grace à la double boucle.

Sub afficher()
For i = 1 To dimension
For j = 1 To dimension
If generation2(i, j) <> generation1(i, j) Then
If generation2(i, j) = 1 Then Cells(i, j).Interior.ColorIndex = couleur1 Else Cells(i, j).Interior.ColorIndex = couleur2
End If
Next j
Next i
End Sub


Le code de ce sous programme est à soigner car le temps d'affichage est beaucoup plus long que le temps de calcul. Les seules cases qui changent d'affichage(de couleur)sont celles qui correspondent aux valeurs de i et j pour lesquelles generation1(i,j) et generation2(i,j) sont différents. Pour cela une double boucle compare les 2 générations. Les croix X, placées au départ pour définir la génération 0, ne se déplacent pas; elles sont là pour rappeller la génération 0.

Sub basculement2()
For i = 1 To dimension
For j = 1 To dimension
generation1(i, j) = generation2(i, j)
Next j
Next i
End Sub

Le sous programme basculement2 sert à initialiser les données de génération1 avec celles de génération2, une fois que celles ci sont modifiées. Ce sous programme fait exactement l'inverse du sous programme basculement.

Sub programmeprincipal()
init
For n = 1 To longueur
Cells(65, 2).Value = n
basculement
evolution
afficher
basculement2
Next n
End Sub

Le programmeprincipal est le chef d'orchestre. Il définit l'ordre dans lequel les différents sous programmes sont appelés. A travers la boucle il fait recommencer autant de fois que le paramètre longueur le calcul de générations. C'est donc ce programme qu'il faut appeler pour démarrer le programme, après avoir défini la génération 1.

 


Quelques colonies intéressantes

Certaines colonies, comme celles proposées ci-dessous, permettent de prouver certains résultats, par exemple qu'il existe des colonies stables, des colonies périodiques, des colonies tueuses,des colonies qui se déplacent, et des colonies dont le nombre d'individus tend vers l'infini. On peut les tester avec le programme fourni et copier-coller ces colonies qui sont sur la page "exemples de colonies"

cette colonie est stable et prouve donc qu'il existe des colonies stables dites aussi 1-périodiques.
cette colonie, présentée plus haut est 2-périodique. Elle est appellé clignotant.
cette colonie, appellée planeur, se déplace et est pseudo 4-périodique. la vitesse de ce planeur est de une case en horizontal et une case en vertical toutes les 4 générations.
cette colonie est un vaisseau spatial. Elle est pseudo 4-périodique, et elle se déplace deux fois plus vite dans le sens horizontal que le planeur.
La colonie ci dessus est formée de deux stuctures périodiques sur lesquelles rebondit un planeur. On l'appelle le relais
Cette structure est formée de deux planeurs, qui se désintégrent, lors de leurs rencontres.
Cette colonie est constituée d'une stucture stable ( en haut), qui va se réveler gloutonne, absorbant totalement le planeur au bout de quelques générations.
Cette colonie est la plus petite (11 cellules) connue ayant un développement infinie. La suite des générations construit une succession de points, formés de 4 cellules, qui dessinent une courbe périodique rappellant une sinusoïde. Il faut être patient ( 10 minutes)et attendre 400 à 500 générations pour voir cette courbe apparaitre, mais ça vaut le coup.
Voila une association de 5 cellules à descendance nombreuse. Il paraitrait qu'au bout de 1103 générations, la colonie se stabilise à l'intérieur d'un cadre de dimension 51x109, et est alors constituée de 19 blocs stables. Malheureusement je n'ai pas constaté la même chose, sans pouvoir expliquer pourquoi.


 

Conclusion

Il existe sur ce sujet une documentation nombreuse et variée.
Vous trouverez de nombreux sites en tapant "jeu de la vie" ou " vie artificielle" ou "automate cellulaire" dans un moteur de recherche.
des livres :
1) Vie artificielle de Jean Philippe Renard chez Vuibert informatique
2) Jeux mathématiques et mathématiques des jeux de Jean Paul Delahaye, bibliothèque pour la science.
Si un lecteur programmeur en Java, voulait proposer un programme explicité et commenté, je pourrais l'inclure dans cette page.
Si certains veulent proposer des améliorations du programme en Visual basic, elles sont bien sur bienvenues.

Pour toutes remarques concernant cette page, écrire à Philippe Bondon.