Gioco di vita

Il gioco della vita è un automa cellulare immaginato da John Horton Conway nel 1970 e che è probabilmente il più noto di tutti gli automi cellulari. Nonostante le regole molto semplici, il gioco della vita è completo di Turing .

Il gioco della vita è un gioco di simulazione in senso matematico piuttosto che divertente. Sebbene non sia descritto dalla teoria dei giochi , alcuni lo descrivono come un "gioco a zero giocatori".

Regole

Il gioco della vita è un "  gioco da zero giocatore", poiché non richiede l'intervento del giocatore durante il suo sviluppo. È un automa cellulare , un modello in cui ogni stato conduce meccanicamente allo stato successivo sulla base di regole prestabilite.

Il gioco si svolge su una griglia bidimensionale, teoricamente infinita (ma di lunghezza e larghezza finite e più o meno grandi in pratica), le cui scatole - chiamate "celle", per analogia con le cellule viventi - possono assumere due stati distinti: " vivo o morto".

Una cella ha otto celle adiacenti, che sono celle adiacenti orizzontalmente, verticalmente e diagonalmente.

In ogni fase, l'evoluzione di una cellula è interamente determinata dallo stato dei suoi otto vicini come segue:

Pertanto, la configurazione Gol-blinker1.pngdà il turno successivo alla configurazione Gol-blinker2.pngche poi restituisce la prima.

Possiamo anche formulare questa evoluzione come segue:

Gol-born.png Questo è il caso della cella verde nella configurazione a sinistra; Gol-nochange.png Nel caso della configurazione a sinistra, la cellula situata tra le due cellule viventi rimane morta nella fase successiva; Gol-dead.png Questo è il caso del globulo rosso nella configurazione a sinistra.

Lo stato successivo di una cella è: (S = 3) OR (E = 1 AND S = 2).

Con:

Legenda dei diagrammi

Per rappresentare il processo, le cellule viventi vengono solitamente mostrate colorate sulla griglia, su uno sfondo di cellule morte incolori.

I diagrammi in questo articolo seguono le seguenti convenzioni sui colori:

Storia

Il gioco della vita è stato inventato da John Horton Conway nel 1970, mentre era professore di matematica all'Università di Cambridge , nel Regno Unito .

JH Conway è quindi interessato a un problema proposto dal matematico John Leech nel campo della teoria dei gruppi e che riguardava l'impilamento denso di sfere a 24 dimensioni (noto come reticolo di Leech ). Ha scoperto alcune proprietà notevoli e ha pubblicato i risultati del suo studio nel 1968. Conway era anche interessato a un problema presentato intorno agli anni '40 da un famoso matematico: John von Neumann .

Quest'ultimo ha cercato di trovare un'ipotetica macchina in grado di riprodursi. Ottiene questo risultato costruendo un modello matematico con regole complesse su un sistema di coordinate cartesiane. Conway cerca di semplificare le idee di von Neumann e finisce per avere successo. Unendo i suoi precedenti successi alle reti di Leech con il suo lavoro sulle macchine autoreplicanti, ha dato vita al gioco della vita.

Il primo contatto tra il grande pubblico e queste opere avvenne nel 1970 attraverso una pubblicazione su Scientific American nella colonna di Martin Gardner  : "  Giochi matematici  ".

Gardner scrive nelle sue colonne che “il gioco della vita rese rapidamente Conway famoso e aprì anche un nuovo campo di ricerca matematica, quello degli automi cellulari. In effetti, le analogie del gioco della vita con lo sviluppo, il declino e le alterazioni di una colonia di microrganismi, lo avvicinano ai giochi di simulazione che imitano i processi della vita reale. "

Secondo Gardner, Conway ha sperimentato diversi set di regole riguardanti la nascita, la morte e la sopravvivenza di una cellula prima di sceglierne una in cui la popolazione cellulare non è esplosa (cosa che spesso accade quando le condizioni di nascita sono povere. Meno rigide) ma dove le strutture interessanti appaiono facilmente . In origine, John Conway lo suonava a mano, usando una griglia di go board e go stones per materializzare le cellule viventi.

Sono state scoperte diverse strutture interessanti, come l '"aliante", uno schema che si sposta in diagonale ogni 4 generazioni, o vari "cannoni" che generano un flusso infinito di alianti. Queste possibilità aumentano l'interesse per il gioco della vita. Inoltre, la sua popolarità sta aumentando poiché arriva in un momento in cui è sul mercato una nuova generazione di minicomputer più economici, che consente di testare le strutture durante la notte, quando nessun altro le utilizza.

Alla fine degli anni '80, la potenza dei computer era sufficiente per consentire la creazione di programmi di ricerca automatica della struttura efficienti; insieme al massiccio sviluppo di Internet, portano a una rinascita nella produzione di strutture interessanti.

In definitiva, il gioco della vita attira l'interesse del grande pubblico per gli automi cellulari più (grazie a vari screen saver, tra le altre cose ) rispetto, ad esempio, a tutto il lavoro di Edgar Frank Codd , uno specialista riconosciuto nel campo e autore del libro di consultazione Automi cellulari (1968).

Strutture

Nell'universo possono comparire strutture composte da più celle; i più classici sono:

Ci sono anche altre strutture, che appaiono molto più raramente (se non del tutto per i Giardini dell'Eden) nel mondo di gioco:

Strutture stabili

Le strutture stabili (in inglese still life ) sono insiemi di cellule che hanno fermato tutti gli sviluppi: sono in condizioni stabili e cambieranno di più fintanto che non compaiono elementi di disturbo nelle loro vicinanze. Un blocco di quattro celle è la struttura stabile più piccola possibile.

Alcune figure si stabilizzano nelle strutture floreali dopo una successione di iterazioni paragonabili alla fioritura.

Oscillatori

Gli oscillatori ruotano ciclicamente rivestendo diverse forme prima di tornare al loro stato iniziale. Le cifre di questo tipo sono molto numerose: attualmente ne conosciamo centinaia. La "rana" è una struttura che si ripete ogni due generazioni.

Possono apparire relativamente facilmente nel mondo di gioco attraverso l'evoluzione spontanea di "semi" molto più semplici.

Navi

Le navi - shipping - ( astronavi inglesi , "astronavi") sono strutture capaci, dopo un certo numero di generazioni, di produrre copie di se stesse, ma spostate nell'universo del gioco.

Il movimento di una nave che ritorna dopo n stadi alla sua configurazione iniziale mossa da A quadrata orizzontalmente e B quadrata verticalmente è indicato AB , e la sua velocità (A, B) c / n , dove c rappresenta la "velocità della luce" nel gioco della vita, cioè la velocità massima di una cellula per generazione. È stata dimostrata l'esistenza di navi di tipo A - B per ogni A e B . Distinguiamo:

Il primo vaso obliquo, chiamato Gemini , è stato scoperto da Andrew J. Wade nel 2010. Sposta 5.120 cellule verticalmente e 1.024 cellule orizzontalmente ogni 33.699.586 generazioni. Esistono varianti in cui la velocità e il periodo sono diversi. È anche un costruttore universale .

Dimostriamo anche che un vaso di tipo A - B ha necessariamente un periodo N ≥ 2 (A + B) , così che la velocità massima per un vaso diagonale è (1, 1) c / 4, e che per un vaso ortogonale è ( 2, 2) c / 4 = (1, 1) c / 2.

È noto costruire vasi di grandi dimensioni e periodo desiderati, utilizzando una serie di componenti. . L' aliante è la nave più piccola nel gioco della vita, che vanta anche la velocità più alta per una nave diagonale.

Mathusalems

I Matusalemme sono strutture attive che richiedono tempo prima di stabilizzarsi. Alcuni, come i "conigli", impiegano più di 15.000 generazioni prima di stabilizzarsi in un numero più o meno elevato di vari detriti.

Puffers

I puffeurs (in inglese puffer "generatore di fumo") sono configurazioni che si muovono lasciandosi dietro una scia costituita da detriti.

Pistole, canoni, canna

I cannoni o i lanciatori, o le navi lancia (in inglese cannoni ) sono in qualche modo oscillatori che lasciano cadere detriti, in grado di produrre navi a velocità variabile (ogni 15, 23, 30 o 360 generazioni, per esempio, o in un modo apparentemente imprevedibile per pseudo- lanciatori di navi casuali ).

Tali strutture possono essere create da pesci palla che vengono modificati in modo che i detriti si adattino insieme sotto forma di vasi. Il primo cannone scoperto emette un aliante ogni 30 generazioni.

Giardini dell'Eden

Un Giardino dell'Eden è una configurazione senza un possibile passato: nessuna configurazione conferisce alla fase successiva un Giardino dell'Eden.

La dimostrazione matematica si basa sul calcolo combinatorio e può essere trovata in particolare in Winning Ways for your Mathematical Plays , un libro pubblicato nel 1982 da Berlekamp , Conway e Guy .

Costruttori universali

Nel 2010 è stato scoperto Gemini, il primo vero costruttore universale del gioco della vita. Questa cifra enorme è di 4.217.807 celle su 4.220.191. Man mano che avanza, questa cifra crea una copia di se stessa distruggendo quella precedente. L'operazione richiede circa 34 milioni di generazioni. Mentre Gemini si muove e non lascia nulla dietro, è anche una nave. È anche la prima nave a muoversi obliquamente, cioè né ortogonalmente né diagonalmente.

Dimensione e complessità

La potenza e la capacità di memoria dei personal computer poiché il passaggio a 64 bit consente l'esplorazione di spazi cellulari molto ampi del gioco della vita. Possiamo quindi sperare nell'emergere di strutture complesse con un alto livello di auto-organizzazione , anche estetica. Stephen Wolfram e altri hanno esplorato questo percorso. Dagli anni '80, il clown emerge all'iterazione 110 da una dinamica di una rete avviata da una U iniziale di 7 celle (generalmente chiamata "pi heptomino") che forma un'immagine della lettera U.

Nota: il clown viene addestrato a testa in giù. Per vedere un clown come nell'illustrazione, è necessario disegnare una U capovolta.

Dettagli sulla dinamica della rete: questa "U" di 7 celle (detta anche heptomino pi) evolve verso una struttura complessa e "organica", passando per forme molto estetiche. Inoltre, la struttura è auto-riproducibile con uno spostamento di fase, la nuova struttura figlia (iterazione 45) interferendo con una versione della struttura genitore (iterazione 15) nel corso dell'evoluzione. All'iterazione 110 otteniamo questa immagine di un "clown". Quindi la rete si stabilizza su una forma stabile oscillante complessa.

Domande matematiche

Sono state dimostrate alcune proprietà del gioco della vita, in particolare:

Calcolabilità

Nonostante la sua semplicità, questo gioco è una macchina di Turing universale  : è possibile calcolare qualsiasi algoritmo a condizione che la griglia sia abbastanza grande e le condizioni iniziali corrette.

Simulazione

Diversi programmi per computer simulano il gioco della vita; compreso Cellebration di Mirek . Quelli scritti in Java o JavaScript possono essere facilmente inclusi in una pagina web. Questi simulatori sono però poco efficaci quando rappresentano il terreno tramite una tavola bidimensionale e si accontentano di far evolvere le celle seguendo le regole di Conway.

Nel 1980, Bill Gosper ha inventato e poi ha scritto Hashlife , un algoritmo di simulazione molto più efficiente, che consente di manipolare diversi milioni di cellule su milioni di generazioni in tempi più brevi. Questo algoritmo era basato su un'idea diversa: infatti, se consideriamo una porzione dello spazio di gioco relativamente isolata dai suoi vicini, è possibile farla "girare" per un certo numero n di generazioni, quindi memorizzare il risultato . Se la configurazione di partenza viene riprodotta altrove, potremo quindi "saltare" direttamente n generazioni per questa parte del gioco. Questo nuovo algoritmo quindi "ruota" diverse porzioni dello spazio a velocità differenti e riesce a preservare la consistenza ai bordi . di ciascuna regione così simulata. Utilizzava una tabella hash per archiviare e recuperare rapidamente le configurazioni locali.

Il gioco della vita è estremamente sensibile a come calcolare la prossima generazione. L'implementazione convenzionale è sincrona , vale a dire che lo stato di ciascuna cella di generazione n +1 è calcolato dallo stato delle celle di generazione n . Bersini e Detours hanno dimostrato che i comportamenti di gioco della vita interessanti scompaiono con quasi tutti i modelli di aggiornamento non sincrono (dove n +1 stati possono influenzarsi a vicenda, come nella vita reale). Tuttavia, Nehaniv ha dimostrato che qualsiasi comportamento sincrono può essere emulato da automi cellulari asincroni ed è quindi possibile trovare il comportamento del gioco della vita senza un "orologio globale" che cronometri l'evoluzione delle generazioni.

Dal 2008 molti programmi (il più noto dei quali è Golly ) integrano questo algoritmo in un'interfaccia grafica. Hanno permesso di creare configurazioni enormi e molto ingegnose e di seguirne l'evoluzione, infondendo una nuova dinamica nel già ricchissimo studio di questo automa cellulare.

Dal 2012, una ricerca su Google per i termini "Il gioco della vita di Conway" fa apparire un easter-egg  : un gioco interattivo della vita appare sullo sfondo.

Varianti

Esistono varianti del gioco della vita, basate su regole di quartiere leggermente diverse, ad esempio HighLife o Day & night . Questa variante ha due tipi di celle, "positive" e "negative", ciascuna che risponde alle stesse regole, a differenza del segno. Una cella positiva richiede una somma di 3 per "nascere", una negativa una somma di −3. Le cellule viventi diventano parte del bilancio delle cellule circostanti per la loro sopravvivenza o declino. Le due popolazioni generalmente non possono sopravvivere fianco a fianco.

Bibliografia

Documento utilizzato per scrivere l'articolo : documento utilizzato come fonte per questo articolo.

Note e riferimenti

Appunti

Riferimenti

  1. ( Gardner 1970 ).
  2. ( Codd 1968 ).
  3. (in) "  Elenco oscillatori  " su LifeWiki
  4. (in) Creazione dell'astronave Adam P. Goucher Oblique Life , Game of Life News, 19 maggio 2010 (accesso 11 maggio 2010).
  5. Thomas Morin, "  Limite di velocità delle navi: dimostrazione  " ,9 maggio 98(visitato il 27 febbraio 2019 ) .
  6. Bernard Feltz et al, Emergence and Reductionism: from the Game of Life to Science of Life , in SELF-ORGANIZATION AND EMERGENCE IN LIFE SCIENCES , Springer Netherlands Editor , 2006, ( ISBN  978-1-4020-3916-4 ) ( Stampa ) 978-1-4020-3917-1 (in linea ) [1]
  7. NM Gotts, Emergent phenomena in large sparse random array of Conway's Game of Life , in INTERNATIONAL JOURNAL ON SYSTEM SCIENCES, Volume 31, Issue 7 July 2000 , pages 873 - 894 [2]
  8. Jean-Claude Perez, "NUOVI MODI VERSO L'INTELLIGENZA ARTIFICIALE: pluridisciplinarità, auto-organizzazione e reti neurali", 1988, Ed. Masson Paris (ripubblicato nel 1989), pagine 261-262, ( ISBN  2-225-81815-0 ) .
  9. ER Berlekamp, ​​JH Conway, RK Guy, Winning Ways for Your Mathematical Plays, AK Peters / CRC Press; 2a edizione (30 marzo 2004)
  10. http://mirekw.com/ca/download.html
  11. H. Bersini, V. Detours, "Asynchrony Induces Stability in Cellular Automata Based Models", In Proceedings of the IVth Conference on Artificial Life - MIT Press / Bradford Books, 1994.
  12. CL Nehaniv, "Evolution in Asynchronous Cellular Automata", Artificial Life VIII , 65-73, MIT Press, 2002.
  13. CL Nehaniv, "Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network", International Journal of Algebra & Computation , 14 (5-6): 719-739, 2004.
  14. Golly su SourceForge.net .
  15. it: Elenco delle bufale e degli easter egg di Google # Cerca

Vedi anche

Articoli Correlati

link esterno