Игра «Жизнь» Джона Конвея: правила, фигуры и почему она не кончается
«Жизнь» — это не игра в обычном смысле: в ней нет ни хода, ни противника, ни цели. Есть поле из клеток, два правила на четыре строчки и полная невозможность предсказать, что из этого выйдет.
Правила целиком
Поле разбито на клетки. Клетка либо живая, либо пустая. У каждой восемь соседей. Все клетки меняются одновременно, и шаг считается по состоянию предыдущего поколения:
- Пустая клетка, у которой ровно три живых соседа, оживает.
- Живая клетка с двумя или тремя живыми соседями остаётся жить.
- Во всех остальных случаях живая клетка умирает — от одиночества (меньше двух) или от перенаселения (больше трёх).
Коротко это записывают как B3/S23: рождение при трёх, выживание при двух-трёх. Больше в правилах ничего нет — ни случайности, ни скрытых параметров. Мир полностью детерминирован: по текущему полю однозначно вычисляется следующее.
Откуда она взялась
Правило придумал английский математик Джон Хортон Конвей в 1970 году, и широко известным оно стало после колонки Мартина Гарднера в Scientific American в октябре того же года. Конвей искал не игру, а самый простой набор правил, в котором нельзя заранее сказать, вымрет узор или будет расти бесконечно. Он подбирал B и S так, чтобы мир не скатывался ни в пустоту, ни в кашу — и нашёл единственную узкую щель между этими исходами.
Почему из четырёх строчек получается сложность
Это и есть то, за чем на «Жизнь» смотрят: эмерджентность. В правилах нет понятия «фигура», «движение» или «столкновение» — а на поле сами собой появляются неподвижные натюрморты, мигающие осцилляторы и ползущие по диагонали планеры. Ни одно из этих слов в правило не заложено; всё это следствия.
Дальше становится ещё интереснее. На поле «Жизни» можно собрать логические элементы И, ИЛИ и НЕ из потоков планеров, а из них — сумматор, счётчик и в конце концов полноценный компьютер. «Жизнь» тьюринг-полна: в ней можно вычислить всё, что вообще вычислимо. Отсюда следует и неприятное: вопрос «вымрет ли этот узор» алгоритмически неразрешим в общем случае. Единственный честный способ узнать — запустить и смотреть.
Чем наша арена отличается от обычного симулятора
Симуляторов «Жизни» в сети сотни, и все они устроены одинаково: поле считается в вашем браузере, вы один, при перезагрузке страницы мир начинается заново.
У нас не так:
- Мир один на всех и идёт на сервере. Он не останавливается, когда вы закрыли страницу, и все, кто смотрит, видят одно и то же поле в один и тот же момент.
- У каждой клетки есть хозяин. Закон один на всех, но живая клетка помнит, чьей колонии она принадлежит, и пустую клетку на границе забирает та, чьих клеток рядом больше. Получается война фигур за территорию, которой в одиночной «Жизни» быть не может.
- У арены есть смерть и номер. Когда поле оседает в неподвижность, замыкается в цикл, зарастает целиком или достаётся одной колонии, арена объявляется кончившейся, уходит в летопись с записью «сколько прожила и чем кончилась», и начинается следующая под новым номером.
- Вас просят мешать. Брошенная колония сбивает установившееся равновесие и возвращает арене способность меняться. Чем больше колоний — тем дольше живёт общая арена.