thumb|Glider gun Gra w życie (Life, The game of life) – jeden z pierwszych i najbardziej znanych przykładów automatu komórkowego, wymyślony w roku 1970 przez brytyjskiego matematyka Johna Conwaya. mały|Tor wyścigowy w Grze w Życie Gra została spopularyzowana przez Martina Gardnera na łamach Scientific AmericanMartin Gardner, „Mathematical Games,” Scientific American, vol. 223, no. 4, October 1970, p. 120-123.. Od momentu publikacji zawsze wzbudzała duże zainteresowanie z powodu zaskakującego sposobu, w jaki struktury potrafią ewoluować. To właśnie jej pojawienie się wzbudziło zainteresowanie automatami komórkowymi wśród studentów, którzy traktowali ją jako rozrywkę oraz fizyków, którzy zwrócili uwagę na możliwości automatów w zakresie symulatorów fizycznych. Dzisiaj matematyków, ekonomistów i naukowców z innych dziedzin interesuje sposób, w jaki przy zastosowaniu tylko kilku prostych reguł powstają skomplikowane struktury.

Powstanie gry Conway zainspirowany pracami Stanisława Ulama, Roberta Schrandta oraz nad układami sąsiadów i regułami zmian, eksperymentował nad stworzeniem takiego automatu pod koniec lat 60. XX wieku. Reguły, które w ostateczności przyczyniły się do powstania gry Życie zostały wybrane, ponieważ pozwalały na równowagę pomiędzy zbyt szybkim rozrastaniem się struktur i zbyt wolnym pojawianiem się szybko znikających obiektów. Do badania populacji żyjących Conway używał komputera PDP-7.

Opis reguł gry Gra toczy się na nieskończonej planszy (płaszczyźnie) podzielonej na kwadratowe komórki. Każda komórka ma ośmiu „sąsiadów” (tzw. sąsiedztwo Moore’a), czyli komórki przylegające do niej bokami i rogami. Każda komórka może znajdować się w jednym z dwóch stanów: może być albo „żywa” (włączona), albo „martwa” (wyłączona). Stany komórek zmieniają się w pewnych jednostkach czasu. Stan wszystkich komórek w pewnej jednostce czasu jest używany do obliczenia stanu wszystkich komórek w następnej jednostce. Po obliczeniu wszystkie komórki zmieniają swój stan dokładnie w tym samym momencie. Stan komórki zależy tylko od liczby jej żywych sąsiadów. W grze w życie nie ma graczy w dosłownym tego słowa znaczeniu. Udział człowieka sprowadza się jedynie do ustalenia stanu początkowego komórek.

Zdefiniowano kilka wzorców reguł generowania, najbardziej rozpowszechnione są reguły wymyślone przez Conwaya. Do nich też odnosi się podział struktur, przedstawiony w dalszej części artykułu.

Reguły gry według Conwaya Martwa komórka, która ma dokładnie 3 żywych sąsiadów, staje się żywa w następnej jednostce czasu (rodzi się); Żywa komórka z 2 albo 3 żywymi sąsiadami pozostaje nadal żywa; przy innej liczbie sąsiadów umiera (z „samotności” albo „zatłoczenia”).

Szczegółowy podział struktur ze względu na zachowanie Niezmienne Struktury niezmienne, inaczej stabilne lub statyczne, pozostają identyczne bez względu na krok czasowy (dla każdej żywej komórki spełniony jest warunek przetrwania i dla żadnej spośród martwych nie jest spełniony); najprostsza taka struktura (block) składa się z 4 żywych komórek. Pojawiają się bardzo często jako produkty końcowe ewolucji struktur. Tworzy się je stosunkowo prosto, istnieją schematy według których można wymyślać nowe tego typu struktury.

Oscylatory Oscylatory zmieniają się okresowo, co pewien czas powracają do swojego stanu pierwotnego; najprostsza taka struktura składa się z trzech żywych komórek położonych w jednym rzędzie. Najprostsze z nich dość często pojawiają się jako produkty końcowe ewolucji struktur.

Okresy oscylatorów najczęściej przyjmują wartości 2, 3, 4, 6 lub 8, choć w grze w życie znaleziono i takie, których okres wynosi prawie 150000. Dla pewnych reguł istnieje nawet oscylator o nazwie „biały rekin”, który ma okres 150000034.

thumb|Fontanna – oscylator (okres 14) Większość liczb naturalnych może być długościami okresu oscylatora. Nie odkryto oscylatorów o okresach 19, 23, 38, oraz 41, ale jest bardzo prawdopodobne, że takowe również istnieją. Warto dodać, że jedyne znane oscylatory o okresach 34 i 51 składają się z niezależnie działających struktur o okresie 2 lub 3 i 17, na przykład oscylator o okresie 34 powstaje z oscylatorów o okresach 2 i 17 umieszczonych w określonej odległości od siebie. Dla cyklu długości 14 znamy tylko jeden oscylator (Fontanna).

Charakterystyczną cechą oscylatorów o dłuższych okresach jest podobieństwo tych o cyklu jednakowej długości (np. oscylatory długości 32 przypominają zegary z obracającą się wskazówką).

Niestałe Struktury niestałe zmieniają się i nigdy nie powracają do swojego stanu pierwotnego. Jest to w praktyce grupa struktur, których nie można zakwalifikować do żadnej z pozostałych kategorii, dlatego jest ich najwięcej, a ich uzyskanie nie sprawia większych trudności (losowy układ komórek wprowadzony jako warunki początkowe zwykle okazuje się strukturą niestałą).

Niektóre struktury niestałe rozwijają się jednak w interesujący sposób. Jedną z cech, którymi opisuje się takie struktury jest stosunek liczby kroków, po których następuje stabilizacja, do liczby komórek w stadium początkowym. Stabilizacją nazywamy zamianę na konfigurację układów stabilnych, oscylatorów i statków (zwykle gliderów). Wartość ta oznaczana będzie tutaj przez L. Najważniejsze spośród najprostszych struktur niestałych: R-Pentomino (F-Pentomino) – chaotyczny rozwój aż do 1103 kroku, emisja kilkudziesięciu gliderów; L≈221; B-Heptomino – rozwój przez ponad 100 kroków aż do uzyskania zespołu struktur stabilnych; emituje glidera; L≈15; Pi-Heptomino – efektowny rozwój przez ponad 200 kroków aż do uzyskania charakterystycznego zespołu blinkerów (oscylatorów) i struktur stabilnych, tzw. rezultatu B-Pi; L≈30; Bi-Pi-Heptomino – struktura złożona z dwóch Pi-Heptomino odwróconych względem siebie do góry nogami. Efektownie rozwija się, po czym zanika po około 10 krokach czasowych; W-Mino – efektowny rozwój, zakończony po 50 krokach powstaniem zbioru blinkerów (oscylatorów) i struktur stabilnych; L≈6.

Najdłużej rozwijające się w struktury niezmienne nazwane są matuzalemami (nazwa pochodzi od Matuzalema). Terminem diehard (ang. die-hard - niereformowalny) natomiast określa się układ, który co prawda znika, ale dopiero po długim czasie.

Odkryto również kilka układów nieśmiertelnych – wykazujących nieskończony wzrost. Podane poniżej ciekawe przykłady po okresie przejściowym tworzą „lokomotywy kładące bloki” (ang. „block-laying switch engine”) o okresie 288 (w wypadku ostatniego układu – dwie lokomotywy):

Plik:Game of life infinite1.pngPlik:Game of life infinite2.pngNieśmiertelny układ – tylko 10 komórek – najmniejsza możliwa liczbaNieśmiertelny układ – mieści się w kwadracie 5x5Plik:Game of life infinite3.pngNieśmiertelny układ – mieści się w jednej linii

thumb|Do niedawna najmniejszy znany Ogród Edenu. thumb|Wzór mniejszy od dotychczasowego o jedną komórkę (szare zostały usunięte, granatowe – dodane) Ogrody Edenu formalnie są strukturami plasującymi się w kategorii niestałych, ale zostały wyróżnione ze względu na swoją szczególną właściwość. Są to bowiem układy, które nie mogą powstać w wyniku ewolucji jakiejkolwiek struktury. Jest ich bardzo niewiele, najmniejszy spośród nich składa się z około 100 komórek.

Statki (spaceships)

Tzw. „statki” zwykle zmieniają się okresowo – choć okresy nie przekraczają jednak najczęściej kilkunastu kroków czasowych – ale wraz z każdym cyklem przesuwają się o stałą liczbę pól po planszy w określonym kierunku.

Najbardziej znanym przykładem takiej struktury, będącym jednocześnie niejako symbolem gry w życie, jest glider (szybowiec).

Glider Przez długi czas po powstaniu gry w życie nie było jasne, czy istnieje jakikolwiek statek, czyli struktura, która mogłaby poruszać się w nieskończoność po planszy. Wyznaczono nawet nagrodę za jego odkrycie, w wysokości 50 dolarów. Udało się w końcu (w wyniku ewolucji R-Pentomino) odnaleźć układ, nazywany po polsku „szybowcem” (ang. glider), który przesuwa się po planszy i nigdy nie zastyga.

Układ ten stał się symbolem społeczności hakerskiej. W październiku 2003 roku Eric Raymond zaproponował szybowiec na emblemat hakerski. Został on bez większych głosów sprzeciwu zaakceptowany przez społeczność, chociaż część hakerów uważa, że społeczność nie powinna mieć godła jako takiego.

Glider jest najważniejszą strukturą gry w życie, ze względu na:

wielkie możliwości tworzenia nowych struktur, nawet bardzo złożonych, poprzez zderzanie ich odpowiedniej ilości w odpowiednim względnym położeniu; olbrzymią liczbę struktur (tzw. dział) będących w stanie produkować glidery (z różnymi częstotliwościami); kluczowy udział w niemal każdej strukturze obrazującej pewien algorytm, np. poszukiwaniu liczb pierwszych czy generowaniu liczb pseudolosowych oraz tworzonych tylko dla samego efektu.

Glider jest oscylatorem, o okresie długości 4. Może przesuwać się wyłącznie na ukos, pod kątem 45 stopni. Nie istnieją jego modyfikacje, to znaczy, że nie istnieje taki algorytm, który pozwala na dodawanie nowych komórek tak, aby powstające struktury dalej były statkami.

Glider często powstaje samoczynnie, jako produkt reakcji, w których olbrzymia liczba komórek ewoluuje w chaotyczny sposób.

Inne statki thumb|Dakoty: LWSS, MWSS i HWSS Poza tym znane są także tzw. statki kosmiczne. Różnią się one od glidera kierunkiem poruszania się (pion lub poziom, a nie ukos) oraz możliwością modyfikacji – poprzez dodawanie komórek w odpowiedni sposób będziemy uzyskiwać kolejne statki. W zależności od ich wielkości nazywane są LWSS, MWSS, HWSS lub OWSS (skrótowce od Light/Medium/Heavy/Over Weight Space Ship – Lekki/Średni/Ciężki/„Nadciężki” Statek Kosmiczny). Stosuje się też do nich nazwę Dakota z liczbą określającą ich rozmiar. Jeszcze większe Dakoty nie mogą latać samodzielnie, ale mogą w towarzystwie mniejszych.

thumb|Statki Poza tym istnieje jeszcze kilka innych statków o stosunkowo niewielkich rozmiarach (m.in. Maszyna Schicka, Rzutka). Pozostałe (kilkaset) takie struktury są duże (kilkaset żywych komórek) i trudne do tworzenia. Wymyślający je informatycy nadają im często artystyczną formę, np. ryby czy falującej wody.

Działa (guns) Działa to oscylatory, które co jeden okres „wyrzucają” z siebie jeden statek, który odłącza się i egzystuje samodzielnie. Najwięcej dział generuje glidery, poza tym część jest zdolna do wytwarzania statków kosmicznych. Długość okresu tych struktur waha się od 30 (najprostszy Gosper Glider Gun) aż do kilkudziesięciu tysięcy kroków czasowych. Ze względu na fakt, że są to formy bardzo zaawansowane (od stu do nawet kilku tysięcy żywych komórek), ich tworzenie jest zwykle bardzo czasochłonne i wymaga praktyki.

Plik:Gospers glider gun.gif Gosper Glider Gun

Puffery Puffery, inaczej puffer trainy – dymiące pociągi. Struktury oscylujące (o okresie zwykle w okolicach kilkunastu kroków) oraz poruszające się po planszy, a przy tym pozostawiające za sobą cyklicznie inne struktury, które odłączają się i egzystują samodzielnie.

Najprostsze puffery (składają się one już z dwudziestu kilku żywych komórek) – zostawiają za sobą statki lub chaotyczny, stabilny pas, tzw. ruiny (debris). Bardziej złożone – oscylatory, działa czy nawet inne puffery. Powszechnie stosowaną metodą tworzenia prostych pufferów jest odpowiednie składanie MWSS-ów oraz niewielkiej struktury niestałej, jak np. B-Heptomino.

Puffery są najbardziej efektownymi strukturami gry w życie. Przykładowo, mają one możliwość przeprowadzenia algorytmu wyznaczającego liczby pierwsze. Jednocześnie, ich tworzenie jest tak trudne, że nawet doświadczeni informatycy traktują je jako wymagające nie lada poświęcenia. Wpływa na to między innymi fakt, że niektóre z tych struktur mają po 5000 komórek żywych w stadium początkowym. Do tej pory wynaleziono około setki pufferów.