"Élet" játék

Az "Élet" játék ( Eng.  Conway's Game of Life ) egy cellás automata , amelyet John Conway angol matematikus talált fel 1970 -ben .

Szabályok

• A játék cselekvési helye egy cellákba jelölt sík, amely lehet korlátlan, korlátozott vagy zárt.
• Ezen a felületen minden cellát nyolc szomszéd veszi körül, és két állapotú lehet: "élő" (megtelt) vagy "halott" (üres).
• Az élő sejtek eloszlását a játék elején nevezzük első generációnak. Minden következő generáció az előző alapján kerül kiszámításra a következő szabályok szerint:
  • egy üres (halott) cellában, amely három élő sejttel szomszédos, élet születik;
  • ha egy élő sejtnek két vagy három élő szomszédja van, akkor ez a sejt tovább él; ellenkező esetben (ha kevesebb, mint kettő vagy háromnál több élő szomszéd) a sejt elpusztul („a magánytól” vagy „a túlzsúfoltságtól”).
• A játék akkor ér véget
  • egyetlen „élő” sejt sem marad a pályán;
  • a következő lépés konfigurációja pontosan (eltolások és forgatások nélkül) megismétli önmagát a korábbi lépések egyikében (időszakos konfiguráció kerül hozzáadásra)
  • a következő lépésben egyik cella sem változtatja meg állapotát (az előző szabály egy lépéssel visszalép, stabil konfiguráció jön létre)

A játékos nem vesz részt aktívan a játékban . Csak az "élő" cellák kezdeti konfigurációját rendezi vagy generálja, amelyek aztán a szabályoknak megfelelően változnak. A szabályok egyszerűsége ellenére nagyon sokféle forma fordulhat elő a játékban.

Eredet

John Conway érdeklődni kezdett egy probléma iránt, amelyet az 1940 -es években javasolt a neves matematikus , John von Neumann , aki olyan hipotetikus gépet próbált létrehozni, amely képes reprodukálni önmagát. Neumann Jánosnak sikerült egy ilyen gép matematikai modelljét létrehoznia nagyon összetett szabályokkal. Conway megpróbálta leegyszerűsíteni Neumann elképzeléseit, és végül sikerült megalkotnia azokat a szabályokat, amelyek az Életjáték szabályaivá váltak.

Ennek a játéknak a leírása először a Scientific American magazin októberi ( 1970 ) számában jelent meg , "Math Games" címszó alatt, Martin Gardner ( Martin Gardner ) [1] által .

Számítógépes megvalósítás

A játék számítógépes megvalósításaiban a mező korlátozott és általában zárt - a mező felső határa „csatlakozik” az aljához, a bal szegély pedig a jobb oldalhoz, ami a mező felületének emulációja. torus , de a képernyőn a mező mindig egységes rácsként jelenik meg.

A legegyszerűbb „generációváltás” algoritmus szekvenciálisan végignézi a rács összes celláját, mindegyikhez megszámolja a szomszédokat, meghatározva a sejt sorsát az új generációban (nem változik, meghal, megszületik). Egy ilyen algoritmus két kétdimenziós tömböt használ - az aktuális és a következő generációhoz.

Egy gyorsabb algoritmus elvégzi az első lépést az összes cellán, ugyanakkor összeállít egy listát a cellákról, amelyeket a következő generációban meg kell nézni. Azok a sejtek, amelyek nem tudnak alapvetően megváltozni egy generáció alatt, nem szerepelnek a listán. Például, ha egy cella és az összes szomszédja nem változott az új generáció jelenlegi számítása során, akkor ez a cella nem fog megváltozni a következő lépés során.

Ábrák

Röviddel a szabályok közzététele után számos érdekes mintát fedeztek fel (az élő sejtek elrendezésének változatai az első generációban), különösen: r -pentamino és sikló ( sikló ).

Ezen alakok egy része változatlan marad az összes következő generációban, mások állapota időszakosan megismétlődik, egyes esetekben a teljes alak elmozdulásával. Van egy alak ( Diehard ), amely mindössze hét élő sejtből áll, amelyek leszármazottai százharminc generáción át léteznek, majd eltűnnek.

Conway eredetileg azt javasolta, hogy egyetlen kezdeti kombináció sem vezethet korlátlan szaporodáshoz, és 50 dollár bónuszt ajánlott fel annak, aki bebizonyította vagy megcáfolta ezt a hipotézist. A díjat az MIT egy csoportja nyerte el, akik egy fix, ismétlődő figurát találtak ki, amely időről időre mozgó "vitorlázókat" hozott létre. Így az élő sejtek száma korlátlanul növekedhet. Ezután mozgó figurákat találtak, amelyek más figurák "szemétét" hagyták maguk után.

Mára többé-kevésbé az alábbi ábrák osztályozása fejlődött ki:

• Stabil adatok : változatlan adatok
• Százévesek : stabilizálódás előtt hosszú ideig változó alakok [2] ;
• Periodikus számadatok : olyan számok, amelyekben az állapot bizonyos számú, 1-nél nagyobb generáció után ismétlődik;
• Mozgó figurák : alakok, amelyekben az állapot ismétlődik, de némi elmozdulással;
• Fegyverek : ismétlődő állapotú alakzatok, ezenkívül mozgó alakzatok létrehozása ;
• Gőzmozdonyok : mozgó alakzatok ismétlődő állapotokkal, amelyek más alakzatokat hagynak maguk után nyomként;
• Felfalók : rugalmas darabok, amelyek megsemmisítésükkel túlélik az ütközést néhány mozgó darabbal;
• Reflektorok : stabil vagy periodikus alakok, amelyek képesek megváltoztatni irányukat , amikor mozgó alakok ütköznek velük ;
• Szorzók : olyan konfigurációk, amelyekben az élő sejtek száma a lépések számának négyzetével nő;
• Olyan alakzatok, amelyek megkettőződnek egyes alakzatokkal való ütközéskor.

Édenkert

Az Édenkert (Garden of Eden) olyan sejtek elrendezése, amelynek nem lehet előző generációja. Szinte minden olyan játéknál, amelyben az előző lépésben több szomszéd határozza meg a sejtek állapotát, be lehet bizonyítani az Édenkertek létezését, de sokkal nehezebb egy konkrét figurát megszerkeszteni.

"Számok"

A legegyszerűbb, 3 x 5 cellás "betűtípus" használatával, amelyet nyilvánvalóan Eric Angelini javasolt 2007-ben, sok formát kaphat. Például az ezzel a betűtípussal írt 90-es szám egy siklót generál [3] .

Hatás a tudományok fejlődésére

Bár a játék csak két egyszerű szabályból áll, már több mint negyven éve felkelti a tudósok figyelmét. Az "Élet" játék és módosításai hatással voltak (bizonyos esetekben kölcsönösen) az olyan egzakt tudományok számos területére, mint a matematika , a számítástechnika és a fizika [4] . Ezek különösen:

• automata elmélet ,
• Algoritmusok elmélete ,
• Játékelmélet és matematikai programozás ,
• Algebra és számelmélet ,
• Valószínűségszámítás és matematikai statisztika ,
• Kombinatorika és gráfelmélet ,
• fraktál geometria ,
• Számítógépes matematika ,
• Döntéselmélet ,
• Matematikai modellezés .

Ezen túlmenően, a játékban fellelhető számos mintának megvannak a hasonlóságai más, néha teljesen „nem matematikai” tudományágakban. Íme egy lista azon tudományokról, amelyek elméletei érdekes érintkezési pontokkal rendelkeznek az „élet” jelenségeivel:

• Kibernetika . Maga a játék Conway sikeres kísérlete arra, hogy bebizonyítsa az egyszerű önreprodukáló rendszerek létezését, valamint valamiféle „intelligencia” megjelenését az önreprodukáló rendszerekben.
• Biológia . Lenyűgöző a külső hasonlóság a primitív organizmusok populációinak fejlődésével.
• Bakteriológia . A játék néhány érdekes változata további feltételekkel pontosan megismételheti a baktériumok szaporodását, amelyek véletlenszerű valószínűséggel (a módosítási feltételnek megfelelően) mutálódhatnak.
• Élettan . A sejtek születése és halála hasonló a neuronimpulzusok megjelenésének és eltűnésének folyamatához.
• Csillagászat . Néhány összetett kolónia fejlődése meglepően sematikusan megismétli a spirálgalaxisok fejlődési szakaszait [5] [6] .
• Szilárdtestfizika . Az automaták elméletét általában és az "Élet" játékot különösen az "átviteli jelenségek" - diffúzió , viszkozitás és hővezető képesség - elemzésére használják .
• Kvantumfizika . Az "élet" sejtek viselkedése (újak születése és kölcsönös megsemmisülése) sok tekintetben emlékeztet az elemi részecskék ütközésekor fellépő folyamatokra .
• Nanomechanika . Az álló és pulzáló kolóniák szemléltető példái a nanotechnológia alapján létrehozott legegyszerűbb eszközöknek.
• Elektrotechnika . A játékszabályok az öngyógyító elektromos áramkörök modellezésére szolgálnak .
• Kémia . A játékban beépített konfigurációk a felszínen zajló kémiai reakciók során jönnek létre; különösen M. S. Shakaeva kísérleteiben mozgó molekuláris struktúrák keletkeznek, hasonlóan az "élet" siklóhoz. Többdimenziós sejtautomaták segítségével próbálják megmagyarázni a periodikus kémiai reakciókat is. Az elemi részecskék önszerveződésével a szupramolekuláris kémia is foglalkozik .

Talán ez a játék kapcsolódik más tudományos jelenségekhez, beleértve azokat is, amelyek a modern tudomány számára még ismeretlenek. Az is lehet, hogy a természet és a társadalom jelenleg feltáratlan törvényei az "Élet"-nek és annak módosulásainak köszönhetően érthetőbbé válnak.

Tények

• A játékszabályok olyanok, hogy semmilyen interakciót nem lehet gyorsabban továbbítani, mint a sakkkirály lépését . Sebességét - egy cella bármely irányban - gyakran " fénysebességnek " nevezik .
• A "sikló" figurát 2003-ban javasolták a hackerek emblémájának .
• A „ Game of Life ” első orosz nyelvű említése 1971-re vonatkozik, és a Science and Life magazin fordításában „Evolution” néven ismert .
• Ha beírja a „ conway's game of life ” kifejezést a Google keresősávjába , akkor a szokásos lekérdezés eredménye mellett ennek a játéknak a hasonlósága is megjelenik háttéranimációként [7] [8] .

Módosítások

• A "Life" / "Evolution" játéknak vannak módosításai a következők szerint:
  • méretek  - síkon, térfogatban;
  • színesség - monokróm, fekete-fehér (sakktábla), színes;
  • az algoritmus iránya - közvetlen, fordított;
  • evolúciós állandók – klasszikus (B3/S23), módosított;
  • a játéktér mérete - korlátozott, korlátlan, félig korlátozott;
  • terepi tevékenység - aktív, passzív;
  • a játékosok száma - nulla játék, egy, kettő;
  • játéktevékenységek - passzív, aktív;
  • mezőgeometriák — téglalap, hatszögletű.

• Érdekes Conway inverz problémája – egy adott ábra elődjének keresése [9] . Megoldásához a statisztika apparátusát lehet bevonni: a Monte Carlo-módszert , a szimulációs modellezést , valamint a heurisztikus módszerek teljes arzenálját .
• A színes játék hatékony algoritmusa az eredeti kép monoton képre bontása, majd a klasszikus életszabályok alkalmazása után ezek egymásra épülése; térfogati változatokhoz - ortogonális transzformációs algoritmus. Ennek gyakorlati alkalmazására példa mindenféle képernyővédő, absztrakt képek, műalkotások tervezése.
• A sakk, fekete-fehér változatban két játékos vesz részt, a születési színt a generatív triász színének túlsúlya határozza meg, a mozdulatok rögzítése a sakkjelölés szabályai szerint történik. Az eredeti határképződmények mellett itt is színütközések figyelhetők meg, például a „sikló” a jelölésben: fehér a2b2c2, fekete c3b4 - teljesen elszíneződik az átalakulási ciklus során, és ugyanez: fehér a2b2, fekete c2c3 b4 - demonstrálja a „sikló” kromatikus ciklikussága a geometriai ciklusán belül.
• Egy aktív sakkjátszmában a játékosoknak lehetőségük van egyetlen bevezetéssel befolyásolni az „Élet/Evolúció” eseményeit – korlátozott számú zseton eltávolításával a saját színükből, hogy kiterjesszék, stabilizálják a történelem menetét és ellensúlyozzák az ellenfelet. ez. Az elméleti alapok itt a döntéshozatali módszerek , a játékelmélet apparátusa .
• A játék 3D -s megvalósításában minden cella 26 másik cellával határos, 4-5 szomszéddal túlél, és 5 szomszéddal születik egy új, és vannak 3D-s stabil struktúrák is, amelyek egy része a 2D-hez hasonlít. [tíz]

Jegyzetek

1. ↑ Martin Gardner . John Conway új „élet” pasziánszjátékának fantasztikus kombinációi  // Scientific American . - 4. szám (1970. október) .
2. ↑ Életszótár: Hosszú élet . Letöltve: 2015. szeptember 21. Az eredetiből archiválva : 2017. szeptember 22.. (határozatlan)
3. ↑ Számjegyek az életben . www.radicaleye.com. Letöltve: 2017. július 15. Az eredetiből archiválva : 2017. augusztus 8.. (határozatlan)
4. ↑ Toffoli T., Margolus N. Sejtautomaták gépei. — M.: Mir, 1991. — ISBN 5-03-001619-8
5. ↑ M. W. Mueller, W. D. Arnett. A csillagképződés és a szabálytalan szerkezet terjedése spirálgalaxisokban  //  The Astrophysical Journal. - 1976-12-01. — Vol. 210 . — P. 670–678 . — ISSN 0004-637X . - doi : 10.1086/154873 .
6. ↑ H. Gerola, P. E. Seiden. Sztochasztikus csillagkeletkezés és galaxisok spirális szerkezete  (angol)  // The Astrophysical Journal. - 1978-07-01. — Vol. 223 . — P. 129–135 . — ISSN 0004-637X . - doi : 10.1086/156243 .
7. ↑ Jon Mitchell. Hogyan épített egy Google mérnök univerzumot egy húsvéti tojásba (2012. október 5.). Letöltve: 2016. január 31. Az eredetiből archiválva : 2016. október 16.. (határozatlan)
8. ↑ Siobhan Roberts. Prológus // Genius At Play: The Curious Mind of John Horton Conway . — Bloomsbury Publishing USA, 2015. — P. XV. - 480 p. - ISBN 1-620-40594-6 , 978-1-620-40594-9.
9. ↑ Journal of Science and Life . 8. szám, 1972, 141-144.
10. ↑ Archivált másolat . Letöltve: 2021. augusztus 24. Az eredetiből archiválva : 2021. július 18. (határozatlan)

Irodalom

• Adamatzky András. Game of Life Cellular Automata. - Springer-Verlag London, 2010. - ISBN 978-1-84996-216-2 - doi : 10.1007/978-1-84996-217-9 .
• Paul Rendell. Az életjáték Turing-gépe univerzalitása. - Springer International Publishing, 2016. - (Emergence, Complexity and Computation; 18. kötet). - ISBN 978-3-319-19841-5 , 978-3-319-19842-2. - doi : 10.1007/978-3-319-19842-2 .
• Weatherell C. Etűdök programozóknak. - M . : Mir, 1982. - S. 19-22.
• Gardner M. Tic-tac-toe. - M .: Mir, 1988. - S. 287-343. — ISBN 5030012346 .
• Shcheglov G. Sakk evolúció. - Lambert Akadémiai Kiadó, 2012. - 88 p. — ISBN 9783848424603 .
• Trofimov M. Élet a Macintosh-on // Monitor, 1995. - 2. sz., 72. o.; 4. szám, 72. o.; 5. szám, 66. o.
• Tudomány és Élet folyóirat . 8. szám, 1971, p. 130-133.
• Folyóirat A tudományos felfedezések világában. No. 5.4(11), 2010, p. 50-53, 139. ISSN 2072-0831 (nyomtatott), ISSN 2307-9428 (online)
• A Fiatal Technikus című folyóirat melléklete . 1989. augusztus 8. szám, p. 11-13
• Hayes B. A cellás automata modellt hoz létre a világról és a körülötte lévő világról. // A tudomány világában , 1984, 5. sz., 97-104.

Linkek

• ConwayLife.com – Game of Life és a kapcsolódó cellás automaták, Golly szoftver
• Életszótár
• Klumova I. N. Játék "Élet"  // Kvant . - 1974. - 9. sz . - S. 26-30 .
• Martin Gardner . John Conway új „élet” pasziánszjátékának fantasztikus kombinációi  // Scientific American . — Vol. 223, 4. szám (1970. október) . - P. 120-123. Az eredetiből archiválva : 2013. május 1.

Szótárak és enciklopédiák	Britannica (online)