Découverte d’un vaisseau spatial 1D de 3,7 milliards de cellules dans le Game of Life de Conway

• Le forum du Conway’s Game of Life annonce la réalisation d’un motif de 1D spaceship (vaisseau spatial 1D) d’environ 3,7 milliards de cellules (3.7B).
• Ce motif se déplace avec une période de 133,076,755,768 générations et la boîte englobante initiale mesure 3707300605×1 cellules.
• Les développeurs ont combiné quatre systèmes de bras de construction ECCA1·ECCA2 (compression arm), binary arm, fuse arm, etc., pour implémenter la réplication, le nettoyage et le redémarrage automatiques.
• La simulation a été validée dans les environnements Golly et lifelib, et apg (calcyman) a ajouté au dépôt le code de vérification du cycle complet.
• Cette découverte est considérée comme un exemple de progrès de la technique de slow salvo et des outils d’automatisation de motifs géants.

---

Rapport d’achèvement du vaisseau spatial 1D

• Hippo.69 a annoncé qu’un vaisseau spatial de vitesse 2c/133076755768 avait été achevé, ce qui correspond à un déplacement de deux cellules par période.
  • La plage de coordonnées y est d’environ ±5,537,521,000 et le x maximal est d’environ 11,075,626,500.
• apg (calcyman) a confirmé, grâce à une simulation complète, que le motif fonctionne correctement et a corrigé une erreur de saisie sur la valeur de période.
• La version finale est partagée avec plusieurs fichiers .mc (example.mc, example_42168M.mc, example_46000M.mc), permettant une relecture pas à pas dans Golly.

Simulation et débogage

• Lors du débogage initial, un Cordership a créé un glider inversé, provoquant des dégâts de type SoD (Stop of Destruction).
  • Le réglage “switch far seed” a été modifié pour prendre en compte ce glider.
• La simulation utilise l’optimisation Hashlife de lifelib pour progresser rapidement par sauts de dizaines de millions de générations.
• Un script Lua basé sur BigNum automatise les sauts massifs de générations dans Golly et enregistre des points de contrôle à des événements clés (par ex. le lancement d’ecca2, l’arrivée du cordership, etc.).

Structure et principe de fonctionnement

• Le système global est composé de quatre bras de construction.
  • Fuse arm : génération et initialisation d’un signal unidimensionnel basé sur un blinker.
  • Binary arm : interprétation d’un signal binaire en combinant deux gliders afin de générer des structures.
  • ECCA1 / ECCA2 : bras de construction ultra-denses qui décodent des instructions compressées pour nettoyer le motif et préparer la génération suivante.
• En dernière étape, ECCA2 lance une flotte de corderships (cordership fleet) pour éliminer les motifs résiduels, puis ramène finalement l’état à la dimension (y = 0).
• L’ensemble du processus est conçu comme une structure parfaitement symétrique, avec des côtés qui fonctionnent de manière identique autour de l’axe central (spine).

Développement et collaboration

• Le projet a été achevé grâce à la collaboration entre calcyman (apg) et Hippo.69.
  • calcyman a conçu la moitié initiale (structure des bras et base de code).
  • Hippo.69 a ensuite réalisé, pendant plusieurs années, les tâches restantes de nettoyage, de synchronisation et de débogage.
• Les utilisateurs du forum ont proposé les noms “Arrow 1” ou “Unidimensional Spaceship 1”.
• Des membres de la communauté comme hth3 et I6_I6 ont tenté des simulations dans Golly et laissé des messages de félicitations.

Signification technique

• Ce vaisseau spatial est le premier large motif auto-réplicatif se déplaçant en unidimensionnel, démontrant un nouveau niveau de complexité computationnelle dans le Game of Life.
• Les techniques modernes, dont l’automatisation du slow salvo, le décodeur de compression ECCA et le contrôle du Cordership, ont toutes été mobilisées.
• Les chercheurs prévoient des optimisations supplémentaires pour réduire la taille et augmenter la vitesse à l’avenir, et examinent aussi la publication d’un article de recherche.

[GN⁺]

Commentaires sur Hacker News

• Au début, j’ai commencé à lire en me disant « oh, intéressant », mais je ne pensais pas qu’il y aurait autant de jargon propre à la communauté Game of Life
  Des termes comme ECCA1 et gpse90 arrivaient de partout, au point que j’ai fini par me dire qu’il faudrait sans doute passer quelques heures sur le wiki

  • Le livre gratuit Conway’s Game of Life: Mathematics and Construction est une bonne introduction
  • Je vais voir ce forum environ une fois par an, et ça me sidère toujours de voir combien de temps et d’intelligence certaines personnes y consacrent
  • En réalité, ce n’est pas tant du « vocabulaire du Game of Life » que de la terminologie mathématique du domaine des automates cellulaires

• C’est fascinant de voir qu’on part d’une simple ligne, qu’elle explose en une énorme structure complexe en 2D, puis qu’après d’innombrables générations elle redevient une ligne de 3,7 milliards de cellules
  J’aimerais vraiment que quelqu’un analyse les unités d’abstraction qu’il y a là-dedans

  • D’après ce message du forum, c’est en fait une structure clairsemée avec moins de 1/100 de cellules vivantes par rapport à la longueur de la ligne (Unidimensional spaceship 1)
  • Avec cette explication, je comprends mieux. Au départ, je croyais qu’il s’agissait d’un glider d’automate cellulaire unidimensionnel

• Lire les longues explications du forum GoL, c’est un peu comme faire vivre à mon épouse ce que je lui fais subir quand elle entend mes réunions Zoom de boulot. Cette avalanche de jargon est vraiment magnifique

  • Ça m’a fait penser à cette vidéo
  • Je trouve cette analogie bien plus drôle que le nombre de karma qu’a reçu ce commentaire
  • La seule différence, c’est que même quand je ne comprends pas, je m’amuse quand même. Mon épouse, elle, ne s’intéresse qu’à mon humeur — du genre : « donc cette architecture RISC n’est pas conforme à l’ADA-1056 ? Waouh, formidable chéri ! »

• « Mon dieu, mais c’est un Quine ! »
  Quand une séquence linéaire de bits est interprétée comme un plateau de Game of Life, elle se réplique en se décalant de deux pixels vers la droite
  C’est plus difficile qu’une simple réplication, mais l’idée de l’interpréter comme un auto-réplicateur sur bande qui réimprime son propre code deux pixels plus loin est magnifique

  • En réalité, ce genre de structure s’appelle un « spaceship ». C’est l’un des deux spaceships découverts le même jour. Mais c’est la première fois qu’on a un spaceship 1D
  • En fait, le déplacement est plus facile que l’auto-réplication. On n’a toujours pas découvert de véritable replicator, même s’il existe des millions de spaceships

• Il y avait cette remarque : « comme le début est lent, sautez directement à la génération 42168M », et ça m’a fait imaginer des êtres manipulant l’univers comme un jouet en disant : « ça devient intéressant vers 13,8 milliards d’années »

  • D’un point de vue philosophique, la réalité pourrait aussi être une simulation de GoL complexe. Si nous vivons dans une simulation, est-ce qu’on pourrait seulement le savoir ?

• Il y a deux questions ouvertes intéressantes à propos du Game of Life

  1. Quel est le comportement à partir d’un état initial aléatoire ? Comme c’est Turing-complet, une forme de vie intelligente pourrait-elle émerger ? Est-ce le chaos qui domine, ou l’intelligence qui apparaît ? (discussion liée)
  2. Existe-t-il une structure superstable qui se maintienne malgré n’importe quelle perturbation extérieure ? (question liée)
  • La première question est abordée dans The Recursive Universe (1984) de William Poundstone. Ce livre définit la vie à partir de l’idée de machine auto-réplicatrice, et plus tard Gemini, créé en 2010 par Andrew J. Wade, a été le premier cas réussi répondant à cette définition.
    La probabilité que la vie apparaisse à partir d’un état initial aléatoire est proche de zéro, mais la vie peut évoluer
  • C’est Turing-complet, mais les calculs réels restent difficiles, et les motifs tendent vers le chaos ou l’extinction. Pour transporter de l’information, il faut des structures complexes comme les spaceships. En comparaison, des variantes comme Lenia ou Neural CA sont plus stables
  • Les configurations aléatoires sont remplies d’un bruit homogène à 50 % de densité, donc les structures intéressantes y émergent rarement. Il faut partir d’un bruit sans échelle pour voir apparaître une structure globale
  • Être Turing-complet ne garantit pas l’intelligence, mais sur un plan infini, il se peut qu’une forme de vie intelligente finisse par apparaître et remplisse l’ensemble. S’il en apparaît plusieurs, elles pourraient aussi entrer en compétition d’extinction
  • Si on ajoute continuellement des points au hasard sur un plan infini, il finira par émerger une forme de vie intelligente transformant une énergie à basse entropie en haute entropie

• J’ai autrefois réalisé une expérience de glider à mouvement continu — glider.gif

  • C’est vraiment magnifique. On dirait une œuvre d’art qui exprime visuellement les règles de base

• Je me demandais s’il existait une visualisation de ce glider. J’aurais aimé le voir avec l’axe du temps comme une dimension

  • Si j’ai bien compris, cela commence simplement comme une ligne de 1x3,7 milliards de cellules dans un GoL 2D
  • Pour l’exécuter, le logiciel Golly est le meilleur choix. Grâce à l’algorithme HashLife, la simulation est rapide
  • Après la première étape, ce n’est déjà plus un système 1D, donc une telle visualisation est impossible

• C’est une structure qui ne tient dans une boîte de hauteur 1 cellule qu’à certaines étapes précises

  • Je ne suis pas un GoLticien, mais avec les règles standard, ce genre de structure me semble impossible en dehors de la stabilité ou de l’extinction.
    Cela dit, la passion et le soin qu’on sent dans ce fil sont vraiment impressionnants

• En 1995, j’ai reçu un e-mail d’un certain John Conway. À l’époque, c’était simplement à cause d’un message que j’avais posté dans un newsgroup de maths, et je n’ai compris que plus tard que c’était bien Conway
  En voyant aujourd’hui cet incroyable univers du GoL, je me demande à quoi l’humanité devrait consacrer un tel potentiel créatif