Hra "Život"

Hra „Život“ ( angl.  Conway's Game of Life ) je buněčný automat vynalezený anglickým matematikem Johnem Conwayem v roce 1970 .

Pravidla

• Místem působení hry je rovina vyznačená do buněk, které mohou být neomezené, omezené nebo uzavřené.
• Každá buňka na tomto povrchu má kolem sebe osm sousedů a může být ve dvou stavech: být „živá“ (zaplněná) nebo „mrtvá“ (prázdná).
• Rozmístění živých buněk na začátku hry se nazývá první generace. Každá další generace se počítá na základě předchozí podle následujících pravidel:
  • v prázdné (mrtvé) buňce, která sousedí se třemi živými buňkami, se rodí život;
  • má-li živá buňka dva nebo tři žijící sousedy, pak tato buňka nadále žije; jinak (jsou-li méně než dva nebo více než tři žijící sousedé), buňka zemře („z osamění“ nebo „z přeplněnosti“).
• Hra končí, pokud
  • na hřišti nezůstane ani jedna „živá“ buňka;
  • konfigurace v dalším kroku se bude přesně (bez posunů a rotací) opakovat v jednom z předchozích kroků (je přidána periodická konfigurace)
  • v dalším kroku žádná z buněk nemění svůj stav (předchozí pravidlo platí o krok zpět, vytvoří se stabilní konfigurace)

Hráč se aktivně neúčastní hry . Pouze zařídí nebo vygeneruje počáteční konfiguraci „živých“ buněk, které se pak mění podle pravidel. Navzdory jednoduchosti pravidel se ve hře může vyskytovat obrovské množství forem.

Původ

John Conway se začal zajímat o problém navržený ve 40. letech 20. století renomovaným matematikem Johnem von Neumannem , který se pokoušel vytvořit hypotetický stroj, který by se mohl reprodukovat sám. Johnu von Neumannovi se podařilo vytvořit matematický model takového stroje s velmi složitými pravidly. Conway se snažil Neumannovy myšlenky zjednodušit a nakonec se mu podařilo vytvořit pravidla, která se stala pravidly Hry o život.

Popis této hry byl poprvé publikován v říjnovém ( 1970 ) vydání časopisu Scientific American pod názvem „Math Games“ od Martina Gardnera ( Martin Gardner ) [1] .

Počítačová implementace

V počítačových implementacích hry je pole omezeno a zpravidla uzavřeno - horní okraj pole je „propojen“ se spodním a levý okraj vpravo, což je emulace povrchu torus , ale na obrazovce je pole vždy zobrazeno jako jednotná mřížka.

Nejjednodušší algoritmus „generační změny“ postupně prochází všechny buňky mřížky, počítá sousedy pro každou z nich a určuje osud buňky v nové generaci (nezmění se, zemře, narodí se). Takový algoritmus používá dvě dvourozměrná pole - pro současnou a pro příští generaci.

Rychlejší algoritmus provede první průchod všemi buňkami, ale zároveň vytvoří seznam buněk, na které se lze podívat v další generaci. Buňky, které se za generaci nemohou zásadně změnit, nejsou v seznamu zahrnuty. Pokud se například některá buňka a všichni její sousedé nezměnili během aktuálního výpočtu nové generace, pak se tato buňka během dalšího průchodu nezmění.

Postavy

Krátce po zveřejnění pravidel bylo objeveno několik zajímavých vzorů (variant uspořádání živých buněk v první generaci), zejména: r -pentamino a kluzák ( kluzák ).

Některé z těchto obrazců zůstávají nezměněny ve všech následujících generacích, stav jiných se periodicky opakuje, v některých případech s posunutím celého obrazce. Existuje postava ( Diehard ) pouhých sedmi živých buněk, jejichž potomci existují sto třicet generací a poté zmizí.

Conway původně navrhl, že žádná počáteční kombinace nemůže vést k neomezené reprodukci a nabídl bonus 50 dolarů tomu, kdo tuto hypotézu potvrdí nebo vyvrátí. Cenu vyhrála skupina na MIT , která přišla s pevnou, opakující se figurou, která periodicky vytvářela pohyblivé „kluzáky“. Počet živých buněk by tak mohl růst donekonečna. Pak byly nalezeny pohybující se postavy, zanechávající za sebou „odpadky“ od jiných postav.

K dnešnímu dni se více či méně rozvinula následující klasifikace čísel:

• Stabilní údaje : údaje, které zůstávají nezměněny
• Století : čísla, která se dlouho mění, než se stabilizují [2] ;
• Periodické obrazce : obrazce, ve kterých se stav opakuje po určitém počtu generací větším než 1;
• Pohyblivé figury : figury, ve kterých se stav opakuje, ale s určitým posunutím;
• Zbraně : tvary s opakujícími se stavy, navíc vytvářející pohyblivé tvary ;
• Parní lokomotivy : pohybující se tvary s opakujícími se stavy, které zanechávají jiné tvary jako stezky;
• Požírači : odolné kusy, které mohou přežít srážky s některými pohyblivými kusy tím, že je zničí;
• Reflektory : stabilní nebo periodické obrazce schopné změnit svůj směr , když s nimi pohybující se postavy narazí ;
• Multiplikátory : konfigurace, ve kterých počet živých buněk roste jako druhá mocnina počtu kroků;
• Tvary, které se při kolizi s některými tvary duplikují.

Rajská zahrada

Rajská zahrada (Garden of Eden) je uspořádání buněk, které nemohou mít předchozí generaci. Téměř u každé hry, ve které v předchozím kroku určuje stav buněk více sousedů, je možné existenci rajských zahrad prokázat, ale sestrojit konkrétní figurku je mnohem obtížnější.

"Čísla"

Pomocí nejjednoduššího „fontu“ 3 x 5 buněk, který zjevně navrhl Eric Angelini v roce 2007, můžete získat spoustu tvarů. Například číslo 90 napsané tímto písmem generuje kluzák [3] .

Vliv na rozvoj věd

Přestože se hra skládá pouze ze dvou jednoduchých pravidel, přitahuje pozornost vědců již více než čtyřicet let. Hra „Život“ a její modifikace ovlivňovaly (v některých případech vzájemně) mnoho oblastí exaktních věd, jako je matematika , informatika a fyzika [4] . Jedná se zejména o:

• teorie automatů ,
• teorie algoritmů ,
• Teorie her a matematické programování ,
• Algebra a teorie čísel ,
• Teorie pravděpodobnosti a matematická statistika ,
• Kombinatorika a teorie grafů ,
• fraktální geometrie ,
• výpočetní matematika ,
• teorie rozhodování ,
• Matematické modelování .

Mnohé vzory nalezené ve hře mají navíc své obdoby v jiných, někdy zcela „nematematických“ disciplínách. Zde je seznam věd, jejichž teorie mají zajímavé body kontaktu s fenomény „Života“:

• Kybernetika . Samotná hra je Conwayovým úspěšným pokusem dokázat existenci jednoduchých samoreprodukujících se systémů a také vznik jakési „inteligence“ v samoreprodukujících se systémech.
• Biologie . Vnější podobnost s vývojem populací primitivních organismů je působivá.
• Bakteriologie . Některé zajímavé varianty hry s dodatečnými podmínkami mohou přesně opakovat množení bakterií, které mohou s náhodnou pravděpodobností mutovat (podle modifikační podmínky).
• Fyziologie . Zrození a smrt buněk jsou podobné procesu vzniku a zániku neuronových impulsů.
• Astronomie . Evoluce některých složitých kolonií překvapivě schematicky opakuje fáze vývoje spirálních galaxií [5] [6] .
• Fyzika pevných látek . Teorie automatů obecně a hra "Život" zvláště se používá k analýze "přenosových jevů" - difúze , viskozity a tepelné vodivosti .
• Kvantová fyzika . Chování "životních" buněk (zrození nových a vzájemné ničení) v mnohém připomíná procesy, ke kterým dochází při srážce elementárních částic .
• Nanomechanika . Stacionární a pulzující kolonie jsou názorným příkladem nejjednodušších zařízení vytvořených na bázi nanotechnologií.
• Elektrotechnika . Pravidla hry slouží k modelování samoopravných elektrických obvodů .
• Chemie . Konfigurace podobné těm zabudovaným ve hře vznikají během chemických reakcí na povrchu; zejména při pokusech M. S. Shakaeva vznikají pohyblivé molekulární struktury, podobné „životnímu“ kluzáku. Probíhají také pokusy vysvětlit periodické chemické reakce pomocí vícerozměrných buněčných automatů. Samoorganizací elementárních částic se zabývá i supramolekulární chemie .

Možná je tato hra spojena s dalšími vědeckými fenomény, včetně těch, které jsou moderní vědě dosud neznámé. Je také možné, že v současnosti neobjevené zákony přírody a společnosti se díky „Životu“ a jeho modifikacím stanou srozumitelnějšími.

Fakta

• Pravidla hry jsou taková, že žádná interakce nemůže být přenášena rychleji než pohyb šachového krále . Jeho rychlost – jedna buňka v libovolném směru – je často označována jako „ rychlost světla “.
• Figurka „kluzáku“ byla navržena v roce 2003 jako emblém hackerů .
• První ruskojazyčná zmínka o „ Hře o život “ se vztahuje k roku 1971 a je známá jako „Evoluce“ v překladu časopisu Science and Life .
• Pokud do vyhledávacího pole Google zadáte „ conway's game of life “ , pak se kromě standardního výsledku dotazu zobrazí jako animace na pozadí podobnost této hry [7] [8] .

Úpravy

• Existují modifikace hry "Life" / "Evolution" podle:
  • rozměry  - v rovině, v objemu;
  • barevnost - jednobarevná, černobílá (šachovnice), plnobarevná;
  • směr algoritmu - přímý, zpětný;
  • evoluční konstanty — klasické (B3/S23), upravené;
  • velikost hřiště - omezená, neomezená, poloomezená;
  • činnost v terénu - aktivní, pasivní;
  • počet hráčů - nulová hra, jeden, dva;
  • herní činnosti - pasivní, aktivní;
  • geometrie pole — obdélníkové, šestiúhelníkové.

• Zajímavý je Conwayův inverzní problém – hledání předchůdce daného obrazce [9] . K jeho řešení lze zapojit statistický aparát: metodu Monte Carlo , simulační modelování a také celý arzenál heuristických metod .
• Efektivním algoritmem pro plnobarevnou hru je rozklad původního obrazu na monotónní, následovaný jejich superpozicí po aplikaci klasických životních pravidel na ně; pro objemové varianty - algoritmus ortogonální transformace. Příklady praktického použití jsou všechny druhy spořičů obrazovky, abstraktní obrázky a návrhy uměleckých děl.
• V šachové, černobílé verzi se účastní dva hráči, barva narození je určena převahou barvy v generativní trojici, záznam tahů se provádí podle pravidel šachového zápisu. Kromě původních hraničních útvarů jsou zde pozorovány barevné kolize, například „kluzák“ v zápisu: bílá a2b2c2, černá c3b4 - během transformačního cyklu se zcela odbarví a totéž: bílá a2b2, černá c2c3 b4 - demonstruje chromatická cykličnost „kluzáku“ v rámci jeho geometrického cyklu.
• V aktivní šachové hře mají hráči možnost ovlivňovat události „Života/Evoluce“ jediným úvodem – odebráním omezeného počtu žetonů své barvy, aby se rozšířili, stabilizovali běh dějin a působili proti soupeři. tento. Teoretickým základem jsou zde rozhodovací metody , aparát teorie her .
• Ve 3D implementaci hry každá buňka ohraničuje 26 dalších buněk, přežívá se 4–5 sousedy a s 5 sousedy se rodí nová a existují i ​​3D stabilní struktury, z nichž některé jsou podobné 2D. [deset]

Poznámky

1. ↑ Martin Gardner . Fantastické kombinace nové solitaire hry Johna Conwaye "life"  // Scientific American . - č. 4 (říjen 1970) .
2. ↑ Slovník života: dlouhověkost . Získáno 21. září 2015. Archivováno z originálu 22. září 2017. (neurčitý)
3. ↑ Číslice v životě . www.radicaleye.com. Získáno 15. července 2017. Archivováno z originálu 8. srpna 2017. (neurčitý)
4. ↑ Toffoli T., Margolus N. Stroje celulárních automatů. — M.: Mir, 1991. — ISBN 5-03-001619-8
5. ↑ M.W. Mueller, W.D. Arnett. Šíření tvorby hvězd a nepravidelná struktura ve spirálních galaxiích  //  The Astrophysical Journal. - 12.12.1976. — Sv. 210 . — S. 670–678 . — ISSN 0004-637X . - doi : 10.1086/154873 .
6. ↑ H. Gerola, P. E. Seiden. Stochastická tvorba hvězd a spirální struktura galaxií  (anglicky)  // The Astrophysical Journal. - 1978-07-01. — Sv. 223 . — S. 129–135 . — ISSN 0004-637X . - doi : 10.1086/156243 .
7. ↑ Jon Mitchell. Jak inženýr Google vybudoval vesmír ve velikonočním vejci (5. října 2012). Získáno 31. ledna 2016. Archivováno z originálu 16. října 2016. (neurčitý)
8. ↑ Siobhan Robertsová. Prolog // Genius At Play: The Curious Mind of John Horton Conway . — Bloomsbury Publishing USA, 2015. — P. XV. — 480p. - ISBN 1-620-40594-6 , 978-1-620-40594-9.
9. ↑ Journal of Science and Life . č. 8, 1972, str. 141-144.
10. ↑ Archivovaná kopie . Získáno 24. srpna 2021. Archivováno z originálu dne 18. července 2021. (neurčitý)

Literatura

• Andrew Adamatzky. Buněčné automaty Game of Life. - Springer-Verlag London, 2010. - ISBN 978-1-84996-216-2 - doi : 10.1007/978-1-84996-217-9 .
• Paul Rendell. Univerzálnost Turingova stroje ve hře o život. - Springer International Publishing, 2016. - (Emergence, Complexity and Computation; sv. 18). - ISBN 978-3-319-19841-5 , 978-3-319-19842-2. - doi : 10.1007/978-3-319-19842-2 .
• Weatherell C. Etudy pro programátory. - M .: Mir, 1982. - S. 19-22.
• Gardner M. Piškvorky. - M .: Mir, 1988. - S. 287-343. — ISBN 5030012346 .
• Shcheglov G. Šachová evoluce. - Lambert Academic Publishing, 2012. - 88 s. — ISBN 9783848424603 .
• Trofimov M. Life on the Macintosh // Monitor, 1995. - č. 2, s.72; č. 4, str. 72; č. 5, str. 66.
• Časopis Věda a život. č. 8, 1971, str. 130-133.
• Časopis Ve světě vědeckých objevů. č. 5.4(11), 2010, str. 50-53, 139. ISSN 2072-0831 (tištěné), ISSN 2307-9428 (online)
• Příloha časopisu Mladý technik. č. 8. srpna 1989, str. 11-13
• Hayes B. Buněčný automat vytváří model světa a světa kolem něj. // Ve světě vědy , 1984, č. 5, s. 97-104

Odkazy

• ConwayLife.com - Hra o život a příbuzné buněčné automaty, Golly program
• Slovník života
• Klumova I. N. Hra "Život"  // Kvant . - 1974. - č. 9 . - S. 26-30 .
• Martin Gardner . Fantastické kombinace nové solitaire hry Johna Conwaye "life"  // Scientific American . — Sv. 223, č. 4 (říjen 1970) . - S. 120-123. Archivováno z originálu 1. května 2013.

Slovníky a encyklopedie	Britannica (online)