Half-Life: нечітке розширення гри Conway Life

Моя магістерська робота Half-Life починається з простої ідеї:

Що станеться, якщо гра Conway Life перестане бути строго бінарною?

У класичній грі Life кожна клітина або жива, або мертва. Саме ця різкість робить модель такою привабливою: правила дуже короткі, але глобальна поведінка може породжувати сталі фігури, осцилятори, кораблі, глайдери, генератори глайдерів і навіть обчислювально універсальні конструкції.

Водночас бінарний простір станів є обмеженням. У реальних або натхненних реальністю системах об’єкти не завжди миттєво переходять між двома крайніми станами. Вони можуть рости, згасати, відновлюватися або певний час залишатися в проміжному стані. У роботі я досліджував цю ідею через новий тристановий клітинний автомат Half-Life.

Модель можна розуміти як дискретне наближення нечіткої версії Conway Life. Вона зберігає квадратну ґратку, околицю Мура та синхронне оновлення клітин, але розширює простір станів із двох значень до трьох:

$0$ позначає мертву клітину,
$0.5$ позначає напівживу клітину,
$1$ позначає живу клітину.

Назва Half-Life пов’язана саме з цим проміжним станом. Клітина не мусить народжуватися або зникати за один крок. Народження відбувається як $0 \to 0.5 \to 1$ , а смерть як $1 \to 0.5 \to 0$ .

Що досліджує робота

Метою було не лише формально визначити новий автомат, а й перевірити, чи таке невелике розширення справді створює нову цікаву поведінку. Тому робота поєднує математичне означення, автоматизований пошук, експериментальний аналіз і вебсимулятор.

Основні частини роботи: побудова нечіткого розширення Conway Life, формальне означення моделі Half-Life, реалізація інструмента для пошуку правил і фігур, експерименти з інтервальними правилами та вебзастосунок Fuzzy Life для візуалізації результатів.

Модель Half-Life

Ґратка така сама, як у класичній Life:

\mathbb{Z}^2

Простір станів:

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

Конфігурація є функцією, яка кожній клітині ґратки ставить у відповідність її стан:

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

Околиця є восьмиклітинною околицею Мура:

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

Відмінність від класичної гри Life полягає в сумі сусідів. Оскільки сусід може мати значення $0$ , $0.5$ або $1$ , сума вже не обмежена цілими числами від 0 до 8. Вона може набувати значень:

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

Сума сусідів клітини $x$ у конфігурації $h$ :

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

Правило Half-Life записується через частини B і S. B задає інтервали народження, а S задає інтервали виживання. Наприклад:

B3-7/S2-3,5-8

Це означає, що мертва клітина рухається до народження, коли сума сусідів лежить між 3 і 7, а жива або напівжива клітина виживає при сумі від 2 до 3 або від 5 до 8.

Цільова функція має вигляд:

\operatorname{Target}(s,q)= \begin{cases} 1, & q=0 \textrm{ і } s\in B,\\ 1, & q\in\{0.5,1\} \textrm{ і } s\in S,\\ 0, & \textrm{інакше.} \end{cases}

Вона не встановлює новий стан напряму. Вона лише визначає, куди має рухатися клітина: до стану $1$ або до стану $0$ . Локальна функція переходу зміщує поточний стан на половину кроку в напрямку цієї цілі:

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

Тому Half-Life не перемикає клітину миттєво. Народження і смерть мають проміжну фазу.

Чому потрібен автоматизований пошук

У класичних Life-like правилах є $2^{18}=262\,144$ можливостей. У Half-Life можливих сум сусідів 17. Якщо дозволити довільні множини для народження і виживання, кількість правил зростає до:

2^{17} \cdot 2^{17} = 2^{34} \approx 17\,000\,000\,000

Такий простір неможливо дослідити вручну. Навіть якщо обмежитися простими інтервалами, отримуємо понад 23 тисячі комбінацій. Тому я реалізував інструмент Half-Life Explorer мовою Rust.

Інструмент симулює багато правил, генерує випадкові початкові конфігурації та шукає поведінку, яка вмирає, вибухає, стабілізується, осцилює або рухається. У головних двовимірних експериментах кожне правило тестувалося на 3 000 випадкових конфігураціях на ґратці $48\times48$ .

Ця класифікація є емпіричною. Вона не доводить довгострокову поведінку правила, але дає практичний спосіб знаходити цікаві кандидати.

Теоретичний приклад

Для правила B1/S1.5-2 у роботі наведено простий рухомий візерунок. Нехай $F$ є глобальною функцією переходу, а $\mathrm{H}_0$ є фігурою з чотирма напівживими клітинами:

\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{інакше.} \end{cases}

Для кожного $t\ge 0$ виконується:

F^t(\mathrm{H}_0)=T_{\langle -t,0\rangle}\mathrm{H}_0.

Тобто після кожного покоління фігура має ту саму форму, але зміщується на одну клітину вліво. Це корабель періоду 1 зі швидкістю $c$ .

Еволюція $\mathrm{H}_0$ за правилом B1/S1.5-2. Посилання відкриває цю фігуру безпосередньо в симуляторі.

Результати експериментів

Перший великий експеримент перевіряв усі правила з одним інтервалом народження та одним інтервалом виживання: 153 можливих інтервали народження, 153 можливих інтервали виживання, 23 409 правил і 70 227 000 симуляцій.

У цьому просторі було знайдено 243 правила, які породжували принаймні одну рухому фігуру. Найсильнішим правилом у цьому запуску було B1/S1.5-2: після дедуплікації воно дало 20 типів глайдерів і 3 типи осциляторів.

Другий експеримент досліджував правила з розділеним інтервалом виживання, наприклад:

B3-7/S2-3,5-8

Таке правило дозволяє клітині виживати при низькій або високій щільності сусідів, але не в проміжку між ними. У спостережених симуляціях це часто заважало появі великих стабільних скупчень і натомість підтримувало цикли росту та розпаду.

Із 11 475 правил у цьому експерименті глайдери створили 309 правил. Із них 266 використовували розділений інтервал виживання. Це не математичний доказ переваги таких правил, але сильний емпіричний сигнал, що цей напрям вартий подальшого дослідження.

Після об’єднання та дедуплікації результатів фінальний каталог містив:

514 правил, які підтримують рухомі структури,
3 381 знайдену фігуру,
глайдери й кораблі з різними швидкостями,
осцилятори з багатьма періодами,
приклади, готові до відкриття у вебсимуляторі.

Найповільніший знайдений глайдер має швидкість $c/26$ .

Осцилятор періоду 60 за правилом B1.5/S1.

Fuzzy Life

Практичною частиною роботи є вебзастосунок Fuzzy Life, у якому можна запускати правила Half-Life і переглядати знайдені фігури. Застосунок написаний на React і рендерить симуляцію через HTML5 Canvas.

Інтерактивний симулятор

Правила Half-Life і знайдені фігури можна спробувати безпосередньо у Fuzzy Life.

Відкрити Fuzzy Life ->

Симулятор поєднує офлайн-пошук у Rust із візуальним середовищем у браузері. Він містить режим Half-Life, класичну Conway Life, одновимірні автомати та інші експериментальні варіанти. У режимі Half-Life доступні готові правила й фігури з каталогу, тому результати роботи можна не лише прочитати, а й одразу побачити в русі.

Висновок

Головний результат роботи полягає в тому, що дуже невелике розширення класичної Life створює великий і змістовний простір правил. Один проміжний стан змінює те, як клітини народжуються, виживають, згасають і формують рухомі структури.

Half-Life не має замінити Conway Life. Це близька модель, яка ставить інше питання: що буде, якщо життя не мусить бути одразу живим або мертвим, а може спочатку бути напівживим?