Wat is een cellulaire automaat
Een cellulaire automaat is een bord met vakjes, elk in een bepaalde toestand (hier: levend of dood), dat verandert in stappen die generaties heten. In elke stap worden alle vakjes tegelijk bijgewerkt met dezelfde regel, die alleen naar de acht buren rond elk vakje kijkt.
De Game of Life win of verlies je niet: jij kiest de beginopstelling en de regels doen de rest. Het bijzondere is dat uit zulke simpele regels zeer complex en onvoorspelbaar gedrag ontstaat, en daarom wordt het bestudeerd in de wiskunde, de informatica en zelfs de biologie.
De regels in gewone taal
Je kijkt naar het aantal levende buren van elk vakje (de acht eromheen, diagonalen meegeteld) en past deze regels tegelijk toe op het hele bord:
- Een levende cel met minder dan twee levende buren sterft van eenzaamheid.
- Een levende cel met twee of drie levende buren blijft leven.
- Een levende cel met meer dan drie levende buren sterft door overbevolking.
- Een dood vakje met precies drie levende buren wordt geboren.
De verkorte notatie voor deze regels is B3/S23: B (van birth, geboorte) 3 betekent dat een cel geboren wordt met 3 buren, en S (van survival, overleven) 23 betekent dat hij overleeft met 2 of 3. De alternatieve regels in de tool gebruiken dezelfde notatie, bijvoorbeeld HighLife is B36/S23 en Zaden is B2/S.
Een generatie met de hand uitgerekend
Neem de knipperaar: drie levende cellen op een horizontale rij. De middelste heeft 2 levende buren en overleeft dus. De cellen aan de uiteinden hebben maar 1 buur en sterven. De vakjes direct boven en direct onder het midden hebben 3 levende buren (de drie van de rij) en worden dus geboren. Resultaat: een verticale rij van drie cellen.
In de volgende generatie herhaalt het proces zich en is de rij weer horizontaal. Daarom is de knipperaar een oscillator met periode 2. Probeer hetzelfde met het blok, een vierkant van 2 × 2: elke cel heeft 3 buren en overleeft dus, en geen enkel leeg vakje heeft 3 levende buren. Het verandert nooit, en daarom heet het een stilleven.
Geschiedenis: Conway, Gardner en het tijdschrift
De Britse wiskundige John Conway bedacht het spel in 1970. Martin Gardner maakte het bekend in zijn column over wiskundige spelletjes in Scientific American, in het nummer van oktober 1970, en sindsdien is er een enorme gemeenschap van liefhebbers ontstaan die patronen zoeken en catalogiseren.
Na verloop van tijd werd bewezen dat het spel Turing-compleet is: met de juiste figuren kan het in principe alles berekenen wat een computer kan berekenen. Dat is een van de redenen waarom het nog steeds beroemd is: onbeperkte complexiteit uit minimale regels.
Patroonfamilies en welke je moet proberen
Patronen worden ingedeeld naar hun gedrag. Ze staan allemaal in het menu «Patroon» van de tool, onder deze namen:
| Familie | Patroon | Wat het doet |
|---|---|---|
| Stilleven | Blok, Bijenkorf | Verandert nooit: 4 cellen het blok, 6 de bijenkorf |
| Oscillator | Knipperaar, Pad, Baken | Periode 2: begint elke 2 generaties opnieuw |
| Oscillator | Pulsar | Periode 3, 48 cellen in de beginfase |
| Oscillator | Pentadecathlon | Periode 15 |
| Ruimteschip | Glider | 5 cellen; schuift elke 4 generaties 1 vakje diagonaal op |
| Ruimteschip | Lichte ruimteschip | Steekt het bord in een rechte lijn over, periode 4 |
| Kanon | Gosper-gliderkanon | Stoot elke 30 generaties een nieuwe glider uit |
| Beginchaos | R-pentomino | 5 cellen die 1.103 generaties nodig hebben om stabiel te worden op een oneindig vlak |
Het Gosper-kanon werd in 1970 gevonden door Bill Gosper en was het eerste bewijs dat een populatie onbeperkt kan groeien. Naast deze bevat de tool Eikel en Diehard, twee kleine patronen die er heel lang over doen om uit te kristalliseren.
Zo gebruik je de tool Game of Life
- Tik of sleep over het bord om levende cellen te tekenen (tik nog eens op een levend vakje om het te wissen), of kies een patroon uit het menu «Patroon».
- Tik op «Start». Met «Eén generatie» ga je stap voor stap verder om de evolutie rustig te volgen, en met «Pauze» stop je alles. Met het bord geselecteerd kun je ook het toetsenbord gebruiken: spatie start of pauzeert, N gaat één stap verder, R vult willekeurig en C wist alles.
- Pas de «Snelheid», de «Bordgrootte» en de «Regel» aan en probeer «Willekeurig» (met «Dichtheid bij willekeurig») om met een bord vol cellen te beginnen. Met «Wissen» maak je het bord leeg.
- Zet «Kleur cellen op basis van hun leeftijd» aan om te zien welke zones het langst stabiel zijn. Bovenaan staan de generatie en de levende cellen, en de tool meldt het wanneer het bord stabiel wordt, in een cyclus belandt of uitsterft.
Alles wordt op je apparaat berekend en er wordt niets naar een server gestuurd. De tool bewaart de instellingen (grootte, snelheid, regel) in je browser, maar niet de tekening.
Experimenten om te doen
- Laad de glider en tel hoeveel generaties het duurt voordat hij een vakje diagonaal is opgeschoven: het zijn er 4. Met verbonden randen loopt hij rond het bord en verschijnt hij aan de andere kant weer.
- Zet twee gliders op botsingskoers en kijk hoe het afloopt: afhankelijk van hoe ze aankomen kunnen ze elkaar vernietigen of een stilleven achterlaten.
- Laad het Gosper-kanon op een bord van minstens 48 × 48 en tel hoe lang het duurt voordat elke glider wordt gelanceerd: 30 generaties.
- Laad de R-pentomino op een groot bord en vergelijk met en zonder verbonden randen. Op een oneindig vlak duurt het 1.103 generaties voordat hij stabiel is, maar op een eindig bord verandert het resultaat.
- Verander de regel met dezelfde tekening. Met Zaden (B2/S) sterft elke cel in elke generatie en blijven alleen de geboortes over, dus de tekening breidt zich naar buiten uit; met Doolhof (B3/S12345) ontstaan structuren die op gangen lijken.
Beperkingen van een eindig bord
Het oorspronkelijke spel speelt zich af op een oneindig vlak. Het bord van de tool heeft een vaste grootte, dus wat de rand bereikt, gedraagt zich anders: met verbonden randen komt het aan de tegenovergestelde kant weer binnen (het bord wordt een soort donut), en zonder verbinding dooft het uit tegen een muur.
Daarom hebben grote patronen ruimte nodig (het Gosper-kanon vraagt minstens 48 × 48) en kunnen sommige, zoals de R-pentomino, anders eindigen dan je op een onbegrensd vlak ziet. Past het patroon niet, dan vraagt de tool om een groter bord.
Veelgestelde vragen
Wat zijn de regels van de Game of Life van Conway?
Een levende cel met 2 of 3 levende buren blijft leven; met minder dan 2 sterft hij van eenzaamheid en met meer dan 3 door overbevolking. Een dood vakje met precies 3 levende buren wordt geboren. Samengevat: B3/S23.
Wat betekent B3/S23?
B is geboorte (birth) en S is overleven (survival). B3 betekent dat er een cel geboren wordt bij 3 levende buren en S23 dat een cel met 2 of 3 levende buren overleeft.
Wat is een glider?
Een figuur van vijf cellen die diagonaal opschuift, één vakje per 4 generaties. Het bekendste patroon van het spel.
Wie heeft de Game of Life bedacht?
De Britse wiskundige John Conway, in 1970. Martin Gardner maakte het dat jaar bekend in het tijdschrift Scientific American.
Waarom verdwijnt mijn tekening of blijft hij stilstaan?
Dat is heel gewoon: veel kleine figuren sterven uit of worden binnen enkele generaties stabiel. Probeer een ander beginpunt, een groter bord of «Willekeurig».