Conway.exe il gioco della vita

"La vita è un processo che può essere astratto da ogni sua implementazione particolare."

Implementazione del Gioco della Vita (in inglese Game of Life), un automa cellulare introdotto negli anni sessanta dal matematico inglese John Horton Conway, a cui è dedicato il nome del programma. È un automa bidimensionale a 2 stati, in cui lo stato di una cella dipende dallo stato della cella stessa e delle 8 celle adiacenti.

Se non sai cos'è una automa cellulare potresti leggere, prima di continuare, questa mia pagina sull'automa cellulare unidimensionale, il più semplice automa cellulare possibile. In tale automa è possibile codificare la regola con cui esso evolve attraverso l'enumerazione di tutte le possibili configurazioni e l'assegnazione ad ognuna di esse del valore da utilizzare per la cella il turno successivo.

Già per il Gioco della Vita, che è più complesso solo per essere bidimensionale invece che unidimensionale, ciò diventa molto scomodo. Ogni cella ha infatti 8 vicini, che aggiunti allo stato della cella stessa ci danno 2⁹ = 512 possibili configurazioni. Non è certamente comodo specificare una regola dando 512 valori. Il numero totale di regole possibili, oltre a quella specifica del Gioco della Vita, è enorme (2⁵¹², un numero rappresentabile in decimale con 155 cifre).

Le regole della vita

I 512 valori che rappresentano la specifica regola del Gioco della Vita possono però essere sintetizzati con 3 semplici regole:

• una cella spenta con esattamente 3 celle accese adiacenti si accende (riproduzione)
• una cella accesa con meno di 2 celle accese adiacenti si spegne (isolamento)
• una cella accesa con più di 3 celle accese adiacenti si spegne (sovrappopolazione)

Negli altri casi lo stato della cella resta immutato (con più o meno di 3 celle accese adiacenti una cella spenta resta spenta, con 2 o 3 celle accese adiacenti una cella accesa resta accesa).

L'ulteriore regola sottintesa, che permette di ricavare tutti i valori, è la completa simmetria della regola rispetto a rotazioni e riflessioni.

Vediamo quindi il senso del nome dato da Conway al proprio automa: è un tentativo di imitare e schematizzare i tratti più elementari della vita biologica.

Computabilità

Nonostante la semplicità di queste regole è stato dimostrato che questo automa è Turing equivalente, cioè ha le stesse potenzialità di calcolo di una macchina di Turing universale. In altre parole in esso è possibile eseguire qualsiasi algoritmo. Sono molto interessanti le implementazioni nel Gioco delle Vita di una macchina di Turing o del Gioco della Vita stesso, facilmente reperibili in rete.

Utilizzo dei colori

Invece di disegnare semplicemente le celle accese e spente con due colori differenti ho voluto aggiungere un po' di informazioni utilizzando più colori. Le celle spente vanno dal verde al nero, in base al tempo in cui sono rimaste spente. Le celle accese invece vanno dal verde all'azzurro, in base al tempo in cui sono rimaste accese senza spegnersi. In questo modo il colore verde evidenzia le parti dinamiche della griglia, l'azzurro quelle statiche.

Libreria espandibile

È disponibile anche una libreria di pattern preconfigurati, facilmente estendibile aggiungendo dei semplici file di testo, eventualmente strutturati in cartelle. Ad esempio l'aliante (in inglese glider, proposto da Eric Raymond come simbolo della comunità hacker) può essere rappresentato da un file di testo contenente le seguenti righe:

//Glider
//Richard Kenneth Guy, 1970
010
001
111

Per permettere di importare facilmente le configurazioni dalle differenti fonti disponibili (come ad esempio questo sito) il programma di importazione accetta come carattere per la cella accessa 1, * e O (lettera o maiuscola), mentre non ha nessun vincolo sul carattere per rappresentare la cella spenta. Inoltre interpreta come riga di commento le righe che iniziano con !, # e //.

È possibile inoltre importare direttamente delle immagini.

Il fatto di poter strutturare la libreria in cartelle e sottocartelle permette di suddividere le configurazioni salvate in base alla tipologia. Le categorie principali di pattern sono:

• still life: una configurazione completamente statica, come il block;
• oscillator: una configurazione che dopo un certo numero di iterazioni torna alla sua configurazione di partenza, come il blinker;
• spaceship: una configurazione che dopo un certo numero di iterazioni torna alla configurazione di partenza, ma traslata nello spazio, l'esempio più famoso è il già citato glinder;
• gun: una configurazione che genera a ripetizione un qualche tipo di spaceship, il più semplice esempio è il Gosper glider gun.

Esistono poi altre categorie più particolari. Ad esempio gli eater sono degli still life (o meno comunemente degli oscillator) che interagiscono con certi pattern per poi tornare alla configurazione di partenza. Oppure i puffer, delle spaceship che lasciano dei "detriti" dietro di sé durante il loro moto. Un'altra categoria molto particolare sono i cosiddetti garden of eden, configurazioni che non hanno predecessori, cioè non possono derivare da alcuna altra configurazione. In altre parole i garden of eden possono esistere solo alla generazione 0.