Game of Life

https://xpil.eu/GbrYB

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

https://xpil.eu/GbrYB

9 komentarzy

  1. 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 🙂

    1. W pierwszym skanie wyłapałem tylko "z kumplem", "przyjemnego", "bawiliśmy" i "doszliśmy". Czy trzeba mnie już izolować? 😉

      386 to był potwór obliczeniowy dostępny tylko tym najbogatszym. Nam, maluczkim, pozostawały 80186 (ew. jego odpowiednik NEC V20). I pewnie jeszcze miałeś Herculesa, burżuju?

  2. 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)

    1. O żeż. 2 MB to faktycznie potentat. Pamiętam, że Civilization I tego wymagało. I trzeba było formatować dyskietkę na 1.8 MB żeby się cała gra zmieściła (a i tak trzeba było wywalić pliki z niepotrzebnymi animacjami).

      1. 🙂

        W Civ I grałem na Amidze. 4 dyskietki więc trochę wachlowania było. Ale się grę odpalało, ustalało warunki początkowe i szło się do kuchni zrobić coś do jedzenia bo a) komp i tak nie był do użycia b) jak się zaczęło grać to nie ma zmiłuj. Komputer w tym czasie wygenerował co miał wygenerować. I zaczynała się GRA!

        A RAM gdy kupowałem peceta (1994) miał prosty przelicznik: 1 megas = 1 milion złotych 🙂 Chyba na szafie mam jeszcze te pamięci po bańce 🙂

        1. Wersja na PC była w oryginale na dwóch dyskietkach, jednak (jak już wspomniałem) dało się to upchać na jedną, pod warunkiem że się tą jedną sformatowało gęściej, no i że się umiejętnie wywaliło parę plików.

          Nawet nie wiedziałem, że była wersja na Amisię.

          Btw Civ I przysłużyła mi się przy biciu prywatnego (dość niechlubnego) rekordu z serii "ile najdłużej wytrzymałeś bez spania?". Połączenie służby wojskowej (dużo rozrywek, mało snu) z Civ I okazało się strzałem w dziesiątkę. Trzy doby bez zmrużenia oka. Nigdy więcej. Nie dość, że człowiek potem pada jak martwy, to jeszcze na ogół pachnie jak Laboratoire Garnier le Skunx.

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

    1. 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,

Skomentuj Romek Anuluj pisanie odpowiedzi

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.