Game of Life

Za młodu interesowałem się byłem rozmaitymi algorytmami. Jednym z nich jest Game of Life - napiszę dziś króciutko cóż to takiego. Temat jest wprawdzie oklepany do bólu, ale ponieważ to mój blog, będę pisał nawet o dupie Maryni i gówno komu do tego 🙂

Game of Life (będę używał skrótu GoL bom leniw) to automat komórkowy, w wersji klasycznej dwuwymiarowy. "Gra" odbywa się na płaszczyźnie podzielonej na kwadratowe pola. Każde pole może zawierać maksymalnie jedną "żywą" bakterię (zwyczajowo oznacza się "żywe" pola na czarno a "martwe", tj. bez bakterii - na biało). No i teraz najciekawsze:

1. Jeżeli bakteria ma mniej niż dwóch sąsiadów (tzn. "żywych" sąsiadów), w następnym pokoleniu umiera z nudów.

2. Jeżeli bakteria ma więcej niż trzech sąsiadów, w następnym pokoleniu umiera z powodu tłoku.

3. Jeżeli bakteria ma dwóch lub trzech sąsiadów, przeżywa do następnego pokolenia.

4. Wreszcie, jeżeli puste pole jest otoczone przez dokładnie trzy bakterie, w następnym pokoleniu rodzi się na tym polu bakteria.

Proste, prawda? Spójrzmy na przykłady:

W poniższym przykładzie, środkowa bakteria umiera z powodu tłoku:

gol-4Co prawda przykład jest nie do końca jednoznaczny, ponieważ oprócz środkowej bakterii, która umiera, powyżej niej powinna urodzić się nowa, jako że w poprzednim pokoleniu komórka jest otoczona przez trzech sąsiadów. Ponadto, bakteria poniżej powinna przeżyć, ponieważ ma dokładnie trzech sąsiadów. Jednak nie wiemy tego na pewno, bo widać tylko mały fragment "świata", o rozmiarach 3x3 - skrajne komórki mogą mieć sąsiadów, których tutaj nie widać.

Tak czy siak, środkowa bakteria umiera bo ma za dużo sąsiadów.

Kolejny przykład:

gol-3

Tu środkowa komórka również "umiera", tym razem z nudów.

I jeszcze dwa przykłady:

 

 

gol-1 gol-2

W przykładzie po lewej, środkowa komórka przeżywa ponieważ ma dokładnie dwóch sąsiadów. W przykładzie po prawej na środkowym polu rodzi się nowa komórka, ponieważ w poprzednim pokoleniu pole miało dokładnie trzech sąsiadów.

W zasadzie to wszystko jeśli chodzi o reguły. Czy da się z tego wycisnąć coś ciekawego?

Otóż da się. Okazuje się bowiem, że w zależności od początkowego ustawienia da się uzyskać całkiem ciekawe "kolonie" komórek. Zacznijmy od bardzo prostego przykładu:

gol-5

To tak zwany "szybowiec". Proszę zwrócić uwagę, że po czterech pokoleniach komórki są ułożone w identyczny sposób jak na początku, ale są przesunięte o jedno pole w prawo i w dół. A więc jest to "nieśmiertelna" konstrukcja, która bezustannie wędruje, o tak:

gol-glider

 

Kolejna, jeszcze prostsza konstrukcja to tzw "światła uliczne", trzy komórki obok siebie, które w kolejnych pokoleniach przeskakują między układem pionowym i poziomym:

gol-blinker

Światła uliczne to najprostszy oscylator, czyli układ, który powraca do ustawienia wyjściowego w skończonej liczbie kroków. Innym prostym oscylatorem jest żabka:

gol-frog

Nieco bardziej skomplikowanym oscylatorem jest krokodyl, który potrzebuje piętnastu cykli żeby powrócić do ustawienia początkowego:

gol-croco

Znajdowanie oscylatorów jest zadaniem dość trudnym obliczeniowo. Oscylator z największą dotychczas znaną liczbą cykli to white shark, który replikuje się po ponad stu pięćdziesięciu milionach cykli.

Jeszcze jeden interesujący oscylator (177 cykli):

gol-104p177

Inną kategorią układów są tak zwane "matuzalemy", czyli układy, które stabilizują się po bardzo dużej liczbie cykli.

Bardzo efektowne są tzw "breedery" czyli wielkie układy przemieszczające się w nieskończoność i pozostawiające za sobą "ślad" w postaci innych aktywnych struktur. Poniżej przykład takiego breedera:

gol-breeder

Szczytowym osiągnięciem GoL jest implementacja za jej pomocą pełnej Maszyny Turinga, która - jak Czytelnik zapewne pamięta ze studiów - jest funkcjonalne równoważna dowolnemu komputerowi (a więc może przeprowadzać dowolnie skomplikowane obliczenia). Nie oznacza to oczywiście, że jest to "komputer" jakoś wybitnie szybki - zasymulowanie pojedynczego cyklu procesora za pomocą GoL zajmuje ponad 11 tysięcy cykli. Jest to tak zwana Paul Rendell's Turing Machine. Z wielkiej wysokości wygląda o tak:

gol-rendel

GoL doczekała się również wersji planszowej. Co prawda nie za bardzo wyobrażam sobie, żeby dało się w to grać dłużej niż kilkanaście minut, ale jeżeli ktoś jest fanatykiem (i znajdzie drugiego takiego samobójcę), czemu by nie...

Na koniec jeszcze opowiem o wariantach GoL. Po pierwsze, można eksperymentować ze zmianą warunków narodzin, przeżywalności i śmierci - w miarę ciekawie jest jeszcze w sytuacji, kiedy oryginalne reguły zmodyfikuje się nieco i doda przepis mówiący, że nowa bakteria rodzi się nie tylko przy trzech ale i przy sześciu sąsiadach.

Dalsze modyfikacje polegają na użyciu komórek innych niż kwadratowe. Jedyne rozsądne warianty wśród wielokątów foremnych to trójkąty i sześciokąty, jednak prowadzi się też eksperymenty ze światami wypełnionymi komórkami niesymetrycznymi.

Można wreszcie eksperymentować z dodaniem kolejnego wymiaru. Przy założeniu, że w 3D pojedyncza komórka jest sześcianem, każda komórka ma 26 sąsiadów, a więc ilość możliwych warunków narodzin, przeżywania i śmierci jest nieporównanie większa niż w dwóch wymiarach. A przecież oprócz sześcianów można jeszcze kombinować z czternastościanami albo - zgodnie z badaniami Weaire-Phelan - mieszkanką dwunastościanów i czternastościanów. Albo z bryłami wypełniającymi przestrzeń nieregularnie.

A jak się już ktoś konkretnie napije, może zacząć kombinować w większej niż trzy ilości wymiarów. Ale to już całkiem inna opowieść 😉


9
Dodaj komentarz

avatar
3 Comment threads
6 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
XYZxpilTomekxpilromek Recent comment authors
  Subscribe  
najnowszy najstarszy oceniany
Powiadom o
romek
Gość
romek

Jako że w liceum byłem w klasie biolchem tośmy się z kumplem w ramach łączenia przyjemnego (komputer! PC! 386!!) z pożytecznym (biologia!) bawiliśmy w te różne konfiguracje 🙂 Ale do breederów to nie doszliśmy 🙂

Romek
Gość
Romek

To był kumpla komputer, ja wtedy miałem Amigę 🙂 Jego tata miał doktorat z matematyki więc taki mainframe w domu był uzasadniony. I AFAIK miał 2 mega RAM (komputer, nie tata)

Tomek
Gość
Tomek

O kurka!!! 2MB RAM!!! Nie musiał pożyczać od kumpli, żeby Worda 2.0 zainstalować.... Czad...

%d bloggers like this: