Joc de la vida

El joc de la vida és un autòmat cel·lular dissenyat pel matemàtic britànic John Horton Conway el 1970.

Pistola de planadors de Bill Gosper (Glider Gun).

De fet, el joc és de zero jugadors, és a dir, la seva evolució queda determinada tan sols pel seu estat inicial, sense que es necessiti cap mena d'interacció amb jugadors humans. La forma de jugar al joc de la vida és mitjançant la configuració del seu estat inicial, i observant com evoluciona. Existeix una variant on dos jugadors competeixen entre ells.

Regles

L'univers del joc de la vida és una malla ortogonal bidimensional infinita (exemple: una taula o matriu), de cel·les individuals, cadascuna de les quals té dos estats possibles: viu o mort. Cada cel·la interacciona amb els seus vuit veïns, que són les cel·les a què està connectada horitzontalment, verticalment o diagonalment. A cada unitat de temps, es donen les següents transicions:

1. Tota cel·la viva amb menys de dos veïns vius mor (de solitud).
2. Tota cel·la viva amb més de tres veïns vius mor (de sobreconcentració).
3. Tota cel·la viva amb dos o tres veïns vius, segueix viva per a la següent generació.
4. Tota cel·la morta amb exactament tres veïns vius torna a la vida.

Aquest patró inicial constitueix la llavor del sistema. La primera generació és creada aplicant aquestes regles simultàniament a totes les cel·les de la malla. Les regles es continuen aplicant repetidament per crear futures generacions.

Origen

Conway estava interessat en un problema presentat els anys 40 pel matemàtic John von Neumann, que intentava trobar una màquina hipotètica que pogués construir còpies d'ella mateixa. Va aconseguir trobar un model matemàtic amb regles molt complexes sobre una malla amb coordenades cartesianes. Conway va intentar simplificar les idees de Von Neumann, i de fet ho va aconseguir. Unint el seu èxit en el problema de Leech de teoria de grups amb el seu interès en les idees de Von Neumann, Conway va donar llum al Joc de la vida.

Va aparèixer per primer cop a l'octubre de 1970, en un article del Scientific American, a la columna de Martin Gardner de Jocs matemàtics. Des d'un punt de vista teòric, el joc resulta molt interessant, perquè té la capacitat d'una Màquina de Turing universal; és a dir, tot el que pot ser computat algorísmicament pot ser computat amb un joc de la vida. Gardner va escriure:

«

El joc va fer famós a l'instant Conway, però també va obrir una nova branca en la investigació matemàtica, el camp dels autòmats cel·lulars (...) Per l'analogia del joc de la vida amb el naixement, caiguda i alteracions de la societat amb els organismes vius, pertany a una classe emergent del que s'anomenen jocs de simulació (jocs que s'assemblen a processos de la vida real).

»

Des de la seva publicació, ha atret molt d'interès per les maneres sorprenents com poden evolucionar els patrons. El joc de la vida és un exemple d'autoorganització. Resulta interessant per a moltes branques de la ciència, inclosa la física, la biologia, l'economia, les matemàtiques o la filosofia, i d'altres ciències que observen la manera en què regles molt senzilles poden generar patrons complexos.

Segurament va ajudar a la seva popularitat el fet que el joc de la vida sorgís coincidint amb l'aparició d'una nova generació d'ordinadors barats, fet que possibilitava que el joc podia desenvolupar-se durant hores en aquestes màquines, que d'altra manera quedaven sense utilitzar durant la nit. Pel que fa a aquest aspecte, la seva popularitat va ser molt superior a la que despertaria més endavant la generació per ordinador de fractals. Per a molts aficionats, el joc de la vida era simplement un repte de programació, una manera de malgastar cicles de CPU. Per altres, el joc tenia més connotacions filosòfiques. Va esdevenir objecte de culte en els anys 70 i més endavant; desenvolupament actuals han arribat a crear emulacions teòriques de sistemes d'ordinador en els límits d'un tauler del joc de la vida.

Conway va escollir les regles amb cura, després de molta experimentació, per complir tres criteris:

1. No hi hauria d'haver un patró inicial pel que existeixi una prova simple que la població pot créixer indefinidament.
2. Hi hauria d'haver patrons inicials que aparentment creixin sense límit.
3. Hi hauria d'haver patrons inicials simples que creixin i canviïn per un període considerable de temps abans de finalitzar de les següents maneres possibles:

   • Esvaint-se completament (per sobreconcentració o per arribar a dispersar-se en excés).
   • Entrant en una configuració estable que romangui sense canvis, o entrant en una fase oscil·latòria en què es repeteix un cicle sense fi de dos o més períodes.

Exemples de patrons

L'evolució i moviment d'un planador (glider).

Hi ha molts tipus diferents de patrons en el joc de la vida, incloent patrons estàtics, patrons que es repeteixen o oscil·latoris, i patrons que es mouen al llarg de la malla (naus). Els exemples més simples de cadascuna de les tres classes es mostren a baix, amb el conveni habitual de mostrar les cel·les vives en negre i les mortes en blanc.

Bloc	Barca	Pampallugador	Gripau	Planador	Nau lleugera
Block	Boat	Blinker	Toad	Glider	LWSS

El "bloc" i la "barca" són patrons estàtics vius, el "pampallugador" i el "gripau" són oscil·ladors, i el "planador" i la "nau lleugera" són naus.

Els patrons anomenats "Matusalems" (Methuselah) poden evolucionar durant llargs períodes abans de repetir-se. "Diehard" és un patró que desapareix després de 130 passos, mentre que "Acorn" triga 5206 generacions a estabilitzar-se, i en aquest temps genera 25 planadors.

Diehard	Acorn

Al principi, Conway va conjecturar que cap patró podia créixer indefinidament, és a dir, que per cada configuració inicial de cel·les vives, la població no podia créixer per sobre d'una determinada cota superior. En la primera presentació del joc, a Mathematical Games, Conway va oferir un premi de 50$ per a la primera persona que pogués demostrar la certesa o falsedat de la conjectura abans de finals de 1970. Una manera de demostrar que la conjectura era falsa seria descobrint patrons que contínuament afegeixen comptadors a la malla: una "pistola", que seria una configuració que dispara repetidament objectes com el "planador", o el "tren", una configuració que es mogués deixant darrere una marca de "fum".

El premi va ser guanyat el novembre d'aquell mateix any per un equip del Massachusetts Institute of Technology, liderat per Bill Gosper; la "pistola de Gosper" (Gosper Gun), mostrada a sota, produeix el primer planador en la 15a generació, i un altre planador cada 30 generacions. Aquesta primera pistola de planadors és encara la més petita coneguda avui en dia.

Gosper Glider Gun

Més tard, es van trobar patrons més simples que també creixien indefinidament. Els tres patrons següents ho fan: els dos primers creen un mecanisme de blocs, i el tercer en crea dos. El primer només té 10 cel·les vives (s'ha demostrat que és la mínima quantitat necessària). La segona cap en una malla de 5x5. La tercera només té una cel·la d'alçada.

Emblema furoner

El planador (glider) del Joc de la Vida

El símbol del planador va ser proposat com a emblema furoner per Eric S. Raymond a l'octubre de 2003, i ha estat àmpliament acceptat com a tal. Els motius per escollir aquest símbol com a emblema foren els següents:

• El Joc de la vida va néixer a la dècada dels 1970, quasi al mateix temps que Internet i Unix, i va fascinar els furoners des d'aleshores.
• En el Joc de la vida, existeixen regles simples de cooperació amb el qual és proper, que porten a resultats inesperats, d'una complexitat enorme, imprevisible amb el simple anàlisis de les regles. Aquest fet sembla paral·lel a la forma com emergeixen els fenòmens com el desenvolupament del programari lliure en la comunitat furonera.
• Reuneix els requisits per ser un bon logo: és senzill, marcat, difícil de confondre amb alguna altra cosa, i fàcil de marcar en una tassa o en una samarreta. A més, pot ser modificat, combinat amb altres elements, o simplement utilitzat com a fons.

Enllaços externs

• Pàgina principal del Joc de la vida, amb un applet per jugar-hi online. (anglès)
• A Turing Machine in Conway's Game of Life - Descriu la implementació d'una màquina de Turing a partir dels patrons del Joc de la vida. (anglès)
• Game of Life on JavaScript