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 3×3 – 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ść 😉

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

9 komentarzy do "Game of Life"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
romek
Gość

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ść

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ść

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

xpil
Gość

Faktycznie, to było ciekawe zjawisko. Word 2.0 działał na jednym MB pamięci, o ile się go już zainstalowało. Haczyk polegał na tym, że instalator wymagał 2MB. A więc trzeba było iść do kolegi (który też miał 1MB) i zabrać pożyczyć od niego tę pamięć na parę chwil. No ubaw po pachy,

XYZ
Gość

Czy to nie dowód na nieistnienie maszyny czasu?

XYZ-r.2034