Joc de la vida

De Viquipèdia
Dreceres ràpides: navegació, cerca
Pistola de planadors de Bill Gosper (Glider Gun).

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

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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, incloent 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[modifica | modifica el codi]

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 abaix, amb el conveni habitual de mostrar les cel·les vives en negre i les mortes en blanc.

 Bloc     Barca     Pampallugador     Gripau     Planador     Nau lleugera   
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 
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 15ena generació, i un altre planador cada 30 generacions. Aquesta primera pistola de planadors és encara la més petita coneguda avui en dia.

Glider gun
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.

Patró que creix indefinidament     Patró que creix indefinidament en una malla de 5x5

Patró d'una cel·la d'alçada que creix indefinidament

Emblema hacker[modifica | modifica el codi]

El planador (glider) del Joc de la Vida

El símbol del planador va ser proposat com a emblema hacker 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 en la dècada dels 1970, quasi al mateix temps que Internet i Unix, i ha fascinat els hackers des d'aleshores.
  • En el Joc de la vida, existeixen regles simples de cooperació amb el que és proper, que porten a resultats inesperats, d'una complexitat enorme, imprevisible amb el simple anàlisis de les regles. Aquest fet sembla ser paral·lel a la forma com emergeixen els fenòmens com el desenvolupament del programari lliure en la comunitat hacker.
  • 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[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Joc de la vida