Matteo Basei

Una collezione di piccoli programmi realizzati a scopo didattico.

Conway.exe il gioco della vita

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

John von Neumann

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. A differenza di quest'ultimo, in cui è possibile codificare la regola attraverso l'enumerazione di tutte le possibili configurazioni, in questo caso la cosa non è così comoda. Ogni cella ha infatti 8 vicini, che aggiunti allo stato della cella stessa ci danno 29 = 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 (2512, un numero rappresentabile in decimale con 155 cifre).

Risultato ottenuto dopo 100 iterazioni partendo da una configurazione random.
Risultato ottenuto dopo 100 iterazioni partendo da una configurazione random.

Le regole della vita

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

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).

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.

Implementazione di una macchina di Turing progettata da Paul Rendell, funzionante e caricata nel programma direttamente da un'immagine 1714 x 1647.
Implementazione di una macchina di Turing progettata da Paul Rendell, funzionante e caricata nel programma direttamente da un'immagine 1714 x 1647.

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.

La configurazione Halfmax, scoperta da Jason Summers nel 2005, dove è possibile apprezzare i due differenti colori utilizzati nel programma per le parti statiche e dinamiche.
La configurazione Halfmax, scoperta da Jason Summers nel 2005, dove è possibile apprezzare i due differenti colori utilizzati nel programma per le parti statiche e dinamiche.

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 menu dal quale è possibile selezionare i pattern salvati nella libreria del programma.
Il menu dal quale è possibile selezionare i pattern salvati nella libreria del programma.

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:

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.