Découvrir Logiciels & programmation Liens Web Propriétés remarquables Recherche automatisée Documentation Zoo

Le jeu de la Vie
Recherche automatisée d'oscillateurs et de navires

Dernière mise à jour le 14 juin 97


Un algorithme

Le mode d'utilisation

L'accélération de la recherche

Les implémentations (C et Pascal)


Un algorithme de recherche d'oscillateurs et de navires

Il est possible d'automatiser la recherche de certaines structures : les structures fixes, les oscillateurs, et les navires. Une description détaillée (en anglais) d'un algorithme de recherche a été proposée par Dean Hickerson.

Cet algorithme consiste à parcourir itérativement toutes les configurations satisfaisant les règles du jeu de la vie et des contraintes fixées par l'utilisateur.

L'algorithme procède de la façon suivante : On cherche une structure de période T s'inscrivant dans un rectangle de dimensions données.

Au départ, l'état de toutes les cases est inconnu pour tous les instant de 0 à T.
Ensuite le programme cherche une case inconnue et tente de choisir un état pour celle-ci.

L'exploration s'arrête : Cet algorithme permet donc de trouver si il en existe des structures oscillantes, ou des navires.
Une bonne partie des navires présentés dans la série d'articles Spaceships in Conway's Game of Life par David I. Bell on été découvert par un programme appliquant cet algorithme.

Ce type d'algorithme peut aussi très simplement être adapté pour rechercher des antécédents à une structure donnée. Il faut placer la structure dont on recherche des antécédents dans le rectangle correspondant à la période T et ne pas imposer de contraintes quand à la périodicité de la structure.


Il est possible d'utiliser un programme réalisé sur ce modèle selon deux approches :


Sur l'accélération de la recherche.
Les implémentations
Retourner à la page principale