La fourmi de Langton

La fourmi de Langton est un petit programme informatique qui décrit une fourmi se déplaçant sur les cases d’une grille. Les règles qui régissent le mouvement de la fourmi sont d’une grande simplicité, et pourtant son comportement est complexe et tout sauf anodin. Et personne ne comprend vraiment pourquoi…

Les règles du jeu

Pour jouer à la fourmi de Langton (du nom de son créateur Chris Langton) il vous faut une feuille quadrillée, un crayon et une gomme. Au départ les cases de la grille peuvent être blanches ou noires, mais supposons pour commencer qu’elles sont toutes blanches. Mettez une petite flèche dans une des cases : ce sera votre fourmi, et l’orientation de la flèche indiquera sa direction.

A chaque tour, la fourmi se déplace selon les règles suivantes :

  1. Si la fourmi est sur une case blanche, elle effectue une rotation vers la gauche; si elle est sur une case noire, elle effectue une rotation vers la droite ;
  2. La fourmi inverse la couleur de la case sur laquelle elle se trouve (blanc devient noir et réciproquement);
  3. La fourmi avance d’une case dans la direction de son orientation.

    Et on recommence. Facile, non ?

    Voici ci-dessous un dessin du premier déplacement de notre fourmi : on part d’une configuration donnée (T=0) et on applique les 3 règles du mouvement : rotation, inversion de couleur et déplacement, et on termine dans la nouvelle configuration (T=1).

    Si vous êtes courageux, prenez votre crayon et votre gomme, et faites avancer la fourmi 5 fois. Le résultat doit être semblable à celui ci-dessous.

    Rassurez-vous pour la suite, en pratique on ne simule pas l’évolution de la fourmi avec un papier et un crayon, mais avec un (petit) programme informatique. Alors simulons  notre fourmi et voyons ce qu’elle dessine avec les cases noires.

    Les phases de la vie de la fourmi

    A vue de nez, rien de bien enthousiasmant dans cette fourmi. Elle obéit à des règles très simples et on se dit que son évolution ne va pas être bien passionnante. Et pourtant, quand on la simule pendant quelques milliers de tours, il se passe des choses vraiment étonnantes.

    En effet, la fourmi va passer par 3 phases vraiment très différentes, la phase « symétrique », la phase « chaotique » et la phase « autoroute ».

    Au début de son évolution, la fourmi se balade dans une zone assez limitée de la grille, en dessinant des configurations régulières et symétriques. En voici quelques exemples (la fourmi est en rouge) :

    Quand on voit ces figures, on peut penser que la fourmi de Langton va passer le restant de son existence à dessiner des jolies choses bien symétriques. Mais à partir de 500 tours, tout change. Elle se met à avoir un comportement chaotique, en élargissant son terrain de jeu et en créant des configurations très irrégulières.

    Cette phase chaotique dure jusqu’à environ 10000 tours, et là le miracle se produit : la fourmi entame la construction d’une autoroute très régulière qui la conduit à l’infini.

    Voyez par vous-même cette vidéo que j’ai réalisée et qui montre les 12 000 premiers tours. Observez bien la phase symétrique (jusqu’à 500), la phase chaotique (de 500 à 10000) et vous comprendrez vite à la fin de la vidéo ce que l’on appelle l’autoroute ! (attention la vidéo s’accélère au fur et à mesure)

    Le mystère de l’autoroute

    L’autoroute est en fait un motif périodique de 104 pas qui se répète, et conduit au tracé que vous observez sur le film précédent. Personne ne comprend pourquoi elle apparaît et comment elle peut émerger du désordre qui caractérise la phase chaotique.

    Ce qu’il y a de plus perturbant, c’est que même si on part d’une grille dont les cases sont coloriées aléatoirement en blanc ou en noir, l’autoroute finit toujours par apparaître un jour ou l’autre.

    C’est encore un problème ouvert de démontrer que quelle que soit la configuration initiale, une autoroute apparaît (à moins de chercher un contre-exemple, mais aucun n’a été trouvé à ce jour).

    Toutefois un pas intéressant a été franchi : on peut démontrer que la trajectoire de la fourmi est toujours non-bornée. C’est à dire que la fourmi finit toujours son parcours à l’infini…mais on ne sait pas montrer que c’est toujours via une construction d’autoroute !

    Généraliser la fourmi

    Il existe de nombreuses manières de généraliser le jeu de la fourmi de Langton. On peut bien sûr démarrer avec une grille dont certaines cases sont déjà noires. On peut modifier la topologie de la feuille, et jouer sur un tore au lieu d’un plan infini. On peut aussi changer la nature de la grille, triangulaire ou hexagonale par exemple. On peut également lancer plusieurs fourmis en même temps.

    Une autre généralisation fascinante consiste à ajouter d’autres couleurs que le noir et le blanc. Si par exemple on ajoute le rouge, on doit définir la séquence des couleurs, par exemple blanc->noir->rouge->blanc, et la rotation associée à chaque couleur, par exemple blanc=gauche, noir=droite, rouge=droite. Mais on aurait aussi bien pu choisir rouge=gauche. Et ce choix peut être critique pour le comportement global de la fourmi !

    Si on joue avec N couleurs, on a donc tout un tas de choix possibles (du genre 2^N) et tous ces choix peuvent conduire à des résultats très très différents. Un joli florilège dans la vidéo ci-dessous, qui montre que des règles en apparence très proches peuvent donner des comportements globaux très éloignés.

    A quoi sert la fourmi ?

    La fourmi de Langton est un bel exemple de ce concept un peu flou que tout un tas de monde appelle l’émergence. Il s’agit en gros du fait qu’un système au comportement élémentaire simple peut donner lieu à un comportement global complexe. On retrouve cette idée en informatique, en physique, en biologie ou en sociologie.

    La fourmi est donc une sorte de « forme de vie artificielle », à l’instar du jeu de la vie de Conway ou des automates cellulaires unidimensionnels de Wolfram, et dont on peut étudier le comportement pour essayer de comprendre comment des formes complexe peuvent émerger d’un système aux règles élémentaires si simples.

    La fourmi de Langton n’a pas encore livré tous ses mystères !

    17 réflexions sur “La fourmi de Langton

      • Je trouve ca génial ! J’ai tout de même une question, on voit la création d’autoroutes dans le cadre d’un espace infini. Si on considère un espace fini dont les bords se rejoignent ainsi qu’un nombre de tours suffisamment important. Peut-on voir émerger une organisation supérieur, un motif se répliquant et se stabilisant comme dans le cas de l’autoroute ?

        • En fait même avec un espace fini dont les bords se rejoignent (c’est à dire un tore) l’autoroute finit par apparaître. Elle ne va pas à l’infini car elle se détruit quand elle revient sur la figure chaotique du centre, mais réapparaît toujours et ainsi de suite.

          Ce motif en autoroute se comporte comme une sorte d’attracteur du système.

    1. Pour ceux que ça intéresse (je pense aux geeks de mon espèce), le principe de la fourmi est abordé dans un ouvrage fort sympathique, « la science du Disque-Monde » (donc écrit en partie par Terry Pratchett, que j’invite tout le monde à découvrir).

    2. Au Passage,la preuve du fait que la fourmi est non bornée est très courte et assez facile.

      Remarque 1.
      On colorie l’espace avec un damier rouge/bleu. Il est facile de voir que si initialement, la fourmi est placée horizontalement sur une case bleue, alors lors de sa balade, elle sera toujours placée horizontalement sur les cases bleues et verticalement sur les cases rouges.

      Preuve.
      Supposons par l’absurde que la fourmie ne visite qu’un espace borné. Parmis les cases visitée un nombre infini de fois, il en existe une qui est la plus à gauche. Parmis celles qui sont les plus à gauche, il en existe une qui est la plus haute. Regardons cette case d’un peu plus près. Par symétrie, on peut suppose qu’elle est coloriée bleue. Elle ne va donc jamais rentrer dans cette case par le bas ou par le haut. Quitte à ne regarder qu’au bout d’un certain temps, elle ne rentre dans cette case que par la droite. Mais alors, une fois sur deux, quand elle rentre dans cette case, elle ressort dans la case immédiatement au dessus d’elle, ce qui contredit le choix initial de notre case. CQDF.

    3. Pingback: Les automates cellulaires élémentaires | Science étonnante

    4. Pingback: La fourmi de Langton et le concept d’émergence | Metaxu. Le blog de Philippe Quéau

    5. Fantastique. J’avais déjà réflechi au sujet de l’émergence avec le « jeu de la vie », mais l’exemple d’une configuration unique qui emerge après la phase chaotique est tout simplement bluffant.

    6. Merci pour la présentation et les vidéos. Cela dit, je suis un peu surpris que la compréhension du principe n’ait pas été trouvée rapidement ! En effet, il me semble que la réponse est contenue dans l’énoncé lui même, c’est à dire, le fait que l’ordre de marche de la fourmi est de tourner sur elle même, donc, de rester centré et non d’aller dans une direction aléatoire. Il n’y a pas de chaos issu de ce programme, même si cela y laisse penser. Ce qui me surprend le plus, c’est que tout le monde se laisse abuser par l’apparence, au lieu de s’en tenir à l’énoncé de la relation de causalité guidant la fourmi. Bon, il y a une astuce complémentaire, mais la simple observation suffit pour trouver la réponse, et une hypothèse à vérifier…
      Si vous êtes intéressé, faites moi signe, je développerai, des fois que je me plante !

    7. Je me pose une question et je sais pas si il y a des programmes pour le faire et à mon avis ça peut être intéressant, ce serrait de voir le résultat avec plusieurs fourmis sur l’échiquier

    8. Bonjour, j’ai quelques questions ! Serait-il possible de savoir où est-ce que tu t’es documenté pour ce billet ? Aussi, as tu un lien/référence où on trouve la démonstration du caractère non bornée de la trajectoire de la fourmi? Et enfin, t’es tu intéressé aux différents types de représentation (par exemple sur un graphe planaire) de la fourmi de Langton, et ses autres usages (Machine de Turing je crois)? Ah, et j’oubliais, j’ai essayé de lire quelques trucs sur l’émergence, mais la notion a l’air assez floue encore. As-tu des références claires à ce propos?

      Merci d’avance pour ta réponse (Ou les réponses d’autrui !)

    9. Bonjour,

      J’ai l’impression que la phase « symétrique », dans le cas où les directives sont elles-même symétriques (case blanche, rotation à gauche / case noire, rotation à droite), correspond à une situation probable dépendante de la distance au point de départ (et donc du nombre de cases, qui représentent chacune une possibilité de ne pas pouvoir revenir au point de départ, le retour à celui-ci constituant une condition nécessaire au respect de la symétrie). Autrement dit, plus on avance dans le nombre de tours, plus l’automate s’éloigne de son point de départ et plus la probabilité devient faible qu’il puisse y retourner, du fait des motifs créés en chemin, qui constituent un risque de divergence.

      Ensuite, lorsque la distance devient telle que la probabilité de revenir au point de départ est insuffisante et que la divergence se produit, le système semble se comporter comme un générateur aléatoire de variété.
      Et le fait de voir finalement apparaître « l’autoroute » m’a fait faire le lien avec la loi de Godwin. Transposée ici, cela donnerait quelque chose du type : s’il existe un motif tel qu’avec les directives données il puisse se reproduire à l’infini, alors la probabilité de le voir apparaître tendra vers 1 à mesure que le nombre de tours tendra vers l’infini.
      Or, pendant la phase « chaotique », comme je l’ai évoqué plus haut, le système semble se comporter comme un générateur aléatoire de variété. Donc, le motif devrait apparaître. Il ne resterait qu’à respecter deux conditions. Premièrement, un fois construit, que l’automate puisse l’amorcer, ce qui signifie qu’il doit l’aborder par la bonne case, avec la bonne orientation (là encore, ce n’est qu’une question de nombre d’essais et donc de temps). Deuxièmement, que le motif soit situé aux abords d’un champ vierge de toute interférence.

      Ce point relatif aux interférences m’amène justement à penser que si nous nous amusions à encercler la zone utilisée pendant la phase « chaotique » avec des cases noires, l’intersection de « l’autoroute » et des points de ce cercle provoquerait la fin de « l’autoroute » et un retour à la phase « chaotique ». Mais « l’autoroute » finirait inéluctablement par réapparaître dès lors que les conditions citées plus haut seraient réunies.

    10. Bonjour,

      Une piste de réflexion: Si on supprime l’aspect chaîne de Makrov du jeu de la fourmi en introduisant une vraie dimension aléatoire à l’état du plateau, on constate que l’autoroute n’apparait plus !

      On peut faire cela en rajoutant une ligne au code pour donner l’aspect chat de shroedinger à la couleur de la case (i.e. donner une probabilité de 50/50 non connue tant que la fourmi n’avance pas sur la prochaine case que la case soit blanche ou noire).
      (Ceci ne change pas les règles, les cases visitées ne sont plus soumises à cette probabilité si la fourmie doit repasser dessus.)

      On montre alors que l’état de départ du plateau conditionne l’apparition de l’autoroute.
      Ou encore, que pour toute situtation qui converge vers un schéma donné en tangeante, il existe un état initiale du plateau ou le schéma ne converge jamais.

      Bien à vous,
      -DAB

      Cf fichier :
      https://www.dropbox.com/s/gsb8v8yieoiw13g/Copie%20de%20Fourmie%20de%20Langton_GBI2.xlsm?dl=0

    11. « Ce qu’il y a de plus perturbant, c’est que même si on part d’une grille dont les cases sont coloriées aléatoirement en blanc ou en noir, l’autoroute finit toujours par apparaître un jour ou l’autre. »

      Non, sur une grille en damier ce n’est pas la même l’autoroute qui apparaît mais un « ptit chemin » sur deux cycles.

    12. Pingback: La fourmi de Langton — Science étonnante #21 - Blog NSellier TV

    Laisser un commentaire

    Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

    Logo WordPress.com

    Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

    Image Twitter

    Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

    Photo Facebook

    Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

    Photo Google+

    Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

    Connexion à %s