Spil "Livet"

Spillet "Life" ( Eng.  Conway's Game of Life ) er en cellulær automat opfundet af den engelske matematiker John Conway i 1970 .

Regler

• Spillets handlingssted er et fly markeret i celler, som kan være ubegrænset, begrænset eller lukket.
• Hver celle på denne overflade har otte naboer , der omgiver den og kan være i to tilstande: at være "levende" (fyldt) eller "død" (tom).
• Fordelingen af ​​levende celler i begyndelsen af ​​spillet kaldes den første generation. Hver næste generation beregnes ud fra den forrige efter følgende regler:
  • i en tom (død) celle, som støder op til tre levende celler, fødes liv;
  • hvis en levende celle har to eller tre levende naboer, så fortsætter denne celle med at leve; ellers (hvis der er færre end to eller flere end tre levende naboer), dør cellen ("af ensomhed" eller "af overfyldning").
• Spillet slutter hvis
  • ikke en eneste "levende" celle vil forblive på banen;
  • konfigurationen på det næste trin vil nøjagtigt (uden skift og rotationer) gentage sig selv på et af de tidligere trin (en periodisk konfiguration tilføjes)
  • ved næste trin ændrer ingen af ​​cellerne sin tilstand (den forrige regel gælder et skridt tilbage, en stabil konfiguration dannes)

Spilleren deltager ikke aktivt i spillet . Den arrangerer eller genererer kun den indledende konfiguration af "levende" celler, som derefter ændres i henhold til reglerne. På trods af reglernes enkelhed kan der forekomme et stort udvalg af former i spillet.

Oprindelse

John Conway blev interesseret i et problem foreslået i 1940'erne af den berømte matematiker John von Neumann , som forsøgte at skabe en hypotetisk maskine, der kunne reproducere sig selv. John von Neumann formåede at skabe en matematisk model af en sådan maskine med meget komplekse regler. Conway forsøgte at forenkle Neumanns ideer og til sidst lykkedes det at skabe de regler, der blev reglerne for Livets Spil.

Beskrivelsen af ​​dette spil blev først offentliggjort i oktober ( 1970 ) udgaven af ​​Scientific American magazine , under overskriften "Math Games" af Martin Gardner ( Martin Gardner ) [1] .

Computerimplementering

I computerimplementeringer af spillet er feltet begrænset og som regel lukket - den øvre kant af feltet er "forbundet" til bunden, og den venstre kant til højre, som er en emulering af overfladen af ​​en torus , men på skærmen vises feltet altid som et ensartet gitter.

Den enkleste "generationsændring"-algoritme ser sekventielt gennem alle cellerne i gitteret, tæller naboer for hver og bestemmer cellens skæbne i den nye generation (vil ikke ændre sig, vil dø, blive født). En sådan algoritme bruger to todimensionelle arrays - for den nuværende og for den næste generation.

En hurtigere algoritme laver den første passage gennem alle cellerne, men opbygger samtidig en liste over celler, der skal ses på i næste generation. Celler, der ikke grundlæggende kan ændre sig i en generation, er ikke inkluderet på listen. For eksempel, hvis en celle og alle dens naboer ikke har ændret sig under den aktuelle beregning af den nye generation, så ændres denne celle ikke i løbet af næste gang.

Figurer

Kort efter offentliggørelsen af ​​reglerne blev flere interessante mønstre opdaget (varianter af arrangementet af levende celler i den første generation), især: r -pentamino og svævefly ( svævefly ).

Nogle af disse tal forbliver uændrede i alle efterfølgende generationer, andres tilstand gentages periodisk, i nogle tilfælde med en forskydning af hele figuren. Der er en figur ( Diehard ) på kun syv levende celler, hvis efterkommere eksisterer i hundrede og tredive generationer og derefter forsvinder.

Conway foreslog oprindeligt, at ingen indledende kombination kunne føre til ubegrænset reproduktion og tilbød en bonus på $50 til den, der beviste eller modbeviste denne hypotese. Prisen blev vundet af en gruppe på MIT , som kom op med en fast, gentagende figur, der med jævne mellemrum skabte bevægelige "svævefly". Således kunne antallet af levende celler vokse i det uendelige. Derefter blev der fundet bevægelige figurer, der efterlod "skrald" fra andre figurer.

Til dato er følgende klassificering af figurer mere eller mindre udviklet:

• Stabile tal : tal, der forbliver uændrede
• Centenarians : tal, der ændrer sig i lang tid, før de stabiliseres [2] ;
• Periodiske tal : tal, hvor tilstanden gentages efter et vist antal generationer større end 1;
• Bevægende figurer : figurer, hvor tilstanden gentages, men med en vis forskydning;
• Kanoner : former med gentagne tilstande, der desuden skaber bevægelige former ;
• Damplokomotiver : bevægelige former med gentagne tilstande, der efterlader andre former som spor;
• Devourers : elastiske brikker, der kan overleve kollisioner med nogle bevægelige brikker ved at ødelægge dem;
• Reflekser : stabile eller periodiske figurer, der er i stand til at ændre deres retning , når bevægelige figurer kolliderer med dem ;
• Multiplikatorer : konfigurationer, hvor antallet af levende celler vokser som kvadratet af antallet af trin;
• Former, der duplikeres, når de kolliderer med nogle former.

Edens Have

Edens Have (Edens Have) er et arrangement af celler, der ikke kan have en tidligere generation. For næsten ethvert spil, hvor cellernes tilstand bestemmes af flere naboer i det foregående trin, er det muligt at bevise eksistensen af ​​Edens haver, men det er meget sværere at konstruere en specifik figur.

"Number"

Ved at bruge den enkleste "skrifttype" på 3 gange 5 celler, som tilsyneladende blev foreslået af Eric Angelini i 2007, kan du få en masse former. For eksempel genererer tallet 90 skrevet i denne skrifttype et svævefly [3] .

Indflydelse på udviklingen af ​​videnskaber

Selvom spillet kun består af to enkle regler, har det tiltrukket sig videnskabsmænds opmærksomhed i mere end fyrre år. Spillet "Life" og dets modifikationer påvirkede (i nogle tilfælde gensidigt) mange dele af sådanne eksakte videnskaber som matematik , datalogi og fysik [4] . Disse er især:

• automatteori ,
• Teori om algoritmer ,
• Spilteori og matematisk programmering ,
• Algebra og talteori ,
• Sandsynlighedsteori og matematisk statistik ,
• kombinatorik og grafteori ,
• fraktal geometri ,
• Beregningsmatematik ,
• Beslutningsteori ,
• Matematisk modellering .

Derudover har mange mønstre fundet i spillet deres analogier i andre, nogle gange helt "ikke-matematiske" discipliner. Her er en liste over videnskaber, hvis teorier har interessante berøringspunkter med fænomenerne "Livet":

• Kybernetik . Selve spillet er Conways succesfulde forsøg på at bevise eksistensen af ​​simple selvreproducerende systemer, samt fremkomsten af ​​en form for "intelligens" i selvreproducerende systemer.
• Biologi . Den ydre lighed med udviklingen af ​​populationer af primitive organismer er imponerende.
• Bakteriologi . Nogle interessante variationer af spillet med yderligere betingelser kan nøjagtigt gentage reproduktionen af ​​bakterier, som kan mutere med en tilfældig sandsynlighed (i henhold til modifikationsbetingelsen).
• Fysiologi . Fødsel og død af celler ligner processen med fremkomst og forsvinden af ​​neuronimpulser.
• Astronomi . Udviklingen af ​​nogle komplekse kolonier gentager overraskende skematisk udviklingsstadierne for spiralgalakser [5] [6] .
• Faststoffysik . Teorien om automater generelt og spillet "Life" i særdeleshed bruges til at analysere "overførselsfænomener" - diffusion , viskositet og termisk ledningsevne .
• Kvantefysik . Opførselen af ​​"livs" celler (fødslen af ​​nye og gensidig udslettelse) minder på mange måder om de processer, der opstår under kollisionen af ​​elementarpartikler .
• Nanomekanik . Stationære og pulserende kolonier er et illustrativt eksempel på de enkleste enheder skabt på basis af nanoteknologi.
• Elektroteknik . Spillets regler bruges til at modellere selvhelbredende elektriske kredsløb .
• Kemi . Konfigurationer som dem, der er bygget i spillet, skabes under kemiske reaktioner på overfladen; især i M. S. Shakaevas eksperimenter opstår bevægelige molekylære strukturer, der ligner et "livs"-svævefly. Der gøres også forsøg på at forklare periodiske kemiske reaktioner ved hjælp af multidimensionelle cellulære automater. Selvorganiseringen af ​​elementarpartikler behandles også af supramolekylær kemi .

Måske er dette spil forbundet med andre videnskabelige fænomener, inklusive dem, der stadig er ukendte for moderne videnskab. Det er også muligt, at de i øjeblikket uopdagede natur- og samfundslove vil blive mere forståelige takket være "Livet" og dets modifikationer.

Fakta

• Spillets regler er sådan, at ingen interaktion kan overføres hurtigere end skakkongens træk . Dens hastighed - en celle i enhver retning - omtales ofte som " lysets hastighed ".
• "Svævefly"-figuren blev foreslået i 2003 som emblem for hackerne .
• Den første russisksprogede omtale af " Game of Life " refererer til 1971 og er kendt som "Evolution" i oversættelsen af ​​Science and Life magazine .
• Hvis du indtaster " conway's game of life " i Googles søgelinje , så vil en lighed med dette spil blive vist som en baggrundsanimation ud over standardforespørgselsresultatet [7] [8] .

Ændringer

• Der er modifikationer af spillet "Life" / "Evolution" i henhold til:
  • dimensioner  - på flyet, i volumen;
  • kromaticitet - monokrom, sort og hvid (skaktern), fuld farve;
  • algoritmens retning - direkte, omvendt;
  • udviklingskonstanter — klassisk (B3/S23), modificeret;
  • størrelsen af ​​spillefeltet - begrænset, ubegrænset, semi-begrænset;
  • feltaktivitet - aktiv, passiv;
  • antallet af spillere - nul-spil, en, to;
  • spilaktiviteter - passiv, aktiv;
  • feltgeometrier - rektangulær, sekskantet.

• Af interesse er Conways omvendte problem - søgen efter en forgænger til en given figur [9] . For at løse det kan statistikapparatet inddrages: Monte Carlo-metoden , simuleringsmodellering samt hele arsenalet af heuristiske metoder .
• En effektiv algoritme til et fuldfarvespil er nedbrydningen af ​​det originale billede til monotone, efterfulgt af deres superposition efter at have anvendt de klassiske leveregler på dem; for volumetriske varianter - ortogonal transformationsalgoritme. Eksempler på den praktiske anvendelse af dette er alle slags pauseskærme, abstrakte billeder og design af kunstværker.
• I skak, sort og hvid version deltager to spillere, fødselsfarven bestemmes af overvægten af ​​farve i den generative treklang, registreringen af ​​træk udføres i henhold til reglerne for skaknotation. Ud over de oprindelige grænseformationer observeres farvekollisioner her, for eksempel "glideren" i notationen: hvid a2b2c2, sort c3b4 - misfarves fuldstændigt under transformationscyklussen, og det samme: hvid a2b2, sort c2c3 b4 - demonstrerer den kromatiske cyklicitet af "svæveflyet" inden for dens geometriske cyklus.
• I et aktivt skakspil har spillerne mulighed for at påvirke begivenhederne i "Life/Evolution" ved en enkelt introduktion - ved at fjerne et begrænset antal jetoner af deres farve for at udvide, stabilisere historiens gang og modvirke modstanderen i dette. Det teoretiske grundlag her er beslutningstagningsmetoder , spilteoriens apparat .
• I 3D -implementeringen af ​​spillet grænser hver celle op til 26 andre celler, overlever med 4-5 naboer, og en ny er født med 5 naboer, og der er også 3D-stabile strukturer, hvoraf nogle ligner 2D. [ti]

Noter

1. ↑ Martin Gardner . De fantastiske kombinationer af John Conways nye kabale "life"  // Scientific American . - nr. 4 (oktober 1970) .
2. ↑ Livsordbog: Lang levetid . Hentet 21. september 2015. Arkiveret fra originalen 22. september 2017. (ubestemt)
3. ↑ Cifre i livet . www.radicaleye.com. Hentet 15. juli 2017. Arkiveret fra originalen 8. august 2017. (ubestemt)
4. ↑ Toffoli T., Margolus N. Machines of cellular automata. — M.: Mir, 1991. — ISBN 5-03-001619-8
5. ↑ M.W. Mueller, W.D. Arnett. Udbredelse af stjernedannelse og uregelmæssig struktur i spiralgalakser  //  The Astrophysical Journal. - 1976-12-01. — Bd. 210 . — S. 670–678 . — ISSN 0004-637X . - doi : 10.1086/154873 .
6. ↑ H. Gerola, P. E. Seiden. Stokastisk stjernedannelse og galaksers spiralstruktur  (engelsk)  // The Astrophysical Journal. - 1978-07-01. — Bd. 223 . — S. 129–135 . — ISSN 0004-637X . - doi : 10.1086/156243 .
7. ↑ Jon Mitchell. Hvordan en Google-ingeniør byggede et univers i et påskeæg (5. oktober 2012). Hentet 31. januar 2016. Arkiveret fra originalen 16. oktober 2016. (ubestemt)
8. ↑ Siobhan Roberts. Prolog // Genius At Play: The Curious Mind of John Horton Conway . — Bloomsbury Publishing USA, 2015. — P. XV. - 480 sider. - ISBN 1-620-40594-6 , 978-1-620-40594-9.
9. ↑ Journal of Science and Life . nr. 8, 1972, s. 141-144.
10. ↑ Arkiveret kopi . Hentet 24. august 2021. Arkiveret fra originalen 18. juli 2021. (ubestemt)

Litteratur

• Andrew Adamatzky. 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. Turing Machine Universality of the Game of Life. - Springer International Publishing, 2016. - (Emergence, Complexity and Computation; vol. 18). - ISBN 978-3-319-19841-5 , 978-3-319-19842-2. - doi : 10.1007/978-3-319-19842-2 .
• Weatherell C. Etuder for programmører. - M . : Mir, 1982. - S. 19-22.
• Gardner M. Tic-tac-toe. - M .: Mir, 1988. - S. 287-343. — ISBN 5030012346 .
• Shcheglov G. Skak Evolution. - Lambert Academic Publishing, 2012. - 88 s. — ISBN 9783848424603 .
• Trofimov M. Life on the Macintosh // Monitor, 1995. - Nr. 2, s.72; nr. 4, side 72; nr. 5, s.66.
• Journal Science and Life. nr. 8, 1971, s. 130-133.
• Journal I videnskabelige opdagelsers verden. nr. 5.4(11), 2010, s. 50-53, 139. ISSN 2072-0831 (print), ISSN 2307-9428 (online)
• Tillæg til bladet Young Technician. nr. 8. august 1989, s. 11-13
• Hayes B. Cellular automaton skaber en model af verden og verden omkring den. // In the world of science , 1984, nr. 5, s. 97-104

Links

• ConwayLife.com - Game of Life og relaterede cellulære automater, Golly-program
• Livsordbog
• Klumova I. N. Game "Life"  // Kvant . - 1974. - Nr. 9 . - S. 26-30 .
• Martin Gardner . De fantastiske kombinationer af John Conways nye kabale "life"  // Scientific American . — Bd. 223, nr. 4 (oktober 1970) . - S. 120-123. Arkiveret fra originalen den 1. maj 2013.

Ordbøger og encyklopædier	Britannica (online)