Spelet "Livet"

Spelet "Life" ( Eng.  Conway 's Game of Life ) är en cellulär automat som uppfanns av den engelske matematikern John Conway 1970 .

Regler

• Handlingsplatsen för spelet är ett plan markerat i celler, som kan vara obegränsat, begränsat eller stängt.
• Varje cell på denna yta har åtta grannar som omger den och kan vara i två tillstånd: att vara "levande" (fylld) eller "död" (tom).
• Fördelningen av levande celler i början av spelet kallas den första generationen. Varje nästa generation beräknas utifrån den föregående enligt följande regler:
  • i en tom (död) cell, som ligger i anslutning till tre levande celler, föds liv;
  • om en levande cell har två eller tre levande grannar, så fortsätter denna cell att leva; annars (om det finns färre än två eller fler än tre levande grannar) dör cellen ("från ensamhet" eller "från överbefolkning").
• Spelet slutar om
  • inte en enda "levande" cell kommer att finnas kvar på fältet;
  • konfigurationen vid nästa steg kommer exakt (utan skiftningar och rotationer) att upprepa sig i ett av de tidigare stegen (en periodisk konfiguration läggs till)
  • i nästa steg ändrar ingen av cellerna sitt tillstånd (den tidigare regeln gäller ett steg tillbaka, en stabil konfiguration bildas)

Spelaren deltar inte aktivt i spelet . Den ordnar eller genererar bara den initiala konfigurationen av "live" celler, som sedan ändras enligt reglerna. Trots reglernas enkla kan en stor mängd olika former förekomma i spelet.

Ursprung

John Conway blev intresserad av ett problem som föreslogs på 1940 -talet av den kända matematikern John von Neumann , som försökte skapa en hypotetisk maskin som kunde reproducera sig själv. John von Neumann lyckades skapa en matematisk modell av en sådan maskin med mycket komplexa regler. Conway försökte förenkla Neumanns idéer och lyckades så småningom skapa reglerna som blev reglerna för Livets spel.

Beskrivningen av detta spel publicerades först i oktobernumret ( 1970 ) av tidskriften Scientific American , under rubriken "Math Games" av Martin Gardner ( Martin Gardner ) [1] .

Datorimplementering

I datorimplementationer av spelet är fältet begränsat och som regel stängt - fältets övre kant är "ansluten" till botten och vänsterkanten till höger, vilket är en emulering av ytan på en torus , men på skärmen visas fältet alltid som ett enhetligt rutnät.

Den enklaste algoritmen för "generationsförändring" tittar sekventiellt igenom alla celler i gittret, räknar grannar för var och en, bestämmer cellens öde i den nya generationen (kommer inte att förändras, kommer att dö, födas). En sådan algoritm använder två tvådimensionella arrayer - för den nuvarande och för nästa generation.

En snabbare algoritm gör den första passagen genom alla celler, men bygger samtidigt upp en lista med celler att titta på i nästa generation. Celler som inte kan förändras i grunden under en generation ingår inte i listan. Till exempel, om någon cell och alla dess grannar inte har ändrats under den aktuella beräkningen av den nya generationen, kommer denna cell inte att ändras under nästa pass.

Figurer

Kort efter publiceringen av reglerna upptäcktes flera intressanta mönster (varianter av arrangemanget av levande celler i den första generationen), särskilt: r -pentamino och glider ( glider ).

Vissa av dessa siffror förblir oförändrade i alla efterföljande generationer, andras tillstånd upprepas med jämna mellanrum, i vissa fall med en förskjutning av hela figuren. Det finns en figur ( Diehard ) av endast sju levande celler vars ättlingar existerar i hundra och trettio generationer och sedan försvinner.

Conway föreslog ursprungligen att ingen initial kombination kunde leda till obegränsad reproduktion och erbjöd en bonus på $50 till den som bevisade eller motbevisade denna hypotes. Priset vanns av en grupp vid MIT som kom fram till en fast, upprepande figur som med jämna mellanrum skapade rörliga "glidare". Således kunde antalet levande celler växa i det oändliga. Sedan hittades rörliga figurer som lämnade efter sig "skräp" från andra figurer.

Hittills har följande klassificering av figurer mer eller mindre utvecklats:

• Stabila siffror : siffror som förblir oförändrade
• Hundraåringar : siffror som förändras under lång tid innan de stabiliseras [2] ;
• Periodiska siffror : siffror där tillståndet upprepas efter ett visst antal generationer större än 1;
• Rörliga figurer : figurer där tillståndet upprepas, men med viss förskjutning;
• Vapen : former med upprepade tillstånd, som dessutom skapar rörliga former ;
• Ånglok : rörliga former med upprepade tillstånd som lämnar andra former efter sig som spår;
• Devourers : motståndskraftiga pjäser som kan överleva kollisioner med vissa rörliga pjäser genom att förstöra dem;
• Reflektorer : stabila eller periodiska figurer som kan ändra riktning när rörliga figurer kolliderar med dem ;
• Multiplikatorer : konfigurationer där antalet levande celler växer som kvadraten av antalet steg;
• Former som dupliceras när de kolliderar med vissa former.

Edens trädgård

Edens trädgård (Edens trädgård) är ett arrangemang av celler som inte kan ha en tidigare generation. För nästan alla spel där tillståndet för cellerna bestäms av flera grannar i föregående steg, är det möjligt att bevisa existensen av Edens trädgårdar, men det är mycket svårare att konstruera en specifik figur.

"Siffror"

Genom att använda det enklaste "fonten" med 3 gånger 5 celler, som tydligen föreslagits av Eric Angelini 2007, kan du få många former. Till exempel genererar siffran 90 skrivet i detta teckensnitt ett glider [3] .

Inflytande på vetenskapens utveckling

Även om spelet bara består av två enkla regler, har det uppmärksammats av forskare i mer än fyrtio år. Spelet "Life" och dess modifieringar påverkade (i vissa fall ömsesidigt) många delar av sådana exakta vetenskaper som matematik , datavetenskap och fysik [4] . Dessa är i synnerhet:

• automatteori ,
• Teori om algoritmer ,
• Spelteori och matematisk programmering ,
• Algebra och talteori ,
• Sannolikhetsteori och matematisk statistik ,
• kombinatorik och grafteori ,
• fraktal geometri ,
• Beräkningsmatematik ,
• Beslutsteori ,
• Matematisk modellering .

Dessutom har många mönster som finns i spelet sina analogier i andra, ibland helt "icke matematiska" discipliner. Här är en lista över vetenskaper vars teorier har intressanta beröringspunkter med fenomenet "Livet":

• Cybernetik . Spelet i sig är Conways framgångsrika försök att bevisa existensen av enkla självreproducerande system, samt uppkomsten av någon form av "intelligens" i självreproducerande system.
• Biologi . Den yttre likheten med utvecklingen av populationer av primitiva organismer är imponerande.
• Bakteriologi . Några intressanta varianter av spelet med ytterligare villkor kan exakt upprepa reproduktionen av bakterier, som kan mutera med en slumpmässig sannolikhet (enligt modifieringsvillkoret).
• Fysiologi . Cellernas födelse och död liknar processen för uppkomst och försvinnande av neuronimpulser.
• Astronomi . Utvecklingen av vissa komplexa kolonier upprepar överraskande schematiskt utvecklingsstadierna för spiralgalaxer [5] [6] .
• Fasta tillståndets fysik . Teorin om automater i allmänhet och spelet "Life" i synnerhet används för att analysera "överföringsfenomen" - diffusion , viskositet och värmeledningsförmåga .
• Kvantfysik . Beteendet hos "livs"-celler (födelsen av nya och ömsesidig förintelse) påminner på många sätt om de processer som sker under kollisionen av elementarpartiklar .
• Nanomekanik . Stationära och pulserande kolonier är ett illustrativt exempel på de enklaste enheterna som skapats på basis av nanoteknik.
• Elektroteknik . Spelets regler används för att modellera självläkande elektriska kretsar .
• Kemi . Konfigurationer som de som byggs i spelet skapas under kemiska reaktioner på ytan; i synnerhet i experimenten av M. S. Shakaeva, uppstår rörliga molekylära strukturer, liknande ett "livs" glidflygplan. Det görs också försök att förklara periodiska kemiska reaktioner med hjälp av multidimensionella cellulära automater. Självorganiseringen av elementarpartiklar behandlas också av supramolekylär kemi .

Kanske är detta spel kopplat till andra vetenskapliga fenomen, inklusive de som fortfarande är okända för modern vetenskap. Det är också möjligt att de för närvarande oupptäckta naturlagarna och samhället kommer att bli mer begripliga tack vare "Livet" och dess modifieringar.

Fakta

• Spelets regler är sådana att ingen interaktion kan överföras snabbare än schackkungens drag . Dess hastighet - en cell i valfri riktning - kallas ofta för " ljusets hastighet ".
• "Glider"-figuren föreslogs 2003 som emblemet för hackarna .
• Det första ryskspråkiga omnämnandet av " Game of Life " hänvisar till 1971 och är känt som "Evolution" i översättningen av tidskriften Science and Life.
• Om du skriver in " conway's game of life " i Googles sökfält kommer, förutom standardfrågeresultatet, en likhet med detta spel att visas som en bakgrundsanimation [7] [8] .

Ändringar

• Det finns modifieringar av spelet "Life" / "Evolution" enligt:
  • dimensioner  - på planet, i volym;
  • kromaticitet - monokrom, svart och vit (rutbräda), fullfärg;
  • algoritmens riktning - direkt, omvänd;
  • evolutionskonstanter — klassisk (B3/S23), modifierad;
  • storleken på spelplanen - begränsad, obegränsad, halvbegränsad;
  • fältaktivitet - aktiv, passiv;
  • antalet spelare - noll-spel, en, två;
  • spelaktiviteter - passiv, aktiv;
  • fältgeometrier — rektangulär, hexagonal.

• Av intresse är Conways omvända problem - sökandet efter en föregångare till en given figur [9] . För att lösa det kan statistikapparaten vara involverad: Monte Carlo-metoden , simuleringsmodellering , såväl som hela arsenalen av heuristiska metoder .
• En effektiv algoritm för ett fullfärgsspel är nedbrytningen av originalbilden till monotona, följt av deras överlagring efter att ha tillämpat de klassiska levnadsreglerna på dem; för volymetriska varianter - ortogonal transformationsalgoritm. Exempel på praktisk tillämpning av detta är alla typer av skärmsläckare, abstrakta bilder och design av konstverk.
• I schack, svart och vit version deltar två spelare, födelsefärgen bestäms av övervikten av färg i den generativa triaden, inspelningen av drag utförs enligt reglerna för schacknotation. Förutom de ursprungliga gränsformationerna observeras färgkollisioner här, till exempel "glidaren" i notationen: vit a2b2c2, svart c3b4 - missfärgas helt under transformationscykeln, och samma sak: vit a2b2, svart c2c3 b4 - visar "glidarens" kromatiska cyklicitet inom dess geometriska cykel.
• I ett aktivt schackspel har spelare möjlighet att påverka händelserna i "Life / Evolution" genom en enda introduktion - att ta bort ett begränsat antal marker i deras färg för att expandera, stabilisera historiens gång och motverka motståndaren i detta. De teoretiska grunderna här är beslutsfattande metoder , spelteorins apparat .
• I 3D- implementeringen av spelet gränsar varje cell till 26 andra celler, överlever med 4–5 grannar, och en ny föds med 5 grannar, och det finns också 3D-stabila strukturer, av vilka några liknar 2D. [tio]

Anteckningar

1. ↑ Martin Gardner . De fantastiska kombinationerna av John Conways nya patiensspel "life"  // Scientific American . - Nr 4 (oktober 1970) .
2. ↑ Livslexikon: Livslängd . Hämtad 21 september 2015. Arkiverad från originalet 22 september 2017. (obestämd)
3. ↑ Siffror i livet . www.radicaleye.com. Hämtad 15 juli 2017. Arkiverad från originalet 8 augusti 2017. (obestämd)
4. ↑ Toffoli T., Margolus N. Machines of cellular automata. — M.: Mir, 1991. — ISBN 5-03-001619-8
5. ↑ M.W. Mueller, W.D. Arnett. Utbredning av stjärnbildning och oregelbunden struktur i spiralgalaxer  //  The Astrophysical Journal. - 1976-12-01. — Vol. 210 . — S. 670–678 . — ISSN 0004-637X . - doi : 10.1086/154873 .
6. ↑ H. Gerola, P. E. Seiden. Stokastisk stjärnbildning och galaxers spiralstruktur  (engelska)  // The Astrophysical Journal. - 1978-07-01. — Vol. 223 . — S. 129–135 . — ISSN 0004-637X . - doi : 10.1086/156243 .
7. ↑ Jon Mitchell. Hur en Google-ingenjör byggde ett universum i ett påskägg (5 oktober 2012). Hämtad 31 januari 2016. Arkiverad från originalet 16 oktober 2016. (obestämd)
8. ↑ Siobhan Roberts. 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 . nr 8, 1972, sid. 141-144.
10. ↑ Arkiverad kopia . Hämtad 24 augusti 2021. Arkiverad från originalet 18 juli 2021. (obestämd)

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 för programmerare. - M . : Mir, 1982. - S. 19-22.
• Gardner M. Tic-tac-toe. - M .: Mir, 1988. - S. 287-343. — ISBN 5030012346 .
• Shcheglov G. Chess Evolution. - Lambert Academic Publishing, 2012. - 88 sid. — ISBN 9783848424603 .
• Trofimov M. Livet på Macintosh // Monitor, 1995. - Nr 2, s.72; nr 4, sid 72; nr 5, sid.66.
• Journal Science and Life. nr 8, 1971, sid. 130-133.
• Journal I de vetenskapliga upptäckternas värld. nr 5.4(11), 2010, sid. 50-53, 139. ISSN 2072-0831 (tryckt), ISSN 2307-9428 (online)
• Tillägg till tidningen Ung Tekniker. nr 8 augusti 1989, sid. 11-13
• Hayes B. Cellulär automat skapar en modell av världen och världen runt den. // In the world of science , 1984, nr 5, s. 97-104

Länkar

• ConwayLife.com - Game of Life och relaterade cellulära automater, Golly-programmet
• Livets ordbok
• Klumova I. N. Game "Life"  // Kvant . - 1974. - Nr 9 . - S. 26-30 .
• Martin Gardner . De fantastiska kombinationerna av John Conways nya patiensspel "life"  // Scientific American . — Vol. 223, nr 4 (oktober 1970) . - S. 120-123. Arkiverad från originalet den 1 maj 2013.

Ordböcker och uppslagsverk	Britannica (online)