Göm menyn

Game of Life

Game of life är en cellulär automat som konstruerades av matematikern John Conway, 1970.

Det är ett spel för 0 spelare som spelas på ett oändligt rutat papper. Varje ruta (cell) kan vara död (vit) eller levande (svart). Varje gång klockan tickar föds eller dör några celler, enligt särskilda regler.

Cellulära automater är diskreta matematiska modeller som till exempel kan användas för att studera fenomen i kaotiska system, eller bara för att de är roliga att titta på.

Regler

  • En levande cell med 0-1 levande grannar dör av ensamhet.
  • En levande cell med 4-8 levande grannar dör av trängsel.
  • En död cell med 3 levande grannar återföds.
  • Alla övriga celler är oförändrade.

Mönster

Genom att studera Game of Life har man upptäckt återkommande mönster i alla storlekar. De större är flera tusen celler breda och höga.

Stabila

Följande är ett "block". Varje död/vit cell har högst 2 levande/svarta grannar, så de förblir döda. Varje levande cell har 3 levande grannar, så de förblir levande. Inget förändras.

Block

Följande är en "bikupa". Som ovan finns det ingen levande cell med 0-1 levande grannar (ingen dör), och ingen död cell med 3 levande grannar (ingen återföds). Inget förändras.

Bikupa

Oscillerande

Här appliceras exakt samma regler som ovan, men på annorlunda indata. För dessa indata får vi ett repeterande mönster i 2 (blinker) respektive 3 (pulsar) steg.

Blinker

Pulsar

Rymdskepp

Här har vi en seglare och ett lätt rymdskepp. Dessa mönster repeterar sig själva på ett sätt som gör att de ständigt flyttar sig, snett respektive rakt.

Seglare

Lätt rymdskepp

Fördjupning (frivillig)

Game of Life är en två-dimensionell cellulär automat. Det finns även automater med andra antal dimensioner.

En-dimensionell cellulär automat

Principen är att vi har en rad med celler, till skillnad från det tvådimensionella "spelbrädet" vi hade i Game of Life.

För varje "tick" uppdateras varje cell beroende på det gamla tillståndet för cellen själv och dess två grannar. Det finns 8 sådana tillstånd:

  • levande, LEVANDE, levande (till vänster, "jag själv", till höger)
  • levande, LEVANDE, död
  • ...
  • död, DÖD, död

Detta är alltså de indata som ska avgöra om en viss cell fortsätter leva, dör, fortsätter vara död, eller återföds. Men vilken regel ska vi applicera? I Game of Life var ju regeln "om jag har 0-1 eller 4-8 levande grannar dör jag, om jag har 3 levande grannar återföds jag, annars ändras inget". Vilken regel gäller för de 1-dimensionella automaterna?

Det har vi faktiskt inte bestämt. Game of Life är namnet på en av väldigt många tänkbara tvådimensionella automater. Här har vi också många tänkbara endimensionella automater, beroende på exakt hur vi väljer att konstruera vår uppdateringsregler.

Så hur många tänkbara uppdateringsregler finns det? Ja, om vi håller oss till att en cell bara påverkas av de omedelbara grannarna, finns det alltså 8 olika input till regeln. För vart och ett av dessa inputs kan regeln välja att cellen i nästa steg ska vara död eller levande. Det finns alltså 8 oberoende val att göra, och varje val har 2 alternativ. Det blir 2^8 = 256 tänkbara regler som man kan välja att använda. Här är det viktigt att inse att man i varje automat bara väljer en av dessa 256, och sedan applicerar den konsistent steg för steg.

Reglerna är har en standardiserad numrering. Regel 1 säger till exempel att alla mönster leder till att cellen dör. Nedan ser vi exempel på flera intressanta regler.

Övre raden i varje regel visar de 8 olika inputs man kan ha, från levande-levande-levande till död-död-död. Undre raden visar vad regeln bestämmer att mittencellen ska bli efter att regeln har applicerats. Regel 30 säger t.ex. att levande-levande-levande leder till att mittencellen dör, medan levande-död-död leder till att mittencellen återföds.

Regler

Vi kan också visa vad olika regler ger upphov till, steg för steg, om man applicerar dem i ett starttillstånd med en enda levande cell. Istället för att animera detta, som vi gjorde ovan, visar vi nu 20 steg ("generationer") där varje steg är en separat rad. Det blir alltså en tvådimensionell bild där y-dimensionen egentligen motsvarar tid. Själva automaten är fortfarande 1-dimensionell.

Resultat

Vissa regler skapar fraktaler (till exempel Sierpinski-trianglar) och vissa mönster som skapas har hittats i naturen, bland annat på snäckskal.

Cellulär automat i naturen

Videor

Game of Life-magi

Metapixel i Game of Life

Bildkällor

http://mathworld.wolfram.com/ElementaryCellularAutomaton.html

http://www.aimfeld.ch/cellmorphs/cellmorphs.html

https://en.wikipedia.org/wiki/Conway's_Game_of_Life


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2021-12-03