Voilà ce qu'un jour on m'a obligé à faire : UN AUTOMATE CELLULAIRE...
ça fait peur hein...
un petit topo pour ceux que ça interessent
John Horton Conway créateur du « Jeu de la Vie »
John Horton Conway est né le 26 décembre 1937 à Liverpool en Angleterre,il est un mathématicien anglais extrêmement prolifique qui s'est penché sur les théories des groupes finis, des nœuds, des nombres, des jeux et du codage.
Il a étudié à l'Université de Cambridge en Angleterre. Il est depuis 1981 un membre de la Royal Society.
John Conway est actuellement (2004) professeur de mathématiques à l'université de Princeton, aux états-Unis.
Il est principalement connu pour sa « théorie combinatoire des jeux » et pour avoir inventé « le jeu de la vie », un automate cellulaire.
Il est également l'un des inventeurs de « Sprouts » ainsi que du « Phutball » (le football du philosophe), et il a écrit des analyses détaillées d'autres jeux, comme « le cube Soma ».
Il est également le concepteur du « problème de l'ange », toujours non résolu en 2004.
Il a conçu un nouveau système de nombres, « les nombres surréels », et une nomenclature pour les nombres entiers excessivement grands, « la notation des flèches chaînées de Conway ». Il a travaillé sur la classification des groupes finis et a découvert les « groupes de Conway ».
La vie est complexité. Le tissage d'une toile par l'araignée, ou la construction d'une fourmilière par ses habitantes, suggèrent que ces insectes sont dotés d'intelligence. Il n'en est rien. Selon la démonstration des biologistes, c'est en suivant aveuglément des règles élémentaires, progressivement affinées par la sélection naturelle, que tout animal inférieur manifeste des comportements atteignant parfois l'extrême complexité.
Dans son univers et dans son langage, l'informaticien qualifie « d'émergence » l'apparition sur son écran de motifs complexes générés par des règles simples.
Dans l'expérience Life, chaque molécule de la paroi BioWall est morte (éteinte) ou vive (allumée). De seconde en seconde, chaque molécule gagnera un nouvel état (de mort ou de vie), ne dépendant que du nombre de molécules vivantes existant dans son voisinage immédiat.
Une colonie de molécules vivantes forme alors un motif qui se déforme au cours du temps, s'étend et colonise agressivement l'espace ou, au contraire, s'éteint graduellement. Le visiteur peut stimuler la persistance de cette population artificielle en exerçant une pression sur une molécule morte, ce qui lui prête vie, de manière à modifier localement le comportement collectif de l'ensemble.
Il s’agit donc d’un automate cellulaire présente un aspect biologique, comme l’indique son nom: les cellules naissent vivent ou meurent selon la densité locale de la population.
Pour jouer au jeu de la vie, on dispose d'un réseau de cellules à deux états et on utilise le voisinage de Moore.
La complication vient du fait que la cellule centrale intervient dans son évolution.
Autrement dit, à chaque étape de l'évolution du système, chaque cellule évolue en fonction des huit cellules adjacentes et de son propre état.
Une des règles les plus simples est la règle de parité, qui assigne à la cellule la valeur 1 si le nombre de voisines dont la valeur est 1 est impair et qui, sinon, lui assigne la valeur 0. C'est sur cette règle que s'appuie un système d'autoreproduction simple, qui a été imaginé en 1960 par Edward Fredkin du Massachusetts Institute of Technology.
Le voisinage utilisé est le voisinage de Von Neumann. La traduction algorithmique de cette règle est sans difficulté: La case prend pour valeur la somme des valeurs de ses voisines modulo 2.
Les automates les plus simples étant ceux à une dimension tel que le modèle de Fredkin.
COMPRENDRE LE JEU DE LA VIE
En, 1970, John Conway, mathématicien de l'Université de Cambridge, spécialiste notamment de la "théorie des jeux", inventa "Le jeu de la vie", un automate cellulaire. Retour sur une modélisation mathématique d'une vie artificielle simpliste et pourtant source d'innombrables développements...
Aujourd'hui fort célèbre, ce jeu de simulation utilise un damier "infini" sur lequel on place plusieurs pions censés représenter les cellules d'un organisme vivant. Des cellules naissent ou meurent à chaque tour de jeu en se conformant à trois règles simples.
On considère que, sur le damier, une case appelée « cellule » possède huit cases « voisines ».
Figure 1
n 1. Toute cellule ayant exactement deux ou trois autres pions voisins reste en place et survit à la génération suivante.
n 2. Toute cellule ayant 0, 1, 4, 5, 6, 7 ou 8 voisins est éliminée
n si elle n'a aucun voisin ou seulement un, elle meurt d'isolement.
n Si elle a quatre voisins ou plus, elle meurt d'étouffement
n 3. Une case vide entourée de trois pions voisins exactement donne naissance à une cellule à la génération suivante.
La naissance d’une cellule sur une case n’influe pas sur la survie ou la mort des cellules de la génération précédente. Autrement dit, les seules cellules que l’on doit prendre en comte pour l’établissement de la génération future sont celles de la génération « actuelle ».
En appliquant ces règles, des figures initiales évoluent, grossissent parfois et meurent aussi de temps en temps...
Voici deux motifs (voir figure 2) : le premier a une évolution cyclique d'ordre 2 (toutes les deux générations, on retrouve le motif initial), le second est stable à partir de la génération 4 (on appelle son dernier motif la "ruche")
Figure 2
Figure 3
Ce jeu fut publié pour la première fois par Martin Gardner (vulgarisateur talentueux des mathématiques, auteur de dizaines de livres traitant des mathématiques, de philosophie ou encore d'énigmes ; c'est aussi un grand pourfendeur du "paranormal") en 1970 dans la revue Scientific American, "Le Jeu de la vie" eut tellement de succès que des laboratoires furent paralysés pendant des mois : les informaticiens détournaient le matériel informatique pour tester le jeu... On raconte même que les écrans graphiques furent créés pour sa simulation. L'intérêt porté à ce jeu peut sembler dénué de fondement.
Pourtant, cet univers, simpliste à l'extrême, est riche d'enseignements en ce qui concerne les mathématiques.
Le principal avantage du "Jeu de la vie" est qu'il permet, à partir des trois règles qui le définissent, de faire émerger des phénomènes surprenants.
Ils existent sous 3 formes :
n Petits
n Moyens
n Grands
Ces structures plutôt simples se déplacent horizontalement.
Le Téramino est une structure composée de 4 cellules uniquement, disposées en « T ».
Cette structure se développe en 10 générations pour devenir finalement un oscillateur à 2 phases que l’on appelle « feu clignotant »
Il existe beaucoup d’autres configurations de départ. Celles présentées ci-dessus sont parmi les plus simples et les plus courantes.
Dans quelques les organismes finissent pas mourir, lorsqu’ils ne meurent pas ils conduisent aux organismes qui suivent :
Identiques de génération en génération.
Organismes qui se retrouvent identiques à eux-mêmes et à la même place au bout d’un certain nombre de générations appelé « la période de l’oscillateur ».
Déplacements de l’organisme qui suivent les lignes verticales, horizontales et les diagonales
Il a été démontré que l'évolution à long terme d'une configuration initiale donnée du Jeu de la vie est indécidable !
Cela signifie qu'il n'existe pas d'algorithme permettant de connaître le comportement du jeu (cyclique, infini, stable...) à partir d'un motif de départ.
Le problème est imprédictible, alors que le jeu est commandé par des règles déterministes !
Une modification infime dans la génération initiale peut produire d’énormes modifications dans l’évolution de l’automate.
8 problemes algorithmiques/systemes rencontres
n découverte d'une librairie graphique (SDL) et adaptation nécessaire aux spécificités de la librairie exemple:
La notion de surface: SDL repose sur le concept de " surface " (le type structuré SDL_Surface) qui sert à représenter un ensemble planaire de pixels. Chaque surface a ses caractéristiques propres (taille, bits par pixel, etc.)
Attention : cette librairie peut ne pas être installée sur votre ordinateur auquel cas il est conseillé de télécharger la version 1.2.8 (version la plus stable) à l’adresse suivante :
www.libsdl.org
n la fonction comparaison des différentes cellules ne fonctionnait pas dans un premier temps.
Le langage C++ introduit le concept de fonction inline en ajoutant le mot clé inline.
Ce mot clé permet de définir des fonctions qui seront directement évaluées à la compilation, et dont l'appel dans le programme sera remplacé par la valeur évaluée.
Ce concept de pseudo-fonction était déjà possible en langage C, grâce à la directive de préprocesseur #define.
Toutefois cette directive ne permettait aucun contrôle de type, ce que le mot clé inline réalise...
n l'interface (le gui) n'est pas terminé, la gestion des évènements souris n'étant pas implémentée.
n la portabilité du code nécessite de connaître les contraintes inhérentes à chaque OS, exemple :
sous linux, le programme compile avec la ligne suivante
n gcc -o prog prog.c -I/usr/local/include -lSDL -ldl -lpthread
n pour SDL installé dans /usr/local
n pour gérer les processes légers, ce que j'ignorais.
En effet , SDL est une bibliotheque multi-threads ce qui signifie que plusieurs partie du code peuvent s'exécuter simultanément sur des ordinateurs multiprocesseurs voir sur les Pentium 4 HT.
SDL (Simple Directmedia Layer) est une API multimédia multi-plateforme gratuite.
Ainsi, plutôt que de connaître les appels systèmes nécessaires afin de prendre le contrôle du matériel, que ce soit en entrée (évènements claviers/souris/joystick) ou en sortie (contrôleur vidéo/son), SDL intercepte les différents appels et les interprète.
Soit DOS par exemple, on appelait l'affichage au moyen des fonctions assembleurs :
n mov int 13h
n int 10h
n pour selectionner le mode vga/mcga (320*200*8)
Or il est aujourd'hui impossible faute de standardisation de faire de même pour les résolutions courantes comme 1024*768*32 quel que soit le materiel utilisé (la norme vesa n'étant plus mise-à-jour).
SDL est donc une surcouche qui se charge d'interpréter pour le système-cible les appels qui lui sont passés.
De surcroît, SDL permet assez facilement de charger les extensions (SDL_GL_GetProcAddress ()), ce qui permet de faire de la programmation 3d via opengl plus facilement qu'en utilisant GLUT tout en offrant un bien plus grand contrôle des évènements et en étant plus simple à mettre en œuvre qu'une fenêtre Windows ou X11.
L'un des principaux attraits de SDL est son aspect multi-plateformes : disponible sous windows et linux, SDL existe également sous d'autres OS comme BEOS, MACOS X, Solaris, FreeBSD, SGI/IRIX entres autres.
Naturellement le portage Linux supporte X11, mais aussi SVGAlib, DGA etc..
Ainsi, un programmeur n'a pas à apprendre les spécificités de programmation de chaque OS : un programme réalisé au moyen de cette librairie peut être tout simplement recompilé tel quel la plupart du temps et génèrer un exécutable adapté.
9.2.1 Exemple de programme minimal:
#include <stdlib.h>
#include "SDL.h"
main(int argc, char *argv[])
{
if ( SDL_Init(SDL_INIT_AUDIO|SDL_INIT_VIDEO) < 0 ) {
fprintf(stderr, "Impossible d'initialiser SDL: %s\n", SDL_GetError());
exit(1);
}
atexit(SDL_Quit);
exit(0);
}
n Ce petit programme initialise la video et le système-son de SDL, et affiche un message d'erreur si cela s'avère impossible.
n Ce code-source est le même pour tous les OS précédemment cités.
n La gestion audio/video en est grandement simplifiée, d'où le 'Simple' par lequel commence le nom de la librairie.
Il reste encore bien des perspectives concernant le Jeu de la vie.
Parmi celles-ci :
n Construire un organisme qui se reproduit lui-même.
n
Commentaires