TLHE Mar 24 2023 at 10:01

Пятничные клеточные автоматы: циклические конфигурации; камень-ножницы-бумага

Easy

6 min

Timeweb Cloud corporate blogAlgorithms*Popular scienceProgramming*Reading room

Review

👾, Хабр!

На прошлой неделе мы снова расширили классическую «life-like» модель, добавив к ней параметр радиуса поиска соседей. Сегодня немного отойдём от этого вида и заглянем в область прочих конфигураций. Начнём с циклических КА.

❯ Отличия конфигурации

Давайте вспомним, что лежит в основе всех рассмотренных нами ранее конфигураций:

Клетка может быть пустой или заполненной;
Правила перехода клетки между этими состояниями определяются количеством живых соседей (заполненных, с состоянием 1).

И всё. Это наша основа, которую мы расширяли новыми характеристиками и условиями. Потому и говорили о «life-like» модели, так как все конфигурации соответствовали этим базовым правилам.

Сегодняшняя же модель вносит изменения в саму основу и выглядит следующим образом:

Клетки всегда заполнены и логически равны, отличается только числовое значение состояний;
Правила перехода определяются количеством соседей, находящихся в следующем состоянии от значения самой клетки.

Как следует из названия, состояния цикличны: следующее состояние для клетки с максимальным значением – 0.

Многие рассмотренные ранее расширения актуальны и для новой основы – мы всё так же указываем окрестность, радиус и количество состояний (ранее мы называли их поколениями). Но мы отказываемся от характеристик B и S, которыми обозначали количество соседей для рождения/выживания, а вместо них вводим одну новую – T (Threshold) – количество соседей в следующем состоянии для перехода клетки.

Общепринятой нотации для циклических КА нет. Часто параметры указывают просто в порядке «Радиус/Пороговое_значение_перехода/Количество_состояний/Тип_окрестности» без буквенных обозначений, со слешами в качестве разделителей. Воспользуемся этим вариантом записи, но сопроводим её явным буквенным обозначением параметров – R, T, G, N. В отличии от ранее рассмотренных конфигураций, в циклических КА окрестность фон Неймана (NN –

) используется если не чаще, то наравне с окрестностью Мура (NM –

❯ Демоны

Согласно LifeWiki, «циклические клеточные автоматы – это класс КА, широко известных тем, что они создают спиральные узоры». И это действительно визитная карточка конфигурации.

В основе спиралей находятся, так называемые, «демоны» – завихрения бесконечно сменяющих друг друга состояний, волны от которых распространяются во все стороны от демона, создавая характерную картину.
Подробно возникновению спиралей в циклических КА посвящена отдельная статья.

Стоит отметить, что необходимо как минимум 3 состояния для появления демона. Они часто устойчивы, и на многих правилах не могут быть разрушены в принципе, защищаясь от повреждений генерируемыми волнами.

Как и жуки в LtL, демоны – преобладающие структуры на всей конфигурации.

Начнём с самого наглядного представления:

^R1/T1/G14/NN

Данное правило интересно своим двойным поведением – сначала случайно сгенерированное поле расчищается однородными участками состояний, и только после этого столкновением участков образуются демоны. Здесь они представлены в своём самом явном виде, на прочих же правилах они могут быть менее оформлены, но всё ещё будут являться системообразующими.

Демоны бывают разных форм и видов, могут появляться с разной частотой, распространять волны с разной скоростью, а у волн может быть разная ширина одноцветных участков.

^R2/T2/G6/NN

Угловатость примеров выше обусловлена не только использованием окрестности фон Неймана. На обоих окрестностях можно найти как скруглённые, так и угловатые виды.

^R3/T4/G5/NN

На правилах с большим количеством демонов, они могут сливаться с соседями в цепи, образуя более сложные – двойные, тройные, и более (на анимации – справа от центра) структуры:

^R3/T15/G3/NM

Повышенные пороговые значения часто дают виды с «артефактами», как на примерах ниже:

^R2/T9/G4/NM

^R2/T5/G8/NM

На некоторых правилах можно встретить местный аналог космических кораблей, которые хвостами-линиями формируют фоновый узор:

^R2/T3/G5/NN

^R1/T2/G5/NM

^R1/T3/G4/NM

❯ Стабильные виды

Слишком высокие пороговые значения не позволяют появляться демонам и приводят к стабильным, часто кубическим, видам:

^R2/T5/G3/NN

^R1/T2/G3/NN

^R2/T11/G3/NM

❯ Два состояния

Правила с только лишь двумя состояниями приходят в стабильный вид после разделения сетки. На границах участков клетки часто колеблются между двумя состояниями, но при этом не нарушают общий вид.

^R5/T23/G2/NN

^R1/T4/G2/NM

^R2/T5/G2/NN

Последние примеры могли напомнить вам модель сегрегации Шеллинга. Это действительно довольно близкое поведение, но с несколькими уточнениями: по Шеллингу поиск соседей происходит в одном радиусе, а поиск позиции для «переселения» – по всей сетке. У нас же оба процесса выполняются по одному радиусу. Также важно, что клетки в модели сегрегации не меняют собственное состояние, а обмениваются позициями (мы не привязаны к идентификации конкретной клетки, потому можно сказать, что клетки обмениваются состояниями), а обмен, в классическом представлении, происходит с пустой клеткой.

❯ Модификации конфигурации

Как и с любой другой конфигурацией, мы вольны вносить любые изменения, если хотим того.

Для примера, давайте внесём модификацию в одно из рассмотренных ранее правил, и с 50% вероятностью будем недосчитываться одного соседа.

Не узнали? Это R2/T2/G6/NN, второе рассмотренное сегодня, угловатое правило. Незначительная модификация, а вид уже совершенно другой. Тут даже интересен не столько новый вид, сколько новое поведение – демоны с этой модификацией менее устойчивы: они легче разрушаются, а пока живы могут немного смещать собственный центр.

Альтернативные окрестности

Конечно, мы можем менять и окрестность. Подавляющее большинство описанных правил во всех конфигурациях построены на окрестностях Мура и фон Неймана, которые и мы упоминаем в каждой статье множество раз, но нам ничего не мешает построить новые.

Например, мы можем сделать периметр фон Неймана, оставив от одноимённой окрестности только внешние клетки –

, что даст нам очень интересный сетчатый вид на правилах с чётным радиусом.

^R4/T4/G6/NNR

Аналогично можно изменить и окрестность Мура –

. Как и с прошлой модификацией – при R1 окрестность эквивалентна стандартной.

^R2/T5/G4/NMR

Через окрестность мы можем также задать и направление смены состояний –

^R5/T16/G4/ND

Ну и напоследок, давайте попробуем придумать линейный вид: зададим в качестве окрестности только первую, последнюю и центральную вертикальные линии. А для дополнительного направления обрежем первую до середины, а последнюю от середины, включительно –

^R3/T3/G5/NL

❯ Камень-ножницы-бумага

Можно заметить, что циклический КА с тремя состояниями работает как будто по правилам всем известной игры – 3 состояния, каждое из которых «бьёт» следующее и повреждается предыдущим. В нашем случае победа над клеткой заканчивается её поглощением, а «играет» клетка сразу против группы соседей.

Однако если взглянуть на варианты этой игры с большим количеством состояний, то под циклический КА они уже не очень подходят. Но мы можем их адаптировать.

КНБ 5

Самым известным, из расширенных вариантов правил, будет игра с двумя дополнительными состояниями, в разных названиях от «огонь, вода» до «ящерица, Спок». Вне зависимости от названий, исход столкновения чередуется с каждым следующим состоянием. 0 выигрывает у 1 и 3, а проигрывает 2 и 4, и так для каждого.

Следовательно, и наша адаптация должна учитывать при рассмотрении соседей не только клетки в следующем состоянии, а всех возможных «победителей». Состояние клетки, соответственно, также будет сменяться не на следующее, а именно на выигравшее состояние. Считаем, конечно, каждого участника отдельно, а не сумму всех потенциальных.

Тут у нас есть ещё одно допущение – если победителей несколько, мы можем учитывать первого, последнего, с максимальным значением и просто случайного. В случае, если рассматриваем максимальное значение, может возникнуть дополнительный выбор первый/последний/случайный, если таких победителей несколько. Всё это тоже может влиять на вид симуляции. На примерах ниже будем использовать первого победителя.

^{КНБ5 – R1/T3/G5/NM}

Мы получили не самый уникальный вид, хотя контуры волн имеют довольно нехарактерный вид для циклических КА. Тем не менее, это правило интересно, скорее, концептуально.

КНБ 7/9/15/25/101/…

Все дальнейшие расширения правил КНБ идут по одному шаблону – нечётное количество состояний; каждое «орудие» проигрывает следующей половине и побеждает предыдущую. Такое простое разделение на две целочисленные половины позволяет нам реализовать симуляцию для любого количества состояний.

Небольшой интерактив: на основе предыдущего абзаца предположите, что мы увидим на анимации ниже?

КНБ15 – R1/T3/G15/NM

У нас возникают демоны на трёх состояниях. И, заметьте, несмотря на то, что мы берём первого победителя, демоны всё равно приходят к структуре, где состояния клеток перепрыгивают больше трети прочих. На правилах с неустойчивыми демонами вся система, в конечном счёте, сведётся к трём победившим цветам-состояниям.

Учитывая, что каждый демон приходит к собственной комбинации, финальный вид получается достаточно разнообразным на цвета. Повторить это поведение на классических циклических КА нельзя, а значит мы нашли уникальную особенность этой модификации.

^{R1/T2/G101/NM}

Читайте также

О клеточных автоматах:

Прочее:

← Предыдущая часть | Следующая часть →

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

Tags:

Hubs: