Aller au contenu

Automate cellulaire/Jeu de la vie

Un livre de Wikilivres.

Ce livre a pour projet de répertorier et analyser les différentes structures du Jeu de la vie. Ce jeu sans joueur est en fait un automate cellulaire qui suit quelques règles simples mais qui permet de visualiser des concepts mathématiques complexes comme l’émergence.

Imaginé par John Horton Conway dans les années 1970, c’est un automate cellulaire totalistique de classe IV (selon la classification de Stephen Wolfram de 1980), qui permet l’émergence de structures complexes capables de se propager, ce que Conway a nommé « vie »).

Le jeu se déroule sur une grille de taille variable (en général de grande taille, avec effet de bord ou non).

L’état d’une cellule est binaire (mort ou vivant) et dépend uniquement de l’état précédent des 8 cellules voisines:

  • 0 ou 1 cellules voisines vivantes : « mort par isolement »,
  • 2 cellules voisines vivantes : « survie » (la cellule reste vivante si elle l'était déjà),
  • 3 cellules voisines vivantes : « vie » (la cellule devient vivante quel que soit son état précédent, on parle parfois de « naissance »),
  • 4 à 8 cellules voisines vivantes : « mort par surpopulation ».
Motif initial (t) Décimal du motif Poids à t Valeur de X à t+1
0 0 0
1 1 0
2 1 0
3 2 X
4 1 0
5 2 X
6 2 X
7 3 1
8 1 0
9 2 X
10 2 X
11 3 1
12 2 X
13 3 1
14 3 1
15 4 0
16 1 0
17 2 X
18 2 X
19 3 1
20 2 X
21 3 1
22 3 1
23 4 0
24 2 X
25 3 1
26 3 1
27 4 0
28 3 1
29 4 0
30 4 0
31 5 0
32 1 0
33 2 X
34 2 X
35 3 1
36 2 X
37 3 1
38 3 1
39 4 0
40 2 X
41 3 1
42 3 1
43 4 0
44 3 1
45 4 0
46 4 0
47 5 0
48 2 X
49 3 1
50 3 1
51 4 0
52 3 1
53 4 0
54 4 0
55 5 0
56 3 1
57 4 0
58 4 0
59 5 0
60 4 0
61 5 0
62 5 0
63 6 0
64 1 0
65 2 X
66 2 X
67 3 1
68 2 X
69 3 1
70 3 1
71 4 0
72 2 X
73 3 1
74 3 1
75 4 0
76 3 1
77 4 0
78 4 0
79 5 0
80 2 X
81 3 1
82 3 1
83 4 0
84 3 1
85 4 0
86 4 0
87 5 0
88 3 1
89 4 0
90 4 0
91 5 0
92 4 0
93 5 0
94 5 0
95 6 0
96 2 X
97 3 1
98 3 1
99 4 0
100 3 1
101 4 0
102 4 0
103 5 0
104 3 1
105 4 0
106 4 0
107 5 0
108 4 0
109 5 0
110 5 0
111 6 0
112 3 1
113 4 0
114 4 0
115 5 0
116 4 0
117 5 0
118 5 0
119 6 0
120 4 0
121 5 0
122 5 0
123 6 0
124 5 0
125 6 0
126 6 0
127 7 0
128 1 0
129 2 X
130 2 X
131 3 1
132 2 X
133 3 1
134 3 1
135 4 0
136 2 X
137 3 1
138 3 1
139 4 0
140 3 1
141 4 0
142 4 0
143 5 0
144 2 X
145 3 1
146 3 1
147 4 0
148 3 1
149 4 0
150 4 0
151 5 0
152 3 1
153 4 0
154 4 0
155 5 0
156 4 0
157 5 0
158 5 0
159 6 0
160 2 X
161 3 1
162 3 1
163 4 0
164 3 1
165 4 0
166 4 0
167 5 0
168 3 1
169 4 0
170 4 0
171 5 0
172 4 0
173 5 0
174 5 0
175 6 0
176 3 1
177 4 0
178 4 0
179 5 0
180 4 0
181 5 0
182 5 0
183 6 0
184 4 0
185 5 0
186 5 0
187 6 0
188 5 0
189 6 0
190 6 0
191 7 0
192 2 X
193 3 1
194 3 1
195 4 0
196 3 1
197 4 0
198 4 0
199 5 0
200 3 1
201 4 0
202 4 0
203 5 0
204 4 0
205 5 0
206 5 0
207 6 0
208 3 1
209 à 222 > 3 0
223 7 0
224 3 1
225 à 254 >3 0
255 8 0

Il existe 256 motifs initiaux () :

  • 172 motifs donne 0 pour valeur à t+1 (soit 67,2 %)
  • 84 donne un valeur différente de 0 (soit 32,8 %)
    • 56 donne 1 (soit 21,9 %)
    • 28 donne X (soit 10,9 %) ie. 1 ou 0 selon la valeur de X à t

On retrouve bien les trois catégories d’état (mort, vie, survie).

On remarque de nombreux motifs similaires (par transformation géométrique, symétrie ou rotation) qui ont donc le même destin :

  • 1, 4, 32, 128
  • 2, 8, 16, 64
  • 3, 6, 9, …, 96, 144, 192
  • 5, 33, 132, 160
  • 7, 41, 148, 224
  • 10, 18, 72, 80
  • 24, 66
  • 127, 223, 251, 254
  • etc.

On peut donc produire un tableau simplifié.

Tableau simplifié

[modifier | modifier le wikicode]
Motif initial (t) Décimal du motif Poids à t Valeur de X à t+1
0 0 0
1, 4, 32, 128 1 0
2, 8, 16, 64
3, 5, 6, 9, 12, 17, 20, 24, 33, 34, 36, 40, 48, 65, 65, 68, 96, 129, 130, 132, 136, 144, 160, 192 2 X
10, 18, 72, 80
3 1
4 0
5 0
6 0
7 0
255 8 0

On classe les structures en fonction de leurs périodes :


Consultez également ces pages dans d’autres projets Wikimedia :

Ressources multimédia sur Commons.
Article encyclopédique sur Wikipédia.