POWRÓT DO STRONY GŁÓWNEJ

Game of Life - Reactivated,
Automaty Komórkowe

Copyright © 2005   Robert Nowotniak
Instytut Informatyki, Politechnika Łódzka


Kod źródłowy: https://github.com/rnowotniak/GameOfLife2005.

Spis treści


Wprowadzenie

Program Game of Life - Reactivated służy do badania automatów komórkowych, a w szczególności bardzo powszechnej od pewnego czasu Gry w Życie, która od ponad 30 lat fascynuje wiele osób, a zwłaszcza informatyków i matematyków. Gra w Życie to automat komórkowy, wymyślony w 1970 roku przez brytyjskiego matematyka Johna Conwaya. Automaty komórkowe są dyskretnymi modelami matematycznymi, w których każda komórka znajduje się w określonym stanie i działa według lokalnej dla siebie reguły (funkcji przejścia). Wszystkie komórki pracują niezależnie od siebie i w sposób współbieżny.

Gra w Życie pokazuje przede wszystkim, jak skomplikowane wzorce mogą się wyłonić z układów rządzących się bardzo prostymi regułami. Z takimi zachowaniami mamy do czynienia w naturze. Współdziałanie wielu komórek sterowanych lokalnymi regułami potrafi stworzyć efekt, zauważalny jedynie globalnie w całym układzie.

Podstawowe właściwości automatów komórkowych to:

Formalnie rzecz biorąc, automat komórkowy stanowi trójka uporządkowana, złożona z sieci komórek {i}, dopuszczalnego zbioru stanów S oraz reguły (funkcji) przejścia λ. Dodatkowo program Game of Life Reactivated pozwala przypisać każdemu polu warunki środowiska W, które mają wpływ na wartość funkcji przejścia. Warunki środowiska na danym polu to uporządkowana trójka liczb rzeczywistych.

- zbiór stanów, w których może przebywać komórka.

Funkcja przejścia λ określa stan, w którym ma się znaleźć komórka i w t+1 kroku symulacji. Dziedziną λ jest zatem iloczyn kartezjański warunków środowiska W, otoczenia komórki i w kroku t oraz dotychczasowego stanu komórki si w kroku t


Zauważmy, że przy naszych założeniach odwzorowanie λ nie jest surjekcją. Zbiór stanów jest wspólny dla wszystkich rodzajów komórek, ale to od funkcji przejścia danego rodzaju komórki zależy, w jakim podzbiorze stanów zbioru S będzie się znajdować komórka.

Samoorganizacja automatu komórkowego polega na wyłanianiu się pewnego rodzaju wewnętrznego uporządkowania struktury kolonii komórek z upływem czasu, które to uporządkowanie nie jest wymuszone przez czynniki zewnętrzne. Podobna właściwość występuje w rzeczywistości, w fizyce i chemii. Wystarczy pomyśleć sobie chmurę i zastanowić się, co decyduje o jej kształcie.

Podstawy dla rozwoju automatów komórkowych stworzyli w latach 40 Stanisław Ulam i John von Neumann. Pomimo swej prostej budowy automaty mogą tworzyć nieskończenie skomplikowane wzory o zadziwiającej złożoności i właściwościach. Należą do nich zwłaszcza samoorganizacja, powielanie i wyłanialność wzorców zachowań. Te cechy bardzo upodobniają działanie automatów komórkowych do naturalnych organizmów i struktur (chmury, kryształy, skały), do wahań cen akcji na giełdzie lub chociażby do natężenia ruchu w komunikacji ulicznej.


Automaty jednowymiarowe

Duży wkład w zbadanie dwustanowych automatów jednowymiarowych o promieniu jeden miał na początku lat 80 Stephen Wolfram. Rozważaną rodzinę automatów podzielił na cztery klasy. Automaty komórkowe mogą tworzyć struktury zadziwiająca przypominające swoją budową twory naturalne. Jednowymiarowy automat o regule 22 tworzy nieregularne, sprawiające wrażenie przypadkowości, struktury o chaotycznych zagęszczeniach. Taka struktura przypomina powierzchnie niektórych rodzai muszli morskich.


Każda komórka to automat skończony o 1-wymiarowych otoczeniu, promień 1.
Numer reguły tego automatu w notacji Wolframa to 18.

Czy pozorna losowość występowania nieregularnych zagęszczeń na powyższej, sztucznej kolonii komórek nie jest podobna do powierzchni naturalnej muszli morskiej? Czy to więc znaczy, że komórki muszli są automatami, wykonującymi proste algorytmy, dobrane przez naturę?


Muszla morska: Olivia Porphyria

Stephen Wolfram podzielił rozważaną przez siebie grupę automatów na cztery klasy.


Dwuwymiarowe automaty komórkowe - klasy (2,1)

Komórki w grze wymyślonej przez Conwaya mogą być w jednym z dwu stanów, a funkcja decydująca o zmianie stanu jest bardzo prosta. Komórka martwa, mająca dokładnie trzech sąsiadów, staje się żywa. Komórka żywa żyje nadal, jeśli ma dokładnie dwóch lub trzech żywych sąsiadów. Sama powyższa reguła pozwoliła odnaleźć prawdziwe bogactwo form, m.in. stałe układy komórek, oscylatory, obiekty przesuwające się, a nawet takie które wykonują działania arytmetyczne, logiczne czy nawet symulują komputer (w sensie Turinga)!

Proste trwałe formy życia dla gry Conwaya: ul, łódź, okręt, bochenek.
Migacz i ropucha to układy - oscylatory.
       

Najczęściej używanym sąsiedztwem w automatach komórkowych tej klasy jest (obok sąsiedztwa Neumanna) sąsiedztwo Moora, czyli dla komórki i o współrzędnych (x0, y0) zbiór komórek:


Kilka innych reguł przejść dla automatów (2,1)

Komórki Conwaya używają najpowszechniejszej, ale nie jedynej reguły przejścia dla automatów klasy (2,1). Innych możliwych funkcji przejścia jest całe mnóstwo. Jeżeli przyjąć, że istnieją tylko dwa rodzaje komórek, których sąsiedztwem jest sąsiedztwo Moora o promieniu 1, to daje to nam 28=256 różnych automatów. I to przy założeniu, że argumentem funkcji jest tylko liczba sąsiadów w danym stanie. Jeśli wartość funkcji przejścia zależałaby od rozmieszczenia stanów sąsiadów, to otrzymalibyśmy liczbę 2256 automatów - ale część z nich byłaby symetryczna względem siebie.

Brian's Brain (/2/3)

Najbardziej znany trójstanowy automat komórkowy. Występujące tu komórki trzech rodzajów: oczekujące, płonące lub przetwarzające. Jeśli komórka oczekująca ma dokładnie dwóch (w sensie Moora) płonących sąsiadów, to również staje się płonąca - i tylko wtedy. Komórka płonąca staje sie w swoim kolejnym kroku przetwarzająca. Komórka przetwarzająca zawsze staje się oczekującą.

Coral (S:45678 B:3)

Kolonia komórek rozrastająca się dość równomiernie we wszystkich kierunkach. Utworzenie dużej ,,dziury'' wewnątrz spowoduje jej zarośnięcie.

Amazing (S:12345 B:3)

Przy takiej funkcji przejścia komórki rozmnażają się we wszystkich kierunkach, tworząc bardzo dobrze (losowo) wyglądający labirynt.

Replicator

Replikator jest określony zbiorem reguł 1357/1357. Tym czym zadziwia najbardziej, jest wierne powielanie początkowego układu komórek w ośmiu egzemplarzach, dokładnie co trzydzieści dwie generacje. Poniższa seria pokazuje niektóre z nich.

Oprócz tego Replicator ma inną szczególną własność. Jak widzimy powyżej, niektóre generacje komórek sprawiają wrażenie zupełnego chaosu (generacja numer 30). Jednak cała kolonia przenosi w sobie początkową informację, która wyłoni się samoistnie za kilka generacji. To jeszcze nie wszystko. Można zauważyć, że rozmnażające się komórki mają niektóre właściwości fali informacji. Gdy fala trafi na ścianę martwych komórek i takich, których funkcja przejścia jest stała, potrafi się od takiej ściany odbić! - odwracając początkowy układ. Podobnie dwie biegnące ku sobie ,,fale'' mogą się przeniknąć, nie zakłócając informacji o zbiorach, które replikują.


Dwukrotnie odbita fala replikacji

Highlife (S:23 B:36)

Wszechświat oparty na funkcji przejścia Highlife jest podobny do klasycznego świata Conwaya, ale ciekawy ze względu na występujące w nim proste replikatory, które nie zostały jeszcze odkryte w przypadku funkcji Conwaya, pomimo iż dowiedziono, że takie istnieją. Powielający się układ musi mieć w przypadku Highlife określony kształt, który składa się tylko z sześciu komórek, więc jego powstanie zachodzi dość często w losowych koloniach. Układ komórek rozszerza się ukośnie, a co 12 * 2n występują dokładnie dwie kopie początkowego żyjątka, podczas gdy w generacji o numerze 12 (2n - 1) występuje 2n pełnych żyjątek. Taki rodzaj replikacji jest symulacją w komórkach funkcji Highlife automatu jednowymiarowego, w którym funkcją przejścia jest operacja alternatywy wyłączającej na stanach dwóch sąsiadów komórki.


Dwa pasma replikatorów w Highlife,
poniżej ropucha obracająca szybowiec.

Państwa miasta (Walled Cities) (2345/45678)

Każdy spójny organizm w tym ekosystemie rozszerza swoje granice do momentu, gdy będzie zbiorem wypukłym. Stworzenie drogi połączenia pomiędzy organizmami prowadzi do ich syntezy. Po ustabilizowaniu obszarów można zaobserwować chaotyczne przemiany komórek w ich wnętrzach, jednak organizmy nie będą się już nigdy powiększać. Nowe komórki są tworzone tylko we wnętrzach organizmów.


Kilka organizmów po lewej stronie zostało połączonych drogami.
Organizmy po prawej stronie powstały z rozrośniętych połączeń.

Wire World

W roku 1987 Brian Silverman zaprojektował 4-stanowy automat komórkowy, w którym działanie komórek może w zaskakujący sposób symulować przepływ prądu elektrycznego. Funkcja przejścia takiego automatu dana jest poniższą tabelką.

Stan Numer 0 1 2 3 4 5 6 7 8
Brak komórki 0 0 0 0 0 0 0 0 0 0
Przód elektronu 1 2 2 2 2 2 2 2 2 2
Tył elektronu 2 3 3 3 3 3 3 3 3 3
Przewodnik 3 3 1 1 3 3 3 3 3 3

Ten prosty zbiór reguł pozwala tworzyć dowolnie złożone układy działające jak obwody elektroniczne. W szczególności mogą to być dowolne bramki logiczne oraz elementy wykonujące działania arytmetyczne i logiczne.

Oto trzy małe generatory prądu o różnych natężeniach w komórkach Wire World. W trzecim z układów po lewo mamy dwie diody (przewodząca i zaporowa).
Bramka NOT. Aby działała, natężenie i faza wchodzących impulsów muszą być zgodne z impulsami wytwarzanymi we wnętrzu bramki.

Bramki XOR, AND, OR, NAND

Użycie kombinacji powyższych bramek logicznych pozwoliło stworzyć bardzo skomplikowane obwody elektroniczne jako układy automatów komórkowych Wire World. (O minimalizacji takich układów z bramkami można się dowiedzieć na mojej stronie o algorytmie Quine'a-McKluskey'a.)

Poniżej przedstawiony jest układ komórek, który symuluje przerzutnik RS, składający się z dwóch bramek NAND, w których wyjścia wpływają do jednego z wejść sąsiedniej bramki. Układ komórek jest niesymetryczny, ponieważ przecięcie przewodników w Wire World wymaga wprowadzenia dodatkowego elementu o rozmiarze podobnym do bramki NAND.


Przerzutnik RS
(1) - Wejście R‾ (Reset)
(2) - Wejście S‾ (Set)
(3) - Wyjście Q
(4) - Wyjście Q‾

Maze Race – komórki w labiryncie

Automat komórkowy wymyślony przeze mnie. Występują cztery stany. Komórki w dwóch stanach (zielone i czerwone) budują chaotyczny labirynt, zgodnie z regułą amazing, a komórki w pozostałych dwóch stanach próbują znaleźć wyjście z tego labiryntu (białe i żółte), rozchodząc się we wszystkich kierunkach, rozdzielając na skrzyżowaniach.


Cztery różne generacje

Układ komórek inspirowany kafelkami na FTIMS

Każdy, kto zajmował się kiedyś automatami komórkowymi lub grą w życie, zaczyna się z czasem zastanawiać nad układem komórek zgodnym z kolorami kafelek ma każdej napotkanej podłodze lub ścianie. Kafelki na podłodze parteru FTIMS tworzą następujący wzór.

Co powstanie z takiego układu komórek? Oto rezultaty.

Wynik po około 170 generacjach z funkcją Conwaya
Wynik po około 50 generacjach z funkcją Amoeba
Wynik po około 60 generacjach z funkcją Coral

Maszyna Turinga w Grze w Życie

W roku 2000 Paul Rendell udowodnił Turing-zupełność Gry w Życie Conwaya, projektując maszynę Turinga, jako układ komórek. Automat jest rozszerzalny do Uniwersalnej Maszyny Turinga. Oznacza to ekosystem żyjątek, który jest modelem komputera, mogącego wykonać dowolny algorytm - także symulować inny, dowolny automat i algorytm.
Przypuszcza się także, że Uniwersalną Maszynę Turinga da się zbudować w świecie Highlife - tworząc głowicę na jednym z końców strumienia replikacji oraz wykorzystując drugi, rozwijający się koniec jako nieskończenie długą taśmę.
Duży rozmiar i złożoność poniższego ekosystemu (około 2000 x 2000) uniemożliwiają wykorzystanie go w praktyce do czegokolwiek.


Projekt Maszyny Turinga w Grze w Życie (Paul Rendell 2000)

Wszechświat jako cyfrowy model fizyczny?

Gra w życie Conwaya i automaty komórkowe prowokują do zadania mnóstwa dziwnych pytań. Jak bardzo wszechświat jest podobny do ogromnego automatu komórkowego? Czy różnicą jest tylko gigantyczna złożoność tego pierwszego? Jeśli tak, to wszechświat byłby tylko wielkim komputerem, wykonującym jakiś algorytm. Czy o jakimkolwiek zdarzeniu można byłoby powiedzieć, że jest tak naprawdę losowe, jeśli pełna informacja o aktualnym stanie wszystkich komórek (czyli cząstek elementarnych, nie ważne jakich) pozwoliłaby obliczyć stan wszechświata w dowolnej późniejszej chwili czasu? Czy może wszystko jest czysto deterministyczne, tak jak w grze Conwaya, i istniałby ,,wzór na wszystko'', pozwalający przy znajomości pełnej informacji o stanie bieżącym obliczyć wszystko, co nastąpi później? A gdyby móc zapisać i później wiernie odtworzyć stan całej materii, na jej najgłębszym poziomie, w ciele człowieka, to czy odtworzone zostałyby też jego myśli i wspomnienia? Czy pamięć, uczucie, marzenie i wizja w ludzkim umyśle są jedynie konsekwencją aktualnego stanu materii w jego mózgu? Pesymistyczna wizja. Gdyby taka funkcja przejścia istniała, to czy byłaby złożona? Wydaje się, że tak. Z drugiej strony gra Conwaya pokazała, że bardzo proste reguły tworzą bardzo złożone systemy.

Obrazy różnych układów komórek

Jak napisać własną wtyczkę z funkcją przejścia?

Program Game of Life Reactivated jest oparty na systemie wtyczek, co ułatwia jego rozszerzanie i modyfikowanie. Funkcje przejścia są z założenia bardzo krótkie i proste. Bardzo łatwo można napisać definicję własnej funkcji przejścia, skompilować ją do postaci modułu i przypisać go rodzajowi komórki. Takie podejście umożliwia bardzo elastyczne tworzenie dowolnie wyszukanych automatów komórkowych.

Kod takiego dynamicznie ładowanego modułu może wyglądać następująco.

#include "common.h"
#include "komorka.h"
#include "sasiedztwo.h"
#include "srodowisko.h"

/*
 * Przykładowa funkcja przejścia
 */
extern "C" int
funkcja
(const Warunki_Srodowiska *W, const Sasiedztwo_Moora *S, int stan)
{
   int Zywi_Sasiedzi = Zlicz_Niemartwych_Sasiadow(S);
   const Komorka *k;

   // Komórka umiera przy ujemnej temperaturze
   if (W->temperatura() < 0)
      return 0;

   // Komórka przyjmuje stan 1 przy dużym nasłonecznieniu i wilgotności
   if (W->oswietlenie() > 50 && W->wilgotnosc() > 50)
      return 1;

   // Komórka przyjmuje stan 2, jeśli jej północy sąsiad też jest w takim stanie
   if ((k = S->Sasiad_Polnocny()) && k->podaj_stan() == 2)
      return 2;

   // Komórka przyjmuje stan 4, jeśli ma
   // ponad pięciu niemartwych sąsiadów w stanie 3
   if (Zlicz_Sasiadow_W_Stanie(S, 3) > 5)
      return 4;

   // W pozostałych przypadkach komórka obumiera
   return 0;
}
Kompilacja nowego modułu z funkcją przejścia:

Gotowe moduły ze zbiorami reguł

Kod funkcji Biblioteka .dll (MS Windows ©) Biblioteka .so (GNU/Linux)
1d-150.cpp 1d-150.dll 1d-150.so
3stany.cpp 3stany.dll 3stany.so
amazing.cpp amazing.dll amazing.so
amoeba.cpp amoeba.dll amoeba.so
artist.cpp artist.dll artist.so
brians_brain.cpp brians_brain.dll brians_brain.so
conway.cpp conway.dll conway.so
coral.cpp coral.dll coral.so
highlife.cpp highlife.dll highlife.so
maze_race.cpp maze_race.dll maze_race.so
replicator.cpp replicator.dll replicator.so
ring.cpp ring.dll ring.so
seeds.cpp seeds.dll seeds.so
sierpinski.cpp sierpinski.dll sierpinski.so
walled_cities.cpp walled_cities.dll walled_cities.so
wire_world.cpp wire_world.dll wire_world.so

Pobieranie

Kod źródłowy dostępny jest w repozytorium: https://github.com/rnowotniak/ifs2004.

Niniejszy program jest wolnym oprogramowaniem; możesz go rozprowadzać dalej i/lub modyfikować na warunkach Powszechnej Licencji Publicznej GNU, wydanej przez Fundację Wolnego Oprogramowania - według wersji 2-giej tej Licencji lub którejś z późniejszych wersji. Również tam znajdziesz dalsze informacje (w szczególności o braku jakiejkolwiek gwarancji).

Materiały i odnośniki

Lista pomysłów

POWRÓT DO STRONY GŁÓWNEJ