XXI Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Клеточные автоматы. История и реализация самой странной игры человечества

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Николайко А.А. 1

---

1МОУ Раменская СОШ 21

Ющенко О.В. 1

---

1МОУ Раменская СОШ 21

Работа в формате PDF

1.3 MB

Автор работы награжден дипломом победителя III степени

Диплом школьникаСвидетельство руководителя

Введение

(2) Все началось с клеток. Миллиарды лет назад, когда геологическое строение нашей земли только начинало формироваться, уже начали появляться первые простейшие живые организмы: бактерии, цианобактерии, прокариоты, эукариоты и др. Эти вещества долгое время развивались в пустынной среде, размножались и эволюционировали в то, что мы имеем в биосфере нашей планеты на сегодняшний день. Но возможно ли создать подобную среду для размножения, деления и вымирания клеток прямо на компьютере?

(3) Одной из главных целей является изучение этого вопроса и конечное понимание, как именно это возможно.

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

• Разобрать историю создания клеточных автоматов

• Изучить биографию Джона Конвея

• Рассказать, что такое Игра “Жизнь”

• Разобрать самые распространенные паттерны

• Рассмотреть другие вариации клеточных автоматов

• Реализовать клеточные автоматы на языке программирования С++

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

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

Раздел 1. Теоретическая часть

История первых клеточных автоматов

(5) В 40-е годы 20 века Станислав Улам, работая в Лос-Аламосской национальной лаборатории, изучал рост кристаллов, используя простую решёточную модель. Его коллега, Джон фон Нейман, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель называется кинематической. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом, фон Нейман ввёл понятие клеточных автоматов как инструмент математического моделирования, следуя идее Улама. В качестве основной цели преследовалась необходимость обеспечения более реалистичных моделей поведения сложных и распределённых в двух- или трёхмерном пространстве систем.

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

Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана одним из конструкторов первого электронного компьютера Бёрксом, который сохранил активный интерес к этой области и на протяжении последующих лет. Его «Очерки по клеточным автоматам» являлись хорошим обобщением знаний того времени в данной области. Одновременно с работами Бёркса его коллега по Мичиганскому университету Голланц приступил к использованию клеточных автоматов для решения задач адаптации и оптимизации. Им был разработан программный имитатор универсальных клеточных автоматов общего назначения.

Джон Конвей и игра “Жизнь”

(7) Британский математик, внёсший огромный вклад в математику: сформулировал гипотезу чудовищного вздора в теории групп, заложил основы комбинаторной теории игр, попутно открыв сюрреальные числа, также внёс вклад в теорию узлов, теорию чисел и многое другое. Джон Конвей говорил, что не проработал ни единого дня, а только играл.

В нашей истории он играет одну из важнейших ролей, создав в 1970 году игру “Жизнь” и тем самым популяризовав модель клеточных автоматов. Но автоматы фон Неймана были крайне сложны — у них было несколько десятков возможных состояний, которые кодировались разными цветами. Конвей радикально упростил законы, по которым работает клеточный автомат, и с этого момента начался расцвет этой области математики и компьютерной науки.

Как же работает игра “Жизнь”?

(8) Допустим, у нас есть поле, состоящее из клеточек. (9) Эти клетки мы можем либо закрашивать, либо стирать. При этом, у каждой клетки есть 8 (10) соседних клеток, которые её окружают, и для каждой клетки мы подсчитываем количество соседних закрашенных клеток ровно также, (11) как в игре “Сапер” цифры показывают количество окружающих клетку мин.

(12) Дальше мы действуем по следующим правилам:

• (13) если клетка ещё не закрашена, и у нее есть ровно три закрашенных соседа, то ее мы тоже закрашиваем

• (14) если клетка уже закрашена, то она остается закрашенной, если у нее есть ровно два или три закрашенных соседа

• (15) в остальных случаях мы стираем клетку

• (16) игра заканчивается либо тогда, когда все клетки стираются, либо тогда, когда поле клеток приходит к своему оптимальному положению: то есть при следующей итерации клетки остаются в таком же положении, либо зацикливаются до бесконечности

(17) У этих правил есть даже специальное название: B3/S23, что означает, что клетка рождается, если у нее есть ровно три соседа, а выживает, если у нее два или три соседа. На этом этапе мы уже можем заметить сходство с биологическими моделями: клетки рождаются, выживают, умирают подобно биологическим клеткам или микробам, которые рождаются, если вокруг них есть еще микробы. Если вокруг микроба других микробов становится слишком много, то он умирает от перенаселения, а если их слишком мало, то он умирает от одиночества.

(18) Именно из-за этого игра получила название Игра “Жизнь”, хотя это не совсем игра, ведь по сути играть мы в нее не можем. Все, что мы можем сделать, так это задать изначальное положение клеток и посмотреть, как они будут развиваться. Из-за этого её часто называют игрой от 0 лица или игрой для 0 игроков.

(19) Чтобы наглядно продемонстрировать работу игры Жизнь, посмотрим, как будут вести себя клетки на игровом поле.

(20) К примеру, закрасим на пустом клеточном поле одну клетку. (21) У нее не будет ни одного живого соседа, поэтому, следуя правилам игры, она умирает. (22) Попробуем закрасить две клетки. (23) У каждой клетки будет всего один (24) живой сосед, поэтому обе они также погибнут (25). Если же мы расположим (26) три клетки в виде лесенки, мы заметим, что у каждой клетки (27) будет по два соседа, поэтому они выживут. Но также (28) вот здесь находится пустая клетка, у которой три закрашенных соседа, а поэтому при следующей итерации она закрасится. После этого на поле образуется квадрат (29), который никак не изменится на протяжении следующих шагов игры, так как у каждой закрашенной клетки по 3 соседа, а пустых клеток с 3 соседями нет. Такие фигуры называют устойчивыми или фигурами-натюрмортами.

(30) Теперь попробуем взять 3 клетки в линию. У клеток по краям будет (31) всего один сосед, поэтому в следующей итерации они погибнут (32). Клетка посередине выживет, так как у нее ровно два живых соседа. А вот эти две клетки сверху и снизу имеют (33) по 3 живых соседа, поэтому при следующем шаге они смогут родиться. (34) После этого процесс повторится, но совершенно наоборот и таким образом будет повторяться вечно. (35) Такие фигуры называют осцилляторами, то есть фигуры, которые циклично переходят из одного состояния в другое.

(36) Вот еще несколько примеров устойчивых фигур и осцилляторов. И пожалуй, одна из самых известных фигур – глайдер. Он также является осциллятором, но в отличие от других каждый свой цикл он сдвигается на одну клетку по диагонали.

(37) В игре также присутствуют различные ружья, которые создают фигуры (например: ружье Госпера), космические корабли и паровозы, которые оставляют за собой блоки или фигуры.

(38) Теперь посмотрим, что будет, если мы случайно расположим клетки на поле.

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

Другие виды клеточных автоматов

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

(39) Например, правила B3/S12345 или B3/S1234 создают случайные лабиринты, алгоритм генерации которых можно даже использовать в создании игр.

(40) С правилом B1/S012345678 создаются вот такие красивые растущие фракталы.

(41) Используя правила B35678/S5678 можно создать вот такую поглощающую диамёбу.

Я уже упоминал, что с помощью игры Жизнь можно создать компьютер и это правда, ведь она является полностью Тьюринг-полной, то есть в теории, в ней можно создать вычислительную машину, калькулятор, который будет производить различные арифметические операции и даже полноценный компьютер, куда можно загрузить программы, состоящие из двоичного кода, возможно даже… создать игру Жизнь в игре Жизнь? Но как вы понимаете, провернуть всё это будет очень сложно, и на это уйдут годы, если не десятки лет. (42) Поэтому и для этого придумали специальный клеточный автомат, под названием WireWorld. В нем можно проводить различные логические операции, управлять движением сигнала и многое многое другое. Энтузиасты даже смогли создать такую расстановку клеток, что автомат способен производить вычисления, другой же, например, способен находить все простые числа.

(43) Вот ещё парочка примеров разных правил. Правило 161, которое в точности реализует один из популярных фракталов, треугольник Серпинского. А вот, так называемый, “Персидский ковер”.

Раздел 2. Практическая часть

(44) Итак, мы узнали историю создания первых клеточных автоматов, познакомились с творением Джона Конвея, а теперь пришло время написать программу для воссоздания различных клеточных автоматов, в том числе и игры Жизнь на языке С++.

Моя программа должна будет работать в консоли, принимать любые правила в формате B*\S* и воспроизводить каждый автомат безошибочно.

Алгоритм программы будет такой: (45)

1. Запись правил клеточного автомата в переменные

2. Инициализация первого поколения игры случайными значениями

3. Анализ каждого поколения на наличие соседей у клеток и генерация последующих шагов на основе этих данных

4. По правилам игра закончится, когда все клетки поля придут к оптимальному значению, либо погибнут.

(46) Поле будет находиться в двух двумерных массивах: один для текущего поколения и второй для нового. Функция worldInit инициализирует первое поколение случайными значениями координат с помощью библиотеки random.

Функция printWld отвечает за вывод поля в консоль. Далее идет подготовка к генерации следующего поколения клеток. Этот алгоритм состоит из нескольких функций:

• (47) readNeighbors – функция, которая считывает соседей каждой клетки и записывает и двумерный массив, который передается в следующую функцию

• (48) countLive – функция, которая из соседей клетки считает только живые

• (49) nextGen – основная функция, которая на основе уже полученных данных генерирует следующее поколение

• (50) compareWld – функция, которая сравнивает новый мир с текущим и выводит -1, если оптимальная генерация пока что не найдена

Далее с помощью уже упомянутой функции printWld на экран консоли выводится новое поколение, а старое стирается.

(51) Вызов всех функций осуществляется в функции main.

Посмотрим, как алгоритм будет работать на деле.

(52) Запишем туда правила для обычной игры Жизнь (B3/S23). Как мы видим, алгоритм успешно справляется: случайно расставляет живые клетки и подсчитывает каждый шаг. Мы можем увеличить или уменьшить шанс появления клеток или увеличить размер поля, но, к сожалению, слишком большой размер приводит к морганию консоли, так как она просто не успевает быстро обновиться.

(53) Попробуем изменить правила. Вот выстраиваются уже знакомые нам лабиринты. А вот пример воспроизведения диамебы.

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

Заключение

(54) Изучая материал для своего проекта, я узнал много нового для себя и узнал о существовании такой интересной дискретной математической модели, как клеточный автомат. Если так задуматься, то их потенциал не ограничивается простым созерцанием на алгоритмическую реализацию живой природы. Это на первый взгляд лишь простой алгоритм, лишь 3 простых правила, которые дают огромный простор для создания чего-то совершенно большего. Это игра, которая существует своей жизнью, существует без вмешательства человека. Она может развиваться путем рождения новых клеток, скрещивания различных фигур, а может внезапно полностью умереть. Поэтому эта модель и похожа на живую жизнь, похожа своей независимостью, индивидуальностью и непредсказуемостью. Ведь количество правил клеточных автоматов доходит до 2¹⁸, а вариантов различных генераций так вообще бесконечно много. И я хочу, чтобы об этом узнало как можно больше людей, чтобы больше людей могло наслаждаться умиротворяющей и завораживающей жизнью “компьютерных живых организмов”, которые являются лишь ещё одной из тысяч невероятных математических моделей.

исок литературы

1. https://ru.wikipedia.org/wiki/Конвей,_Джон_Хортон

2. https://habr.com/ru/articles/718620/

3. https://ru.wikipedia.org/wiki/Клеточный_автоматПриложение