Game of life
INTRODUCERE
Game of life a fost conceptualizat de matematicianul britanic John Horton Conway în 1970. Acest automat celular funcționează fără implicarea directă a jucătorului, deoarece progresul său este dictat doar de configurația sa inițială. Jucătorii se implică în joc prin stabilirea unei configurații inițiale și apoi asistând la dezvoltarea acesteia în timp. În mod remarcabil, acest joc emulează diferite procese de calcul, inclusiv constructori universali și mașini Turing.
Cine?
John Horton Conway FRS (26 decembrie 1937 – 11 aprilie 2020) a fost un matematician englez apreciat, renumit pentru contribuțiile sale profunde la diferite domenii, inclusiv grupuri finite, teoria nodurilor, teoria numerelor, teoria jocurilor combinatorii și teoria codificării. Originar din Liverpool, Conway și-a început cariera la Universitatea din Cambridge înainte de a se muta în Statele Unite. Acolo, el a fost la Universitatea Princeton, până la moartea sa. Moștenirea lui Conway se extinde dincolo de mediul academic; a lăsat, de asemenea, o amprentă de neșters asupra matematicii recreaționale prin crearea Jocului vieții, un automat revoluționar celular. Din păcate, Conway a cedat complicațiilor cauzate de COVID-19 la vârsta de 82 de ani, pe 11 aprilie 2020.
REGULI
Jocul Vieții se desfășoară într-o rețea infinită, bidimensională, compusă din celule pătrate, fiecare fie într-o stare vie, fie într-o stare moartă (alternativ descrisă ca populată sau nepopulată). Fiecare celulă interacționează cu cele opt celule învecinate ale sale, care pot fi găsite pe orizontală, verticală sau diagonală adiacente. Cu fiecare iterație de timp, au loc următoarele tranziții:
Orice celulă vie cu mai puțin de doi vecini vii moare din cauza subpopulării.
Orice celulă vie cu doi sau trei vecini vii continuă să trăiască până la generația următoare.
Orice celulă vie cu mai mult de trei vecini vii moare din cauza suprapopulării.
Orice celulă moartă cu exact trei vecini vii devine vie, ca prin reproducere.
Modelul inițial servește ca sămânță a sistemului. Prima generație apare prin aplicarea regulilor menționate mai sus în mod simultan la fiecare celulă din sămânță, fie că este vie sau moartă. Nașterile și decesele apar simultan în fiecare moment discret cunoscut sub numele de „căpușă”. Generațiile ulterioare sunt determinate exclusiv de cea anterioară, deoarece regulile sunt aplicate în mod repetat pentru a genera iterații ulterioare.
EXEMPLE
În Jocul Vieții, există diverse modele cu comportamente distincte, clasificate în funcție de modul în care evoluează.
Primele modele interesante din Jocul Vieții au fost descoperite fără utilizarea computerelor. Folosind hârtie milimetrică, table negre sau chiar table de joc fizice, cum ar fi cele de Go, au fost identificate cele mai simple naturi moarte și oscilatoare. De exemplu, un model numit R-pentomino necesită 1103 generații pentru a se stabiliza și generează șase nave spațiale în timpul acestui proces.
Exemple frecvente ale acestor tipuri de modele includ:
Still lifes: Configurații care nu se schimbă, indiferent de evoluția din jurul lor.
Oscillators: Modele care oscilează între două sau mai multe stări.
Spaceships: Configurații care se deplasează pe grilă într-un mod specific.
Aceste modele pot apărea chiar și în configurații inițiale aleatorii și sunt ușor de observat, cu celulele vii reprezentate de puncte negre și cele moarte de puncte albe. Perioada se referă la numărul de iterații necesare pentru ca un model să se întoarcă la configurația sa inițială.
Still lifes
Loaf
Boat
Bee-hive
Block
Oscillators
Blinker (period 2)
Toad (period 2)
Beacon (period 2)
Pulsar (period 3)
Spaceships
Glider
Light-weight spaceship (LWSS)
Middle-weight spaceship (MWSS)
Heavy-weight spaceship (HWSS)
AlgOrITM
Programatorii de calculator au dezvoltat inițial algoritmi pentru a urmări modelele în Jocul Vieții, reprezentându-le sub formă de matrice bidimensională în memoria computerului. Aceste matrice rețineau generația curentă a celulelor și calculau succesorii acestora. De obicei, celulele moarte și cele vii sunt reprezentate de 0 și 1, respectiv. Un buclu imbricat parcurge fiecare element al matricei curente, numărând vecinii vii pentru a determina starea fiecărei celule din matricea succesorilor. Pentru a optimiza calculul, au fost introduse îmbunătățiri minore, cum ar fi sărirea actualizărilor pentru zonele inactive.
Pentru a simplifica luarea deciziilor, bucla de numărare poate fi rearanjată în funcție de punctul de vedere al unui observator științific în loc de o abordare egocentrică. Utilizarea memoriei poate fi redusă prin utilizarea unei singure matrice și a două buffer-e de linie, cu matrici toroidale care necesită un al treilea buffer pentru a gestiona efectele de graniță. Diverse strategii abordează limitele de memorie, inclusiv presupunerea celulelor moarte în afara matricei sau utilizarea matricilor toroidale. În mod alternativ, programatorii pot opta pentru diferite structuri de date, cum ar fi vectorii de perechi de coordonate, cu toate că acest lucru poate încetini simulările. Algoritmi avansați precum Hashlife și actualizările asincrone pot fi utilizate pentru a explora modele mari. Exemple de cod sursă pentru implementarea Jocului Vieții în diferite limbaje de programare pot fi găsite online.