Origine

Reguli

Exemple de modele

Algoritmi

Link catre joc 

Stanislaw Ulam, lucrând la Laboratorul Național Los Alamos în anii 1940, a investigat creșterea cristalelor, folosind o rețea cristalină simplă ca model. În același timp, colegul său, John von Neumann, se concentra pe problema sistemelor de autoreplicare. Von Neumann a propus inițial un model în care un robot construiește alt robot, cunoscut sub numele de modelul cinematic. Ulterior, Ulam a sugerat utilizarea unui sistem discret pentru a crea un model simplu de autoreplicare. Ulam și von Neumann au dezvoltat un sistem de automate celulare la sfârșitul anilor 1950, utilizând ideea de a considera lichidul ca fiind compus din unități discrete pentru a calcula mișcarea acestuia. Aceste automate celulare, denumite automatele celulare Von Neumann, au fost bidimensionale și conțineau un autoreplicator implementat algoritmic. John Conway a continuat munca inițiată de Ulam și von Neumann, experimentând cu automate celulare bidimensionale în 1968, rezultând Jocul Vieții. Jocul, prezentat publicului în 1970, a atras interesul datorită modului surprinzător în care modelele evoluează și poate fi folosit ca o analogie didactică pentru concepte precum emergența și autoorganizarea. Popularitatea sa a fost amplificată odată cu disponibilitatea computerelor mai accesibile, iar Jocul Vieții a devenit o provocare de programare și o sursă de reflecții filosofice.

Universul Jocului Vieții este o grilă ortogonală infinită, bidimensională, cu celule pătrate, fiecare dintre acestea fiind într-una dintre cele două stări posibile, vie sau moartă (sau populată, respectiv nepopulată). Fiecare celulă interacționează cu cele opt celule învecinate, care sunt celulele care sunt adiacente orizontal, vertical sau diagonal. La fiecare pas în timp, au loc următoarele schimbări:

1. Orice celulă vie cu mai puțin de doi vecini vii moare, datorită subpopulării.

2. Orice celulă vie cu doi sau trei vecini vii trăiește în generația următoare.

3. Orice celulă vie cu mai mult de trei vecini vii moare, datorită suprapopulării.

4. Orice celulă moartă cu exact trei vecini vii devine o celulă vie, datorită reproducerii.

Jocul începe prin inițializarea sistemului cu un model, modelul inițial. Prima generație este creată prin aplicarea regulilor de mai sus simultan la fiecare celulă, vie sau moartă, din modelul inițial. Nașterile și decesele au loc simultan, iar momentul discret în care se întâmplă acest lucru este uneori numit tact.[a] Fiecare generație este o funcție pură⁠ a stării precedente. Regulile se aplică repetat pentru a crea generațiile următoare.

Jocul Vieții oferă o varietate impresionantă de modele, clasificate în funcție de comportamentul lor. Modelele includ naturi moarte, oscilatoare și nave spațiale. Unele dintre cele mai vechi și interesante modele au fost descoperite chiar înainte de era computerelor. De exemplu, R-pentomino, care necesită 1103 generații pentru a se stabiliza și generează șase glidere, a fost una dintre primele nave spațiale descoperite. Oscilatoarele, precum pulsarul cu perioada de 3, sunt comune, dar se cunosc oscilatoare cu perioade diferite. Există și modele care cresc lent înainte de a se stabiliza, numite Matusalem, cum ar fi R-pentomino. Jocul a atras atenția prin capacitatea sa de a genera modele cu creștere infinită. Conway a oferit un premiu pentru demonstrarea sau infirmarea conjecturii sale inițiale că niciun model nu poate crește la infinit, iar acest premiu a fost câștigat cu ajutorul tunului cu glidere Gosper. S-au găsit și alte modele cu creștere nelimitată, cum ar fi tunul cu glidere Simkin și modelele cu motor de comutare. Jocul Vieții este Turing-complet, putând simula arhitecturi de computere programabile și fiind capabil să construiască obiecte complexe, inclusiv copii ale lui însuși. Recent, a fost descoperită prima navă-cal elementară, Sir Robin, după patruzeci și opt de ani de la ultima descoperire similară.

În primele etape ale evoluției Jocului Vieții, programatorii au creat algoritmi pentru a urmări modelele în evoluție. Aceste programe, de obicei, reprezentau modelele folosind matrici bidimensionale, cu 0 și 1 pentru celule moarte și vii. Un algoritm de bază implica parcurgerea matricii și calcularea stării succesoare a fiecărei celule în funcție de vecinii săi. Pentru a economisi timp și memorie, se pot face îmbunătățiri, cum ar fi să nu se actualizeze celulele care nu s-au schimbat recent și să se optimizeze stocarea modelelor. Strategii precum grilele toroidale și alocarea dinamică a memoriei au fost adoptate pentru a gestiona limitele matricilor și memoria finită a computerelor. Există și alte structuri de date, cum ar fi vectorii de coordonate, care permit modelelor să evolueze pe câmpuri mari fără limitele matricilor. Algoritmi mai avansați, cum ar fi Hashlife, permit explorarea și simularea modelelor mari pe durate mari de timp. Astfel, în ciuda complexității Jocului Vieții, există o varietate de abordări și tehnici pentru a-l implementa eficient în diferite limbaje de programare.