Jocul „Viața”

Jocul „Life” ( Eng.  Conway’s Game of Life ) este un automat celular inventat de matematicianul englez John Conway în 1970 .

Reguli

• Locul de acțiune al jocului este un plan marcat în celule, care poate fi nelimitat, limitat sau închis.
• Fiecare celulă de pe această suprafață are opt vecini care o înconjoară și poate fi în două stări: să fie „în viață” (umplută) sau „moartă” (gol).
• Distribuția celulelor vii la începutul jocului se numește prima generație. Fiecare generație următoare este calculată pe baza celei anterioare, conform următoarelor reguli:
  • într-o celulă goală (moartă), care este învecinată cu trei celule vii, se naște viața;
  • dacă o celulă vie are doi sau trei vecini vii, atunci această celulă continuă să trăiască; în caz contrar (dacă sunt mai puțin de doi sau mai mult de trei vecini vii), celula moare („din singurătate” sau „din supraaglomerare”).
• Jocul se termină dacă
  • nici o celulă „vie” nu va rămâne pe teren;
  • configurația la pasul următor se va repeta exact (fără schimburi și rotații) la unul dintre pașii anteriori (se adaugă o configurație periodică)
  • la pasul următor, niciuna dintre celule nu își schimbă starea (regula anterioară se aplică cu un pas înapoi, se formează o configurație stabilă)

Jucătorul nu participă activ la joc . Acesta aranjează sau generează doar configurația inițială a celulelor „vii”, care apoi se schimbă conform regulilor. În ciuda simplității regulilor, în joc pot apărea o mare varietate de forme.

Origine

John Conway a devenit interesat de o problemă propusă în anii 1940 de renumitul matematician John von Neumann , care încerca să creeze o mașină ipotetică care să se poată reproduce singură. John von Neumann a reușit să creeze un model matematic al unei astfel de mașini cu reguli foarte complexe. Conway a încercat să simplifice ideile lui Neumann și în cele din urmă a reușit să creeze regulile care au devenit regulile Jocului Vieții.

Descrierea acestui joc a fost publicată pentru prima dată în numărul din octombrie ( 1970 ) al revistei Scientific American , sub titlul „Jocuri matematice” de Martin Gardner ( Martin Gardner ) [1] .

Implementarea calculatorului

În implementările jocului pe computer, câmpul este limitat și, de regulă, închis - marginea superioară a câmpului este „conectată” la partea de jos, iar marginea stângă la dreapta, care este o emulare a suprafeței unui torus , dar pe ecran câmpul este întotdeauna afișat ca o grilă uniformă.

Cel mai simplu algoritm de „schimbare de generație” caută secvențial prin toate celulele rețelei, numără vecinii pentru fiecare, determinând soarta celulei în noua generație (nu se va schimba, va muri, se va naște). Un astfel de algoritm folosește două matrice bidimensionale - pentru generația curentă și pentru următoarea generație.

Un algoritm mai rapid face prima trecere prin toate celulele, dar în același timp construiește o listă de celule pe care să le examineze în generația următoare. Celulele care nu se pot schimba fundamental într-o generație nu sunt incluse în listă. De exemplu, dacă vreo celulă și toți vecinii săi nu s-au schimbat în timpul calculului curent al noii generații, atunci această celulă nu se va schimba în timpul următoarei treceri.

Cifre

La scurt timp după publicarea regulilor, au fost descoperite mai multe modele interesante (variante ale aranjamentului celulelor vii din prima generație), în special: r -pentamino și glider ( glider ).

Unele dintre aceste cifre rămân neschimbate în toate generațiile ulterioare, starea altora se repetă periodic, în unele cazuri cu o deplasare a întregii figuri. Există o cifră ( Diehard ) de doar șapte celule vii ai căror descendenți există de o sută treizeci de generații și apoi dispar.

Conway a sugerat inițial că nicio combinație inițială nu ar putea duce la reproducere nelimitată și a oferit un bonus de 50 USD oricui a dovedit sau a infirmat această ipoteză. Premiul a fost câștigat de un grup de la MIT care a venit cu o cifră fixă, repetată, care crea periodic „planare” în mișcare. Astfel, numărul de celule vii ar putea crește la infinit. Apoi au fost găsite figuri în mișcare, lăsând în urmă „gunoaie” de la alte figuri.

Până în prezent, următoarea clasificare a cifrelor s-a dezvoltat mai mult sau mai puțin:

• Cifre stabile : cifre care rămân neschimbate
• Centenari : cifre care se schimbă mult timp înainte de a se stabiliza [2] ;
• Cifre periodice : cifre în care starea se repetă după un anumit număr de generații mai mare de 1;
• Figuri în mișcare : figuri în care starea se repetă, dar cu o oarecare deplasare;
• Pistoale : forme cu stări repetate, creând în plus forme în mișcare ;
• Locomotive cu abur : forme în mișcare cu stări repetate care lasă în urmă alte forme ca trasee;
• Devoratoare : piese rezistente care pot supraviețui ciocnirilor cu unele piese în mișcare distrugându-le;
• Reflectori : figuri stabile sau periodice capabile să-și schimbe direcția atunci când figurile în mișcare se ciocnesc de ele ;
• Multiplicatori : configurații în care numărul de celule vii crește ca pătrat al numărului de pași;
• Forme care sunt duplicate la ciocnirea cu unele forme.

Grădina Edenului

Grădina Edenului (Grădina Edenului) este un aranjament de celule care nu poate avea o generație anterioară. Pentru aproape orice joc în care starea celulelor este determinată de mai mulți vecini în pasul anterior, este posibil să se dovedească existența Grădinilor Edenului, dar este mult mai dificil să construiești o anumită figură.

„Numere”

Folosind cel mai simplu „font” de celule 3 pe 5, propus, se pare, de Eric Angelini în 2007, poți obține o mulțime de forme. De exemplu, numărul 90 scris în acest font generează un planor [3] .

Influența asupra dezvoltării științelor

Deși jocul constă doar din două reguli simple, el a atras atenția oamenilor de știință de mai bine de patruzeci de ani. Jocul „Viața” și modificările sale au influențat (în unele cazuri reciproc) multe secțiuni ale științelor exacte precum matematica , informatica și fizica [4] . Acestea sunt, în special:

• teoria automatelor ,
• Teoria algoritmilor ,
• Teoria jocurilor și programarea matematică ,
• Algebra si teoria numerelor ,
• Teoria probabilității și statistică matematică ,
• Combinatorică și teoria grafurilor ,
• geometrie fractala ,
• Matematică computațională ,
• Teoria deciziei ,
• Modelare matematică .

În plus, multe modele găsite în joc își au analogiile în alte discipline, uneori complet „nematematice”. Iată o listă de științe ale căror teorii au puncte interesante de contact cu fenomenele „Vieții”:

• Cibernetica . Jocul în sine este încercarea de succes a lui Conway de a dovedi existența unor sisteme simple de auto-reproducere, precum și apariția unui fel de „inteligență” în sistemele de auto-reproducere.
• Biologie . Asemănarea exterioară cu dezvoltarea populațiilor de organisme primitive este impresionantă.
• Bacteriologie . Unele variații interesante ale jocului cu condiții suplimentare pot repeta exact reproducerea bacteriilor, care pot muta cu o probabilitate aleatorie (în funcție de condiția de modificare).
• Fiziologie . Nașterea și moartea celulelor sunt similare cu procesul de apariție și dispariție a impulsurilor neuronale.
• Astronomie . Evoluția unor colonii complexe repetă în mod surprinzător schematic etapele de dezvoltare ale galaxiilor spirale [5] [6] .
• Fizica stării solide . Teoria automatelor în general și jocul „Viața” în special sunt folosite pentru a analiza „fenomenele de transfer” - difuzie , vâscozitate și conductivitate termică .
• Fizica cuantică . Comportamentul celulelor „vieții” (nașterea altora noi și anihilarea reciprocă) amintește în multe privințe de procesele care au loc în timpul ciocnirii particulelor elementare .
• Nanomecanica . Coloniile staționare și pulsatorii sunt un exemplu ilustrativ al celor mai simple dispozitive create pe baza nanotehnologiei.
• Inginerie electrică . Regulile jocului sunt folosite pentru a modela circuite electrice cu auto-vindecare .
• Chimie . Configurații precum cele construite în joc sunt create în timpul reacțiilor chimice de la suprafață; în special, în experimentele lui M. S. Shakaeva, apar structuri moleculare în mișcare, similare unui planor „viață”. De asemenea, se încearcă explicarea reacțiilor chimice periodice folosind automate celulare multidimensionale. Auto-organizarea particulelor elementare este, de asemenea, tratată de chimia supramoleculară .

Poate că acest joc are legătură cu alte fenomene științifice, inclusiv cu cele care sunt încă necunoscute științei moderne. De asemenea, este posibil ca legile naturii și societății, nedescoperite în prezent, să devină mai înțelese datorită „Vieții” și modificărilor acesteia.

Fapte

• Regulile jocului sunt de așa natură încât nicio interacțiune nu poate fi transmisă mai rapid decât mișcarea regelui șahului . Viteza sa - o celulă în orice direcție - este adesea denumită „ viteza luminii ”.
• Figura „planor” a fost propusă în 2003 ca ​​emblemă a hackerilor .
• Prima mențiune în limba rusă a „ Jocul vieții ” se referă la 1971 și este cunoscută ca „Evoluție” în traducerea revistei Science and Life.
• Dacă introduceți „ conway’s game of life ” în bara de căutare Google , atunci, pe lângă rezultatul interogării standard, o similitudine a acestui joc va fi afișată ca o animație de fundal [7] [8] .

Modificări

• Există modificări ale jocului „Life” / „Evolution” conform:
  • dimensiuni  - în plan, în volum;
  • cromaticitate - monocrom, alb-negru (tabla de șah), color;
  • direcția algoritmului - direct, invers;
  • constante de evoluție — clasice (B3/S23), modificate;
  • dimensiunea terenului de joc - limitat, nelimitat, semilimitat;
  • activitate de teren - activ, pasiv;
  • numărul de jucători - zero-game, unu, doi;
  • activități de joc - pasive, active;
  • geometrii de câmp — dreptunghiulare, hexagonale.

• Interesantă este problema inversă a lui Conway - căutarea unui predecesor al unei figuri date [9] . Pentru a o rezolva, poate fi implicat aparatul de statistică: metoda Monte Carlo , modelarea prin simulare , precum și întregul arsenal de metode euristice .
• Un algoritm eficient pentru un joc full-color este descompunerea imaginii originale în imagini monotone, urmată de suprapunerea lor după aplicarea regulilor clasice de viață; pentru variante volumetrice - algoritm de transformare ortogonală . Exemple de aplicare practică a acestui lucru sunt tot felul de screensavere, imagini abstracte și designul operelor de artă.
• În versiunea de șah, alb-negru, participă doi jucători, culoarea nașterii este determinată de predominanța culorii în triada generativă, înregistrarea mișcărilor se efectuează conform regulilor de notare a șahului. În plus față de formațiunile de frontieră originale, aici se observă coliziuni de culoare, de exemplu, „planorul” în notație: alb a2b2c2, negru c3b4 - se decolorează complet în timpul ciclului de transformare și același lucru: alb a2b2, negru c2c3 b4 - demonstrează ciclicitatea cromatică a „planorului” în cadrul ciclului său geometric.
• Într-un joc de șah activ, jucătorii au posibilitatea de a influența evenimentele din „Viața/Evoluția” printr-o singură introducere - eliminând un număr limitat de jetoane de culoarea lor pentru a se extinde, a stabiliza cursul istoriei și a contracara adversarul în acest. Bazele teoretice aici sunt metodele de luare a deciziilor , aparatul teoriei jocurilor .
• În implementarea 3D a jocului, fiecare celulă mărginește alte 26 de celule, supraviețuiește cu 4-5 vecini și se naște una nouă cu 5 vecini și există, de asemenea, structuri stabile 3D, dintre care unele sunt similare cu 2D. [zece]

Note

1. ↑ Martin Gardner . Combinațiile fantastice ale noului joc de solitaire „life” al lui John Conway  // Scientific American . - Nr. 4 (octombrie 1970) .
2. ↑ Dicționarul vieții: longevitate . Preluat la 21 septembrie 2015. Arhivat din original la 22 septembrie 2017. (nedefinit)
3. ↑ Cifre în viață . www.radicaleye.com. Preluat la 15 iulie 2017. Arhivat din original la 8 august 2017. (nedefinit)
4. ↑ Toffoli T., Margolus N. Machines of cellular automata. — M.: Mir, 1991. — ISBN 5-03-001619-8
5. ↑ M.W. Mueller, W.D. Arnett. Propagarea formării stelelor și a structurii neregulate în galaxiile spirale  //  The Astrophysical Journal. - 1976-12-01. — Vol. 210 . — P. 670–678 . — ISSN 0004-637X . - doi : 10.1086/154873 .
6. ↑ H. Gerola, P. E. Seiden. Formarea stochastică a stelelor și structura în spirală a galaxiilor  (engleză)  // The Astrophysical Journal. - 1978-07-01. — Vol. 223 . — P. 129–135 . — ISSN 0004-637X . - doi : 10.1086/156243 .
7. ↑ Jon Mitchell. Cum un inginer Google a construit un univers într-un ou de Paște (5 octombrie 2012). Consultat la 31 ianuarie 2016. Arhivat din original la 16 octombrie 2016. (nedefinit)
8. ↑ Siobhan Roberts. Prolog // Geniu în joc: Mintea curioasă a lui John Horton Conway . — Bloomsbury Publishing USA, 2015. — P. XV. — 480p. - ISBN 1-620-40594-6 , 978-1-620-40594-9.
9. ↑ Jurnalul de Știință și Viață . Nr. 8, 1972, p. 141-144.
10. ↑ Copie arhivată . Preluat la 24 august 2021. Arhivat din original la 18 iulie 2021. (nedefinit)

Literatură

• Andrew Adamatzky. Game of Life Cellular Automata. - Springer-Verlag Londra, 2010. - ISBN 978-1-84996-216-2 - doi : 10.1007/978-1-84996-217-9 .
• Paul Rendell. Mașina Turing Universalitatea jocului vieții. - 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. Studii pentru programatori. - M . : Mir, 1982. - S. 19-22.
• Gardner M. Tic-tac-toe. - M . : Mir, 1988. - S. 287-343. — ISBN 5030012346 .
• Shcheglov G. Evoluția șahului. - Editura Academică Lambert, 2012. - 88 p. — ISBN 9783848424603 .
• Trofimov M. Viața pe Macintosh // Monitor, 1995. - Nr. 2, p.72; nr. 4, p.72; Nr. 5, p.66.
• Jurnal Știință și viață. Nr. 8, 1971, p. 130-133.
• Jurnal În lumea descoperirilor științifice. Nr. 5.4(11), 2010, p. 50-53, 139. ISSN 2072-0831 (tipărit), ISSN 2307-9428 (online)
• Supliment la revista Tânărul Tehnician. Nr. 8 august 1989, p. 11-13
• Hayes B. Automatul celular creează un model al lumii și al lumii înconjurătoare. // În lumea științei , 1984, nr. 5, p. 97-104

Link -uri

• ConwayLife.com - Jocul vieții și automatele celulare aferente, software-ul Golly
• Dicţionar al vieţii
• Klumova I. N. Jocul „Viața”  // Kvant . - 1974. - Nr 9 . - S. 26-30 .
• Martin Gardner . Combinațiile fantastice ale noului joc de solitaire „life” al lui John Conway  // Scientific American . — Vol. 223, nr.4 (octombrie 1970) . - P. 120-123. Arhivat din original la 1 mai 2013.

Dicționare și enciclopedii	Britannica (online)