U zarania epoki komputerowej, w mrocznych czasach zimnej wojny i wyścigu nuklearnego prowadzono badania nad stworzeniem maszyn, które mogłyby budować kopie samych siebie. Zasadność takich badań nie budzi wątpliwości: wszak armie robotów grają kluczową rolę w licznych wizjach zagłady ludzkości. Zanim zaś zniszczymy Ziemię, moglibyśmy użyć ich do przygotowania nowej planety na przybycie kolonizatorów. Załóżmy, że chcemy użyć robotów do stworzenia systemu kanałów irygacyjnych na Marsie obejmującego, powiedzmy, połowę planety. Oczywiście wyprodukowanie odpowiedniej ilości maszyn na Ziemi oraz przetransportowanie ich na inną planetę stanowiłoby nie lada wyzwanie. Gdyby jednak roboty potrafiły się powielać, moglibyśmy, zamiast wielu, wyprodukować i wysłać tylko jednego robota, który na miejscu powieliłby się odpowiednią ilość razy.
W tym artykule nie będziemy zajmować się jednak ani armią zbuntowanych marsjańskich robotów, które postanowiły najechać Ziemię ani innymi trudnościami technicznymi. Zamiast tego przedstawimy bardzo prosty a zarazem niezwykle ciekawy model pozwalający nam na symulowanie działania takich maszyn przy użyciu naszych komputerów: automat komórkowy. W działaniu może on wyglądać na przykład tak:
Rzecz dzieje się na prostokątnej planszy podzielonej na kwadratowe komórki – dokładnie tak, jak na kartce w kratkę. Każda komórka może być albo żywa (zamalowana kratka) albo martwa (pusta kratka). Na początku zamalujemy pewne kratki – będzie to opis naszej maszyny. Jej działanie będziemy obserwowali patrząc na to, jak układ żywych komórek zmienia się w czasie. Rozwój sytuacji na planszy będzie przebiegał w krokach. W jednym kroku wykonamy na planszy jednocześnie dwie zmiany:
Za komórki „otaczające” przyjmiemy: bezpośrednio w górę, dół, lewo, prawo oraz na skosy, czyli w sumie każda komórka ma ośmiu sąsiadów. Automat działający według powyższych reguł nazywa się Grą w Życie. Przyjrzyjmy się kilku krokom ewolucji przykładowego układu:
Co ciekawe, ostatnia klatka powyższego schematu jest taka sama, jak pierwsza. Oznacza to, że po trzech krokach ewolucji przedstawiony układ powraca do swojej postaci początkowej. Już niedługo przekonamy się, że takie „zapętlające się” układy (zwane oscylatorami) mają szczególne znaczenie w Grze w Życie.
Ręczne analizowanie ewolucji planszy byłoby raczej uciążliwe. Na szczęście w tym miejscu wkraczają komputery. Poniżej znajduje się aplet, który ułatwi nam eksperymenty z automatem komórkowym. Możesz wprowadzić do niego dowolny układ początkowy klikając na pola na planszy oraz śledzić rozwój sytuacji uruchamiając symulację, lub przyglądać się pojedyńczym krokom ewolucji. Możesz też przeciągać planszę po ekranie oraz przybliżać ją i oddalać używając kółka myszy. Podczas trwania symulacji nie możesz wprowadzać zmian na planszy. Symulacja zatrzyma się automatycznie, kiedy układ przestanie ewoluować (to znaczy: aplikowanie powyższych reguł nie zmienia sytuacji na planszy). Plansza w naszym aplecie ma ograniczone wymiary, które powinny być jednak wystarczające do prostych symulacji. Jest to dość istotna różnica względem modelu matematycznego, który zakłada, że plansza jest nieskończona. My przyjęliśmy, że komórki na granicy planszy nigdy nie zmieniają swojego stanu.
Szybko zauważysz, że przypadkowe układy komórek po zwykle gwałtownej ewolucji zamieniają się w bezładnie porozrzucany zbiór trwałych struktur. Jednak w Grze w Życie istnieją również układy niezwykle ciekawe. Aby je zaprezentować przygotowaliśmy kilka przykładów. Najprostszy z nich to Martwa Natura: zawiera on kilka układów, które nie ewoluują. Przykład Kreski pokazuje, w jak różnorodny sposób mogą rozwijać się bardzo podobne początkowo struktury. Kreski z naszego przykładu zamieniają się albo w znaną już martwą naturę albo w oscylatory. Przykłady Szybowiec oraz Statki gwiezdne prezentują być może najważniejsze struktury w Życiu: układy potrafiące przemieszczać się po planszy. Istnieje bardzo wiele takich struktur. Jak widać na przykładach, dzielą się one na dwie kategorie – poruszające się po skosach i na boki. Spróbuj zmodyfikować szybowiec w ten sposób, aby poruszał się on z lewego dolnego do prawego górnego rogu.
Gwoździem programu jest przykład Działo: układ, który w sposób ciągły „produkuje” szybowce. W prawym dolnym rogu znajduje się zaś inna bardzo ciekawa struktura – „pożeracz szybowców”. Gdyby nie on, ilość żywych komórek na planszy rosłaby do nieskończoności (na nieskończonej planszy). Twórca Gry w Życie, matematyk John Conway, nie wierzył w możliwość istnienia struktury, która mogłaby rosnąć w nieskończoność. Wyznaczył nawet nagrodę 50 dolarów dla osoby, która obaliłaby jego przypuszczenia. Działo, odkryte przez Billa Gospera w roku 1970, otworzyło przed Grą w Życie zupełnie nowe perspektywy.
Działo jest dopiero początkiem możliwości Gry w Życie. Odkryto bardzo wiele złożonych układów. Potrafią one na przykład odbić szybowiec (skierować go w inną stronę), skopiować go, albo opóźnić jego wędrówkę przez planszę. Gigantyczne układy Życia mają zaskakujące możliwości, potrafią na przykład znajdować liczby pierwsze. Jaka jest granica możliwości Gry w Życie? Zasada, która rządzi ewolucją planszy, jest przecież niezwykle prosta. Okazuje się, że Gra w Życie potrafi wszystko to, co nasze komputery – to znaczy, że każda czynność, którą można wykonać na komputerze, można również wykonać na planszy Gry w Życie.
Skoro komputery potrafią symulować Grę w Życie, to Gra w Życie również musi umieć symulować Grę w Życie. I potrafi! Na zakończenie przedstawiamy układ – bagatela – siedmiu milionów komórek, który symuluje Grę w Życie na planszy 15x15 (symulowany układ znajduje się w przykładach pod nazwą Galaktyka). Ilu kroków potrzebuje Gra w Życie, aby zasymulować jeden krok Gry w Życie? Nie tak wielu – około trzydziestu pięciu tysięcy.
Co dalej? Zainteresowanym Grą w Życie polecamy polską [2] oraz angielską [3] stronę Wikipedii, jak również LifeWiki [4] – encyklopedię Gry w Życie, zawierającą między innymi katalog kilkuset układów wraz z opisami. „Profesjonalnym” narzędziem do eksperymentowania z Życiem jest darmowy program Golly [5]. Pozwala on na symulowanie wielomilionowych układów (takich jak ten powyżej) na nieograniczonej planszy, jak również zawiera kolekcję spektakularnych wzorów demonstrujących potęgę Życia. Dzięki zaawansowanym algorytmom, Golly potrafi symulować tysiące kroków w ułamki sekund. Osoby, które postawiły już pierwsze kroki w programowaniu, zachęcamy do napisania własnego symulatora Życia (na początku wcale nie musi być interaktywny ani szybki). Choć Gra w Życie powstała na kartce, największe odkrycia zostały dokonane przy udziale komputerów (takich jak ten [6]). Miłej zabawy.
Tekst, aplet, grafika: Wiktor Janas.
Odnośniki:
[1] http://informatyka.wroc.pl/bugs/submit?title=Life
[2] http://pl.wikipedia.org/wiki/Gra_w_%C5%BCycie
[3] http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
[4] http://www.conwaylife.com/wiki/index.php?title=Main_Page
[5] http://golly.sourceforge.net/
[6] http://pl.wikipedia.org/w/index.php?title=Plik:Pdp-7-oslo-2004.jpeg