Невероятные клеточные автоматы: обратные и расширенные поколения

Невероятные клеточные автоматы: обратные и расширенные поколения

👾, Хабр!
Давно не виделись.

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

В первых статьях цикла мы познакомились с поколениями, одной из базовых и простейших модификаций стандартной конфигурации клеточных автоматов. До этого дополнения наши клетки могли находиться лишь в двух логических состояниях – пустая и живая (0 и 1, соответственно). После же, с новым параметром G, мы добавили третье положение – старение, что значило, что клетка, после выхода из состояния 1, начинала отмирать, доходя до состояния G-1, и только после возвращая состояние к 0. Во время старения клетки не влияют на соседей, не проходят проверки выживания, увеличивая собственный счётчик состояния с каждым шагом, но они и не позволяют новым клеткам рождаться на их месте.

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

Со временем участники сообщества начали предлагать дополнения и к этому варианту конфигурации. На поверхности лежали многие вариации, как ещё возможно изменить или переставить состояния клеток. Одним из них были и обратные поколения, a.k.a. snoitareneG, с которых мы и начнём.

Что здесь происходит (для новых читателей серии)
В этой серии мы разбираем клеточные автоматы – дискретную модель, основой которой является сетка из ячеек-клеток, которые изменяют (или не изменяют) своё состояние в зависимости от количества соседей.

Учёт соседей определяется правилами, которые устанавливаются нами. Вариаций правил существует бесчисленное множество, и они были систематизированы в определённые конфигурации.

Самая популярная конфигурация – «B/S», или «life-like», по названию крайне широко известного клеточного автомата «Game of Life», где B/S обозначает, что в нашем правиле мы описываем всего два параметра – количество соседей необходимых для рождения новой клетки в пустой ячейке, и количество соседей для выживания существующей клетки.

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

Начало серии здесь, если желаете ознакомиться последовательно.

Обратные поколения

Вы уже наверняка догадались, в чём отличие: вместо «отмирания» после завершённой жизни, клетка «расцветает» до состояния G-1, и только тогда, становясь живой, начинает влиять на соседей и сама проходит проверки выживания.

После описания модификации, участники сообщества первым делом «перевернули» известные именованные правила, открытые на стандартных поколениях, получив несколько интересных видов.

G8/B45678/S12345 | Lava | 60с., 150×20%
Lava | 60с., 150×20% | G8/B45678/S12345

:h Параметры
G – количество состояний клеток. Минимум – 2 (жива/мертва), бо́льшие значения отвечают за длительность «старения» клетки, когда она уже не считается живым соседом для прочих клеток, но ещё не освободила клетку для рождения новой.
B – перечисление количества соседей, необходимых для рождения новой клетки. С использованием нотации Хенселя каждому количеству могут быть определены конкретные шаблоны расположения соседей. Пример: 2 = 2 живых соседа в любом положении, 2a = 2 рядом стоящих живых соседа, 2-a = 2 живых соседа в любом положении, кроме a.
S – полностью аналогично B, но отвечает за количество/расположения соседей, необходимых для выживания клетки.

Характеристики примера – [ускорение анимации от 100мс. на фрейм, если есть]; длительность анимации; размер и процент центрального заполнения на старте. Поле в примерах всегда 237×237. Границы связаны, если не указано обратное.

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

Lava с обычными поколениями
G8/B45678/S12345 | Lava | 60с., 150×20%
Lava | 60с., 150×20% | G8/B45678/S12345


G3/B458/S012345 | Lines | 29с., 150×20%
Lines | 29с., 150×20% | G3/B458/S012345

Чем всё закончилось (не закончилось)
G3/B458/S012345 | Lines | 10с., 150×20%
Lines | 10с., 150×20% | G3/B458/S012345

Вид с обычными поколениями
G3/B458/S012345 | Lines | 40с., 150×20%
Lines | 40с., 150×20% | G3/B458/S012345


G8/B23/S145678 | BelZhab Sediment | ×1.25, 40с., 200×0.2%
BelZhab Sediment | ×1.25, 40с., 200×0.2% | G8/B23/S145678

Продолжение
G8/B23/S145678 | BelZhab Sediment | ×1.25, 17с., 200×0.2%
BelZhab Sediment | ×1.25, 17с., 200×0.2% | G8/B23/S145678

Вид с обычными поколениями
G8/B23/S145678 | BelZhab Sediment | ×1.25, 22с., 200×0.2%
BelZhab Sediment | ×1.25, 22с., 200×0.2% | G8/B23/S145678


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

G5/B3457/S2367 | Banners | ×1.25, 18с., 150×20%
Banners | ×1.25, 18с., 150×20% | G5/B3457/S2367

Вид с обычными поколениями
G5/B3457/S2367 | Banners | ×1.5, 55с., 150×10%
Banners | ×1.5, 55с., 150×10% | G5/B3457/S2367


G6/B2/S3456 | Sticks | 28с., 150×20%
Sticks | 28с., 150×20% | G6/B2/S3456

Вид с обычными поколениями
G6/B2/S3456 | Sticks | ×1.25, 31с., 150×20%
Sticks | ×1.25, 31с., 150×20% | G6/B2/S3456


G8/B3/S01245678 | Meteor guns | 20с., 150×90%
Meteor guns | 20с., 150×90% | G8/B3/S01245678

Вид с обычными поколениями
G8/B3/S01245678 | Meteor guns | ×1.25, 34с., 150×10%
Meteor guns | ×1.25, 34с., 150×10% | G8/B3/S01245678

Продолжение
G8/B3/S01245678 | Meteor guns | ×1.25, 16с., 150×10%
Meteor guns | ×1.25, 16с., 150×10% | G8/B3/S01245678


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

Расширенные поколения

Данная модификация предлагает новую нотацию для соответствующей части, в которой теперь поочерёдно указывается, сколько итераций клетка будет проводить в активном и пассивном состояниях. Количество перечислений не ограничено и мы вольны указывать цепочки любой длины, но начинаем всегда с обозначения активного состояния. Если переложить последний пример, B3/S01245678/G8, с обычными поколениями, на это расширение, мы получим правило B3/S01245678/16 1+6≠8?.
То есть при рождении клетка жива, пока один раз не провалит проверку выживания, после чего уходит с поля в течении шести итераций.
Для обратных поколений мы можем использовать 0 в первой части обозначения – B3/S01245678/061. Таким образом, клетка при рождении сразу входит в пассивное состояние, запуская отсчёт итераций до следующей активной стадии.

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

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

B1e/S/5-5-5 | ×1.5, 15с., 237×0.1%
×1.5, 15с., 237×0.1% | B1e/S/555

Вариации
B1e/S/5-5-5 | ×2, 14с., симметричный старт
×2, 14с., симметричный старт | B1e/S/555
B1e/S/5-5-5 | ×1.5, 13с., различные стартовые положения
×1.5, 13с., различные стартовые положения | B1e/S/555


B2-ek/S345678/1-3-1-3 | ×1.5, 31с., 150×5%
×1.5, 31с., 150×5% | B2-ek/S345678/1313

Вариации
B2-ek/S345678/1-3-1-3 | ×1.5, 34с., 50×60%
×1.5, 34с., 50×60% | B2-ek/S345678/1313
B2-ek/S345678/1-3-1-3 | ×1.5, 42с., 50×30%
×1.5, 42с., 50×30% | B2-ek/S345678/1313
B2-ek/S345/1-3-1-3 | ×1.5, 19с., 2×50%
×1.5, 19с., 2×50% | B2-ek/S345/1313

Продолжение
B2-ek/S345/1-3-1-3 | ×1.5, 9с., 2×50%
×1.5, 9с., 2×50% | B2-ek/S345/1313


B345/S/5-5 | ×1.5, 23с., 100×5%
×1.5, 23с., 100×5% | B345/S/55

Спустя 10 минут
B345/S/5-5 | ×1.5, 15с., 100×5%
×1.5, 15с., 100×5% | B345/S/55

Вариации
B345/S5/3-3 | ×1.5, 25с., 150×5%
×1.5, 25с., 150×5% | B345/S5/33
B345/S5/3-3 | ×1.5, 47с., 150×100%
×1.5, 47с., 150×100% | B345/S5/33

Мерцание
B345/S/2-1 | ×1.5, 30с., 100×15%
×1.5, 30с., 100×15% | B345/S/21


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

B3kai/S3a45678/3-3 | ×1.5, 28с., 200×15%
×1.5, 28с., 200×15% | B3kai/S3a45678/33

Вариации
B3kai/S345678/2-2-2 | ×1.5, 22с., 150×10%
×1.5, 22с., 150×10% | B3kai/S345678/222
B3kai/S345678/7-7-7 | ×1.5, 21с., 150×10%
×1.5, 21с., 150×10% | B3kai/S345678/777
B3kai/S01234567/3-3-3 | ×1.5, 39с., 100×35%
×1.5, 39с., 100×35% | B3kai/S01234567/333
B3kai/S3a567/3-3 | ×1.5, 29с., 150×15%
×1.5, 29с., 150×15% | B3kai/S3a567/33


B2e3-an/S/2-15-10-2 | ×2, 46с., 3×65%
×2, 46с., 3×65% | B2e3-an/S/215102

Продолжение
B2e3-an/S/2-15-10-2 | ×2, 10с., 3×65%
×2, 10с., 3×65% | B2e3-an/S/215102

И ещё продолжение
B2e3-an/S/2-15-10-2 | ×2, 8с., 3×65%
×2, 8с., 3×65% | B2e3-an/S/215102


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

Для наглядности
B468/S1357/2-2-2 | 14с., 200 итераций, 237×15%
14с., 200 итераций, 237×15% | B468/S1357/222

B468/S1357/3-2-3 | 14с., 200 итераций, 237×15%
14с., 200 итераций, 237×15% | B468/S1357/323

B468/S1357/2-4-2 | 11с., 200? итераций, 237×15%
11с., 200? итераций, 237×15% | B468/S1357/242


B3/S23e4e567/2-7-7-2 | ×1.5, 22с., 3×55%, закрытые границы
×1.5, 22с., 3×55%, закрытые границы | B3/S23e4e567/2772

Вариации
B3/S23e4e5678/2-7-7-2 | ×2, 33с., 50×20%, закрытые границы
×2, 33с., 50×20%, закрытые границы | B3/S23e4e5678/2772
B3/S235678/2-7-7-2 | ×2, 27с., 50×20%
×2, 27с., 50×20% | B3/S235678/2772


B2cek3aej4a7e/S1e2-cn3ery4jz/2-2 | ×2, 67с., 4×90%
×2, 67с., 4×90% | B2cek3aej4a7e/S1e2-cn3ery4jz/22

Вариации
B2cek3aej4a7e/S1e2-cn3ery4jz/2-2 | ×2, 48с., 150×5%
×2, 48с., 150×5% | B2cek3aej4a7e/S1e2-cn3ery4jz/22
B2cek3aej4a7e/S1e2-cn3ery4jzr5i/2-2 | ×1.5, 52с., 150×5%
×1.5, 52с., 150×5% | B2cek3aej4a7e/S1e2-cn3ery4jzr5i/22
B2cek3aej4a7e/S1e2-cn3ery4jz/1-1-1-1-1-1 | ×1.5, 27с., 150×5%
×1.5, 27с., 150×5% | B2cek3aej4a7e/S1e2-cn3ery4jz/111111
B2cek3aej4a7e/S1e2-cn3ery4jz/20-4 | ×5, 40с., 150×1%
×5, 40с., 150×1% | B2cek3aej4a7e/S1e2-cn3ery4jz/204
B2cek3aej4a7e/S1e2-cn3ery4jz/20-4 | ×5, 44с., 3×30%
×5, 44с., 3×30% | B2cek3aej4a7e/S1e2-cn3ery4jz/204

Продолжение
B2cek3aej4a7e/S1e2-cn3ery4jz/20-4 | ×5, 22с., 3×30%
×5, 22с., 3×30% | B2cek3aej4a7e/S1e2-cn3ery4jz/204

Конец

На сегодня всё. В первой статье серии я приводил значение, сколько различных правил возможно на базовой конфигурации (218). После мы как раз рассмотрели стандартные поколения, и с ними подобную цифру уже не представлялось возможным подсчитать, разве что добавить множитель G-1 или же придумать какие-то ограничения/пороги. Но уже там можно было смело говорить о стремлении к бесконечности. О чём бы тогда пришлось говорить сегодня?

Бонус
B3i/S234567/3-1-3 | 4с., 150×95%
4с., 150×95% | B3i/S234567/313
B34/S12/0-1-1 | 5с., блоки от 5×5 до 15×15
5с., блоки от 5×5 до 15×15 | B34/S12/011
B2ei3aei4e/S12345/3-1-1 | ×2, 22с., 20×30%
×2, 22с., 20×30% | B2ei3aei4e/S12345/311
B2aie/S2aie3aie4aie5aie678/1-9-8-4 | ×1.5, 23с., 50×40%, закрытые границы
×1.5, 23с., 50×30%, закрытые границы | B2aie/S2aie3aie4aie5aie678/1984


Читайте также
О клеточных автоматах:

  1. Базовая «life-like» конфигурация
  2. Старение клеток: параметр поколений
  3. Нотация Хенселя: учёт расположения соседей
  4. LtL: расширенный радиус поиска соседей
  5. Циклические клеточные автоматы
  6. Альтернативные окрестности и HROT
  7. Блочные КА, окрестность Марголуса
  8. Взвешенные окрестности, окрестность Гаусса, Far Corners/Edges
  9. Направленные и пользовательские окрестности
  10. Клетки-киллеры, BSFK[L]
  11. Дефицитные правила
  12. Обратные и расширенные поколения (вы здесь)

Прочее:

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


 

Источник

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