De regles simples a la gran complexitat: el Joc de la Vida
Com quatre regles elementals poden donar lloc a un univers sorprenent
Un univers governat per només quatre regles
Imaginem un univers molt senzill. No hi ha persones, animals, planetes ni objectes. Només una quadrícula formada per cel·les.
Cada cel·la només pot tenir dos estats: viva o morta.
I tot el que passa en aquest univers està governat per quatre regles molt simples.
Aquesta és la idea que hi ha darrere del Joc de la Vida, un autòmat cel·lular ideat pel matemàtic britànic John Horton Conway a finals de la dècada de 1960 i popularitzat el 1970.
Malgrat el seu nom, no és pròpiament un joc: no hi ha jugadors, ni puntuació, ni una manera de guanyar. El jugador només decideix la configuració inicial. A partir d'aquí, el sistema evoluciona tot sol.
I és precisament això el que el fa interessant.
Com poden unes regles extremadament simples generar comportaments sorprenentment complexos?
Les quatre regles del Joc de la Vida
Cada cel·la està envoltada per vuit cel·les veïnes. A cada generació, el seu estat futur depèn únicament de quantes d'aquestes veïnes estan vives.
- Una cel·la viva amb menys de dues veïnes vives mor, com si fos per solitud.
- Una cel·la viva amb dues o tres veïnes vives continua viva.
- Una cel·la viva amb més de tres veïnes vives mor, com si fos per sobrepoblació.
- Una cel·la morta amb exactament tres veïnes vives torna a la vida, com si es produís un naixement.
No hi ha cap regla més.
Cada cel·la només observa el seu entorn immediat i aplica aquestes instruccions.
Es tracte, doncs, del que es coneix com atòmat cel·lular.
Quin era el propòsit de Conway?
Conway no intentava reproduir fidelment la vida biològica.
El repte era molt més abstracte: trobar un sistema amb unes regles tan simples com fos possible que, al mateix temps, no tingués un comportament trivial.
Si les regles fossin massa restrictives, totes les cel·les acabarien morint. Si fossin massa permissives, la quadrícula s'ompliria ràpidament sense produir estructures interessants.
Conway buscava una situació intermèdia: un sistema capaç de produir estabilitat, canvi, moviment i comportaments difícils de predir.
La pregunta de fons era extraordinàriament suggeridora:
Quanta complexitat pot sorgir d'un conjunt mínim de regles?
De simples punts a estructures
Quan es posa en funcionament el Joc de la Vida, moltes configuracions desapareixen ràpidament, però d'altres evolucionen cap a formes sorprenents. Algunes queden completament immòbils. Són els anomenats still lifes o estructures estables, altres repeteixen periòdicament una seqüència de formes. Són els oscil·ladors i algunes fins i tot es desplacen per la quadrícula.
El cas més conegut és el glider, una petita configuració de només cinc cel·les que canvia de forma a cada generació i acaba avançant diagonalment.
No existeix cap regla que digui que una figura s'ha de moure. El moviment simplement emergeix de les quatre regles inicials.
El Gosper Glider Gun
Durant els primers estudis del Joc de la Vida, Conway es va preguntar si una configuració finita podia créixer indefinidament. El 1970, un grup dirigit per Bill Gosper va trobar una resposta espectacular: el Gosper Glider Gun.
Es tracta d'una configuració que produeix gliders periòdicament. Els gliders s'allunyen, mentre l'estructura principal continua generant-ne de nous. Per primera vegada es disposava d'una configuració finita capaç de generar activitat indefinidament.
Aquest descobriment va demostrar que aquell petit univers de quadradets blancs i negres tenia moltes més possibilitats de les que semblava.
El concepte d'emergència
El Joc de la Vida és un dels exemples més elegants del fenomen que anomenem emergència.
Una propietat emergent és un comportament global que no està explícitament programat en les regles individuals del sistema. Cada cel·la només sap una cosa: quantes veïnes vives té.
No sap què és un glider, ni sap què és un oscil·lador i tampoc sap en quina direcció s'està movent una estructura. Però, tanmateix, quan milions de decisions locals interactuen, apareixen comportaments globals organitzats.
Aquesta mateixa idea apareix en molts sistemes complexos: colònies d'insectes, xarxes neuronals, ecosistemes, trànsit, mercats o processos socials.
Un ordinador construït amb cel·les
La sorpresa encara va més lluny.
Els gliders poden utilitzar-se per transportar informació. Fent-los col·lidir adequadament es poden construir estructures equivalents a portes lògiques.
Amb prou portes lògiques és possible construir memòria, comptadors i circuits.
El Joc de la Vida és un sistema amb capacitat de computació universal: en principi, es pot construir dins seu una màquina capaç d'efectuar qualsevol càlcul computable, sempre que disposi de prou espai i temps.
És una idea extraordinària.
Un univers governat per només quatre regles pot contenir, dins seu, un ordinador.
Determinista, però difícil de predir
El Joc de la Vida és completament determinista. Si coneixem la configuració inicial, no hi ha atzar: cada generació queda determinada de manera exacta per l'anterior. Però això no significa que sigui fàcil predir-ne el futur.
En configuracions complexes, la manera més pràctica de saber què passarà després de moltes generacions és, sovint, deixar que el sistema evolucioni i observar-ne el resultat.
Aquesta diferència entre determinisme i predictibilitat és una de les idees més interessants que ens deixa el Joc de la Vida.
Conèixer perfectament les regles d'un sistema no implica necessàriament poder anticipar fàcilment el seu comportament.
Una lliçó sobre la complexitat
El Joc de la Vida és només una quadrícula de cel·les que s'encenen i s'apaguen.
Però d'aquest mecanisme elemental apareixen estabilitat, oscil·lació, moviment, creixement, transmissió d'informació i computació. No cal programar explícitament cadascun d'aquests comportaments. Només cal establir unes poques regles locals i deixar que interactuïn.
Potser aquesta és la lliçó més fascinant del Joc de la Vida:
La complexitat no sempre necessita regles complexes. De vegades, unes regles molt simples repetides moltes vegades són suficients per crear un univers extraordinàriament ric.
Per experimentar
Una de les millors maneres d'entendre el Joc de la Vida és provar-lo.
Hem creat una petita simulació interactiva que permet dibuixar les cel·les inicials, iniciar i aturar l'evolució i carregar alguns dels patrons clàssics, com el blinker, el glider o el Gosper Glider Gun.
SIMULADOR INTERACTIU:
Com fer anar el widget:
- ▶ Reprodueix / ⏸ Pausa — engega o atura la simulació.
- ⏭ Pas — avança una sola generació.
- ⟲ Aleatori — genera un tauler nou a l'atzar.
- ✕ Neteja — buida el tauler perquè hi dibuixis a mà.
- Selector de patró — carrega un patró clàssic (planador, pulsar, canó de Gosper...).
- Clic sobre la graella — encén o apaga cel·les una a una.
L'algorisme en Python
import time
# *********************** INPUTS ***********************************************
files = 15
columnes = 30
generacions = 30
retard = 0.3
# Patró inicial: un "glider"
celules_vives = [
(1, 2),
(2, 3),
(3, 1),
(3, 2),
(3, 3)
]
# *****************************************************************************
# *********************** CreaTauler ******************************************
def CreaTauler():
tauler = []
for y in range(files):
fila = []
for x in range(columnes):
if (y, x) in celules_vives:
fila.append(1)
else:
fila.append(0)
tauler.append(fila)
return tauler
# *****************************************************************************
# *********************** ComptaVeines ****************************************
def ComptaVeines(tauler, y, x):
veines = 0
for dy in [-1, 0, 1]:
for dx in [-1, 0, 1]:
if dy == 0 and dx == 0:
continue
ny = y + dy
nx = x + dx
if 0 <= ny < files and 0 <= nx < columnes:
veines += tauler[ny][nx]
return veines
# *****************************************************************************
# *********************** NovaGeneracio ***************************************
def NovaGeneracio(tauler):
nou_tauler = []
for y in range(files):
nova_fila = []
for x in range(columnes):
veines = ComptaVeines(tauler, y, x)
if tauler[y][x] == 1:
# Cel·la viva:
# sobreviu només amb 2 o 3 veïnes
if veines == 2 or veines == 3:
nova_fila.append(1)
else:
nova_fila.append(0)
else:
# Cel·la morta:
# neix si té exactament 3 veïnes
if veines == 3:
nova_fila.append(1)
else:
nova_fila.append(0)
nou_tauler.append(nova_fila)
return nou_tauler
# *****************************************************************************
# *********************** MostraTauler ****************************************
def MostraTauler(tauler, generacio):
print("\033[H\033[J", end="")
print("Generació:", str(generacio))
print()
for fila in tauler:
for celula in fila:
if celula == 1:
print("██", end="")
else:
print(" ", end="")
print()
# ******************************************************************************
# ************************* MAIN ***********************************************
tauler = CreaTauler()
for generacio in range(generacions):
MostraTauler(tauler, generacio)
tauler = NovaGeneracio(tauler)
time.sleep(retard)
print("--FET--")
# ******************************************************************************
El Joc de la Vida i la màquina de Turing
Una de les propietats més sorprenents del Joc de la Vida és que no només pot generar estructures que es mouen o oscil·len. També pot realitzar càlculs.
El Joc de la Vida és Turing-complet. Això significa que, en principi, pot executar qualsevol càlcul que pugui executar una màquina de Turing, sempre que disposi de prou espai i de prou temps.
Una màquina de Turing és un model teòric d'ordinador proposat per Alan Turing el 1936. Consisteix, de manera simplificada, en una cinta dividida en caselles, un capçal capaç de llegir i escriure símbols i un conjunt de regles que indiquen què ha de fer la màquina en cada situació.
La importància d'aquest model és que permet definir matemàticament què significa computar.
En el Joc de la Vida no tenim cap processador, ni memòria RAM, ni instruccions convencionals. Només tenim cel·les que neixen i moren segons l'estat de les seves veïnes.
Però els patrons mòbils, especialment els gliders, poden utilitzar-se per transportar informació. Fent-los interactuar de manera adequada es poden construir portes lògiques, com AND, OR o NOT. I combinant portes lògiques es poden construir circuits, memòria i, finalment, un ordinador complet.
Per tant, dins d'una quadrícula governada només per quatre regles podem construir una màquina capaç d'executar programes.
El Joc de la Vida no està programat per calcular. La capacitat de computació apareix com una conseqüència de les seves regles.
Aquesta és probablement una de les demostracions més espectaculars de la idea central del Joc de la Vida: unes regles molt simples poden generar un sistema amb una complexitat pràcticament il·limitada.
Curiositats
Conway jugava amb un tauler de Go
Abans de disposar d'un programa d'ordinador, John Conway estudiava les primeres evolucions del Joc de la Vida a mà, utilitzant un tauler de Go i les seves pedres per representar les cel·les.
El procediment era lent i fàcilment podia donar lloc a errors. Poc després van aparèixer les primeres implementacions informàtiques, que permetien seguir centenars o milers de generacions automàticament.
Una aposta de 50 dòlars que Conway va perdre
Conway es preguntava si alguna configuració inicial formada per un nombre finit de cel·les podria créixer indefinidament. Va arribar a oferir 50 dòlars a qui resolgués el problema.
El mateix 1970, Bill Gosper i un grup de programadors del MIT van trobar el famós Gosper Glider Gun: una estructura estable que genera gliders periòdicament i, per tant, produeix activitat indefinidament.
Conway va haver de pagar el premi.
La història del repte ja apareix en l'article de Martin Gardner publicat a Scientific American l'octubre de 1970.
Un passatemps per als primers programadors
La publicació de l'article de Gardner va despertar un enorme interès entre matemàtics i programadors. El Joc de la Vida es va convertir ràpidament en un programa ideal per experimentar amb els ordinadors de l'època: les regles eren senzilles de programar, però els resultats podien mantenir la màquina calculant durant hores.
Fins i tot circula la llegenda que una quantitat considerable del temps disponible en alguns ordinadors universitaris dels anys setanta es dedicava a executar simulacions del Joc de la Vida. És difícil quantificar-ho, però il·lustra perfectament la fascinació que va provocar.
Del laboratori al microordinador
El Joc de la Vida també va arribar molt aviat als primers microordinadors personals.
El juny de 1976, la revista informàtica Byte va dedicar la seva portada al Joc de la Vida, mostrant una implementació gràfica en color.
En pocs anys, aquell experiment matemàtic que Conway havia començat movent pedres sobre un tauler de Go s'havia convertit en un dels programes clàssics de la primera cultura informàtica.
Conclusió
El Joc de la Vida demostra que la complexitat no necessita necessàriament regles complexes. Amb només quatre normes elementals apareixen estructures estables, oscil·ladors, moviment, transmissió d'informació i fins i tot computació.
És un sistema completament determinista, però capaç de produir comportaments difícils de predir. I aquesta és probablement la seva gran lliçó: conèixer les regles d'un sistema no significa que sigui fàcil anticipar-ne totes les conseqüències.
De vegades, unes poques regles simples són suficients per crear un univers extraordinàriament complex.
Referències
- Martin Gardner. Mathematical Games: The fantastic combinations of John Conway's new solitaire game "Life". Scientific American, octubre de 1970.
- Berlekamp, Conway i Guy. Winning Ways for Your Mathematical Plays.
- LifeWiki: enciclopèdia especialitzada en patrons i propietats del Joc de la Vida.
- El mítico 'juego de la vida' del matemático John Conway sigue siendo uno de los problemas clásicos de programación 50 años después
- El juego de la vida: una interpretación basada en el contagio de la euforia durante la formación de burbujas especulativas
- La complejidad matemática del “juego de la vida”
- Play the Game of Life online, a single player game invented in 1970 by Cambridge mathematician John Conway.
Bibliografia
- Conway's Game of Life - Trabajo fin de Grado
- El juego de la vida.Drama en tres actos para el aula de matemáticas
Videos
- Life, Death and the Monster (John Conway) - Numberphile
- ¿Conoces el juego de la vida de Conway?
- El Juego de la Vida de Conway - Academia Calculus
- A Collection of all Gliders I know of | Volume Ⅰ | Conway's Game of Life
- El juego de la vida de Conway
Podcast
El Joc de la Vida mostra com unes poques regles locals poden generar estructures i comportaments d'una complexitat sorprenent.