Introduction aux automates cellulaires

Introduction

Tout d’abord, définissons un automate cellulaire comme une série de cellules évoluant selon un ensemble de règles définies, donnant donc lieu à une nouvelle génération de cellules. Le principe est utilisé dans plusieurs domaines tels que l’imagerie numérique, la physique, la chimie, et les domaines nécessitant de l’automatisation, comme le génie industriel.

Un premier exemple concret

On définit souvent les règles d’évolution d’une cellule en fonction des voisines de celle-ci.

Donc, si mes règles sont les suivantes :​

• 0 avec un 0 à sa droite devient 1.
• 0 avec un 1 à sa droite reste 0.
• 1 avec un 0 à sa droite reste 1.
• 1 avec un 1 à sa droite devient 0.

En débutant avec la suite 0010 (choisie arbitrairement), on observera l’évolution suivante pour la génération 1 :

On observe alors le résultat suivant :

• 0010 (génération 0).
• 1011 (génération 1).
• 1000 (génération 2).
• 1110 (génération 3).

On complexifie

Ce principe est très facilement extensible. Par exemple, en utilisant les voisines de gauche et de droite, on compare 3 cellules ayant potentiellement deux états plutôt que deux cellules à deux états.

On a donc de 2^3 = 8 règles à définir (déterminer si elles donnent un 0 ou 1).

Chacune de ces règles ayant 2 résultats possibles (0 ou 1), on trouvera donc 2^8=256 possibilités de règles. Celles-ci sont connues et répertoriées comme les Wolfram Rules et donnent lieu à des motifs prévisibles, parfois chaotiques (mais pas aléatoires, notez que tout est prévisible et reproductible à volonté si on connaît la règle utilisée et la génération 0).

Voici quelques exemples de ces règles et de leurs résultats (comme plus haut, chaque ligne est une nouvelle génération). (Source : http://wolframalpha.com.)

Règle 30

Règle 43

Règle 90

Passons à la 2D et plus encore

Pour une ligne de cellules à 2 états, on atteint rapidement une limite (si on ne regarde que les voisines immédiates).

En langage binaire, imaginons qu’on prenne une phrase (par exemple, un mot de passe) et qu’on transforme sa valeur binaire en matrice de 8 cellules de large.

On décide ensuite de règles pour les quatre voisines du haut, bas, gauche et droite. Incluant la valeur de la cellule elle-même, on a 2^5 = 32 règles à déterminer, ayant chacune une possibilité de 2 valeurs de sortie (0 ou 1). On aura donc, selon le même calcul que les règles Wolfram, 2^32 façons différentes de choisir sa règle, soit plus de 4 milliards.

L’incontournable Game of life

Comparant une cellule et ses 8 voisines, John Conway a créé un ensemble de 4 règles qu’il a animées, donnant lieu au jeu « Game of life ». Je vous laisse observer ses règles et comment elles interagissent entre elles :

1. Une cellule vivante meurt si elle a moins de deux voisines vivantes.
2. Une cellule vivante survie si elle a deux ou trois voisines vivantes.
3. Une cellule meurt si elle a plus de trois voisines vivantes.
4. Une cellule morte avec exactement trois voisines vivantes devient une cellule vivante.

Des exemples de résultats :

On généralise donc en disant :

Pour un nombre S d’états possibles pour une cellule, et pour un nombre N de cellules vérifiées pour établir la prochaine génération, on aura S^(S^N) possibilités de combinaisons de règles.

Par exemple :

• Pour 2 états et 3 cellules vérifiées (comme avec la règle n^o 30), on a 2^(2^3) possibilités.
• Pour 2 états et 9 cellules vérifiées (en agissant sur un pixel et tous ses voisins), on a 2^(2^9) possibilités.
• Pour 2 états et 27 cellules vérifiées (en comparant une grille de cubes en 3D, comme dans le jeu Minecraft), 2^(2^27) possibilités.

Quelques utilisations

Imagerie numérique

Dans un modèle 2D avec plus de deux états, par exemple avec des pixels de couleur, il est possible de créer des transformations de ceux-ci : créer un effet de flou, rendre les contrastes plus forts, affaiblir le grain d’une photo, nettoyer les artefacts laissés par la compression, etc.

Génération aléatoire

La règle Wolfram 90 permet de générer un motif semblable à quelque chose d’aléatoire. Il suffirait de choisir la population binaire initiale en fonction d’un élément connu (la date et l’heure, l’adresse IP de la personne qui visite notre site, etc.) pour générer, après un nombre fini de générations, une nouvelle suite binaire « aléatoire » (notons que le hasard absolu est inexistant en informatique). On pourrait utiliser cette valeur aléatoire comme clé de cryptage, comme valeur pour le salage, etc.

Dans le cadre de la génération aléatoire de cartes de terrain (par exemple dans des jeux vidéos comme les Dungeon Crawler et Rogue-like), on utilise un algorithme d’automate cellulaire afin de nettoyer le résultat des éléments parasites.

Dans l’exemple ci-dessous, tiré du site roguebasin.com : un mur (#) reste un mur s’il possède 4 murs autour de lui. S’il n’est pas un mur, il en devient un s’il est entouré par 5 murs ou plus. Sinon, il devient un espace vide. On utilise donc les automates cellulaires afin de faire du nettoyage.

Sécurité

Je parle de transformation binaire depuis le début de l’article, il est inutile donc de justifier de l’utilité pour le cryptage de données. Comme on peut le deviner, celle-ci est bien souvent unilatérale, selon le type de règles. Malgré le nombre de combinaisons mentionné plus haut, celles-ci ne sont pas toutes utilisables. Dans un cryptage unilatéral, il est absolument inutile que toutes les données se transforment toujours en zéro, par exemple. Dans une optique moins extrême, ultimement, il y aura toujours des risques de collision entre les règles (voir Rainbow Table). Cependant, il s’agit d’une méthode efficace pour être, par exemple, incapable de remonter à un mot de passe à partir de sa version cryptée.

Il y a cependant le moyen d’utiliser différentes règles à chaque génération, de faire varier le nombre de fois que la génération zéro évoluera selon différents critères connus, etc.

Et si on avait plus que deux états ?

On a discuté ici de cellules binaires, à deux états possibles. Et si on augmentait le nombre d’états ? Ça donnerait lieu à plus de possibilités, évidemment.

Pensons à Minecraft, et imaginons que nous utilisons un algorithme d’automate cellulaire pour créer le monde, un algorithme de « Big Bang ». À partir d’une génération zéro complètement aléatoire composée de lave, d’eau, d’air et de terre, il serait possible de faire évoluer, par exemple, une flaque d’eau en air si elle est entourée par plus de 4 carrés de lave, ou alors en terre si elle n’en a qu’une ou deux. On termine nos règles, puis on laisse suivre son cours au « monde » qui se générera par lui-même.

Le Langon Loop, lui, démontre un automate à 8 états capable de se reproduire lui-même en se rétrécissant lorsque ça devient nécessaire.

Et ensuite ?

Comme John Conway l’a dit dans une entrevue, Game of Life n’est pas une percée mathématique importante à proprement parler. Son “jeu” est simplement une démonstration de ce qu’on peut faire avec un ensemble de règles toutes simples. De plus, il est impensable de créer un ensemble de règles valables permettant un cryptage symétrique, et la performance devient un problème si on veut faire évoluer des cellules lorsqu’on a une quantité phénoménale de règles et de cellules à gérer.

Ceci étant dit, les automates cellulaires sont utilisées dans la plusieurs domaines. En imagerie numérique, ils permettent de traiter pixel par pixel et créer des effets comme ceux mentionnés plus haut. Dans la physique, ils permettent d’offrir des modèles de prédiction et d’estimation, par exemple, pour les gaz sur réseau. Dans un contexte industriel, le constructeur universel de Von Neumann démontre la possibilité pour une machine de se reproduire elle-même. Par extension, on pourrait sans doute avoir un système qui évoluerait de lui-même, et plusieurs se penchent donc sur l’intégration des automates cellulaires à des principes d’intelligence artificielle.

La documentation est encore éparse, et le sujet encore jeune, je ne peux donc que vous encourager à lire davantage sur le sujet si cet article a piqué votre curiosité !

—

Olivier Mageau-Pétrin.
Amoureux de la logique et des puzzles, je suis dans le domaine du logiciel depuis maintenant 10 ans. J’adore trouver des solutions efficaces et permettre à la technologie d’œuvrer pour les gens.