Dans les années 1970, John Horton Conway, mathématicien anglais, proposa le « jeu de la vie » à partir d’une idée de Von Neumann. Il s’agit de regarder évoluer un système où chaque case d’un damier à un comportement qui dépend de ses voisins immédiats.

Règles du jeu

Sur une grille de taille variée voire infinie, on dispose au hasard des pions qui symbolisent les cases vivantes. Les cases qui ne comportent pas de pions représentent au contraire des cases mortes. Conway propose quelques lois simples pour faire évoluer ce système qui dépendent du nombre de voisins qu’a chaque pion :

• Pour survivre, un pion doit avoir deux ou trois voisins dans les huit cases qui l’entourent. S’il en a plus il meurt de surpopulation, s’il en a moins, il meurt d’isolement.
• Une case vide qui a exactement trois voisins permet de faire apparaître un nouveau pion

A chaque étape, en fonction de la situation de l’échiquier, on détermine les pions qui meurent ou qui survivent et les cases vides qui font « naître un pion ». Ces règles simples permettent à partir d’une configuration de départ de la grille, de faire évoluer une population de pions.

Des comportements collectifs émergents

Les résultats sont parfois surprenants. Il "émerge" de ces règles simples appliquées aux pions individuels des comportements collectifs. Il permet de voir apparaitre visuellement des propriétés émergentes.

Wikipédia propose un ensemble d'articles sur le jeu de la vie. On y trouve par exemple la configuration du Planneur : un ensemble de 5 pions disposés d'une manière particulière et qui au bout de 4 étapes du jeu de la vie se retrouve à l'identique mais déplacés dans la grille.

Emergence et réductionnisme

On oppose souvent l'émergence au réductionnisme sur lequel est fondée la science.

• Le réductionnisme, au sens fort, élimine les propriétés apparentes d'un système pour les remplacer par les processus élémentaires sous-jacents
• L'émergence au contraire part du fait que "le tout est plus que la somme des parties"

Si le réductionnisme a permis un grand nombre de succès, il ne permet pas d'expiquer un certain nombre de phénomènes que l'on observe à des échellons supérieurs de complexité. Si on dissocie les élements, les propriétés émergentes disparaissent.

Les automates cellulaires

Les règles du jeu de la Vie conduisent à un comportement complexe. Mais si on change les règles du jeu le comportement change. Ce genre de fonctionnement où des pions appliquent des règles simples sur une grille est appelé "automates cellulaires de dimension 2" (la dimension d'une grille plate). On peut retrouver dans ce cas les différents types d'automates cellulaires identifiés par Stephen Wolfram dans son livre "a new kind of science". Dans son cas, il s'est "limité" aux 256 automates cellulaires binaires de dimension 1, ce qui lui permet de distinguer 4 types d'automates cellulaires. Les automates cellulaires binaires de dimension 2 permettent eux 1296 règles différentes du type :

• si une cellule à l'état 1 est entourée par X Cellules à l'état 1 avec E_b<=X<=E_h alors elle conserve son état
  
• si une cellule à l'état 0 est entourée par Y Cellules à l'état 1 avec F_b<=Y<=F_h alors elle passe à l'état 1
• Dans tous les autres cas elle passe à 0
  

On note la règle sous la forme E_bE_hF_bF_h. Ainsi le jeu de la vie est la règle 2333 qui est de classe IV.

Les classes d'automates cellulaires

• Classe 1 : évolution vers un état fixe et homogène (par exemple la grille complètement vierge ou encore complètement couverte de pions) (dynamiques ordonnées)
  
• Classe 2 : évolution vers des structures stables ou périodiques (il peut y avoir des structures locales qui oscillent entre deux états différents, insérées dans ne structure globalement stable) (dynamiques ordonnées cycliques)
  
• Classe 3 : évolution vers une succession de configurations arbitraires : toutes les générations sont localement différentes mais globalement et statistiquement semblables (par exemple la proportion de cellules à l'état 1) (dynamiques désordonnées)
  
• Classe 4 : évolution vers un système complexe ou des structures émergent (comme dans le jeu de la vie ou on trouve par exemple des planneurs et des possibilités de simuler une machine de Turing) (dynamiques complexes à mi-chemin entre les dynamiques ordonnées et désordonnées)
  

La complexité (classe IV) entre l'ordre et le desordre

La complexité apparait à mi-chemin entre l'ordre et le désordre. Au lieu d'avoir un désordre qui s'acroit continuemment à partir de l'ordre, on observe à un moment une augmentation de la complexité jusqu'à un seuil - une transition de phase - où elle décroit ensuite. En physique un système subit une modification profonde de certaines de ses propriétés pendant une transition de phase. Avant et après, on a une certaine forme de stabilité dynamique, mais pendant la transition, lorsque la complexité est maximale, on se retrouve loin de l'équilibre (voir les structures dissipatives de Ilya Prigogine).

La question est de savoir jusqu'à quel niveau de complexité on peut aller. cela revient à étudier la capacité de traitement de l'information du système. Certains automates comme celui du jeu de la vie peuvent simuler une machine de Turing, c'est à dire sont potentiellement capable de traiter n'importe quel problème (propriété de computation universelle). Cela veut dire que le jeu de la vie, par exemple, peut être utilisé comme un ordinateur pour traiter des problèmes (pour cela il dispose de structures qui permettent de produire des signaux - les "canons à glisseurs" - qui peuvent se propager - "planneurs", et être triatés par des types de portes ET, OU ou NON (démonstration faite par Elwyn Berlekamp, John Conway et Richard Guy en 1982).

En fait les automates de classe IV sont les seuls à combiner à la fois des carastérisitique des classes I et II
(stokage de l'information sous forme d'attracteurs) et de la classe III (transmission de l'information mais en détruisant l'état antérieur).

les reseaux d'agents

le modèle des réseaux d'agent est plus général que les automates cellulaires. Les agents sont des programmes indépendants - identiques ou non - caractérisés par

• un ensemble d'attributs qui déterminent leur état,
• un ensemble de fonctions définissant les lois d'interaction entre les agents.

Il faut aussi prendre en compte les règles suivantes :

1. Aucun agent ne contrôle directement les autres agents
   
2. Aucune règle globale ne dicte le comportement du système
3. Les structures et dynamiques globales émergent desinteractions entre agents

Sous l'action de fluctuations qui permettent au réseau de quitter les états d'équilibre, les variations aléatoires des configurations engendrent des sous-réseaux transitoires qui relèvent d'un niveau supérieur. On assiste progressivement à une stabilisation de certaines de ces structures selon une "selection naturelle" en fonction de la satisfaction des contraintes liées à l'environnement (on parle de coévolution structurale). Ce nouvel échelon de complexité est lui-même soumis à au principe de variation-stabilisation pour former une hiérarchie de sous-niveaux en co-évolution.

"C'est chaque fois le même phénomène, il y a création d'un champ de possibles extrêmement large, puis le choix d'une trajectoire de stabilisation qui mène à l'ordre (attracteurs de type points fixes ou périodiques) ou au chaos (attracteurs chaotiques). Pourtant, dans certaines conditions, des structures réussissent à échapper à ces puissant attracteurs en se maintenant à leur frontière. Grâce à leur capacité de mémorisation et de traitement de l'information, elles s'adaptent et évoluent au niveau de cette transition de phase. Elles résistent aisni mieux que d'autres aux fluctuations du milieu et préservent leur "identité" dans l'espace et le temps" (Jean-Claude Heudin)

Automates et matière

On peut assimiler les automates cellulaires à une sorte de matière virtuelle dont on fixe les lois de la physique : des interactions entre des unités simples mais en très grand nombre font émerger des comportements complexes. On pourrait assimiler les différentes classes de dynamiques (ordonnées, desosronnées et complexes) avec différentes phases de la matière.

A partir de : Jean-Claude Heudin, "le jeu de la vie", in Sciences et Avenir Hors Série n°143 sur "l'énigme de l'émergence" juillet/août 2005.

Deux sites pour tester le jeu de la vie : http://www.univ-lemans.fr/enseignements/physique/02/divers/conway.html et http://www.vieartificielle.com/article/?id=91

Complexité / Demains - possibles / Demains - choisir.

Répondre à cet article

Par J-M Cornu | Avant | 02/09/2005 07:03 | Après | Complexité | 2 commentaires | Lu 11626 fois |