Conways Livsspil (ofte kaldet Game of Life) er en robotspil (cellular automaton), som blev skabt af den britiske matematiker John Horton Conway i 1970.

Navnet "spil" kommer af, at man kan opstille forskellige startkonfigurationer (mønstre) og se, hvordan de udvikler sig over tid efter faste regler. Det er dog et nulspiller-spil: når startkonfigurationen er givet, udvikler systemet sig automatisk uden yderligere indblanding. Mange studerer netop, hvordan små ændringer i startopsætningen kan give meget forskellige langtidsadfærd.

Regler

Livets spil foregår på et todimensionelt gitter af kvadrater (celler). Hver celle kan være enten levende eller død. Opdateringen sker i diskrete tidssteg, og alle celler opdateres samtidig efter disse simple regler, som anvender Moores nabolag (de otte omkringliggende celler):

  • En levende celle med færre end to levende naboer dør (underbefolkning).
  • En levende celle med to eller tre levende naboer fortsætter med at være levende (overlevelse).
  • En levende celle med mere end tre levende naboer dør (overbefolkning).
  • En død celle med præcis tre levende naboer bliver levende (fødsel).

På grund af disse simple, deterministiske regler kan komplekse og ofte uventede mønstre opstå over mange generationer.

Typiske mønstre og fænomener

  • Still lifes (stabile mønstre): mønstre, der ikke ændrer sig fra generation til generation (fx "block" og "beehive").
  • Oscillatorer: mønstre, der gentager sig selv efter et antal generationer (fx "blinker" med periode 2).
  • Spaceships: mønstre, der bevæger sig hen over gitteret (fx "glider").
  • Guns: mønstre, der konstant udsender andre mønstre, fx den berømte Gosper glider gun, som udsender glidere og dermed skaber uendelig vækst i et ubegrænset gitter.

Historie og betydning

Conway konstruerede Livets spil i 1970 som et simpelt eksperiment i cellulære automater. Spillet blev hurtigt populært efter omtale i tidsskriftet Scientific American af Martin Gardner. Et vigtigt resultat var opdagelsen af mønstre som glider gun og senere beviser for, at spillet er Turing-komplet—dvs. at det, med de rette konstruktioner, kan udføre enhver beregning, som en almindelig computer kan.

Livets spil har haft stor indflydelse på studiet af emergens, komplekse systemer og algoritmisk kunst, og det bruges både i undervisning og i matematisk forskning som et enkelt eksempel på, hvordan komplekst adfærd kan opstå fra enkle regler.

Praktisk: hvordan man spiller og implementerer

For at "spille" Livets spil vælger man en startkonfiguration af levende celler på et gitter og lader reglerne køre generation for generation. I praksis benyttes ofte computere eller browser-baserede simulatorer, der tillader:

  • At tegne startmønstre manuelt eller indlæse færdige mønstre.
  • At køre simulationen trinvis eller med konstant hastighed.
  • At ændre gitterets størrelse og kantadfærd (fx faste kanter, wrap-around/torus eller et stort/ubegrænset gitter).

Ved implementering i kode er opmærksomhed på ydeevne vigtig for store gitterstørrelser; typiske optimeringer omfatter at holde styr på kun de celler, der kan ændre sig, eller at bruge effektive datastrukturer som hash-sæt til sparse gitterrepræsentationer.

Varianter

Der findes mange varianter af Livets spil med andre fødsels- og overlevelsesregler (fx "HighLife"), andre gittertyper eller flere tilstande end blot levende/død. Disse varianter undersøges for at forstå, hvordan regelændringer påvirker kompleksitet og adfærd.

Selvom reglerne er meget enkle, viser Conways Livsspil på overbevisende vis, hvordan rige og uforudsigelige mønstre kan opstå fra deterministic, lokale regler — et centralt tema i studiet af komplekse systemer.