Game of Life

Le jeu de la vie, également connu simplement sous le nom de Life, est un automate cellulaire conçu par le mathématicien britannique John Horton Conway en 1970.

Le jeu est un jeu sans joueur, ce qui signifie que son évolution est déterminée par son état initial, ne nécessitant aucune autre intervention. On interagit avec le jeu de la vie en créant une configuration initiale et en observant son évolution, ou, pour les joueurs avancés, en créant des motifs aux propriétés particulières.

Règles

L'univers de Game of Life est une grille orthogonale bidimensionnelle infinie de cellules carrées, dont chacune est dans l'un des deux états possibles, vivant ou mort (ou peuplé et non peuplé, respectivement). Chaque cellule interagit avec ses huit voisines, qui sont les cellules adjacentes horizontalement, verticalement ou diagonalement. À chaque étape du temps, les transitions suivantes se produisent :

1. Toute cellule vivante avec moins de deux voisins vivants meurt, comme par sous-population.
2. Toute cellule vivante avec deux ou trois voisins vivants survit à la génération suivante.
3. Toute cellule vivante avec plus de trois voisins vivants meurt, comme par surpopulation.
4. Toute cellule morte avec exactement trois voisines vivantes devient une cellule vivante, comme par reproduction.

Le modèle initial constitue la graine du système. La première génération est créée en appliquant simultanément les règles ci-dessus à chaque cellule de la graine ; les naissances et les décès se produisent simultanément, et le moment discret où cela se produit est parfois appelé un tic. Chaque génération est une pure fonction de la précédente. Les règles continuent d'être appliquées à plusieurs reprises pour créer d'autres générations.


À la fin des années 1940, John von Neumann définissait la vie comme une création (comme un être ou un organisme) capable de se reproduire et de simuler une machine de Turing. Von Neumann réfléchissait à une solution d'ingénierie qui utiliserait des composants électromagnétiques flottant au hasard dans un liquide ou un gaz. Cela s'est avéré peu réaliste avec la technologie disponible à l'époque. Stanislaw Ulam a inventé les automates cellulaires, destinés à simuler les constructions électromagnétiques théoriques de von Neumann. Ulam a discuté de l'utilisation d'ordinateurs pour simuler ses automates cellulaires dans un réseau bidimensionnel dans plusieurs articles. En parallèle, Von Neumann tenta de construire l'automate cellulaire d'Ulam. Bien que réussi, il était occupé avec d'autres projets et a laissé certains détails inachevés. Sa construction était compliquée car elle essayait de simuler sa propre conception technique.

Motivé par des questions de logique mathématique et en partie par le travail sur les jeux de simulation d'Ulam, entre autres, John Conway a commencé à faire des expériences en 1968 avec une variété de règles d'automates cellulaires 2D différentes.[3] L'objectif initial de Conway était de définir un automate cellulaire intéressant et imprévisible. Ainsi, il voulait que certaines configurations durent longtemps avant de mourir, d'autres configurations durent éternellement sans permettre les cycles, etc. Ce fut un défi important et un problème ouvert pendant des années avant que les experts en automates cellulaires ne parviennent à prouver qu'en effet, le jeu de la vie de Conway admettait une configuration qui était vivante dans le sens de satisfaire les deux exigences générales de Von Neumann. Alors que les définitions avant Conway's Life étaient orientées vers la preuve, la construction de Conway visait la simplicité sans fournir a priori la preuve que l'automate était vivant.

Conway a soigneusement choisi ses règles, après de nombreuses expérimentations, pour répondre à ces critères :

1.Il ne devrait pas y avoir de croissance explosive.
2.Il devrait exister de petits modèles initiaux avec des résultats chaotiques et imprévisibles.
3.Il devrait y avoir un potentiel pour les constructeurs universels de von Neumann.
4. Les règles doivent être aussi simples que possible, tout en respectant les contraintes ci-dessus.

De nombreux motifs du jeu de la vie finissent par devenir une combinaison de natures mortes, d'oscillateurs et de vaisseaux spatiaux ; d'autres modèles peuvent être qualifiés de chaotiques. Un modèle peut rester chaotique pendant très longtemps jusqu'à ce qu'il finisse par s'installer dans une telle combinaison.