Généralisations du jeu de la vie : vers une version continue

Elias O'Regan

LIAP5-CRIP5

JET 9 - 2 avril 2003

Présentation

• Les travaux menés sur les automates cellulaires en vie artificielle ont en général pour but d'étudier les systèmes minimaux faisant apparaître certains comportements complexes (déplacement, duplication, auto-organisation, universalité).

• Le jeu de la vie est un très bon exemple pour étudier ce type de problématique, car une règle de transition très simple, mais appliquée en parallèle à un grand nombre d'éléments fait apparaître des dynamiques complexes, et des comportements assimilables à ceux des systèmes vivants.

• Plusieurs généralisations du jeu de la vie ont été étudiées, et l'on s'intéressera ici à une manière, partant de la famille Larger than Life, d'envisager un système dynamique continu ayant le même type de comportements que le jeu de la vie.

du Jeu de la Vie à Larger than Life

• Le point de départ : le jeu de la vie de Conway (1970).

• 1ere généralisation par Bayes (1987) dans un espace 3D. Changement des conditions de survie et de naissance. 4 paramètres (S1,S2,N1,N2) déterminent une règle de transition :– survie ssi S1<NV<S2

– naissance ssi N1<NV<N2

• Etude du cas 2D au LIAP-5, dans (Magnier et al, 2000) : transition de phase, découverte de nombreux gliders.

• Extension de la notion de voisinage : Larger than Life (Griffeath, 1994) et (Evans, 1996, 2000)– Voisinage = voisinage de Moore étendu

Larger than Life : définition

• De la même manière que pour le jeu de la vie, on se place sur une grille 2D, chaque case de cette grille renfermant un automate à 2 états {0,1}, qui change d'état en fonction des états de ses voisins.

• On prend en général comme voisinage, le voisinage de Moore étendu de rayon r.

• Chaque cellule évalue sa densité de voisinage :

Dt (a,b) = 1/|V(a,b)| .Σ(x,y) V(a,b) Ct(x,y)

• La fonction de transition dépend de 4 paramètres (β1, β2, δ1, δ2), et est définie par :

si Ct(x,y) = 0 alors Ct+1(x,y) = 1[β1, β2]( Dt(x,y) )

si Ct(x,y) = 1 alors Ct+1(x,y) = 1[δ1, δ2]( Dt(x,y) )

• L'état suivant est donc 1 ssi Dt I, où I dépend de l'état de la cellule.

zoologie de Larger than Life

• On retrouve les objets classiques des AC : – gliders

– canon à glider

– auto-replicateurs

– puffer …

• Auto-organisation à partir de configurations initiales aléatoires :– labyrinthes

– empreintes digitales

– jeu de la majorité

Invariance par changement de voisinage

• K.Evans (1996, 2000) a mis en évidence certains patterns dont le comportement reste invariant lorsque l'on change leurs tailles et la taille du voisinage d'un même rapport. De manière plus générale, des expérimentations ont montré que pour certaines catégories de patterns, le type de dynamique est conservé, lorsque l'on modifie la forme du voisinage.

• Les voisinages suivants ont été testés :– voisinages de Moore étendu,

– voisinages Von Neuman étendu (carré tourné de 45°),

– voisinages rectangulaires,

– voisinages faisant une approximation discrète d'un disque.

• Dans ces différents cas, on retrouve le même type de dynamique.

Rendre l'espace continu

• D'une manière générale, on observe que les configurations sont invariantes par changement de la forme du voisinage, si on leur fait subire la même modification qu'au voisinage.

• Une autre manière de voir : considérer qu'on approxime un système dynamique continu :

– Moore étendu :• doubler la taille du voisinage et du pattern est équivalent à découper chaque cellule en 4

cellules plus petites.

– Von Neuman étendu :• l'échantillonage se fait sur une grille tournée de 45°.

– Rectangle :• le taux d'échantillonnage n'est pas le même sur les deux axes.

– Approximation d'un disque :• revient à prendre un voisinage circulaire dans le cas continu : on n'approxime plus le

même système.

Vers un temps continu

• La règle de transition de LtL est définie par :– Ct+1 = 1[min,max] (Dt)

• On peut observer un effet de ralentissement en ajoutant des instants intermédiaires (entre t et t+1) :– Ct+1/n = 1/n ( (n-1)Ct + 1[min,max] (Dt) )

• L'ajout d'instants intermédiaires nécessite d'augmenter le nombre d'états possibles des cellules : Q = {0, …, n}.

• Dans le but de trouver un système dynamique continu ayant le même comportement, on regarde la dérivée discrète :– Ct+1/n - Ct = 1/n (1[min,max] (Dt) - Ct )

– (Ct+1/n - Ct) / (1/n) = (1[min,max] (Dt) - Ct )

• en passant à la limite, on obtient : Ct/ t = (1[min,max] (Dt) - Ct )

Le jeu de la vie continu

• On est donc arrivé à une équation différentielle régissant un système dynamique dans lequel tout est continu (espace, temps et états), dont les AC de Larger than Life sont des approximations.

• Si elle admet des solutions, l'équation différentielle

Ct/ t = (1[min,max] (Dt) - Ct )

aura des solutions de la forme :Ct = e-tC0 + k(t)

où k(t) est une fonction positive de Ct

• Remarquons que cette expression empêche l'existence de glider. En effet, le terme e-tC0 ne s'annule jamais. Les pseudo-gliders de ce système dynamique laisseraient alors une trace derrière eux. Une propriété (l'existence de glider) a donc été perdu lors du passage au continu.

Conclusion

• Il existe peut-être d'autres manières de rendre le jeu de la vie continu, tout en préservant l'existence de gliders.

• La question de l'universalité de Larger than Life est toujours posée.

• 3D- fat bug

• relation discret / continu et l'hypothèse "Finite Nature"