Peli "Elämä"

Peli "Life" ( Eng.  Conway's Game of Life ) on soluautomaatti , jonka englantilainen matemaatikko John Conway keksi vuonna 1970 .

Säännöt

• Pelin toimintapaikka on soluihin merkitty taso, joka voi olla rajoittamaton, rajoitettu tai suljettu.
• Jokaisella tämän pinnan solulla on kahdeksan naapuria ympärillä, ja se voi olla kahdessa tilassa: olla "elossa" (täytetty) tai "kuollut" (tyhjä).
• Elävien solujen jakautumista pelin alussa kutsutaan ensimmäiseksi sukupolveksi. Jokainen seuraava sukupolvi lasketaan edellisen sukupolven perusteella seuraavien sääntöjen mukaisesti:
  • tyhjässä (kuolleessa) solussa, joka on kolmen elävän solun vieressä, syntyy elämä;
  • jos elävällä solulla on kaksi tai kolme elävää naapuria, tämä solu jatkaa elämäänsä; muuten (jos naapureita on vähemmän kuin kaksi tai enemmän kuin kolme), solu kuolee ("yksinäisyydestä" tai "ylikansoituksesta").
• Peli päättyy jos
  • yksikään "elävä" solu ei jää kentälle;
  • seuraavan vaiheen konfiguraatio toistaa täsmälleen (ilman siirtoja ja kiertoja) jossakin aikaisemmista vaiheista (lisätään säännöllinen konfiguraatio)
  • seuraavassa vaiheessa mikään soluista ei muuta tilaansa (edellinen sääntö koskee askelta taaksepäin, muodostuu vakaa konfiguraatio)

Pelaaja ei osallistu aktiivisesti peliin . Se vain järjestää tai luo "elävien" solujen alkuperäisen konfiguraation, joka sitten muuttuu sääntöjen mukaan. Sääntöjen yksinkertaisuudesta huolimatta pelissä voi esiintyä valtavasti erilaisia ​​muotoja.

Alkuperä

John Conway kiinnostui ongelmasta, jonka 1940-luvulla ehdotti kuuluisa matemaatikko John von Neumann , joka yritti luoda hypoteettisen koneen, joka voisi toistaa itsensä. John von Neumann onnistui luomaan matemaattisen mallin tällaisesta koneesta hyvin monimutkaisilla säännöillä. Conway yritti yksinkertaistaa Neumannin ajatuksia ja onnistui lopulta luomaan säännöt, joista tuli pelin pelisäännöt.

Tämän pelin kuvaus julkaistiin ensimmäisen kerran Scientific American -lehden lokakuun ( 1970 ) numerossa otsikon "Math Games" alla, kirjoittaja Martin Gardner ( Martin Gardner ) [1] .

Tietokonetoteutus

Pelin tietokonetoteutuksissa kenttä on rajoitettu ja pääsääntöisesti suljettu - kentän yläreuna on "yhdistetty" pohjaan ja vasen reuna oikealle, mikä on emulointi pelin pinnasta. torus , mutta ruudulla kenttä näkyy aina yhtenäisenä ruudukona.

Yksinkertaisin "sukupolvenvaihdos"-algoritmi tarkastelee peräkkäin kaikki hilan solut, laskee naapurit jokaiselle ja määrittää solun kohtalon uudessa sukupolvessa (ei muutu, kuolee, syntyy). Tällainen algoritmi käyttää kahta kaksiulotteista taulukkoa - nykyiselle ja seuraavalle sukupolvelle.

Nopeampi algoritmi suorittaa ensimmäisen kierroksen kaikkien solujen läpi, mutta samalla muodostaa luettelon soluista, joita tarkastellaan seuraavassa sukupolvessa. Solut, jotka eivät voi olennaisesti muuttua sukupolven aikana, eivät sisälly luetteloon. Esimerkiksi jos mikään solu ja kaikki sen naapurit eivät ole muuttuneet nykyisen uuden sukupolven laskennan aikana, tämä solu ei muutu seuraavan läpimenon aikana.

Luvut

Pian sääntöjen julkaisemisen jälkeen löydettiin useita mielenkiintoisia malleja (elävien solujen järjestelyn muunnelmia ensimmäisessä sukupolvessa), erityisesti: r -pentamino ja purjelentokone ( glider ).

Jotkut näistä luvuista pysyvät muuttumattomina kaikissa seuraavissa sukupolvissa, toisten tila toistuu ajoittain, joissakin tapauksissa koko hahmon siirtymällä. On olemassa luku ( Diehard ), joka koostuu vain seitsemästä elävästä solusta, joiden jälkeläiset ovat olemassa satakolmekymmentä sukupolvea ja sitten katoavat.

Conway ehdotti alun perin, että mikään alkuperäinen yhdistelmä ei voisi johtaa rajoittamattomaan lisääntymiseen, ja tarjosi 50 dollarin bonuksen jokaiselle, joka todistaa tai kumosi tämän hypoteesin. Palkinnon voitti MIT :n ryhmä, joka keksi kiinteän, toistuvan hahmon, joka loi ajoittain liikkuvia "liitolaitteita". Siten elävien solujen määrä voi kasvaa loputtomasti. Sitten löydettiin liikkuvia hahmoja, jotka jättivät jälkeensä "roskaa" muista hahmoista.

Tähän mennessä seuraava lukuluokitus on enemmän tai vähemmän kehittynyt:

• Vakaat luvut : luvut, jotka pysyvät ennallaan
• Satavuotiaat : luvut, jotka muuttuvat pitkään ennen kuin vakiintuvat [2] ;
• Jaksolliset luvut : luvut, joissa tila toistuu tietyn sukupolvien lukumäärän jälkeen, joka on suurempi kuin 1;
• Liikkuvat hahmot : hahmot, joissa tila toistetaan, mutta tietyllä siirtymällä;
• Aseet : muodot, joissa on toistuvia tiloja, jotka luovat lisäksi liikkuvia muotoja ;
• Höyryveturit : liikkuvat muodot toistuvilla tiloilla, jotka jättävät jäljelle muita muotoja;
• Devourers : joustavia kappaleita, jotka selviävät törmäyksistä joidenkin liikkuvien kappaleiden kanssa tuhoamalla ne;
• Heijastimet : vakaat tai jaksolliset hahmot, jotka voivat muuttaa suuntaaan , kun liikkuvat hahmot törmäävät niihin ;
• Kertoimet : kokoonpanot, joissa elävien solujen lukumäärä kasvaa askelmäärän neliönä;
• Muodot, jotka toistuvat törmääessään joihinkin muotoihin.

Garden of Eden

Eedenin puutarha (Garden of Eden) on solujen järjestely, jolla ei voi olla aiempaa sukupolvea. Lähes kaikissa peleissä, joissa solujen tilan määräävät useat naapurit edellisessä vaiheessa, on mahdollista todistaa Gardens of Edenin olemassaolo, mutta tietyn hahmon rakentaminen on paljon vaikeampaa.

"Numerot"

Käyttämällä yksinkertaisinta "fonttia" 3 x 5 solua, jota ilmeisesti ehdotti Eric Angelini vuonna 2007, voit saada paljon muotoja. Esimerkiksi tällä kirjasimella kirjoitettu numero 90 luo luiston [3] .

Vaikutus tieteiden kehitykseen

Vaikka peli koostuu vain kahdesta yksinkertaisesta säännöstä, se on herättänyt tutkijoiden huomion yli neljänkymmenen vuoden ajan. Peli "Life" ja sen muunnelmat vaikuttivat (joissakin tapauksissa vastavuoroisesti) moniin tällaisten eksaktien tieteiden osiin, kuten matematiikka , tietojenkäsittelytiede ja fysiikka [4] . Näitä ovat erityisesti:

• automaatti teoria ,
• Algoritmien teoria ,
• Peliteoria ja matemaattinen ohjelmointi ,
• Algebra ja lukuteoria ,
• Todennäköisyysteoria ja matemaattiset tilastot ,
• Kombinatoriikka ja graafiteoria ,
• fraktaaligeometria ,
• Laskennallinen matematiikka ,
• Päätösteoria ,
• Matemaattinen mallinnus .

Lisäksi monilla pelistä löytyvillä kaavoilla on analogiaan muissa, joskus täysin "ei-matemaattisissa" tieteenaloissa. Tässä on luettelo tieteistä, joiden teorioilla on mielenkiintoisia kosketuskohtia "elämän" ilmiöihin:

• Kybernetiikka . Peli itsessään on Conwayn onnistunut yritys todistaa yksinkertaisten itseään toistuvien järjestelmien olemassaolo sekä jonkinlaisen "älyn" ilmaantuminen itseään toistuviin järjestelmiin.
• Biologia . Ulkoinen samankaltaisuus primitiivisten organismien populaatioiden kehityksen kanssa on vaikuttava.
• Bakteriologia . Jotkut pelin mielenkiintoiset muunnelmat lisäehdoilla voivat toistaa tarkasti bakteerien lisääntymisen, jotka voivat mutatoitua satunnaisella todennäköisyydellä (muokkausehdon mukaan).
• Fysiologia . Solujen syntymä ja kuolema ovat samanlaisia ​​​​kuin hermosolujen impulssien synty- ja katoamisprosessi.
• Tähtitiede . Joidenkin monimutkaisten pesäkkeiden evoluutio toistaa yllättävän kaavamaisesti spiraaligalaksien kehitysvaiheita [5] [6] .
• Kiinteän olomuodon fysiikka . Automaattiteoriaa yleensä ja peliä "Life" käytetään erityisesti analysoimaan "siirtoilmiöitä" - diffuusiota , viskositeettia ja lämmönjohtavuutta .
• Kvanttifysiikka . "Elämän" solujen käyttäytyminen (uusien syntyminen ja keskinäinen tuhoutuminen) muistuttaa monin tavoin prosesseja, jotka tapahtuvat alkuainehiukkasten törmäyksen aikana .
• Nanomekaniikka . Kiinteät ja sykkivät pesäkkeet ovat havainnollistava esimerkki yksinkertaisimmista nanoteknologian pohjalta syntyneistä laitteista.
• Sähkötekniikka . Pelin sääntöjä käytetään mallintamaan itseparantuvia sähköpiirejä .
• Kemia . Peliin rakennetut konfiguraatiot syntyvät pinnalla tapahtuvien kemiallisten reaktioiden aikana; erityisesti M. S. Shakaevan kokeissa syntyy liikkuvia molekyylirakenteita, jotka ovat samanlaisia ​​​​kuin "elämän" purjelentokone. Jaksottaisia ​​kemiallisia reaktioita yritetään myös selittää moniulotteisten soluautomaattien avulla. Alkuainehiukkasten itseorganisaatiota käsittelee myös supramolekyylikemia .

Ehkä tämä peli liittyy muihin tieteellisiin ilmiöihin, mukaan lukien niihin, joita nykytiede ei vielä tunne. On myös mahdollista, että tällä hetkellä löytämättömät luonnon ja yhteiskunnan lait tulevat ymmärrettävämmiksi "Elämän" ja sen muunnelmien ansiosta.

Faktat

• Pelin säännöt ovat sellaiset, että mitään vuorovaikutusta ei voida välittää nopeammin kuin shakkikuninkaan liike . Sen nopeutta - yksi solu mihin tahansa suuntaan - kutsutaan usein " valon nopeudeksi ".
• "Liidin" -hahmoa ehdotettiin vuonna 2003 hakkereiden tunnukseksi .
• Ensimmäinen venäjänkielinen maininta " Game of Lifesta " viittaa vuoteen 1971 ja tunnetaan nimellä "Evolution" Science and Life -lehden käännöksessä.
• Jos kirjoitat Googlen hakupalkkiin " conwayn peli elämä " , tavallisen kyselytuloksen lisäksi tämän pelin samankaltaisuus näytetään taustaanimaationa [7] [8] .

Muutokset

• Pelissä "Life" / "Evolution" on muunnelmia seuraavasti:
  • mitat  - tasossa, tilavuudessa;
  • värillisyys - yksivärinen, mustavalkoinen (shakkilauta), täysväri;
  • algoritmin suunta - suora, käänteinen;
  • evoluutiovakiot – klassinen (B3/S23), modifioitu;
  • pelikentän koko - rajoitettu, rajoittamaton, puolirajoitettu;
  • kenttätoiminta - aktiivinen, passiivinen;
  • pelaajien määrä - nollapeli, yksi, kaksi;
  • pelitoiminta - passiivinen, aktiivinen;
  • kenttägeometriat - suorakulmainen, kuusikulmainen.

• Kiinnostava on Conwayn käänteisongelma - tietyn hahmon edeltäjän etsiminen [9] . Sen ratkaisemiseen voidaan käyttää tilastolaitteistoa: Monte Carlo -menetelmää , simulaatiomallinnusta sekä koko heurististen menetelmien arsenaali .
• Tehokas algoritmi täysväripelissä on alkuperäisen kuvan hajottaminen yksivärisiksi , mitä seuraa niiden superpositio sen jälkeen, kun niihin on sovellettu klassisia elämänsääntöjä; tilavuusmuunnoksille - ortogonaalinen muunnosalgoritmi. Esimerkkejä tämän käytännön soveltamisesta ovat kaikenlaiset näytönsäästäjät, abstraktit kuvat ja taideteosten suunnittelu.
• Shakissa, mustavalkoisessa versiossa osallistuu kaksi pelaajaa, syntymäväri määräytyy generatiivisen triadin värin hallitsevuuden mukaan, liikkeiden tallentaminen tapahtuu shakin merkintäsääntöjen mukaisesti. Alkuperäisten rajamuodostelmien lisäksi täällä havaitaan värien törmäyksiä, esimerkiksi merkinnän "liukukone": valkoinen a2b2c2, musta c3b4 - värjääntyy kokonaan muunnossyklin aikana, ja sama: valkoinen a2b2, musta c2c3 b4 - osoittaa "liukukoneen" kromaattinen syklisyys sen geometrisessa syklissä.
• Aktiivisessa shakkipelissä pelaajilla on mahdollisuus vaikuttaa "Life / Evolution" -tapahtumiin yhdellä esittelyllä - poistamalla rajoitettu määrä värillisiä pelimerkkejä laajentaakseen, vakauttaakseen historian kulkua ja vastustaakseen vastustajaa. Tämä. Teoreettinen perusta tässä ovat päätöksentekomenetelmät , peliteorian laitteisto .
• Pelin 3D - toteutuksessa jokainen solu rajoittuu 26 muuhun soluun, selviää 4–5 naapurin kanssa ja uusi syntyy 5 naapurilla, ja on myös 3D-stabiileja rakenteita, joista osa muistuttaa 2D:tä. [kymmenen]

Muistiinpanot

1. ↑ Martin Gardner . John Conwayn uuden pasianssipelin "life" fantastiset yhdistelmät  // Scientific American . - Nro 4 (lokakuu 1970) .
2. ↑ Elämän sanakirja: Pitkäikäisyys . Haettu 21. syyskuuta 2015. Arkistoitu alkuperäisestä 22. syyskuuta 2017. (määrätön)
3. ↑ Numerot elämässä . www.radicaleye.com. Haettu 15. heinäkuuta 2017. Arkistoitu alkuperäisestä 8. elokuuta 2017. (määrätön)
4. ↑ Toffoli T., Margolus N. Soluautomaattien koneet. — M.: Mir, 1991. — ISBN 5-03-001619-8
5. ↑ M.W. Mueller, W.D. Arnett. Tähtien muodostumisen ja epäsäännöllisen rakenteen leviäminen spiraaligalakseissa  //  The Astrophysical Journal. - 12.12.1976. — Voi. 210 . — s. 670–678 . — ISSN 0004-637X . - doi : 10.1086/154873 .
6. ↑ H. Gerola, P. E. Seiden. Stokastinen tähtien muodostuminen ja galaksien spiraalirakenne  (englanniksi)  // The Astrophysical Journal. - 1.7.1978. — Voi. 223 . — s. 129–135 . — ISSN 0004-637X . - doi : 10.1086/156243 .
7. ↑ Jon Mitchell. Kuinka Googlen insinööri rakensi universumin pääsiäismunaan (5. lokakuuta 2012). Haettu 31. tammikuuta 2016. Arkistoitu alkuperäisestä 16. lokakuuta 2016. (määrätön)
8. ↑ Siobhan Roberts. Prologi // 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 . nro 8, 1972, s. 141-144.
10. ↑ Arkistoitu kopio . Haettu 24. elokuuta 2021. Arkistoitu alkuperäisestä 18. heinäkuuta 2021. (määrätön)

Kirjallisuus

• Andrew Adamatzky. Game of Life Cellular Automata. - Springer-Verlag Lontoo, 2010. - ISBN 978-1-84996-216-2 - doi : 10.1007/978-1-84996-217-9 .
• Paul Rendell. Turingin koneen elämänpelin universaalisuus. - Springer International Publishing, 2016. - (Emergence, Complexity and Computation; osa 18). - ISBN 978-3-319-19841-5 , 978-3-319-19842-2. - doi : 10.1007/978-3-319-19842-2 .
• Weatherell C. Etudes ohjelmoijille. - M .: Mir, 1982. - S. 19-22.
• Gardner M. Tic-tac-toe. - M .: Mir, 1988. - S. 287-343. — ISBN 5030012346 .
• Shcheglov G. Shakin evoluutio. - Lambert Academic Publishing, 2012. - 88 s. — ISBN 9783848424603 .
• Trofimov M. Elämä Macintoshissa // Monitori, 1995. - nro 2, s. 72; nro 4, s. 72; nro 5, s. 66.
• Tiede ja elämä -lehti . nro 8, 1971, s. 130-133.
• Lehti Tieteellisten löytöjen maailmassa. nro 5.4(11), 2010, s. 50-53, 139. ISSN 2072-0831 (painettu), ISSN 2307-9428 (verkossa)
• Nuori teknikko -lehden liite . Nro 8. elokuuta 1989, s. 11-13
• Hayes B. Soluautomaatti luo mallin maailmasta ja sitä ympäröivästä maailmasta. // Tieteen maailmassa , 1984, nro 5, s. 97-104

Linkit

• ConwayLife.com - Game of Life ja siihen liittyvät solukkoautomaatit, Golly-ohjelmisto
• Elämän sanakirja
• Klumova I. N. Peli "Elämä"  // Kvant . - 1974. - Nro 9 . - S. 26-30 .
• Martin Gardner . John Conwayn uuden pasianssipelin "life" fantastiset yhdistelmät  // Scientific American . — Voi. 223, nro 4 (lokakuu 1970) . - s. 120-123. Arkistoitu alkuperäisestä 1. toukokuuta 2013.

Sanakirjat ja tietosanakirjat	Britannica (verkossa)