Il gioco della vita

di Federico Peiretti

Ai confini tra la matematica e le scienze della natura, nei nuovi spazi di ricerca aperti dal computer, si sta lavorando ad un progetto affascinante: la costruzione di universi artificiali, popolati da "organismi" che possano simulare la vita reale. Si cerca di ricreare la "vita" al computer, una vita artificiale naturalmente, con organismi artificiali, caratterizzati da regole di comportamento sempre più complesse, simili a quelle naturali e dotati di "sensi" che permettano la "conoscenza" del mondo esterno e la trasmissione alle "generazioni" future delle esperienze e delle informazioni acquisite.
Alla base di queste ricerche ci sono gli automi cellulari, costituiti da spazi omogenei divisi in celle elementari, ognuna delle quali, ad intervalli regolari, cambia stato, secondo regole di evoluzione che riguardano la cella stessa e quelle ad essa confinanti.
Come i frattali, anche gli automi cellulari sono universi in miniatura di incredibile complessità, dai quali però si distinguono per la possibilità di subire trasformazioni nel tempo.

John Von Neumann, 1903 - 1957

E’ stata un'idea di John Von Neumann, di una macchina in grado di riprodursi, che ha portato ad una rappresentazione concettuale avente come punto di partenza proprio uno spazio omogeneo diviso in celle elementari.

John Horton Conway

Ad ognuna delle celle viene associato un numero finito di stati, ad esempio, vuoto, oppure occupato, e lo stato di una cella non dipende solo dalla cella stessa, ma anche da quello delle celle confinanti.
Un automa cellulare è quindi formato da una griglia infinita di “cellule” ognuna delle quali, ad intervalli regolari, cambia di stato, secondo un insieme di regole che non riguardano soltanto la singola cella, ma anche quelle limitrofe, venendosi così a trovare in uno degli stati possibili.

Una cellula che si trovi in un particolare stato k, in un determinato istante, all'istante successivo può “mangiare” le cellule adiacenti, che si trovano nello stato k - 1. La regola è simile a quella di una catena alimentare naturale: una cellula nello stato due può mangiare una cellula nello stato uno, mentre questa a sua volta può mangiare una cellula nello stato zero. Se però lo spazio è ciclico la catena non ha fine e ogni cellula può sempre mangiare le cellule adiacenti dello stato precedente. Le regole stabilite da Von Neumann per i suoi automi cellulari erano però molto complicate, richiedevano infatti ben 29 stati diversi.
Un esempio più semplice di automa cellulare è Life, il Gioco della Vita, il più bel gioco inventato in questi ultimi anni o almeno il più importante, a giudicare dalle sue innumerevoli implicazioni scientifiche e dal fascino di una struttura che ancora oggi, matematicamente, non è del tutto definita. Il Gioco della Vita, The Game of Life, è stato inventato nel 1970 da John Horton Conway, il matematico più geniale ed eccentrico, ed è stato reso popolare da Martin Gardner sulla sua pagina di Scientific American.

Scriveva Gardner:

Il gioco rese immediatamente famoso Conway, ma servì anche ad aprire un nuovo campo di ricerca matematica, il campo degli automi cellulari.

All’inizio il gioco venne proposto soltanto nella sua versione “manuale”, che prevedeva semplicemente un foglio di carta quadrettata e una matita con la quale contrassegnare i quadretti secondo le regole del gioco.
Il foglio rappresenta l’Universo a due dimensioni nel quale ogni quadretto, o cella, può avere soltanto due diversi stati: occupato o vuoto, uno o zero.

Si parte da una configurazione iniziale di organismi o celle occupate che evolve nel tempo secondo alcune semplici regole "genetiche", di vita, di morte e di sopravvivenza. Sono regole che non riguardano soltanto la singola cella, ma anche le otto vicine, cioè quelle indicate nella figura a fianco, aventi in comune con questa un lato oppure un vertice:

1) Un organismo sopravvive fino alla generazione seguente se ha due o tre vicini.

2) Un organismo muore, lascia cioè la cella vuota, se ha quattro o più vicini oppure se ne ha soltanto uno o nessuno.

3) Ogni cella vuota con tre vicini diventa una cella di nascita e alla generazione seguente viene occupata da un organismo.

Sono regole semplicissime che portano però a situazioni estremamente complesse. Giustamente è stato battezzato il Gioco della Vita poiché segue, a modo suo, una regola naturale: si muore se si è troppo isolati oppure se c'è un eccessivo sovraffollamento.

In figura è riportato l’esempio di una configurazione con la sua evoluzione alla prima generazione.

generazione 0 generazione 1

A questo punto non resta che provare il gioco, partendo da alcune semplici configurazioni per seguirne il destino nel corso tempo. Specialmente all'inizio, sarà bene fare molta attenzione nel passaggio da una generazione all’altra, procedendo per gradi e segnando dapprima i "nuovi nati", per eliminare solo in un secondo tempo quelli condannati a morte. Per evitare confusione si possono distinguere i vecchi organismi dai nuovi nati con pallini di colore diverso, ad esempio bianchi e neri.
Al posto di carta e matita si può usare una scacchiera con un numero sufficiente di gettoni bianchi e neri, rispettivamente per i nuovi e i vecchi organismi, gettoni che devono essere messi o tolti dalle caselle, secondo le indicazioni date dalle regole del gioco. Il giocatore interviene solo all'inizio, formando una qualsiasi configurazione di partenza comprendente, nel gioco “manuale”, dalle sei alle dodici pedine o celle occupate.

Ma il grande successo del Gioco della Vita è legato al computer, grazie al quale è possibile analizzare rapidamente un gran numero di generazioni successive e situazioni anche complesse con decine, centinaia di organismi nella configurazione iniziale. In questo modo si può ampliare notevolmente la conoscenza teorica del gioco.

Se si vuole rendere competitivo il gioco, si può mettere di fronte due giocatori, ognuno dei quali parte con una configurazione diversa, formata dallo stesso numero di organismi. Vince chi dei due raggiunge il maggior numero di generazioni e riesce a far nascere più organismi.
Riportiamo alcuni esempi di semplici configurazioni con la loro evoluzione nel tempo. I nomi di queste configurazioni sono quelli usati dallo stesso Conway che ha condotto un approfondito studio su questo argomento.

generazione 0 generazione 1 generazione 2

Morte di un trimino (configurazione di tre organismi)

generazione 0 generazione 1 generazione 2 generazione 3

Trimino “lampeggiatore”, con periodo 2

Si può vedere, ad esempio, un trimino, o gruppo di tre organismi, che muore alla seconda generazione e un trimino "lampeggiatore" che oscilla con periodo 2, alternandosi in righe orizzontali e verticali, un tetramino che evolve verso una configurazione detta "alveare" e un tetramino che alla nona generazione diventa un "semaforo".

generazione 0 generazione 1 generazione 2

Tetramino (configurazione di quattro organismi) che diventa un “alveare” alla seconda generazione.


La maggior parte delle configurazioni raggiungono in breve tempo forme stabili oppure oscillanti all'infinito, come l'alveare o il semaforo.

generazione 0 generazione 1 generazione 2 generazione 3 generazione 4
generazione 5 generazione 6 generazione 7 generazione 8 generazione 9

Un tetramino che diventa un “semaforo” alla nona generazione.

Ma le configurazioni più interessanti sono quelle imprevedibili come l'"aliante", che dopo quattro generazioni ritorna alla forma originale, abbassata però, in diagonale, di una cella. Si tratta quindi di una configurazione che "si muove" nell'universo del Gioco della Vita.

generazione 0 generazione 1 generazione 2 generazione 3 generazione 4

L’”aliante” che, dopo quattro generazioni, ritorna alla forma primitiva, abbassandosi, in diagonale, di un quadretto.

generazione 0 generazione 1 generazione 2 generazione 3 generazione 4

Un quadrimino che in quattro generazioni arriva a una forma stabile, chiamata lo “stagno”. E’ indicato il procedimento di costruzione di ogni generazione, partendo dalla generazione che la precede. I vecchi e i nuovi organismi vengono distinti con pallini rispettivamente bianchi e neri.

Conway riteneva, all’inizio della sua ricerca, che non esistessero configurazioni in grado di produrre un numero infinito di organismi e mise anche in palio un premio di 50 dollari per chi fosse riuscito a dimostrare il contrario.

Un “cannone” che spara “alianti” in azione.

La prima di queste configurazioni, battezzata il “cannone”, venne scoperta da un gruppo di giovani ricercatori del MIT. Si tratta di un oscillatore stazionario che ogni trenta generazioni "spara" un aliante il quale incomincia, come abbiamo detto, a spostarsi nello spazio. Si tratta quindi proprio di una configurazione che cresce all'infinito.

Sono chiamate Giardini dell’Eden le configurazioni “senza padre”, cioè le configurazioni, come quella di figura, che non derivano da alcun’altra configurazione precedente. Le possiamo quindi ritrovare soltanto come generazione 0.

E' possibile sviluppare il Gioco della Vita con caselle di forma diversa, ad esempio si chiama Hexlife il gioco con caselle esagonali oppure nelle tre dimensioni, con organismi che sono cubetti, in relazione fra loro secondo regole analoghe a quelle degli organismi in due dimensioni, oppure si può studiare l’Universo a una sola dimensione, con una striscia di celle che seguendo, anche in questo caso, alcune semplici regole matematiche producono modelli di grande interesse scientifico.

Le configurazioni studiate al computer sono sempre più complesse. Il “Ciclotrone” di figura, ad esempio, è una configurazione con periodo 874, si ripete cioè identica dopo 874 generazioni. Si tenga presente che ogni puntino rappresenta un organismo.

Il Gioco della Vita può essere considerato il più semplice degli automi cellulari. Anche il gioco degli scacchi può essere considerato un antenato degli automi cellulari mentre, all'estremo opposto, come livello di complessità. Ed anche l'universo si potrebbe immaginare come un enorme automa cellulare di cui noi stessi non siamo che pedine controllate da un computer gigantesco e infinitamente complesso.
Gli automi cellulari osservano regole fisse nel tempo. Se si introducono invece strategie variabili che possono cambiare seguendo l'evoluzione del sistema, si passa a quelli che si chiamano modelli evolutivi. Ne sono un esempio i Giochi cellulari di Norman Packard, modelli evolutivi in cui il giovane ricercatore dell'Illinois ha introdotto una nuova variabile: il cibo, che gli organismi devono cercare di procurarsi per riuscire a sopravvivere e a riprodursi. Gli organismi inoltre possono "vedere" i propri vicini e sapere quanto cibo esiste in una determinata zona, modificando sulla base delle informazioni acquisite il proprio comportamento. Tali informazioni vengono poi passate alla generazione successiva.
"Non abbiamo ancora trovato - dice Packard - delle configurazioni belle e attraenti come quelle del Gioco della Vita, ma ci arriveremo presto, e il nuovo gioco sarà ancora più bello".

"Stiamo assistendo alla nascita di un nuovo mondo artificiale - afferma ancora Norman Packard, dell'Università dell'Illinois a Urbana - un mondo che potrà insegnarci qualcosa in più sulla vita, sulla sua origine e sulla sua evoluzione, anche se siamo ancora agli inizi e per ora i modelli che riusciamo a costruire sono molto semplici; sono organismi piuttosto stupidi, ma la rapida evoluzione dei computer, sempre più veloci e più potenti, ci permetterà sicuramente di produrre mondi sempre più ricchi. Sono mondi artificiali che potranno integrare il mondo naturale, anche se non esiste ancora una teoria globale per questi processi creativi e questo significa che non sappiamo ancora bene che cosa stiamo cercando né dove stiamo andando".
In particolare Packard ha utilizzato gli automi cellulari per una simulazione al computer dei fiocchi di neve.
"Dubito - dice invece Roberto Livi dell'Università di Firenze - che si possa parlare di vita artificiale. Non dico che questa sia impossibile, ma sicuramente oggi non è proponibile l'idea di un computer dotato di libero arbitrio, la sua realizzazione non è concepibile con i modelli che abbiamo a disposizione".
Giocando con carta e matita, oppure al computer, anche il lettore, provando nuove configurazioni, potrà fare interessanti scoperte in un campo, come dicevamo ancora tutto da definire: questo è proprio il grande fascino del Gioco della Vita, l'universo nel quale vi invitiamo ad entrare.

Federico Peiretti

In rete

http://www2.polito.it/didattica/polymath/htmlS/Interventi/Articoli/Conway/Conway.htm
John Horton Conway e il gioco della matematica, un articolo di Federico Peiretti.

http://www2.polito.it/didattica/polymath/htmlS/info/BIBLIOID/Conway.htm
La recensione di Il libro dei numeri di John H. Conway e Richard K. Guy, Hoepli, 1999

http://www.bitstorm.org/gameoflife/
Per giocare on line.

http://www.scienzanuova.it/numeri/n08/n08_074.htm
La Matematica della Vita di Piergiorgio Odifreddi (Scienza Nuova, novembre 1998).

http://www2.polito.it/didattica/polymath/htmlS/Interventi/Articoli/Conway/Conway.htm
Un ritratto di Conway, che riporta la sua tecnica per calcolare a quale giorno della settimana corrisponda una qualsiasi data, Doomsday, e un altro suo gioco, Germogli.

http://www.mediamente.rai.it/mediamentetv/learning/corsi/9912c2_1.asp
Introduzione all’Intelligenza Artificiale di Fabio Ciotti (mediamente Learning Center)

http://alpha01.dm.unito.it/personalpages/cerruti/Az1/giocolife.html
La presentazione di Life alle pagine di Umberto Cerruti.

http://www.itportal.it/developer/algoritmi/giocovita/
Il programma per Life
http://www.itportal.it/developer/cpp/automa/
E il programma per un automa cellulare.

http://psoup.math.wisc.edu/Life32.html
Ancora un programma per Life scaricabile dalla rete.

http://radicaleye.com/lifepage/
La pagina di Paul Callahan, tutto su Life con molte configurazioni spettacolari. E’ il punto di partenza per lo studio di Life.

http://dmoz.org/Computers/Artificial_Life/Cellular_Automata/Conway's_Game_of_Life/
I più importanti collegamenti alle pagine di Life.

http://www.brunel.ac.uk/depts/AI/alife/al-gamel.htm
La presentazione del gioco e la storia degli automi cellulari.

http://www.math.com/students/wonders/life/life.html
Per iniziare. Life con numerosi applet .

http://psych.hanover.edu/JavaTest/Play/Life.html
Create la vostra configurazione e divertitevi a vedere come si evolve.

http://www.collidoscope.com/cgolve/
Life a colori. Spettacolare!

http://hensel.lifepatterns.net/
L’applet di Alan Hensel

http://www.argentum.freeserve.co.uk/lex.htm
Life Lexicon di Stephen Silver, per imparare tutti i termini del gioco.

http://entropymine.com/jason/life/
Centinaia di divertenti configurazioni a cura di Jason Summers.

http://hensel.lifepatterns.net/october1970.html
Un articolo storico del 1970. La presentazione di Life di Martin Gardner su Scientific American.

http://www.ics.uci.edu/~eppstein/ca/
La pagina di David Eppstein

http://www.brunel.ac.uk/depts/AI/alife/al-snowf.htm
I fiocchi di neve di Norman Packard.

http://sjsu.rudyrucker.com/~gauri.nadkarni/applet/
Applet per i fiocchi di neve artificiali, su una griglia esagonale.

http://www.santafe.edu/~wuensch/multi_value/dd_life.html
Life nelle versioni su griglia esagonale e nelle tre dimensioni.

http://www.well.com/~dgb/hexlife.html
Applet per Hexlife

http://alife.fusebox.com/
Esempi di vita artificiale del web
http://surf.de.uu.net/zooland/
Un’ampia rassegna delle risorse in rete di Vita Artificiale

http://plus.maths.org/issue20/features/conway/index.html
La vita, il Gioco della Vita e i Marziani in un’intervista di Rachel Thomas a John Conway su PLUS, la più bella rivista di matematica divulgativa in rete.

In libreria

Manfred Eigen, Ruthild Winkler, Il Gioco, le leggi naturali governano il caso, pag. 163 – 179, Adelphi, 1986.

Ivars Peterson, Il turista matematico, pp.233 – 254, Rizzoli, 1991.

Florence Scovel Shinn, The Game of Life and How to Play It, pp. 96, The C.W. Daniel Company Ltd, 1999.

Christoph Adami, Introduction to Artificial Life, pp. 374, Telos Pr, 1997.

Stephen Wolfram, Cellular Automata and Complexity: Collected Papers, pp. 596, Perseus Publishing, 1998.