Gra w życie
Z Wikipedii
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.
Gra została spopularyzowana przez Martina Gardnera na łamach Scientific American. 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.
Spis treści |
[edytuj] Powstanie gry
Conway zainspirowany pracami Stanisława Ulama oraz Roberta Schrandta 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.[1] Do badania populacji żyjących Conway używał komputera PDP-7.
[edytuj] 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", 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.
[edytuj] 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").
[edytuj] Szczegółowy podział struktur ze względu na zachowanie
[edytuj] 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.
 Klocek (blok) |
 Łódź |
 Bochenek |
 Kryształ (ang. beehive – ul) |
 Koniczynka (ang. tub – kadź) |
 Staw (ang. pond) |
[edytuj] 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.
Większość liczb naturalnych może być długościami okresu oscylatora. Wyjątkami są jednak liczby 19, 23, 31, 37, 38, 41, 43, oraz 53. Nie wiadomo, czy oscylatory dla takich długości okresów istnieją, ale jest bardzo prawdopodobne, że tak jest. Warto dodać, że dla okresów 34 i 51 jedyne znane oscylatory składają się z niezależnie działających struktur o okresie 2 lub 3 i 17. Przykładowo oscylator o okresie 34 tworzy się z oscylatorów długości 2 i 17 w takiej odległości, by na siebie nie wpływały. Dla cyklu długości 14 istnieje natomiast 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ą). Ich tworzenie jest dość trudne (wymaga sporej wyobraźni).
 Blinker (światła uliczne) |
 Żabka |
 Krokodyl |
[edytuj] Niestałe
Struktury niestałe zmieniają się, nie powracając nigdy do swojego stanu pierwotnego. Jest to w praktyce grupa łącząca struktury nie należące do żadnej z pozostałych kategorii. Z tego też powodu 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ę być strukturą niestałą).
Niektóre struktury niestałe mają jednak właściwość ciekawego lub bardzo długiego przebiegu rozwoju. Jedną z cech takich struktur jest stosunek liczby komórek w stadium początkowym do liczby kroków, po których następuje stabilizacja, tj. zamiana 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 około 1200 kroku, emisja kilkudziesięciu gliderów; L≈280.
- 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 – umierać, hard – trudno) natomiast określa się układ, który co prawda znika, ale dopiero po długim czasie.
 Diehard – umiera po 130 krokach; ; L≈15. |
 Żołądź – stabilizuje się po 5206 krokach; L≈700. |
Odkryto również kilka układów nieśmiertelnych (Po okresie przejściowym tworzą podobne (takie same?) "dymiące lokomotywy" zostawiające zygzakowatą linię kwadratów (w wypadku ostatniego układu – dwie lokomotywy).):
 |
 |
| Nieśmiertelny układ – tylko 10 komórek | Nieśmiertelny układ – mieści się w kwadracie 5x5 |
 |
|
| Nieśmiertelny układ – mieści się w jednej linii | |
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.
[edytuj] Statki (spaceships)
 Glider (szybowiec) |
 Lot szybowca |
 LWSS (Dakota) |
 Lot Dakoty |
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).
[edytuj] 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ą ilość 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ć wyłącznie się 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.
[edytuj] Inne statki
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.
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ące je informatycy nadają im często artystyczną formę, np. ryby czy falującej wody.
[edytuj] 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.
Gosper Glider Gun
[edytuj] 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 egzystuje samodzielnie.
Najprostsze puffery (składają się one już ze dwudziestu kilku żywych komórek) – zostawiają za sobą statki lub chaotyczny, stabilny pas, tzw. ruiny (debris). Powszechnie stosowaną metodą tworzenia prostych pufferów jest odpowiednie składanie MWSS-ów oraz niewielkiej struktury niestałej, jak np. B-Heptomino. Bardziej złożone – oscylatory, działa czy nawet inne puffery.
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.
Puffera, który zostawia za sobą statki, nazywamy rake'iem (ang. grabie, hulaka). Najprostszy rake składa się z 2 LWSS-ów i B-Heptomina, w skład wszystkich innych również wchodzą WSS-y. Najbardziej złożona struktura tego typu, Spider-Rake, składa się z około 1000 komórek w pierwotnym stadium. Istnieje kilkadziesiąt odkrytych rake'ów.
Breedery (ang. rozpłodnik, hodowca) natomiast to puffery o bardzo złożonym zachowaniu. Breedery pozostawiają za sobą działa lub nawet inne puffery, jednak jedynym warunkiem określającym czy dany puffer jest breederem, jest kwadratowy przyrost w czasie populacji jego żywych komórek (istnieją też działa wystrzeliwujące "hulaków" i regularne układy z brzegiem zapewniającym im rozszerzanie się). Zachowanie breederów przebiega zwykle ten sposób: "czoło", a więc oscylująca i produkująca nowe obiekty część puffera, wysyła w różnych kierunkach statki, które zderzając się, tworzą strukturę niezmienną. Następnie, zwykle po kilkudziesięciu krokach, wskutek zderzeń struktur niezmiennych z gliderami tworzy się działo. W takim razie, skoro co pewien okres czasu czoło wytwarza działo, a każde z dział tworzy statek – przyrost populacji wyraża się funkcją kwadratową. Breedery są najtrudniejszymi i najbardziej skomplikowanymi (po kilka tysięcy komórek w stadium początkowym) strukturami gry w życie. Jak do tej pory, wynaleziono ich kilkanaście.
Warto jednak zwrócić uwagę, że istnieją różne złożone struktury, ale większosć z nich po najdrobniejszym zakłóceniu praktycznie zawsze rozpada się, stabilizując się w sposób podobny do losowych układów. Tworzą się klocki, światła uliczne (często w formie całych skrzyżowań, jak z wypełnionego kwadratu 3 na 3), kryształy (również często w czwórkach, jak z wypełnionego kwadratu 5 na 5)), bochenki, nieco łodzi, stawów i podobnych do łodzi drobnych układów stabilnych. Wylatują też szybowce. Inne migacze są rzadkością, a bardziej złożonych układów praktycznie się nie spotyka.
[edytuj] Modyfikacje gry w życie
[edytuj] Modyfikacje reguł
Reguły, jakim podlega automat opisywane są często skrótowo w następujący sposób:
- przed ukośnikiem umieszcza się te liczby komórek w sąsiedztwie, dla których żywe komórki przeżywają (dla reguły Conwaya będzie to 23);
- następnie umieszcza się ukośnik: /;
- po ukośniku umieszcza się te liczby komórek w sąsiedztwie, dla których martwe komórki ożywają (dla reguły Conwaya będzie to 3);
Reguły Conwaya można więc zapisać : 23/3, a reguły Trzy Cztery : 34/34.
Modyfikacji gry w życie jest zbyt wiele (218 = 262144), by pomieścić je tu wszystkie. Tabela zawiera reguły dołączone do programu Mirek's Cellebration, te wspomniane przez Wolframa oraz kilka innych.
| Reguła | Nazwa | Opis |
|---|---|---|
| /2 | Seeds (nasiona) | Wzrost intensywny, chaotyczny |
| /234 | Serwety | Przypomina koronki, serwety |
| 012345678/1 | Wolfram – 7(e) | |
| 012345678/3 | Płatki, Życie bez śmierci | Wzory przypominają drabiny. [1] |
| 012345678/378 | Wolfram – 9(a) | |
| 01356/13456 | Wolfram – 7(d) | |
| 018/018 | Wolfram | |
| 0238/123567 | Wolfram – 13(f); klasa 3 | |
| 03456/34 | Wolfram – 7(g) | |
| 045/0578 | Wolfram – 7(i) | |
| 0468/236 | Wolfram – 7(a), 13(g); klasa 3 | |
| 1/1 | Narośl | Opracowany przez Kellie Evans; tworzy interesujące formy, startuje nawet od pojedynczej komórki. |
| 12345/3 | Labirynt | Tworzy wzory przypominające labirynty. |
| 12456/0578 | Wolfram – 7(h) | |
| 125/36 | 2x2 | Ma dużo oscylatorów i statków |
| 135/135 | Wolfram – 13(h); klasa 3 | |
| 1357/1357 | Replikator | Automat replikujący Edwarda Fredkina, każda struktura jest z czasem zastępowana przez jej kilka kopii |
| 1358/357 | Ameba | Dobrze zbalansowana między życiem a śmiercią, ma statki |
| 23/3 | Gra w życia Conwaya | Bardzo złożone zachowania (odkryte kilkadziesiąt tysięcy sensownych struktur) |
| 23/36 | HighLife | Podobne do Gry w życie (część jej struktur działa w HighLife), w dodatku struktura samoreplikująca |
| 234/3 | Wolfram – 9(b), 13(b); klasa 2. ma statki | |
| 2345/45678 | Miasta otoczone murem | Tworzy aktywne centra otoczone statycznymi ścianami |
| 2346/367 | Wolfram – 9(c). ma statki | |
| 235678/3678 | Plamy | Struktury szybko się stabilizują, o dziwo znacznie różni się od poprzedniej reguły |
| 235678/378 | Koagulacje | Wzory rozszerzają się, w przeciwieństwie do plam |
| 238/357 | Pseudożycie | Ewolucja przypomina 23/3, ale mało który wzór z gry w życie działa pod tymi regułami |
| 245/368 | Ruch | Losowe struktury zwykle się stabilizują, ale wiele statków występuje naturalnie i często się pojawia. Najczęściej pojawiają się struktury stabilne, okresowe z okresem 2 lub 4, statek o okresie 7 i "dymiący pociąg" o okresie 170. |
| 27/257 | Wolfram – 7(b); ma statki | |
| 34/34 | Trzy Cztery | Początkowo sądzono, że ma ona tendencje do stabilizacji, ale dzięki symulacji komputerowej okazało się, że większe wzory eksplodują. Dużo małych oscylatorów i statki. |
| 34678/3678 | Dzień i Noc | Dużo wzorów o złożonym zachowaniu. Wzory można odwracać – uczynić wszystkie żywe komórki martwymi i na odwrót, a będzie on działał identycznie. |
| 4567/345 | Asymilacja | Tworzy statystyczne struktury przypominające diament, wnętrza kryształów częściowo wypełnione |
| 45678/137 | Wolfram – 7(f) | |
| 45678/3 | Koral | Wzory rosną powoli, tworzą struktury przypominające rafę koralową. |
| 5/345 | Długie życie | Reguła opracowana przez Andrew Trevorrowa, bardzo łatwo można spotkać oscylatory o długim okresie. |
| 5678/35678 | Diameba | Tworzy wielkie zwarte struktury z chaotycznie oscylującymi granicami. Zajmował się nią Dean Hickerson, który też znalazł wzory, których przyrost jest kwadratowy. |
Warto też zauważyć, że wszystkie reguły, które zawierają element /1, np. 1/1 lub 01356/13456 będą miały charakter eksplozji dla każdego wzoru początkowego. Dla każego kroku czasowego komórka (x,y), gdzie x i y to minimalne współrzędne żywej komórki, komórka (x-1,y-1) ma tylko 1 żywego sąsiada, więc ożyje.
[edytuj] Modyfikacje kształtu komórek
Oprócz powszechnie przyjętego podziału płaszczyzny na kwadraty można zastosować także sześciokat (siatka heksagonalna). Najczęsciej stosowaną regułą jest 3/24, jednak nie znaleziono struktur tak interesujących jak w oryginale.
[edytuj] Modyfikacje kolorystyczne
Nie zmieniając reguł automatu, możemy zabarwić część komórek, co da ciekawszy efekt, nie wpłynie jadnak na kształt generowanych struktur.
[edytuj] Immigration
- Dla żywych komórek dostępne są dwa kolory – zwykle czerwony i żółty. Dla martwych sytuacja się nie zmienia względem oryginału.
- Definiując warunki początkowe każdej z komórek przypisujemy jeden kolor. Na każdy z kolorów powinna być zabarwiona przynajmniej jedna komórka, w przeciwnym razie uzyskamy zwykłą grę w życie.
- Nowo powstające komórki przyjmują taki kolor, jaki ma większość z ich 3 żywych sąsiadów.
- Kolory żywych komórek nie zmieniają się w trakcie gry.
[edytuj] QuadLife
- Dla żywych komórek dostępne są aż cztery kolory – zwykle czerwony, żółty, zielony i niebieski. Dla martwych sytuacja się nie zmienia względem oryginału.
- Definiując warunki początkowe każdej z komórek przypisujemy jeden kolor. Na przynajmniej dwa spośród kolorów powinna być zabarwiona przynajmniej jedna komórka, przeciwnym razie uzyskamy zwykłą grę w życie.
- Nowo powstające komórki przyjmują taki kolor, jaki ma większość z ich 3 żywych sąsiadów; jeżeli ma po jednym sąsiedzie z każdego koloru przyjmuje pozostały kolor.
- Kolory żywych komórek nie zmieniają się w trakcie gry.
[edytuj] Darwinia
Gra w życie pojawiła się jako jedno z intr do gry komputerowej Darwinia
- Każda komórka może pozostać żywa najwyżej przez 50 cykli, później umiera.
- Poza tym stosowane są klasyczne zasady Conwaya 23/3.
- Każda symulacja kończy się śmiercią wszystkich komórek.
[edytuj] Charakterystyka automatu komórkowego "Gra w życie"
Stephen Wolfram, który podzielił automaty komórkowe na cztery różne klasy, biorąc pod uwagę efekty jakie one wywołują, przyporządkował grę w życie do klasy czwartej, charakteryzującej się tym, że nie prowadza one ani do globalnego porządku, ani do globalnego chaosu. Przedstawił on hipotezę, że ten automat może wykonywać obliczenia i jest równoważny maszynie Turinga. Chris Langton, twórca innego popularnego automatu komórkowego, znanego jako mrówka Langtona wykazał w roku 1991, że proponowana przez Wolframa klasa czwarta, znajduje się pomiędzy klasą zachowań chaotycznych (klasa II) i struktur okresowych (klasa III).[2]
Przypisy
- ↑ Peter Conevey, Roger Highfield – Granice złożoności. Poszukiwania porządku w chaotycznym świecie ISBN 83-7180-083-5, s.131-132
- ↑ Peter Conevey, Roger Highfield – Granice złożoności. Poszukiwania porządku w chaotycznym świecie ISBN 83-7180-083-5, s. 139
[edytuj] Bibliografia
- The Winlife32 Page
- Conway's Game of Life
- What is the Game of Life?
- Peter Conevey, Roger Highfield – Granice złożoności. Poszukiwania porządku w chaotycznym świecie, Prószyński i s-ka, Warszawa 2007, ISBN 83-7180-083-5
[edytuj] Zobacz też
[edytuj] Linki zewnętrzne
- WinLife32, zaawansowany program do generacji struktur gry w życie (en)
- Obszerna strona dotycząca Gry w życie, zawierająca aplet do generacji automatów komórkowych. (en)
- Strona Roberta Wainwrighta, na której prowadzony jest magazyn dotyczący gry w życie. (en)
- Strona dotycząca gry w życie z programami i wzorami. (en)
- Gra w życie działająca na stronie internetowej
