Úvod

Tato práce se zabývá hrou život (anglicky Game of life), která je dvoustavovým, dvourozměrnym celulárním automatem, který svým chováním připomíná vývoj společenství živých organismů. Hra je označována jako tzv. zero-player hra, jelikož je její průběh determinován počátečním nastavením bez žádného dalšího vstupu. Principy, kterých je hra postavena, se zabýval v roce 1940 John von Neumann, samostnou hru vytvořil anglický matematik John Horton Conway. Hra je příkladem systému, ve kterém z jednoduchých struktur vzniká komplexní chování – objevují se zde tzv. emergentní struktury.

V práci bude ve stručnosti zmíněn historický vývoj hry, dále pak její pravidla, bude popsán herní svět, významné herní struktury a v neposlední řadě bude ukázána souvislost mezi hrou a vědními obory, do kterých zasahuje.

Historie hry

Hra vychází z principu celulárních automatů (jejich popisu je věnována samostatná část práce), které v roce 1940 vymyslel John von Neumann ve snaze vytvořit sebereprodukující se stroj – stroj, který je schopen vytvářet vlastní kopie. Po čase zájem o celulární automaty opadl, jelikož tehdejší technika neměla dostatečný výkon pro práci s těmito strukturami. Zájem o ně pak v roce 1970 přinesl článek Johna H. Conwaye o Hře života v rubrice Matematické hry v časopise Scientific American. Hra stavěla na principech celulárních automatů v jejich velmi zjednodušené podobě.

Vydavatel hry napsal:

“Hra života ihned po vydání proslavila Conwaye, ale také otevřela nové pole matematického výzkumu celulárních automatů. Stalo se tak hlavně z důvodu analogií hry a růstu, úpadku a změn ve společnosti živých organismů.”

Jeho vydání vyvolalo velký čtenářský ohlas a brzy na to byl vydán další článek, který se zabýval technickým provedením hry. V roce 1971 byl založen samostatný časopis LifeLine, který vycházel čtvrletně do roku 1973.

Počáteční výzkum Hry života provázely dvě zásadní otázky – “Může nějaký tvar růst bez omezení?” a “Existuje taková konfigurace, která se vyskytuje v druhé a už v žádné další generaci?”

První otázka byla zodpovězena vytvořením struktury, která se nazývá dělo (gun), další strukturou pak byl pak kouřící vlak, který se hýbe sám a zanechává za sebou stopu. Obě struktury vymyslel R. William Gosper, který za to byl Conwayem oceněn.

Druhé otázce se také říká Problém existence dědečka (The Grandfather problem). Otázka nebyla doposud zodpovězena.

Popularita hry byla způsobena také tím, že se v jejím uveřejnění na trh dostávala nová generace levných počítačů, na kterých hra mohla běžet. Hra byla také prvopočátkem počítačového generování fraktálů.

V nedávné době se objevily pokusy o vytvoření teoretických počítačových systémů založených na Hře života (1,2).

Samoorganizace

Samoorganizace je jednou z teorií o vzniku života na naší planetě. Současná věda poukazuje na fakt, že hmota je schopna sama sebe organizovat a vytvářet struktury. Tímto způsobem je možno vysvětlit vznik života na zemi, jako samoorganizující se proces. Je to proces, při němž organizace určitého systému roste spontánně, tedy bez ovládání prostředí, nebo zásahu nějakého jiného vnějšího systému.

Příkladem může být mraveniště a mravenec. Samotný mravenec je jen primitivním automatem, ať už se jedná o mravence posledního z posledních nebo královnu. Každý z nich dělá jen přesně specifikovanou množinu ukonů a nic víc. Přesto mraveniště jako takové funguje jako perfektně řízený celek, který umí flexibilně a tudíž inteligentně reagovat na nečekané a nepřirozené podněty. Znamená to snad, že si mraveniště uvědomuje samo sebe, že si uvědomuje fakt, že je hromadou jehličí s nějakým hmyzem uvnitř?

Formálně je pojem samoorganizace vysvětlován pomocí pojmu entropie, který určuje míru neuspořádanosti daného systému. Čím je entropie větší, tím větší je míra neuspořádanosti. Samoorganizace pak vzniká v sytému, který se skládá z velkého množství samostatných jednotek, které tvoří menší systémy, mezi nimiž dochází k tokům entropie. Vzniká tedy mezi částmi tvořící celek. Dochází ke vzniku dispativních struktur. Struktur, kde dochází k úniku energie do okolí systému, které mají dva základní rysy. Tím prvním je to, že si vždy vyměnují energii s okolím a tím druhým je fakt, že je dřív nebo později čeká smrt. U živých organismů je to smrt taková, jak ji známe a u jiných struktur, jako jsou chemické reakce, je to zánik reakce, ale v každém případě vede k ukončení samoorganizačního procesu.

Emergence

Emergenece je vznik takových charakteristik systému, které nejsou popsatelné v rámci jednotlivých prvků tvořících tento systém. Např. elementární částice nepohlcují nějakou specifickou vlnovou délku elmag. záření a proto nemají barvu. Ale systém elementárních částic (napr. soubor molekul) již nějakou vlnovou délku může pohlcovat a tedy má barvu. Barva je tedy emergentní jev, který není popsatelný prvky systému.

Celulární automat

Celulární automat je fyzikální model reálné situace. Slouží k časové i prostorové diskrétní idealizaci fyzikálních systémů, kde hodnoty veličin nabývají pouze diskrétních hodnot v průběhu času. Pomocí jednoduchých pravidel je možné vytvořit celulární automat se složitým dynamickým chováním.

Popis hry

Hra je příkladem emergence a sebeorganizace, která je důležitá pro počítačové vědy, fyziku, biologii, biochemii, ekonomii, matematiku, filozofii a další vědní obory, které zkoumají, jakým způsobem z jednoduchým pravidel vzniká komplexní chování.

Pravidla hry

Svět Hry života je tvořen nekonečným dvourozměrným polem (teoreticky; prakticky mají výpočetní zařízení omezenou pamět), kde každá z buněk (prvky pole) je buďto mrtvá, nebo živá. Na začátku hry se nastaví počáteční konfigurace a v následujících diskrétních momentech (tick) probíhá interakce buňky s okolím. Pravidla jsou uplatňována v každé generaci buněk za vzniku generace nové. V průběhu hry vznikají různé tvary, které se dělí do kategorií jako jsou zátiší, oscilátory, děla a další. Každá z buněk interaguje se svým okolím následujícím způsobem:

  • Jakákoliv živá buňka s méně než dvěma živými sousedy zahyne
  • Jakákoliv živá buňka s dvěma, nebo třemi živými sousedy přežívá
  • Jakákoliv žívá buňka s více než třemi živými sousedy zahyne – přemnožení

Jakákoliv mrtvá buňka se třemi živými sousedy se stává živou buňkou – reprodukce

Tato konkrétní pravidla se nazývají S23/B3. Čísla před lomítkem říkají kolik sousedů musí buňka mít, aby přežila, čísla za lomítkem říkají kolik sousedů potřebuje mrtvá buňka k ožití. Tato pravidla byla vybrána vědomě s cílem zajistit, aby populace živých buněk rostla nepředvídatelně. Konkrétně jde o splnění požadavků, že by:

  • neměl existovat žádný počáteční vzor, pro který by šlo snadno dokázat, že populace může růst nade všechny meze
  • měly existovat počáteční vzory zdánlivě nade všechny meze rostoucí
  • a že by měl existovat takový počáteční vzor, který se určitou dobu vyvíjí než uplně vymizí, přejde do stabilní podoby a nebo do oscilační fáze.

Příklad

Černé podbarvení znamená živou buňku, bíle mrtvou buňku. Číslo označuje počet živých buněk v okolí.

Aplikací pravidel S23/B3 se z generace 0 vyvine generace 1 a následně generace 2. Generace 2 je stejná jako generace 1. Struktura je označována jako oscilátor (generace se s určitou periodou objevují znovu). Vzor se nazývá ropucha (toad).

Herní struktury

Struktury, které ve hře vznikají můžeme rozdělit do deseti hlavních kategorií:

Zátiší

Zátiší je stabilní konfigurací – vzor je svým vlastním rodičem (rodič je přímý předchůdce). Jsou často označované jako invariantní formy, jelikož se v průběhu hry nemění. Jsou složené z konečného počtu živých buněk. Další definice říká, že zátiší nesmí být možné rozdělit způsobem, při kterém by jeho části zůstaly stabilní samostatně. Pokud zátíší nevyhovuje druhé definici, mluvíme o pseudozátiší.

 

Blok

Včelín (Beehive)

Bochník (Loaf)

Lod

Dvojblok (pseudozátiší)

Oscilátory

Oscilátor je nestabilním vzorem, který je svým vlastním předchůdcem. S určitou periodicitou se vzor opět navrací do své původní konfigurace. Oscilátory s periodou 2 se nazývají alternátory. Oscilátory s periodou 3 se nazývají pulzary.

Blikač (Blinker)

Ropucha (Toad)

Maják (Beacon)

Pulzar (Pulsar)

Děla

Dělo je stacionárním vzorem, který do nekonečna vytváří vzory, které se po herním poli pohybují.

Posunovací se vzory

Posunovací vzor se pohybuje po hracím poli a s určitou periodicitou se navrací ke své původní podobě – oscilátor. U těchto vzorů se mimo periodicity určuje také jejich rychlost. Základní jednotka rychlosti je definována jako jedna buňka za generaci a představuje nejvyšší rychlost, kterou se ve hře může buňka pohybovat – ve hře se označuje také jako rychlost světla c. Nejznámějším vzorem je křídlo, které se pohybuje rychlostí c/4.

Kuřáci (Puffers)

Kuřák se pohybuje a zanechává za sebou stopu.

Rajská zahrada

Rajská zahrada (také označována jako sirotek) je konfigurace, která se může objevit pouze v nulté generaci. Jeho existenci předpověděl Edward F. Moore a John Myhill. Moorův-Myrhillův teorém říká, že pokud má nějaká konfigurace více než jednoho předka, tak existuje taková konfigurace, která žádného předka nemá a naopak. Teorém se vysvětluje na příkladu: Pokud se hrací plocha skládá z konečného množství buněk N a každá buňka se může nacházet ve dvou stavech, potom celkový počet možných konfigurací je 2N v každé generaci. Pakliže dvě různé konfigurace vytvoří v další generaci totožnou konfiguraci, pak přechodovou funkcí bylo vygenerováno pouze 2N-1 konfigurací a jedna konfigurace tedy nemá předchůdce. První praktický vzor nalezl v roce 1971 Roger Banks.

Metuzalémové (Methuselahs)

Malý vroz, jehož stabilizace trvá dlouhou dobu. R-pentomino se stabilizuje až po 1103 generacích, žalud po 5206 generacích a králíkům přechod trvá 17332 generací.

R-pentomino Zalud (Acorn) Králíci (Rabbits)

Agary (Agars)

Agar je vzor pokrývající celé herní pole a je periodický jak v prostoru, tak čase.

Pilové zuby (Sawtooths)

Populace pilového zubu neustále roste, ale neroste do nekonečna. Po určité době růstu se ustálí na určitou konstantní hodnotu. První takový vzor sestrojil v roce 1991 Dean Hickerson.

Knoty (Wicks)

Knotem je dlouhá sekvence opakujících se vzorů složená ze zátiší a oscilátorů. Na jedné straně může být zapálen a uhořívat.

Závěr

Tato práce prezentovala základní principy hry život, sebeorganizace, emergence a celulárních automatů. Ukázala také důležitost této hry pro různé vědní obory. Pro důkladnější prozkoumání doporučuji vyhledat animace vývoje uvedených vzorů.