22. 4. 2026
Half-Life: fuzzy rozšírenie Conwayovej hry Life
Prehľad mojej diplomovej práce o Half-Life, trojstavovom celulárnom automate inšpirovanom fuzzy rozšíreniami Conwayovej hry Life.

Moja diplomová práca Half-Life sa začína jednoduchou otázkou:

Čo sa stane, keď Conwayova hra Life prestane byť striktne binárna?

V klasickej hre Life je každá bunka buď živá, alebo mŕtva. Práve táto ostrosť je jedným z dôvodov, prečo je model taký zaujímavý: pravidlá sa dajú zapamätať za pár sekúnd, ale výsledné správanie obsahuje stabilné objekty, oscilátory, lode, klzáky, generátory klzákov aj výpočtovo univerzálne konštrukcie.

Binárny stavový priestor je však zároveň obmedzenie. Veľa systémov sa medzi krajnými stavmi nepohybuje okamžite. Niečo môže rásť, slabnúť, doznievať alebo zostať v prechodnom stave. V práci som túto myšlienku skúmal cez nový trojstavový celulárny automat Half-Life.

Model možno chápať ako diskrétnu aproximáciu fuzzy verzie Conwayovej hry Life. Zachováva mriežku, Mooreovo okolie aj synchrónnu aktualizáciu buniek, ale stavový priestor rozširuje z dvoch hodnôt na tri:

  • 00 označuje mŕtvu bunku,
  • 0.50.5 označuje polovične živú bunku,
  • 11 označuje živú bunku.

Názov Half-Life odkazuje práve na medzistav 0.50.5. Bunka sa nemusí narodiť ani zaniknúť v jednom kroku. Narodenie prebieha ako 0→0.5→10 \to 0.5 \to 1 a zánik ako 1→0.5→01 \to 0.5 \to 0.

Čo práca rieši

Cieľom nebolo iba definovať nový automat, ale aj zistiť, či také malé rozšírenie vytvára zaujímavé správanie. Preto práca spája formálnu definíciu, automatizované vyhľadávanie, experimentálnu analýzu a webový simulátor.

Hlavné časti práce sú návrh fuzzy rozšírenia, formálna definícia modelu Half-Life, implementácia nástroja na hľadanie pravidiel a vzorov, experimenty s intervalovými pravidlami a webová aplikácia Fuzzy Life na simuláciu výsledkov.

Model Half-Life

Mriežka je rovnaká ako v klasickej hre Life:

Z2\mathbb{Z}^2

Stavový priestor je:

S={0,0.5,1}\mathcal{S} = \{0, 0.5, 1\}

Konfigurácia je funkcia, ktorá každej bunke v mriežke priradí stav:

h:Z2→Sh: \mathbb{Z}^2 \to \mathcal{S}

Okolie je osemprvkové Mooreovo okolie:

N={−1,0,1}2∖{⟨0,0⟩}.\mathcal{N} = \{-1,0,1\}^2\setminus\{\langle 0,0\rangle\}.

Rozdiel oproti klasickej hre Life je v súčte susedov. Keďže sused môže mať hodnotu 00, 0.50.5 alebo 11, výsledný súčet už nemusí byť celé číslo od 0 do 8. Môže nadobúdať hodnoty:

V={k2:k∈{0,1,…,16}}.\mathcal{V}=\left\{\frac{k}{2}:k\in\{0,1,\dots,16\}\right\}.

Súčet susedov bunky xx v konfigurácii hh je:

NeighborSum⁡HL(h,x)=∑n∈Nh(x+n).\operatorname{NeighborSum}_{HL}(h,x)=\sum_{n\in\mathcal{N}} h(x+n).

Pravidlo Half-Life zapisujem pomocou častí B a S. B určuje intervaly pre narodenie a S intervaly pre prežitie. Napríklad:

B3-7/S2-3,5-8

znamená, že bunka smeruje k narodeniu pri súčte susedov od 3 do 7, zatiaľ čo živá alebo polovične živá bunka prežíva pri súčte od 2 do 3 alebo od 5 do 8.

Jadro modelu tvorí cieľová funkcia:

Target⁡(s,q)={1,q=0 a s∈B,1,q∈{0.5,1} a s∈S,0,inak.\operatorname{Target}(s,q)= \begin{cases} 1, & q=0 \textrm{ a } s\in B,\\ 1, & q\in\{0.5,1\} \textrm{ a } s\in S,\\ 0, & \textrm{inak.} \end{cases}

Tá neurčuje nový stav priamo. Iba povie, či sa má bunka pohybovať smerom k stavu 11, alebo k stavu 00. Lokálna prechodová funkcia potom posunie aktuálny stav o polovicu smerom k cieľu:

fB,S(q,s)=q+0.5⋅sgn⁡(Target⁡(s,q)−q).f_{B,S}(q,s)=q+0.5\cdot\operatorname{sgn}(\operatorname{Target}(s,q)-q).

Half-Life teda neprepisuje bunku naraz. Bunka sa mení postupne, takže narodenie aj zánik majú prechodnú fázu.

Prečo treba automatizované hľadanie

V klasickej hre Life existuje pre Life-like pravidlá 218=262 1442^{18}=262\,144 možností. V Half-Life je možných súčtov susedov 17. Keby sme povolili ľubovoľné množiny pre narodenie a prežitie, dostali by sme:

217⋅217=234≈17 000 000 0002^{17} \cdot 2^{17} = 2^{34} \approx 17\,000\,000\,000

To je príliš veľký priestor na ručné skúmanie. Aj pri obmedzení na jednoduché intervaly vznikne viac než 23-tisíc kombinácií. Preto som vytvoril nástroj Half-Life Explorer v Ruste.

Nástroj simuluje veľké množstvo pravidiel, generuje náhodné počiatočné konfigurácie a hľadá vzory, ktoré sa opakujú, pohybujú, stabilizujú alebo rastú. Pri hlavných 2D experimentoch bolo každé pravidlo testované na 3 000 náhodných konfiguráciách na mriežke 48×4848\times48.

Detekcia je empirická, nie dôkazová. Slúži na hľadanie kandidátov, ktoré sa následne dajú overovať a skúmať podrobnejšie.

Teoretický príklad

Pre pravidlo B1/S1.5-2 práca ukazuje jednoduchý pohybujúci sa vzor. Nech FF je globálna prechodová funkcia a H0\mathrm{H}_0 vzor so štyrmi polovične živými bunkami:

H0(⟨x,y⟩)={0.5,⟨x,y⟩∈{⟨3,4⟩,⟨2,3⟩,⟨2,2⟩,⟨3,1⟩},0,inak.\mathrm{H}_0(\langle x,y\rangle)= \begin{cases} 0.5, & \langle x,y\rangle\in\{\langle 3,4\rangle,\langle 2,3\rangle,\langle 2,2\rangle,\langle 3,1\rangle\},\\ 0, & \textrm{inak.} \end{cases}

Pre každý čas t≥0t\ge 0 platí:

Ft(H0)=T⟨−t,0⟩H0.F^t(\mathrm{H}_0)=T_{\langle -t,0\rangle}\mathrm{H}_0.

Inými slovami, vzor má po každej generácii rovnaký tvar a je posunutý o jednu bunku doľava. Ide teda o loď periódy 1 s rýchlosťou cc.

Vývoj vzoru H0 pri pravidle B1/S1.5-2

Vývoj vzoru H0\mathrm{H}_0 pri pravidle B1/S1.5-2. Kliknutím sa vzor otvorí priamo v simulátore.

Výsledky experimentov

Prvý veľký experiment prešiel všetky pravidlá s jedným intervalom pre narodenie a jedným intervalom pre prežitie: 153 možných intervalov narodenia, 153 možných intervalov prežitia, 23 409 pravidiel a 70 227 000 simulácií.

V tomto priestore sa našlo 243 pravidiel, ktoré vygenerovali aspoň jeden pohybujúci sa vzor. Najvýraznejším pravidlom bolo B1/S1.5-2, pri ktorom sa po deduplikácii našlo 20 typov klzákov a 3 typy oscilátorov.

Druhý experiment skúmal pravidlá s deleným intervalom prežitia, napríklad:

B3-7/S2-3,5-8

Také pravidlo dovolí bunke prežiť v nízkej alebo vysokej hustote susedov, ale nie v medzere medzi nimi. V simuláciách to často bránilo vzniku veľkých stabilných zhlukov a podporovalo cykly rastu a rozpadu.

Z 11 475 testovaných pravidiel v tomto experimente vytvorilo klzáky 309 pravidiel. Z nich 266 používalo delený interval prežitia. Nejde o matematický dôkaz, že delené intervaly sú všeobecne lepšie, ale je to silný empirický signál, že ide o zaujímavý smer ďalšieho skúmania.

Po zlúčení a deduplikácii výsledkov obsahoval finálny katalóg:

  • 514 pravidiel podporujúcich pohybujúce sa štruktúry,
  • 3 381 objavených vzorov,
  • klzáky a lode s rôznymi rýchlosťami,
  • oscilátory s mnohými periódami,
  • vzory pripravené na otvorenie vo webovom simulátore.

Najpomalší nájdený klzák s rýchlosťou c/26

Najpomalší nájdený klzák má rýchlosť c/26c/26.

Oscilátor periódy 60 pri pravidle B1.5/S1

Oscilátor periódy 60 pri pravidle B1.5/S1.

Fuzzy Life

Súčasťou práce je aj webová aplikácia Fuzzy Life, ktorá umožňuje tieto pravidlá a vzory skúšať interaktívne. Simulátor je napísaný v Reacte a vykresľuje sa cez HTML5 Canvas.

Interaktívny simulátor

Pravidlá Half-Life a objavené vzory si môžete vyskúšať priamo vo Fuzzy Life.

Otvoriť Fuzzy Life ->

Simulátor prepája offline vyhľadávanie v Ruste s vizuálnym prostredím v prehliadači. Obsahuje režim Half-Life, klasickú Conwayovu hru Life, jednorozmerné automaty aj ďalšie experimentálne varianty. Pri Half-Life režime sú dostupné prednastavené pravidlá a vzory z katalógu, takže výsledky práce nie sú iba tabuľky v texte, ale dajú sa okamžite spustiť a pozorovať.

Záver

Hlavným výsledkom práce je ukážka, že aj veľmi malé rozšírenie klasickej hry Life vytvára veľký a zaujímavý priestor pravidiel. Jeden medzistav mení spôsob, akým sa bunky rodia, prežívajú, zanikajú a vytvárajú pohybujúce sa štruktúry.

Half-Life nie je náhradou za Conwayovu hru Life. Je to blízky model, ktorý kladie inú otázku: čo sa stane, keď život nemusí byť hneď živý alebo mŕtvy, ale môže byť najprv polovičný?