Jeu de la vie

"Conway jeu" peut se référer à des jeux tel que défini par numéros surréalistes, qui Conway a également développé.

Planeur Gun Gosper création " planeurs ".

The Game of Life est un automate cellulaire imaginé par la Colombie- mathématicien John Horton Conway en 1970. Ce est l'exemple le plus connu d'un automate cellulaire.

Le «jeu» est en fait un zéro-joueurs, ce qui signifie que son évolution est déterminé par son état initial, ne nécessitant aucune entrée de joueurs humains. On interagit avec le jeu de la vie en créant une configuration initiale et en observant comment il évolue. Une variante existe lorsque deux joueurs se affrontent.

Règles

L'univers du jeu de la vie est un infini grille orthogonale bidimensionnelle de cellules carrées, dont chacun est dans l'un des deux états possibles, vivants ou morts. Chaque cellule interagit avec ses huit voisins, qui sont les cellules qui sont directement horizontalement, verticalement ou en diagonale adjacente. A chaque étape de temps, les transitions suivantes se produisent:

1. Toute cellule vivante avec moins de deux voisins vivants meurt, comme si par la solitude.
2. Toute cellule vivante avec plus de trois voisines vivantes meurt, comme si par la surpopulation.
3. Toute cellule vivante avec deux ou trois voisines vivantes vit, inchangée, à la prochaine génération.
4. Toute cellule morte avec exactement trois voisins vivants vient à la vie.

Le motif initial constitue la «graine» du système. La première génération est créée en appliquant les règles ci-dessus simultanément à chaque cellule dans la graine - naissances et décès se produisent simultanément, et le moment discrète à laquelle cela se produit est parfois appelé une tique. (En d'autres termes, chaque génération est une fonction pure de la précédente.) Les règles continuent à être appliqué plusieurs fois pour créer de nouvelles générations.

Origines

Conway se est intéressé à un problème présenté dans les années 1940 par le mathématicien de renom John von Neumann , qui a essayé de trouver une machine hypothétique qui pourrait construire des copies de lui-même et a réussi quand il a trouvé un modèle mathématique pour une telle machine avec des règles très compliquées sur une grille rectangulaire . Conway a essayé de simplifier les idées de von Neumann et a finalement réussi. En couplant son succès précédent avec Le problème de Leech en théorie de groupe avec son intérêt pour les idées de von Neumann sur les appareils de l'auto-réplication, Conway a conçu le jeu de la vie.

Il a fait sa première apparition publique dans le numéro d'Octobre 1970 Scientific American, dans Martin Gardner " Jeux Mathématiques "colonne. D'un point de vue théorique, il est intéressant, car il a le pouvoir d'un machine de Turing universelle: ce est tout ce qui peut être calculée par algorithme peut être calculé à l'intérieur Jeu de la vie. Gardner a écrit:

Le jeu fait Conway instantanément célèbre, mais il a également ouvert un nouveau champ de la recherche mathématique, le domaine de la automates cellulaires ... Parce que des analogies de la vie avec la montée, la chute et des altérations d'une société d'organismes vivants, il appartient à une classe de plus en plus de ce qu'on appelle «jeux de simulation» (jeux qui ressemblent à des processus de la vie réelle)

Depuis sa publication, Jeu de la vie a suscité beaucoup d'intérêt en raison des moyens surprenants dans laquelle les modèles peuvent évoluer. La vie est un exemple de émergence et auto-organisation. Il est intéressant pour les physiciens , biologistes , économistes , mathématiciens , philosophes , génératives scientifiques et autres à observer la façon dont les modèles complexes peuvent émerger de la mise en œuvre des règles très simples. Le jeu peut aussi servir comme une didactique analogie, utilisé pour transmettre la notion quelque peu contre-intuitif que «la conception» et «organisation» peuvent émerger spontanément en l'absence d'un designer. Par exemple, philosophe et scientifique cognitive Daniel C. Dennett a utilisé l'analogue de la vie "l'univers" de Conway largement pour illustrer l'évolution possible des constructions philosophiques complexes, tels que conscience et le libre arbitre, de l'ensemble relativement simple des lois physiques régissant déterministes notre propre univers.

La popularité de la vie de Conway a été aidé par le fait qu'il a vu le jour juste à temps pour une nouvelle génération de peu coûteuse mini-ordinateurs qui ont été libérés dans le marché, ce qui signifie que le jeu pourrait être exécuté pendant des heures sur ces machines qui étaient par ailleurs utilisé la nuit. À cet égard, il préfigure la popularité ultérieure de générées par ordinateur fractales . Pour beaucoup, la vie était tout simplement un défi de programmation, une façon amusante de perdre CPU cycles. Pour certains, cependant, la vie a des connotations plus philosophiques. Il se est développé un véritable culte dans les années 1970 et au-delà; développements actuels ont été jusqu'à créer des émulations théoriques de systèmes informatiques dans les limites d'un conseil de vie.

Conway a choisi ses règles attentivement, après beaucoup d'expérimentation, pour répondre à trois critères:

1. Il devrait y avoir aucun modèle initial pour lequel il ya une simple preuve que la population peut croître sans limite.
2. Il devrait y avoir des motifs initiaux qui, apparemment, ne poussent sans limite.
3. Il devrait y avoir des motifs simples initiales qui se développent et changent pour une période de temps considérable avant de venir à sa fin dans les façons possibles suivantes:

   • Estomper complètement (de la surpopulation ou de devenir trop rares); ou
   • Installation dans une configuration stable qui reste inchangé par la suite, ou d'entrer dans une phase d'oscillation dans laquelle ils répètent un cycle sans fin de deux ou plusieurs périodes.

Des exemples de motifs

L'évolution et le mouvement d'un planeur.

L'évolution et le mouvement d'un LWSS.

De nombreux types de modèles différents se produisent dans le jeu de la vie, y compris les patrons statiques (" natures mortes »), motifs répétitifs (" oscillateurs "- un sur-ensemble de natures mortes), et des motifs qui se traduisent à travers le conseil d'administration (" vaisseaux spatiaux "). Les exemples les plus courants de ces trois classes sont indiquées ci-dessous, avec des cellules vivantes apparaissent en noir, et les cellules mortes apparaissent en blanc.

Block (nature morte)
Bateau (nature morte)
Clignotant (deux phases oscillateur)
Toad (deux phases oscillateur)
Planeur (vaisseau spatial)
Vaisseau spatial (Lightweight LWSS)
Pulsar (triphasé oscillateur)

Le "pulsar" est la période 3 oscillateur le plus commun. La grande majorité des oscillateurs sont naturellement période de 2, comme le clignotant et le crapaud, mais les périodes 4, 8, 15, 30, et quelques autres ont été vus en de rares occasions .

Patterns appelés " Mathusalems "peut évoluer pendant de longues périodes avant de répéter." Diehard "est un modèle qui finit par disparaître après 130 générations, ou des étapes." Acorn "prend 5,206 générations à générer au moins 25 planeurs et stabiliser autant oscillateurs.

Diehard	Gland

Conway origine conjecturé qu'aucun motif peut croître indéfiniment - ce est à dire, que pour toute configuration initiale avec un nombre fini de cellules vivantes, la population ne peut pas dépasser une certaine limite supérieure finie. En apparence originale du jeu dans " Jeux mathématiques ", Conway a offert un prix de 50 $ à la première personne qui pourrait prouver ou de réfuter la conjecture avant la fin de 1970. Une façon de réfuter serait de découvrir des modèles qui maintiennent compteurs ajoutant au champ: un« pistolet », qui serait une configuration qui tire à plusieurs reprises de déplacer des objets tels que le «planeur», ou un «train de pompe», ce qui serait une configuration qui se déplace, mais laisse derrière lui une traînée de "fumée" persistante.

Le prix a été remporté en Novembre de la même année par une équipe de la Massachusetts Institute of Technology, dirigé par Bill Gosper; le «pistolet Gosper" ci-dessous produit son premier planeur sur la 15e génération, et un autre planeur chaque 30e génération à partir de là. Ce premier coup de canon de parapente est toujours le plus petit connu:

Modèles simples ont été plus tard constaté que la pièce également la croissance infinie. Les trois modèles suivants croître indéfiniment: les deux premiers créer un moteur »de bloc portant" switch chacun, tandis que le troisième crée deux. La première n'a que 10 cellules vivantes (qui a été prouvé pour être minime). La seconde tient dans un carré de 5 × 5. La troisième est une seule cellule haute:

Découvertes ultérieures inclus d'autres " armes ", qui sont fixes et jaillissent planeur ou d'autres vaisseaux spatiaux;" inhalateurs », qui se déplacent le long laissant derrière lui une traînée de débris, et" râteaux ", qui se déplacent et émettre des vaisseaux spatiaux. Gosper a également construit le premier modèle avec un asymptotiquement optimal taux de croissance quadratique, appelé " obtenteur ", ou" homard ", qui a travaillé en laissant derrière lui une traînée de pistolets.

Il est possible pour les planeurs d'interagir avec d'autres objets de manière intéressante. Par exemple, si deux planeurs sont tournés en un bloc dans la bonne façon, le bloc se rapprocher de la source des planeurs. Si trois planeurs sont tiré une balle dans la bonne façon, le bloc se déplace plus loin. Cette «mémoire de bloc coulissant" peut être utilisée pour simuler un compteur. Il est possible de construire des portes logiques tels que ET, OU et PAS utilisant planeurs. Il est possible de construire un modèle qui se comporte comme un machine à états finis connecté à deux compteurs. Cela a la même puissance de calcul comme un Machine de Turing universelle, de sorte que le jeu de la vie est aussi puissant que ne importe quel ordinateur avec une mémoire illimitée: il est Turing complet. En outre, un modèle peut contenir une collection d'armes à feu qui se combinent pour construire de nouveaux objets, y compris des copies du modèle original. Un "constructeur universel" peut être construit qui contient un ordinateur complet de Turing, et qui peut construire de nombreux types d'objets complexes, y compris plus de copies de lui-même.

Itération

D'un motif initial aléatoire de cellules vivantes sur la grille, les observateurs trouveront la population en constante évolution que les générations se égrènent. Les tendances qui se dégagent des règles simples peuvent être considérés comme une forme de beauté. Petits sous-masques isolés sans symétrie initiale ont tendance à devenir symétriques. Une fois que cela se produit la symétrie peut augmenter la richesse, mais il ne peut pas être perdu si un sous-motif voisine est assez proche de la troubler. Dans de très rares cas, la société finit par mourir sur, avec toutes les cellules vivantes en voie de disparition, mais cela peut ne pas se produire pour un grand nombre de générations. La plupart des modèles initiaux éventuellement «burn out», soit la production de chiffres ou des motifs qui oscillent toujours entre deux ou plusieurs états stables; plusieurs produisent aussi un ou plusieurs planeurs ou des vaisseaux spatiaux qui voyagent indéfiniment loin de l'emplacement initial.

Algorithmes

Conway a découvert que le F- pentomino échoué à se stabiliser dans un petit nombre de générations.

Les premiers résultats dans le jeu de la vie ont été obtenus sans l'utilisation des ordinateurs. Les simples natures mortes et les oscillateurs ont été découverts tout en suivant le sort de différents petites configurations de départ à l'aide de papier millimétré, tableaux noirs, des plateaux de jeux physiques (telles que Go ) et similaires. Au cours de ces premières recherches, Conway a découvert que le F- pentomino (qu'il appelle le «R-pentomino") n'a pas réussi à se stabiliser dans un petit nombre de générations.

Ces découvertes inspirées programmeurs informatiques dans le monde entier d'écrire des programmes pour suivre l'évolution des modes de vie. La plupart des premiers algorithmes étaient similaires. Ils représentaient les modes de vie comme des tableaux en deux dimensions dans la mémoire de l'ordinateur. Typiquement deux tableaux sont utilisés, l'un pour tenir la génération actuelle et celle dans laquelle pour calculer son successeur. Souvent 0 et 1 représentent les cellules mortes et vivantes, respectivement. Une double boucle considère chaque élément de la gamme actuelle à son tour, en comptant les voisins en direct de chaque cellule de décider si l'élément correspondant de la matrice successeur devrait être 0 ou 1. Le tableau successeur se affiche. Pour la prochaine itération les tableaux changer de rôle pour que la matrice de successeur dans la dernière itération devient la gamme actuelle dans la prochaine itération.

Une variété d'améliorations mineures à ce schéma de base sont possibles, et il ya plusieurs façons d'économiser de calcul inutile. Une cellule qui n'a pas changé à la dernière étape de temps, et dont aucun des voisins changé, est garanti de ne pas changer à l'étape de l'heure ainsi, donc un programme qui garde la trace des zones sont actives peut gagner du temps en ne mettant à jour le zones inactives.

En principe, le domaine de La vie est infinie, mais les ordinateurs ont de la mémoire finie, et généralement la taille des tableaux doit être déclarée à l'avance. Cela conduit à des problèmes lors de la surface active empiète sur la frontière de la matrice. Les programmeurs ont utilisé plusieurs stratégies pour résoudre ces problèmes. La stratégie la plus simple consiste simplement à supposer que chaque cellule en dehors de la gamme est mort. Ce est facile à programmer, mais conduit à des résultats inexacts lorsque la zone active traverse la frontière. Un truc plus sophistiquée consiste à examiner les bords gauche et droit du champ pour être cousues ensemble, et les bords supérieur et inférieur aussi, donnant un toroïdal tableau. Le résultat est que des zones actives qui se déplacent à travers une arête de champ réapparaissent au niveau du bord opposé. Imprécision peut encore aboutir si le motif devient trop importante, mais au moins il n'y a pas des effets de bord pathologiques. Techniques d'allocation de stockage dynamique peuvent également être utilisés, créant toujours plus grands tableaux de tenir modèles de croissance.

Alternativement, le programmeur peut abandonner la notion de représenter le domaine de la vie avec un tableau à 2 dimensions, et d'utiliser une structure de données différente, comme un vecteur de paires de coordonnées représentant des cellules vivantes. Cette approche permet de déplacer le motif sur le terrain sans entrave, tant que la population ne dépasse pas la taille de la matrice de coordonnées direct. L'inconvénient est que le comptage voisines vivantes devient une opération de recherche, ce qui ralentit la vitesse de simulation. Avec des structures de données plus sophistiquées ce problème peut également être en grande partie résolu.

Pour explorer de grands motifs à de grandes profondeurs de temps, des algorithmes sophistiqués comme Hashlife peut être utile.

Variations sur la vie

Depuis sa création originale de la vie, de nouvelles règles ont été élaborées. Le jeu standard de vie, dans lequel une cellule est "né" si elle a exactement trois voisins, reste en vie si elle a 2 ou 3 voisins vivant, et meurt autrement, est symbolisée par "23/3". Le premier numéro, ou liste de nombres, est ce qui est nécessaire pour une cellule de continuer. La deuxième série est l'exigence de la naissance. Ainsi «16/6» signifie «une cellule est né se il ya six voisins, et vit sur se il ya 1 ou six voisins». HighLife est 23/36, parce qu'avoir six voisins, en plus de 23/3 règle du jeu original, provoque une naissance. HighLife est surtout connu pour ses réplicateurs. D'autres variantes existent sur la vie, bien que la grande majorité de ces univers sont soit trop chaotique ou désolée.

Un échantillon d'un oscillateur 48 étapes à partir d'un jeu 2D hexagonale de la vie (règle 34/2).

Certaines variations de modifier la géométrie de l'univers ainsi que la règle. Les variations ci-dessus peuvent être considérés comme 2D Square, parce que le monde est à deux dimensions et mis en une grille carrée. Place 3D et 1D carrés variantes ont été développées, comme l'ont fait les variations 2D hexagonales où le réseau est hexagonale ou triangulaire au lieu de la place.

Les règles de Conway peuvent également être généralisés de sorte qu'au lieu de deux Etats (vivantes et mortes) il ya trois ou plus. Les transitions d'état sont ensuite déterminés soit par un système de pondération, soit par une table spécifiant les règles de transition distinctes pour chaque État; par exemple, Multicolore "Règles Tableau" de Cellebration de Mirek et les familles de la règle "de vie pondérée" comprennent chacun exemples de règles équivalentes à la vie de Conway.

Patterns relatives aux fractales et systèmes fractales peuvent également être observés dans certaines variations de la vie comme. Par exemple, l'automate 12/1 génère quatre approximations très proche de la Triangle Sierpiński lorsqu'il est appliqué à une seule cellule vivante.

L'immigration est une variation qui est le même que le jeu de la vie, sauf qu'il ya deux états ON (souvent exprimé en deux couleurs différentes). Chaque fois qu'une nouvelle cellule est né, il prend l'état ON qui est la majorité dans les trois cellules qui lui ont donné naissance. Cette fonction peut être utilisée pour examiner les interactions entre vaisseaux spatiaux et autres «objets» dans le jeu. Une autre variante similaire, appelé QuadLife, implique quatre différents états ON. Quand une nouvelle cellule est née de trois différents sur les voisins, il prend la quatrième valeur, et par ailleurs, comme l'immigration, il prend la valeur de la majorité. À l'exception de la variation entre les cellules ON, ces deux variations agissent de manière identique à la Vie.

Variante pour deux joueurs

Dans cette variante, les cellules vivantes peuvent avoir deux couleurs et un joueur gagne quand toutes les cellules de la couleur de l'adversaire sont éliminés. Quand une cellule morte devient en direct, sa couleur est déterminée par la couleur dominante de ses cellules vivantes voisins (qui sont exactement trois), comme dans l'immigration précitée. Commencez avec un modèle départ aléatoire ou pré-choisie avec la moitié des cellules vivantes de chaque couleur. Après une itération, le premier joueur peut ajouter une cellule de sa couleur et de supprimer une cellule de la couleur de son adversaire. Après la prochaine itération de l'autre joueur peut faire la même chose, et ainsi de suite.

Programmes de vie notables

Le premier programme de vie a été écrit pour le PDP-7 par Guy et MJT SR Bourne en 1970. Sans son aide quelques découvertes sur le jeu aurait été difficile à faire.

Il ya maintenant des milliers de programmes de la vie en ligne, donc la liste complète ne seront pas fournis ici. Ce qui suit est une sélection d'un petit nombre de programmes avec une certaine réclamation particulière à la notabilité, comme la popularité ou des caractéristiques inhabituelles. La plupart de ces programmes intègrent une interface utilisateur graphique pour l'édition de schémas et la simulation, la capacité de simuler de multiples règles, y compris la vie, et une grande bibliothèque de motifs intéressants dans la vie et d'autres règles de CA.

• Jeu de la vie par Alan Hensel. Une applet Java Web de pop-up avec des algorithmes de simulation rapides et une grande bibliothèque de modèles de vie intéressante.
• Golly. Un multi-plateforme (Windows, Macintosh et Linux) open-source système de simulation de vie par Andrew Trevorrow et Tomas Rokicki y compris le algorithme de Hashlife pour la production extrêmement rapide et Python scriptabilité à la fois pour l'édition et la simulation.
• Life32. Freeware pour les machines Windows inclut de puissantes et scriptable fonctions d'édition de motif.
• La Cellebration de Mirek. 1-D et 2-D automates cellulaires visionneuse gratuite, explorateur et éditeur pour Windows. Comprend les installations puissants de simulation et d'affichage d'une grande variété de règles CA y compris la vie, et un éditeur de scripts.
• Xlife Un laboratoire cellulaire-automate par Jon Bennett. Longtemps l'application standard de simulation Vie Linux, il a également été porté sur Windows. Peut gérer des règles d'automates cellulaires avec le même quartier que la vie et jusqu'à huit états possibles par cellule. Voir ici depuis de nombreuses versions alternatives.