Jeu de la vie

Halfmax dans le jeu de la vie
- crédits: imgur

Imaginé par John Conway dans les années 70, le jeu de la vie est automate cellulaire [6]. Il est représenté par une grille dont les cases sont considérées comme des cellules à deux états: elles sont soit vivantes, soit mortes. Comme tous les automates cellulaires, le jeu de la vie possède une règle d'évolution qui permet de calculer l'état des cellules à partir de leur état précédent. Il apparaît intéressant d'étudier le comportement de tels objets dans le cadre des mathématiques discrètes car ils ont un comportement... discret[1]. En effet, ils possèdent un ensemble dénombrable de cellules dont l'état évolue de façon discontinue rendant cette évolution également dénombrable.

Dans ce billet, nous nous concentrerons sur les automates cellulaires dits élémentaires, plus simples à étudier. Nous considèrerons la règle d'évolution nommée Règle 22 et étudierons les configurations stables et catastrophiques qu'elle produit.

Les automates cellulaires élémentaires

Avant de définir ce que sont les automates cellulaires élémentaires, attardons-nous un peu sur les automates cellulaires. Un automate cellulaire est donc une grille régulière de cellules ayant chacune un état appartenant à un ensemble fini. Pour que l'état des cellules puisse évoluer au cours du temps, on associe à un automate cellulaire une règle d'évolution qui calcule l'état suivant d'une cellule en fonction de son voisinage.

Les automates cellulaires élémentaire sont un cas particulier d'automate cellulaire: leur grille de cellules est unidimentionnelle. Ils peuvent donc être vus comme des séquences circulaires. De plus, nous ne parlerons ici que des automates dont les cellules possèdent deux états, soit mort, soit vivant, on note aussi ces états 0 et 1.

Configurations successives d'un automate cellulaire élémentaire.
- crédits: Sciences Étonnantes

Dans un automate cellulaire élémentaire, on appelle configuration une suite de cellules dont l'état est mort ou vivant. On peut calculer la configuration suivante en appliquant ce qu'on appelle une règle d'évolution. Cette règle s'applique sur trois cellules successives et donne la valeur de la cellule centrale dans la configuration suivante [7].

Puisqu'une cellule peut être dans $2$ états différents, il existe $2^3 = 8$ triplets de cellules différents. De la même manière, pour chaque triplet, la cellule centrale peut être dans $2$ états différents dans la configuration suivante. Comme une règle d'évolution est caractérisé par l'état de la cellule centrale dans la configuration suivante pour chaque triplet de cellules, on peut voir qu'il existe $2^8$ règles d'évolution différentes pour ce type d'automate.

Application d'une règle d'évolution (règle 30) sur un automate cellulaire élémentaire.
Les cellules noires représentent les cellules vivantes et les cellules blanches, les cellules mortes.
- crédits: Wikipedia - Cellular automaton - Elementary Cellular Automata

Le code/La notation de Wolfram

Pour nommer les 256 règles d'évolution, Stephen Wolfram définit en 1983 un code basé sur l'état de chaque triplet possible et de l'application de la règle d'évolution sur celui ci. Les cellules vivantes sont représentées par un $1$ et les cellules mortes par un $0$. Chaque configuration est écrite dans l'ordre, $111$, $110$, $101$, $100$, $011$, $010$, $001$, $000$, et le résultat de l'application de la règle d'évolution sur chaque configuration est écrit dans le même ordre et interprété comme un nombre écrit en binaire [9][8].

Ainsi, la règle disant qu'une cellule est vivante si exactement deux de ses voisines, en inculant la cellule elle-même, sont vivante peut être représentée de la façon suivante:

t111110101100011010001000
t+101101000

Si l'on considère le nombre binaire obtenu, on a:

$(01101000)_2 = (104)_{10}$

D'après la notation de wolfram, cette règle est donc nommée la règle 104.

La Règle 22

Intéressons-nous à présent à la règle 22. En utilisant la notation de wolfram, on peut représenter cette règle sous la forme suivante:

t111110101100011010001000
t+100010110

On peut aussi l'exprimer en disant qu' une cellule est vivante si et seulement si exactement une de ses voisines, incluant la cellule elle-même, est vivante; sinon, la cellule est morte [5]. La règle 22 peut aussi être vue comme un XOR sur l'état de trois cellules consécutives[5] .

Pour cette règle, nous nous intéresserons au problème de détection d'un cycle. Nous parlerons ensuite de ce qui caractérise une configuration stable et enfin nous montrerons comment calculer le nombre de configurations catastrophiques admises par la règle 22.

La règle 22 appliquée sur 100 génération à une séquence de 201 cellules en partant d'une seule cellule vivante.
- crédits: Wolfram Atlas - Rule 22

Détection d'un cycle

Considérons un automate cellulaire élémentaire représenté par une séquence de $n$ cellules et une règle d'évolution. Chaque cellule pouvant être dans deux états différents, on peut voir qu'il existe $2^n$ séquences de cellules différentes. Après un certain nombre d'applications de la règle d'évolution la séquence de cellules va donc correspondre à une séquence déjà vue et puisque cette règle ne change pas entre deux générations, une séquence est toujours suivie de la même séquence.

On peut donc voir qu'à partir d'un certain nombre de générations, un cycle de séquences va apparaître. On pourrait penser que detecter un tel cycle prend beaucoup de temps. En réalité, la taille d'un cycle pour une séquence de $n$ cellules dépend beaucoup de la règle d'évolution qui lui est associée. Les tailles des cycles de longueur maximale des règles 22 et 45 sont données ci-dessous pour des séquences de 0 à 32 cellules.

Longueur maximale des cycles par taille de séquence pour la règle 22.
L'axe vertical représente la longueur d'un cycle et l'axe horizontal le nombre de cellules de la séquence.
Crédits: Atlas de Wolfram - Rule 22 - Finite size properties

On peut voir que la règle 22 produit des cycles relativement courts pour les séquences de moins de 32 cellules contrairement à la règle 45 pour laquelle les cycles contiennent parfois presque toutes les configurations possibles pour un nombre donné de cellules.

Longueur maximale des cycles par taille de séquence pour la règle 45.
L'axe vertical représente la longueur d'un cycle et l'axe horizontal le nombre de cellules de la séquence.
Crédits: Atlas de Wolfram - Rule 45 - Finite size properties

Ici, nous souhaitons détecter l'apparition d'un cycle pour une configuration donnée. Pour faire cela nous allons utiliser l'algorithme de détection de cycle de Floyd aussi connu sous le nom d'algorithme du lièvre et de la tortue [2]. Il existe d'autres algorithmes de détection de cyles utilisables pour les automates cellulaires élémentaires mais celui-ci à l'avantage d'être assez simple à comprendre et à mettre en oeuvre, ainsi que de ne nécessiter qu'une mémoire constante [3].

Explication de l'algorithme

Dans sa forme générale, l'algorithme du lièvre et de la tortue considère une suite de valeurs $x_t, t \in \mathbb{N}$ dans laquelle il faut determiner si un cycle existe. Puisqu'ici nous nous intéressons au cycle dans la suite de configurations d'un automate cellulaire élémentaire, on appelle $x_0$ la configuration initiale (celle que l'on choisit) de cet automate. On note également $evol(x_t)$ l'application de la règle d'évolution à la configuration $x_t$, telle que $evol(x_t) = x_{t+1}$.

x_{t_tortue}Le principe de l'algorithme est le suivant. On possède deux pointeurs, une tortue et un lièvre, sur les valeurs de la suite. Au début de l'algorithme, on initialise la tortue par $evol(x_0)$ et le lièvre par $evol(evol(x_0))$. Tant que les valeurs pointées par le lièvre et la tortue sont différentes, la tortue avance d'un pas dans la suite tandis que le lièvre avance de deux pas.

Si l'on note $x_{t\_tortue}$ la configuration pointée par la tortue , cela revient à dire qu'à chaque étape de l'algorithme, la configuration suivante pointée par la tortue est donnée par $evol(x_{t\_tortue})$.
Similairement, si l'on note $x_{t\_lievre}$ la configuration pointée par le lièvre, la configuration suivante pointée par le lièvre est donnée par $evol(evol(x_{t\_lievre}))$.

Lorsque l'algorithme s'arrête ($x_{t\_tortue} = x_{t\_lievre}$), cela signifie qu'un cycle a été détecté.
Dans l'image suivante, un cycle de longueur 3 commençant en $x_3$ est détecté lorsque la tortue pointe sur $x_3$, c'est-à-dire après 3 configurations calculées (on compte le calcul de la configuration à l'initialisation). On peut voir que même si le cycle commence réellement en $x_2$ (le cycle est 6-3-1), la position de la tortue et du lièvre à la fin de l'algorithme ne permettent ni de voir directement où le cycle commence, ni de donner directement sa longueur.

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 alors un indice i avec xi = x2i.
Crédits: Wikipédia - David Eppstein

Preuve de l'algorithme

Nous allons montrer que l'algorithme de Floyd détecte bien un cycle. Cette démonstration est tirée d'une réponse donnée sur le site Math StackExchange, elle montre deux points:
1. si un cycle existe, la tortue et le lièvre finissent par se rencontrer;
2. quand ils se rencontrent, la tortue est à distance $n\alpha$ du début de la séquence ($\alpha$ étant la taille du cycle) et aussi à $n\alpha$ du lièvre [4].

Soit un $A$ un automate cellulaire de taille $n$ avec pour la règle 22 pour règle d'évolution. On note $A_i$ la configuration obtenue après $i$ applications de la règle d'évolution à cet automate. Puisque le nombre de configurations possibles est fini, tout automate cellulaire élémentaire admet un cycle de configurations. On note $C$ la longueur de ce cycle et $T$ le nombre de configurations le précédant.
On peut voir cela comme un graphe à $T + C$ sommets représenté comme suit pour $T=3$ et $C=6$.

Représentation de la situation pour T = 3 et C = 6.
Crédits: Math StackExchange (utilisateur: 1110101001)

On note les $T$ premiers sommets, $-T, -(T-1), ..., -1$ (en partant du sommet le plus éloigné du cycle), et les sommets du cycle $0, 1, ..., C-1$ (dans l'ordre des arrêtes).
On peut écrire $T$ comme $T = kC + r$ avec $0 <= r < C$.

Après $T$ pas, la tortue est au sommet $0$ et le lièvre au sommet $r$. Ceci est vrai car le lièvre avance 2 fois plus vite que la tortue, il a donc fait $2T$ pas. Les $T$ premiers ne sont pas fait dans le cycle, ce qui lui laisse $T$ pas et comme $T = kC + r$, la position du lièvre est le sommet $r$.

Si $r = 0$, le lièvre et la tortue sont sur le même sommet et c'est fini.
Sinon, après $C-r$ pas supplémentaires, la tortue se retrouve à la position $C-r$ et le lièvre à la position $r + 2*(C-r) = r + 2*C - 2*r = 2*C - r$ qui est la même position que celle de la tortue après avoir parcouru un cycle entier. Le lièvre et la tortue sont donc à la même position $C-r$.

Le nombre de sommets parcourus par la tortue jusqu'à sa rencontre avec le lièvre est donc $T + C - r = kC + r + C - r = (k  + 1)C$.

Ce résultat nous permet également de dire qu'il faudra parcourir au moins $T$ configurations et au maximum $C + T$ configurations pour détecter un cycle en utilisant cet algorithme.

Programme de détection

Le programme suivant déroule l'algorithme de détection de cycle de Floyd, puis utilise les deux derniers points pour trouver le nombre de configurations à calculer avant le cycle ainsi que le nombre de configurations qu'il contient. Les configurations affichées sont celles de la tortue pour les deux premières étapes et celles du lièvre pour la dernière. Par défaut l'algorithme calcule une configuration à la fois ("Pas à pas") mais il est possible de cliquer sur "Grandes étapes" pour que chaque étape soit exécutée en une seule fois. Pour exécuter une étape il suffit de cliquer sur la partie contenant les configurations. Cliquer sur "Randomize" permet d'alterner entre une configuration aléatoire et une configuration dont seule la cellule centrale est vivante. À chaque fois qu'une des trois étapes est terminée, le résultat est affiché dans la barre jaune.

Caractérisation des configurations stables

Les configurations stable d'un automate sont celles qui ne sont pas modifiées par l'application de la règle d'évolution. Ici, nous allons essayer de déterminer ce qui caractérise de telles configurations pour la règle 22.

Rappelons les différents cas de l'application de la règle 22:

t111110101100011010001000
t+100010110

On considère les différents triplets de cellules que peut contenir une configuration stable.
Si l'état de la cellule centrale change lors de l'application de la règle d'évolution, aucune configuration stable ne peut contenir ce triplet. On peut donc commencer par éliminer les triplets dont l'état de la cellule centrale change en appliquant la règle d'évolution, ce qui nous laisse les triplets suivants:

txxxxxx101xxxxxx010xxx000
t+1xx0xx1x0

Le graphe orienté suivant est un graphe de de Bruijn (on l'appellera ici, graphe des chevauchements). Dans ce graphe, les sommets représentent les suites de cellules de taille 2. Pour les arêtes, on considère deux sommets $u$ et $v$. Il existe une arête allant de $u$ à $v$ si on peut écrire $u=ax$ et $v=xb$ tel que $a, x, b \in \{0,1\}^3$. Pour chaque arête, on note la suite de cellule $axb$.

On utilise ce graphe pour représenter les configurations de façon plus visuelle. Par exemple, la configuration 010011010 (de taille 9) est représentée sur ce graphe par le chemin 01, 10, 00, 01, 11, 10, 01, 10,00 (de longueur 9). Notons que comme les suites de cellules sont circulaires, le dernier sommet du chemin est composé de la dernière cellule de la suite ainsi que de la première. Toute configuration de cellule de taille $n$ est donc représentée sous la forme d'un cycle de taille $n$ sur ce graphe.

Graphe des chevauchement de longueur 1 entre des mots binaires de longueur 2

Cette représentation permet aussi de voir quels sont les axiomes appliqués: ce sont les noms des arêtes reliant les sommets. Ainsi, si l'on reprend l'exemple précédant, les axiomes appliqués sont: 010, 100, 001, 011, 110, 101, 010, 100, 001 (toujours de longueur 9).

Chemin dans le graphe des chevauchement pour l'exemple

Sur le graphe des chevauchement, les axiomes stables sont encadrés en rouge. On peut alors voir plusieurs choses: pour tout $n$, il existe une configuration de taille $n$ ne contenant que des 0; pour $n$ pair, il existe deux configurations qui peuvent être exprimées par les expressions rationnelles 01(01){n-2} et 10(10){n-2}.

Configurations catastrophiques

Une configuration est catastrophique si la configuration qui la suit ne contient que des cellules mortes. Dans cette partie, nous allons voir comment caractériser les configurations catastrophiques de taille $n$ pour la règle 22.

De la même façon que pour les configurations stables, on peut remarquer qu'une configuration catastrophique ne peut contenir que des triplets qui engendrent une cellule morte. On ne s'intéresse donc qu'aux triplets:

t111110101xxx011xxxxxx000
t+1000x0xx0

On reconsidère donc le graphe des chevauchement que nous avons utilisé pour les configurations stables, en ne gardant cette fois que les arêtes représentant les triplets catastrophiques:

Graphe des chevauchement contenant uniquement les arêtes représentant les axiomes catastrophiques.

On peut commencer par remarquer que pour tout $n$, une configuration catastrophique contient soit uniquement des cellules mortes, soit elle ne contient aucune suite de deux cellules telle que ces deux cellules sont mortes. Autrement dit, les configurations 100101, 01111110, 0101010 ou 0000010000, ne sont pas des configurations catastrophiques. En effet, si la configuration commence par 00, alors seul ce sommet est accessible par la suite ce qui permet de générer seulement une suite de 0. Par contre si la configuration commence par un 01, 10 ou 11, il n'est jamais possible de passer par une arête dont le triplet de cellules contient deux 0.

Pour simplifier l'écriture, renommons les sommets par leur valeur interprétée en binaire:

Graphe des chevauchement contenant uniquement les arêtes représentant les axiomes catastrophiques, avec les sommets renommés.

On peut donc voir le problème sous l'angle suivant: il faut que l'on réussisse à compter le nombre de configurations de la forme 3*(2133*)*, celles de la formes 13(3*213)*2 et celles de la forme 3(3*213)*21. Dans ces trois expressions ne sont contenues ni la suite de cellules uniquement mortes (0*), ni celle de cellules uniquement vivante (3*). Nous devrons donc ajouter 2 à la formule comptant les 3 types de configurations précédentes.

Commençons par la configuration 3*(2133*)*. Pour une configuration de taille 3, il n'existe qu'une seule configuration possible: 213, qui se traduit par la suite de sommets 10, 01, 11 donnant la configuration 101 (il ne faut pas oublier la paire formée par la dernière et la première cellule de la configuration). Pour une configuration de taille n, on peut voir qu'il est possible d'y placer au maximum $\ceil{n/3}$ triplets 213.
Considérons qu'une configuration de taille n contienne i triplets ($i <= \ceil{n/3}$), le nombre de 3 que l'on peut placer vaut donc $n-3i$. Pour se rendre compte du nombre de configurations de ce type que l'on peut obtenir, on peut représenter les triplets 213 par des barres '|' est un 3 par une étoile '*'. Il apparait alors que nous cherchons à calculer le nombre de mots composés de i barres et de n-3i étoiles qui est exactement la valeur du coefficient binomial $\binom{i+(n-3i)}{n-3i}$.
Il nous suffit alors de calculer la somme de cette formule pour tous les i allant de 1 à $\ceil{n/3}$ pour compter le nombre de configurations de type 3*(2133*)* de taille n.

Nous allons réfléchir de la même façon pour les deux types de configuration suivants. Réutilisons l'idée des barres et des étoiles, on représente toujours chaque suite 213 par une barre et chaque 3 par une étoile. Pour les configurations de type 13(3*213)*2, on peut voir que peu importe la configuration, les deux premières cellules ainsi que la dernière ne changent jamais, on peut donc ne pas les prendre en compte. De la même manière, pour les configurations de type 3(3*213)*21, la première cellule et les deux dernière ne changent jamais, on ne les compte donc pas.
Considérons qu'une configuration de taille n contienne $i$ triplets ($i <= \ceil{n/3}$), le nombre de 3 que l'on peut placer vaut donc $n-3i$. Il apparait alors que nous cherchons à calculer le nombre de mots composés de $i-1$ barres et de $n-3i$ étoiles qui est exactement la valeur du coefficient binomial $\binom{i+(n-3i)-1}{n-3i}$.
Il nous suffit alors de calculer la somme de cette formule pour tous les $i$ allant de 1 à $\ceil{n/3}$ pour compter le nombre de configurations de type 13(3*213)*2 ou de type 3(3*213)21 de taille $n$.

On a donc que le nombre total de configurations catastrophiques vaut:


$\sum_{i=1}^{\ceil{n/3}} \binom{i+(n-3i)}{n-3i} + 2\binom{i+(n-3i)-1}{n-3i}$

Bibliographie

[1] “Mathématiques discrètes.” In Wikipédia, October 27, 2019. https://fr.wikipedia.org/w/index.php?title=Math%C3%A9matiques_discr%C3%A8tes&oldid=163909657.
[2] “Algorithme du lièvre et de la tortue.” In Wikipédia, October 14, 2019. https://fr.wikipedia.org/w/index.php?title=Algorithme_du_li%C3%A8vre_et_de_la_tortue&oldid=163522840.
[3] “Cycle detection” In Wikipédia. https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare
[4] “Proof of Floyd Cycle Chasing (Tortoise and Hare)” In Mathematics StackExchange. https://math.stackexchange.com/questions/913499/proof-of-floyd-cycle-chasing-tortoise-and-hare/913529#913529
[5] “On Patterns and Dynamics of Rule 22 Cellular Automaton” Accessed October 25, 2019. https://wpmedia.wolfram.com/uploads/sites/13/2019/06/28-2-1.pdf.
[6] “Jeu de la vie.” In Wikipédia, August 27, 2019. https://fr.wikipedia.org/w/index.php?title=Jeu_de_la_vie&oldid=162165013.
[7] “Elementary Cellular Automaton.” In Wikipedia, September 17, 2019. https://en.wikipedia.org/w/index.php?title=Elementary_cellular_automaton&oldid=916150717.
[8] “Wolfram Code.” In Wikipedia, June 2, 2019. https://en.wikipedia.org/w/index.php?title=Wolfram_code&oldid=899900605.
[9] “Elementary cellular automaton.” In Wikipedia. https://en.wikipedia.org/wiki/Elementary_cellular_automaton#The_numbering_system

16 Cliquer pour recommander cet article