Клітинний автомат Stepper

В цій статті пропонуються правила для двовимірного клітинного автомата, який, з одного боку, дуже схожий на гру Життя Джона Конвея (conway's Game of Life), а з іншого — володіє істотними відмінностями. Насамперед його відрізняє збільшений до трьох кількість станів клітин, підвищена здатність до самоорганізації, необмежений час активної еволюції і необмежену кількість рухомих конфігурацій.

Для стабільних конфігурацій нові правила збігаються з правилами гри Життя, тому всі стабільні конфігурації в грі Життя існують і в нових правилах. В описуваному клітинному автоматі існує великий клас рухомих конфігурацій, космічних кораблів. Всі ці конфігурації переміщуються з одного і того ж поступального механізму, який нагадує рух і крокового екскаватора і людину на милицях. Подібні космічні кораблі я назвав степпер (stepper), а саме правило Steppers. Так його і будемо називати надалі.

У Steppers існує досить багато осциляторів, причому, деякі осцилятори з гри Життя працюють і в Steppers, що говорить про спадкоємність правил. І, нарешті, знаменитий глайдер Конвея, так само існує у пропонованих правилах. У статті буде розглянута динаміка випадковим чином заповнених решіток, розкрито механізм руху степерів, описані знайдені на даний момент осцилятори і степпери. Так само будуть наведені приклади зіткнень і складного функціонального поведінки.

_r00.png
[00] Приклад рухомої конфігурації, яка генерує потік степерів

Історія розробки правил

У 1988 році я працював у лабораторії технічного зору. Вивчаючи алгоритм скелетонизации растрового монохромного зображення, я написав програму для його реалізації. Сам алгоритм скелетонизации нам так і не згодився і був покинутий, а написана програма після невеликого доопрацювання виявилася цілком пристойним клітинним автоматом з графічним редактором та графічним висновком. Першим випробуванням для неї, звичайно ж, виявилася гра Життя Джона Конвея. Через деякий час, мені захотілося поекспериментувати з іншими правилами, і я згадав про раніше прочитану статтю "Еволюція гри Еволюція" в журналі «Наука і життя» за 1975 рік [1]. У цій статті, намагаючись розвинути гру Життя, автор В. Сидоров додав третій стан для знову народжених клітин. За новими правилами клітина може перебувати в трьох станах, порожня, молода і стара. Молода клітина не гине ні за яких обставин, і в наступному поколінні стає старою.

_r01.png
[01] Позначення станів клітин

Повністю всі правила В. Сидоров сформулював в наступному вигляді:
  1. Молода клітина протягом одного ходу не помирає від перенаселеності, ні від самотності. Через один хід молода клітина перетворюється на стару.
  2. У кожній порожній клітці народжується нова (молода) клітина, якщо ця клітина мала трьох сусідів (сусідами могли бути як старі, так і молоді клітини).
  3. Стара клітина вмирає від перенаселеності, якщо вона межує з чотирма (і більше) старими клітинами або якщо вона межує з трьома (і більше) клітинами, серед яких є хоч одна молода.
  4. Стара клітина вмирає від самотності, якщо вона ізольована чи має тільки одного сусіда (сусідом може бути як стара, так і молода клітина).
У клітинному автоматі В. Сидорова є два, описаних ним, корабля. Пізніше мені вдалося знайти два осцилятора. На жаль, при перевищенні певної критичної маси, популяція втрачає структуру і швидко росте. Так як спостерігати за цим було нецікаво, я взявся розробляти свої закони життя і смерті.
Після відбору різних варіантів були сформовані наступні правила:
  1. Молода клітина протягом одного ходу не помирає від перенаселеності, ні від самотності. Через один хід молода клітина перетворюється на стару (це правило залишено без змін).
  2. На порожній клітці народжується молода клітина, якщо у неї рівно три сусіда, серед яких є хоча б дві старі клітини.
  3. Стара клітина продовжує існувати в наступному поколінні, якщо у неї дві або три сусідні клітини, серед яких не більше однієї молодої.
Більш наочно правила можна представити у вигляді таблиць. По осях відкладено кількість молодих і старих сусідів.

_r02.png
[02] Табличне подання правила В. Сидорова

_r03.png
[03] Табличне подання правила Steppers

Це правило здалося мені настільки цікавим, що я написав свою статтю, і відправив її в той же журнал «Наука і Життя». Через деякий час я отримав відповідь, що найближчим часом публікацій з клітинним автоматом не планується. Більше двадцяти років я потихеньку, з великими перервами займався цим клітинним автоматом, але не робив спроб де-небудь його опублікувати. І тільки з появою чудової програми Golly, в якій можна створювати клітинні автомати з довільним правилами, з'явилася і можливість поділитися своїми скромними дослідженнями. Програма Golly безкоштовна, її можна завантажити з сайту http://sourceforge.net/projects/golly/.

Всі ілюстрації в цій статті проіндексовані, при бажанні можна завантажити архів MilhinSA.Golly2.5.zip в якому під відповідним індексом знаходяться rle-файли з усіма прикладами. В цьому випадку, можна не задовольнятися статичними картинками, а побачити процес в дії. Програма Golly може відкрити цей архів з правилом і прикладами без попереднього розпакування.

У березні 2012 року я опублікував повідомлення про клітинному автоматі Steppers на англомовному форумі conway's Game of Life. Повідомлення викликало певний інтерес серед учасників форуму, деякі з них взяли участь в дослідженні Steppers і поділилися своїми знахідками.

Динаміка

Кращий спосіб перевірити інтегральні характеристики клітинного автомата, це подати на його вхід шумовий сигнал, або, іншими словами, випадковим чином заповнену популяцію. На наступному малюнку показані результати еволюції випадковим чином заповненої тороїдальної сітки гри Життя і Steppers в поколіннях 32, 320 і 3200. Видно, що щільність популяції Steppers падає повільніше, ніж у грі Життя і на якомусь етапі стабілізується.

_r04.png
[04] Еволюція випадкової популяції гри Життя і Steppers

Для отримання статистично достовірних даних був проведений наступний обчислювальний експеримент. Для кожного правила було сформовано випадково заповнене тороидальное поле розміром 256 х 256 клітин з щільністю 50%. Клітинний автомат відпрацьовував до 10 000 поколінь. Для кожного покоління обчислювалася щільність поля у відсотках, а також відсоток клітин змінили свій стан. Останній параметр характеризує активність клітинного автомата. Для кожного автомата цей процес повторювався 1000 разів, потім вихідні дані усереднювалися.

Нижче показані графіки щільності і активності. З цих графіків видно, що щільність і, відповідно, активність гри Життя швидко падає в самому початку розвитку і в 3000-4000 поколінні зменшується в середньому до 3 % щільності. Активність падає, в середньому до 1%. Легко зрозуміти, що це стаціонарні конфігурації і прості осцилятори. Клітинний автомат Steppers еволюціонує за іншим сценарієм. Протягом приблизно 20 поколінь встановлюється баланс між молодими і старими осередками, що призводить до згасальним коливального процесу. Потім щільність починає зменшуватися, і в 500-700 поколінні стабілізується на 21%. Активність стабілізується на 14%. Таким чином, еволюція випадкового поля достатнього розміру продовжується невизначено довго.

_r05.png
[05] Графіки зміни щільності та активності

Графіки зміни щільності та активності показують середнє значення для всього поля, але щільність і активність клітин змінюється не тільки в часі, але і в просторі. При еволюції рівномірно-заповненого випадкового поля видно, що клітини групуються в активні області, формуючи певну текстуру. Щоб виділити області з підвищеною активністю був застосований спеціальний алгоритм відображення клітинного автомата. Працює він таким чином. Для кожної клітинки протягом 32 поколінь підраховується кількість народжень і смертей. Потім виводиться зображення клітинного автомата в панелі чорний-червоний-жовтий-білий. Наступний малюнок показує, що активні осередки в грі Життя досить швидко розпадаються на ізольовані області, які згодом загасають. У клітинному автоматі Steppers активні області безперервно змінюють форму і розміри, зливаються і розпадаються. Досить великі площі залишаються вільними, і в них існують стаціонари, осцилятори, а так само глайдери і степпери. Завдяки цьому, навіть при еволюції випадкового поля в результаті самоорганізації виникає досить цікава картина, за якою цікаво спостерігати.

_r06.png
[06] Зміна активності популяції в процесі еволюції

Слід визнати, що правило Stepper, не тільки дуже живуча, але і дуже вибухонебезпечне. Часто, взаємодія простих конфігурацій веде до нестримному зростанню популяції. На форумі conway's Game of Life були знайдені конфігурації мінімального розміру, викликають необмежений ріст популяції. На наступному малюнку зображено 5-клітинний патерн, а також його стан в 1500 поколінні, причому, не повністю. Розмір популяції трохи менше 20 000 клітин.

_r07.png
[07] 5-клітинний патерн 1500-го покоління

Ще інтенсивніше розвивається лінійний 7-клітинний патерн. Тут він зображений в 500 поколінні, розмір популяції 8 124 клітини. В 3000 поколінні розмір популяції перевищить 500 000 клітин.

_r08.png
[08] 7-клітинний патерн у 500-му поколінні

Рух, степпери

У клітинному автоматі Steppers, на даний момент, виявлені два типи рухомих конфігурацій. Причому, до першого типу належить єдина конфігурація, звана в грі Життя глайдер. Видно, що глайдер в Steppers дуже незначно відрізняється від глайдера з гри Життя. При настільки істотному розходженні цих правил, існування глайдерів було досить несподіваним.

_r09.png
[09] Порівняння глайдерів гри Життя і Steppers

До другого типу відносяться степпери, і їх кількість необмежена, так як необмежений їх розмір. Всі степпери об'єднуються одним і тим же способом пересування. І цей спосіб зобов'язаний своєму існуванню правилом про народження. Нагадаю, звучить воно так «На порожній клітці народжується молода клітина, якщо у неї рівно три сусіда, серед яких є хоча б дві старі клітини». Спробую пояснити, чому правило про народження викликало такий ефект.

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

_r10.png
[10] Еволюція нескінченного ряду клітин в грі Життя і Steppers

Тепер розглянемо еволюцію кінцевого ряду клітин. У грі Життя навпроти крайніх клітин не може народитися нова комірка, так як у неї тільки два сусіда, тому кожне наступне покоління новий ряд стає на дві клітинки коротше, і через деякий час сходить нанівець. Та ж картина спостерігається при еволюції ряду клітин в КА Steppers, тільки в два рази повільніше.

_r11.png
[11] Еволюція кінцевого ряду клітин в грі Життя і Steppers

Але якщо в Steppers з одного боку низки додати до крайніх клітинам по одному сусідові, щоб вона не вимерла в першому поколінні, картина зовсім змінюється. Додати сусідів можна одним з наступних способів.

_r12.png
[12] Перетворення ряду клітин в степпер

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

_r13.png
[13] Відновлення ширини ряду клітин

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

_r14.png
[14] 100-клітинний степпер

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

_r15.png
[15] Приклади степерів

Розміри степерів можуть бути необмежено великими не тільки в ширину, але і в довжину. показав учасник форуму conway's Game of Life Емерсон Дж. Перкінс (Emerson J. Perkins (knightlife)), використовуючи регулярні елементи у довільному порядку можна сконструювати степпер довільної довжини.

_r16.png
[16] Конструювання степпера довільної довжини

На жаль, на даний час невідомі інші типи рухомих конфігурацій крім глайдерів і степерів. Але я все-таки сподіваюся, що вони існують. Зображені вище степпери не залишають після себе жодних конфігурацій, тобто є космічними кораблями. Інші степпери в процесі руху можуть залишати різні стаціонарні конфігурації, випускати глайдери і степпери, а часто за ними слід просто невщухаючий хаос.

Паровози і граблі

Згідно з термінологією гри Життя, рухомі конфігурації, що залишають за собою сміття називаються паровозами (puffers). На наступному малюнку можна побачити підбірку паровозів, які при русі залишають за собою ланцюжок з стаціонарних конфігурацій. Паровоз, який породжує ланцюжок з двох блоків, відрізняється рекордно малим періодом, p6. При швидкості руху c/2, блоки укладаються з періодом всього в три клітини. Ближче просто неможливо. Останній паровоз і зовсім формує безперервну лінію. Це дозволяє віднести його до класу подовжувачів ґнотів (wickstretcher).

_r17.png
[17] Паровози

Паровози, які породжують рухомі конфігурації, називаються граблями (rake). Таке несподіване назву, є наслідком неточного перекладу. Згідно словника Мюллера, слово rake має безліч значень, у тому числі і військово-морське «обстрілювати поздовжнім вогнем». Підозрюю, що саме це малося на увазі авторами терміна rake. Але у нас прижилися граблі, доведеться з цим змиритися. В залежності від напрямку стрільби граблі діляться на передні, бічні і зворотні. У Steppers граблі стріляють глайдерами і степперами. Нижче можна побачити різні варіанти граблів-стрілялок.

_r18.png
[18] Граблі, що стріляють глайдерами, передні і зворотні

_r19.png
[19] Бічні граблі

_r20.png
[20] Зворотні граблі

Не всі паровози мають настільки вузькою спеціалізацією. Паровози на наступному малюнку поряд зі стаціонарними конфігураціями випускають зворотні степпери.

_r21.png
[21] Зворотні граблі плюс стаціонарні конфігурації

А цей паровоз залишає після себе за один період дві баржі, два ботика, чотири бокових степпера і чотири зворотних, в тому числі один великий степпер шириною 12 клітин.

_r22.png
[22] Зворотні, граблі бічні плюс стаціонарні конфігурації

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

Размножители


Размножители (breeders) це конфігурації забезпечують квадратичний зростання популяції. Суть квадратичного росту в тому, що розмножувач породжує конфігурації, які, в свою чергу, теж породжують деякі конфігурації. У Steppers є два типи розмножувачів, це граблі стріляють граблями і граблі стріляють паровозами, залишають стаціонарні конфігурації (сподіваюся, що це пропозицію ніколи не вирвуть з контексту).

На наступному малюнку можна побачити розмножувач, типу MMS (moving-moving-stationary). Це означає, що рухомий об'єкт породжує рухомий, який породжує стаціонарні об'єкти. З періодом p240 він випускає чотири паровоза, які формують ланцюжок з бадей.

_r23.png
[23] Розмножувач типу MMS

Наступний розмножувач відноситься до типу MMM (moving-moving-moving). З періодом p32 він випускає граблі стріляють простими степперами. Слід відзначити невеликий розмір цього размножителя, всього 15 клітин обмежених прямокутником в 5×9 клітин. У грі Життя найменша конфігурація, що володіє квадратичним, зростанням «26-cell quadratic growth», його розмір, як видно з назви, 26 клітин, а розмір і зовсім 16193×15089 клітин.

_r24.png
[24] Розмножувач типу MMM

Емерсон Дж. Перкінс виявив дуже цікавий розмножувач. На його думку, в інших відомих клітинних автоматах подібне не зустрічається. При взаємодії двох однакових поперечних граблів породжуються такі ж граблі. Тобто дві конфігурації безпосередньо породжують собі подібних.

_r25.png
[25] Дві однакові конфігурації породжують собі подібних

Емерсон Дж. Перкінс сконструював ще кілька «синтетичних» розмножувачів. Нижче представлені размножители MMS і MMM типу. При їх створенні використані елементи глайдерного синтезу, що дозволяє сподіватися на його можливість.

_r26.png
[26] MMS розмножувач Перкінса

_r27.png
[27] MMM розмножувач Перкінса

Лічильники

Існують конфігурації, які випускають зворотні граблі в зворотному напрямку. Цим конфігурацій не судилося стати размножителями, так як потік степерів від перших випущених зворотних граблів руйнує всі наступні. Не дивлячись на це, такі патерни представляють певний інтерес. Справа в тому, що при зіткненнях знову випущених зворотних грабель з потоком степерів від перших зворотних граблів виявляється несподіваний ефект. Кожні випущені зворотні граблі знищують перший в потоці степпер, але при цьому відновлюють всі знищені раніше. Але саме так працює двійковий лічильник. Якщо розглядати ланцюжок степерів як послідовність біт і, при цьому, прийняти відсутній степпер за «1», а присутній за «0», то можна побачити, як підраховуються випущені зворотні граблі

_r28.png
[28] Лічильник

Спробуємо на основі цього патерну створити лічильник і перевірити, як він працює. Обмежимося 16-ю розрядами, тобто залишимо в потоці 16 степерів. Візьмемо довільне число, наприклад 9780. Його двійкове подання 0010011000110100. Враховуючи, що період нашого лічильника дорівнює p48, задану кількість зворотних граблів буде випущено в 9780*48=469440 поколінні. Тепер порівняємо стан лічильника в 0 і 469440 поколінні. Можна переконатися, що лічильник працює. У послідовності степерів міститься заданий нами число.

_r29.png
[29] Приклад роботи лічильника

Рушниці

Рушницею (Gun) називають нерухому конфігурацію, що випускає глайдери або космічні кораблі. На даний момент відомо три рушниці стріляють степперами, глайдерные рушниці поки не знайдені. Перше з цих рушниць випускає чотири степпера шириною в чотири клітини. Його період становить p32. На малюнку показана послідовність поколінь T= 0, 6, 12, 18, 24, 32.

_r30.png
[30] Рушниця, що стріляє степперами завширшки 4 клітки в чотирьох напрямках

Друге рушниця має період p14 і випускає чотири степпера шириною п'ять клітин. На малюнку показана послідовність поколінь T= 0, 3, 6, 9, 12, 14.

_r31.png
[31] Рушниця, що стріляє степперами шириною в 5 клітин в чотирьох напрямках

І нарешті, рушницю, яка, як і годиться, стріляє в одну сторону. Його період p10 і вона випускає степпери шириною шість клітин.

_r32.png
[32] Рушниця, що стріляє степперами шириною в 6 клітин

Осцилятори

Осцилятори це нерухомі конфігурації, які є попередниками самих себе. В своєму розвитку, вони через кілька поколінь повертаються до деякого початкового стану. На даний момент відомо близько 200 осциляторів. Деякі з них мають двійників з гри Життя. Видно, що за рахунок старіння клітин період змінюється в бік збільшення. Але не у всіх. Котел (Котлі), це осцилятор в останньому ряду, у грі Життя має період p8. У Steppers його період скоротився до p5.

_r33.png
[33] Зміна періодів осциляторів з гри Життя

В якості експерименту, велика група осциляторів з гри Життя була перенесена в клітинний автомат Steppers. Деякі з них вижили, тобто залишилися осциляторами. Нижче показана частина з них.

_r34.png
[34] Осцилятори, існуючі в грі Життя

Для пошуку осциляторів в Steppers була створена спеціальна програма, з досить примітивним алгоритмом. У центрі тороїдальної решітки розміром 256х256 клітин область розміром 16 х 16 заповнювалася осередками з випадковим станом. Випадковим чином вибиралися 12 видів симетрії вмісту квадрата. Потім, на протязі 500 поколінь вміст центральної області порівнювалося з 32 попередніми станами. У разі якщо більш ніж період назад поточний стан вже зустрічалося, її вміст виводилося в текстовий файл. Один раз виведені патерни повторно вже не пред'являлися. Потім, з досить об'ємного текстового файлу, вручну вдалося вибрати досить цікаві осцилятори. Ось приклади деяких з них.

_r35.png
[35] Приклади осциляторів, знайдених в Steppers

А тут майже повна колекція відомих на даний момент осциляторів

_r36.png
[36] Осцилятори клітинного автомата Steppers

Зіткнення

У Steppers дуже багато варіантів зіткнень, це пов'язано з великою різноманітністю степерів. З-за цього важко зробити хоч скільки-небудь повний огляд зіткнень навіть для простих степерів. Тим не менш, експерименти показали, що при зіткненнях глайдери і степпери можуть знищуватися, народжуватися, змінювати напрямок. В силу підвищеної живучості клітинного автомата Steppers, часто результатом зіткнень стає нестримний ріст популяції. Ймовірно, це може стати перешкодою для завдань глайдерного синтезу і синтезу з участю степерів.
А тепер кілька прикладів. Нижче показані варіанти зіткнення глайдера з блоком. Як видно, результатом зіткнення може бути степпер, вулик (вулик) і корабель (ship). І навпаки, результатом зіткнення глайдера з вуликом може бути блок.

_r37.png
[37] Приклади зіткнень глайдера з блоком

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

_r38.png
[38] Приклади зіткнень двох степерів

Учасник форуму conway's Game of Life Juho Pystynen (Tropylium) запропонував цікаві та функціональні приклади зіткнень. З його дозволу публікую деякі з них.

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

_r39.png
[39] Чотири потоку степерів породжують глайдери

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

_r40.png
[40] Відображення глайдерів

Висновок

У статті представлені результати досить поверхневого вивчення клітинного автомата Steppers. Багато питань залишаються нез'ясованими. Наприклад:
  • Не відомо, чи існують глайдерные рушниці.
  • Не відкрито жодного космічного корабля, який не був би степпером або глайдер, хоча немає підстав думати, що вони неможливі.
  • Не знайдені паровози, що залишають після себе осцилятори
  • Зовсім не вивчені агары. Це конфігурації, що покривають усю площину і периодичные у просторі та часі.
  • Не знайдені пожирачі, конфігурації поглинають глайдери або степпери без шкоди для себе.
  • Не вивчений глайдерный синтез, як і синтез з допомогою степерів.
Сподіваюся, що ці відкриті питання залучать любителів до дослідження клітинного автомата Steppers. Упевнений, на даний момент незрівнянно простіше зробити яке-небудь відкриття в Steppers, ніж під вздовж і поперек вивченою, грі Життя.

завантаження

MilhinSA.Golly2.5.zip (48.2 кб) — Правило MilhinSA і rle-файли прикладів.
Steppers-catalog.zip (221 кб) — Каталог конфігурацій клітинного автомата Steppers.
SidorovI.Golly2.5.zip (18.9 кб) — Правило SidorovI c прикладами.
SidorovI.Science_and_Life_1975.03.djvu (187 кб) — Стаття В. Сидорова в журналі «Наука і життя», 1975.03.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.