Le jeu de la vie à une dimension

Présentation

Ce que l'on appelle le jeu de la vie n'est en réalité pas un jeu a proprement parlé : il ne nécessite pas de "joueur". Hormis pour fixer les conditions initiales du jeu, l'humain ne participe pas au jeu. Un automate cellulaire est un objet mathématique évoluant selon des règles très simples et imitant d'une certaine manière, les capacités auto-reproductrices des êtres vivants. Ces automates sont constitués d'une grille, dont ses cellules peuvent prendre plusieurs états, dont souvent deux, qualifiées de "morte" ou "vivante".

L'application la plus connue de ces automates est un programme informatique introduit par le mathématicien John CONWAY en 1970 : le jeu de la vie.

Ce jeu fascine depuis plus de 50 ans les mathématiciens et les informaticiens, mais aussi les biologistes et les philosophes car, bien que mus par des règles très simples, les automates cellulaires peuvent engendrer d'incroyables résultats, riches et complexes, jusqu'à même en venir a modéliser plus ou moins la vie réelle. En effet, les automates cellulaires sont utilisés pour modéliser des systèmes complexes d'un grand nombre d'entités, précédemment appelé les cellules, qui évolue au cours du temps (en mourant, survivant, ou naissant), et dont le comportement ne dépend que des cellules qu'elles peuvent observer localement autour d'elles.

structure notable du jeu de la vie : breeders.

Les automates cellulaires, et plus particulièrement le jeu de la vie sont très "pratique" pour simuler, par exemple, le comportement des milieux granulaires, l’évolution de l'urbanisation, la propagation des feux, des épidémies, la formation d'un tas de sable,... Les informaticiens, eux, voient les automates cellulaires comme un modèle abstrait représentant le fonctionnement des ordinateurs. Plus précisément, ils constituent un modèle de calcul ayant la puissance des machines de Turing.

Dans la version originale décrite par John CONWAY, l'univers est représenté par un tableau à deux dimensions de taille variable, où chaque élément du tableau sont des cellules, pouvant prendre deux états différents : morte ou vivante. Le passage d'un état à l'autre est guidé par les règles d’évolution suivantes :
- une cellule morte au temps t devient vivante au temps t+1 si et seulement si elle a exactement 3 cellules vivantes dans son entourage.
- une cellule vivante au temps t reste vivante au temps t+1 si et seulement si elle a exactement 2 ou 3 cellules vivantes dans son entourage, sinon elle meurt.

Le jeu de la vie par John Conway. Ici, les cellules vivantes sont représentées par les ronds blancs, et les mortes par les cases noires.

Ici nous considérerons une version simplifiée du jeu de John Conway.

Règles de notre jeu

Nous nous contenterons d'une version plus simple du jeu de la vie, une version à une dimension.
Dans notre version, les suites de cellules seront représentées par des séquences binaires circulaires, dont on appelle 1 les cellules vivantes et 0 les cellules mortes. Vu que l’on considère des séquences circulaires, chaque cellule possède exactement deux voisins.
Le passage d'un état à l'autre est guidé par les règles d’évolution suivantes :
- règle 1 : une cellule vivante meurt si et seulement si au moins une de ses deux voisines est vivante.
- règle 2 : une cellule naît si et seulement si exactement une de ses deux voisines est vivante.

une cellule nait si exactement une de ses deux
voisines est vivante
une cellule nait si exactement une de ses deux
voisines est vivante
une cellule vivante meurt si ses deux voisines sont vivantes
une cellule vivante meurt au moins une de ses
deux voisines est vivantes
une cellule vivante meurt au moins une de ses deux voisines est vivantes
une cellule survit si elle est isolée
figure 1 : Configurations de naissance et de mort des cellules

Programme du jeu de la vie

Le programme ci-dessous fait tourner notre version du jeu de la vie. Les cellules mortes sont représentées par les cases blanches, et les cellules vivantes sont représentées par les cases noires. Ici, nous avons fixé à $\frac{1}{2}$ la probabilité qu'une cellule soit vivante.

Rapide description de l'algorithme

Tout d'abord, la séquence de cellules est stockée dans un tableau que nous appellerons board. Les cellules vivantes seront représentées par des 1 et les cellules mortes par des 0.

Pour chaque case du tableau board, on génère un nombre aléatoire entre 0 et 1. Si ce nombre est égal à 1, on met 1 dans cette case, sinon on y met 0. De cette façon, il suffit de changer la borne supérieure de la génération aléatoire de nombre afin de changer la probabilité qu'une cellule soit vivante à l'instant initial.

Maintenant que notre board est correctement initialisé, il faut appliquer les règles d'évolution de notre jeu pour passer d'une génération à une autre. Pour ce faire, on construit un nouveau tableau qu'on nommera next. Après avoir calculé le nombre de voisins en vie d'une cellule, on peut en déduire son état à la génération suivante, qu'on stockera dans next. Une fois que board a été complètement parcourut, il ne reste plus qu'à échanger les tableaux board et next, et afficher board.

Diverses situations

Stabilité

Soient V, l'événement "la cellule est vivante" et M, l'événement "la cellule est morte".

Une situation est dite stable lorsqu'elle n'est pas modifiée par application de la règle d’évolution. Ainsi, les seules situations stables possibles sont les situations dans lesquelles les cellules mortes et vivantes s'alternent, ou la situation dans laquelle il n'y a que des cellules mortes. Cherchons la probabilité qu'une situation donnée soit stable.
Soit n le nombre de cellules.

Prenons le cas de base non trivial d'une situation stable : on a deux cellules.
Il nous faut alors exactement, une cellule vivante et une morte.

Au temps t=0, la cellule 1 est vivante et a deux cellules voisines mortes, elle reste donc vivante (cf figure 1) au temps t+1.
De la même façon, la cellule 2 est morte et a deux cellules voisines vivantes à t=0 et reste donc morte au temps t+1 (cf figure 1).

Par induction, si on répète ce schéma en alternant les cellules vivantes et mortes, la stabilité est conservée. Alors, si n est impair, la répétition du schéma est impossible. En effet, avec n impair on aurait forcément soit deux cellules mortes côte à côte, soit deux cellules vivantes côte à côte. Alors, une évolution sera possible (cf figure 1) et le schéma ne sera pas stable.

Soit l’événement E : "la génération est stable".
Cherchons la probabilité que E se produise.
D'après la figure 2, la situation stable de base comporte deux cellules : une vivante et une morte. La probabilité que cette situation arrive est (P(V) \times P(M)). Si on répète ce schéma k fois, nous obtenons une séquence circulaire binaire de cellules de taille 2k. Alors, la probabilité que cette séquence soit stable est (P(V) \times P(M)^k}
Ainsi, si n=2k la probabilité d'avoir une situation stable est

     \[ (P(V) \times P(M))^ \frac{n}{2} \]

Et si n=2k+1, il est impossible d'avoir une alternance parfaite entre les cellules vivantes et mortes. Dans ce cas, la probabilité d'avoir une situation stable est donc la même que la probabilité d'être dans la situation où toutes les cellules sont mortes : \frac{1}{n}

On peut donc en déduire que la probabilité d'avoir une situation stable est de :

     \[ P(E) = (P(V) \times P(M))^ \frac{n}{2} + \frac{1}{n}\]

Remontons un peu plus haut ... Dans la cas où toutes les cellules sont mortes, on parle de situation catastrophique. Intéressons-nous un peu plus à ce cas particulier.

Catastrophe

Reprenons nos deux cellules précédentes.

Dans le premier schéma de la figure 3, les cellules 1 et 2 sont voisines l'une de l'autre. D'après la règle 1 de notre jeu, les cellules 1 et 2 deviendront blanche, ce qui nous ramène au deuxième schéma. Une fois que toutes les cellules sont mortes, la règle 2 concernant les naissances ne s'appliquera jamais. On arrive donc dans une situation dite catastrophique.

Lorsqu'en appliquant les règles du jeu sur une génération donnée, la génération suivante n'est composée que de cellules mortes, nous appellerons cela une situation catastrophique.
Pour générer une situation catastrophique il faut suivre deux règle :
- règle 3 : chaque cellule morte doit avoir soit deux voisines vivantes, soit deux voisines mortes.
- règle 4 : chaque cellule vivante doit avoir au moins une voisine vivante.
Ainsi, toutes les cellules vivantes vont mourir à la génération suivante via la règle 1 de notre jeu, et la règle 2 du même jeu concernant les naissances ne sera jamais appliquée.

figure 3 : cas de situation catastrophique

On considère la définition suivante : une configuration de n cellules est catastrophique si et seulement si elle est composé que de cellules mortes ou bien elle est composé de m blocs de cellules vivantes, avec chaque bloc composé d'au moins deux cellules, séparés par exactement une  cellule morte. Cette condition force le nombre de cellules morte à être strictement inférieur à $\frac{n}{3}$.

Essayons de compter le nombre de cas catastrophiques pour une séquence de n cellules donnée grâce à cette définition.

Considérons le cas pour n = 10. Soit i, le nombre de cellules mortes. Par définition,  $1 \leq i \leq \frac{n}{3} $. Regardons le cas où i=2.
Quand i=2, nous avons deux blocs de cellules composés de trois cellules : une morte et deux vivantes. Ces deux blocs sont séparés de n-3i cellules. Ainsi, compter le nombre de situations catastrophiques revient à compter le nombre de répartitions possibles de ces n-3i cellules vivantes restantes.

Soit E l'ensemble de ces répartitions. Le nombre de k-multi-ensembles de E est donné par le coefficient multinomial :

     \[\binom{x+k-1}{k}\]

Ici, k est le nombre de cellules vivantes à placer, et x est le nombre d'endroits où on peut placer ces cellules. Comme on a des séquences de cellules circulaires, alors x = i, et le nombre de cellules vivantes à placer est k = n - 3i. Ainsi, pour n = 10 et i=2, on obtient :

     \[\binom{3+(10-2 \times 3) -1 }{10-2 \times 3} = \binom{8}{2} = 28 \]

Généralisons cette formule pour tout n et pour tout  $1 \leq i \leq \frac{n}{3} $. Le nombre de situations catastrophiques, à rotation près, est de :

     \[\binom{i+(n -3i) -1 }{10-3i} = \binom{n-2i-1}{n-3i}\]

Détection de cycles

Si en partant d'une génération i, et en appliquant les règles d'évolution x fois, on se retrouve à la génération i+x avec les cellules ayant les mêmes états que dans la génération i, on peut affirmer qu'il existe un cycle.

Pour trouver ces cycles, on peut s'appuyer sur l'algorithme du lièvre et de la tortue, également appelé l'algorithme de détection de cycle de Floyd.

Le principe de l'algorithme est le suivant :
Une tortue et un lièvre parcourt la suite x0, x1, x2... Le lièvre court deux fois plus vite. Si la suite admet un cycle, alors l'algorithme trouve un indice i avec xi = x2i.

Maintenant, si la suite xi correspondait à l'état des cellules à la génération i, nous pouvons déterminer l'indice du cycle, ainsi que sa longueur.

Exemple : une séquence de 24 cellules

Les générations du jeu de la vie peuvent mener à différentes situations notables : la stabilité, la catastrophe ou la boucle, évoquées ci-dessus.
Afin de trouver les statistiques de tomber sur l'une de ces trois situations, nous nous sommes aidés d'un programme écrit en Java, dans lequel nous avons modélisé les cellules vivantes par des 1 et les mortes par des 0, en partant sur une nombre de 24 cellules (comme dans la modélisation du programme), et avec 1 chance sur 2 d’avoir une cellule vivante. Alors, le problème revient à trouver tous les nombres binaires a 24 chiffres et a compter lesquels représentent une situation particulière de notre jeu.

Puisque nous manipulons des nombres binaires a 24 chiffres, il y a en tout  $2^{24}$ = 16 777 216 possibilités.

Nous avons vu qu'une situation est stable lorsque soit toutes les cellules sont blanches, soit elles sont alternées noires et blanches : 


Il n'y a donc que trois situations de stabilité. Soit S, l’événement "la situation est stable à la deuxième génération". Nous avons :

     \[P(S) = \frac{3}{2^{24}} = 0,00000018. \]



Concernant les situations catastrophiques, le programme nous renvoi 9 643 possibilités sur  16 777 216. Ce dernier prend en compte toutes les rotations possibles des séquences de cellules. Soit C l'événement : "la situation est catastrophique dès la deuxième génération". Nous avons  :

     \[ P(C) =  \frac{9 643 }{2^{24}} = 0,00057. \]


Pour aller plus loin ...

Diagramme espace-temps

On peut représenter un diagramme espace-temps en suivant l’évolution du jeu de la vie à une dimension en fonction du temps t.  Si on commence initialement avec une seule cellule vivante (première ligne de la figure ci-dessous), on remarque que le diagramme espace-temps présente alors une structure auto-similaire.

Diagramme espace-temps du jeu de la vie, avec une seule cellule vivante a l'état initiale.

Et après ...

Notre version simplifiée du jeu de la vie est assez limités par l'unicité de sa dimension. Le jeu de la vie imaginé par CONWAY est, lui, en deux dimensions et permet de générer des structures beaucoup plus impressionnantes, telle que le breeder, montré en introduction, qui génère un motif à l'infini.

Voici une vidéo qui explore plus en détails les possibilités présentées par le jeu :

Références

6 Cliquer pour recommander cet article