Игра «Жизнь» на примере клеточных автоматов

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

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

прошлое системы по ее настоящему не удается. Картина здесь такая же, как в

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

бесконечно много. (Докажем это утверждение: воспользуемся свойством локализации

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

клеток или их пар так, чтобы они не влияли на нее и друг на друга. Понятно, что все

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

Здесь мы можем заметить признаки нелинейных диссипативных структур: эти

структуры определяли поведение системы при t стремящемся к бесконечности в

случае различных начальных данных.

Третья закономерность – как показывают длительные наблюдения за

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

симметрией, обнаруживают тенденцию к переходу в симметричные формы.

Обретенные свойства симметрии в процессе дальнейшей эволюции не утрачиваются,

симметрия конфигурации может лишь обогащаться.

Условимся классифицировать конфигурации клеток по следующим

параметрам:

• По количеству клеток в комбинации: единичная клетка, дуплет (2 клетки вкомбинации), триплет (3 клетки) и т.д.

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

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

период).

Теперь рассмотрим типичные структуры, появляющиеся в игре «Жизнь».

Простейшими являются стационарные, то есть не зависящие от времени структуры (сам Конуэй называет их «любителями спокойной жизни»). Их примеры показаны на рисунке 1. С помощью этих стационарных структур можно получить множество других. В самом деле, если мы имеем такую структуру, то конфигурация, полученная поворотом на 90 О , также будет стационарной. Конфигурации в нижних рядах показывают, как можно достраивать определенные структуры до любых размеров.

Используя свойство локализации можно строить «большие» стационарные структуры из «малых»-элементарных.

Рис.1. Примеры стационарных структур, реализующихся в игре «Жизнь»

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

называемые N-циклы (периодические структуры).

Примеры 2-циклов показаны на рисунке 2. Об этом говорит сайт https://intellect.icu . При эволюции различных сообществ часто встречается 2-цикл, показанный во второй строке и называемый

«семафором»

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

периодом N, по-видимому, в настоящее время не созданы.

Эволюция взятых наугад начальных данных часто приводит к возникновению простейших локализованных структур (показанных на рисунке 1) и семафоров.

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

имеющие сложную форму.

В игре «Жизнь» существуют конфигурации, которые могут передвигаться по плоскости. Одной из них является «планер» (или «глайдер») – конфигурация из 5

клеток (рис. 3)

После второго хода планер немного сдвигается и отражается относительно диагонали.

В результате двух последующих ходов планер «выходит из пике», ложится на

прежний курс и сдвигается на одну клетку вправо и одну клетку вниз относительно

начальной позиции.

Скорость, с которой шахматный король перемещается по доске в любом

направлении, Конуэй называет «скоростью света». Выбор Конуэя пал именно на этот

термин из-за того, что в изобретенной им игре большие скорости просто не

достигаются. Ни одна конфигурация не воспроизводит себя достаточно быстро,

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

диагонали составляет одну четверть скорости света. Поскольку планер переходит сам

в себя после четырех ходов и при этом опускается на одну клетку по диагонали, то

говорят, что он скользит по полю со скоростью, равной одной четвертой скорости

света. Конуэй также показал, что скорость любой конечной фигуры,

перемещающейся по вертикали или по горизонтали на свободные клетки, не может

превышать половину скорости света. (Скорость движения равна дроби, в числителе

которой стоит число ходов, необходимых для воспроизведения фигуры, а в

знаменателе – число клеток, на которое она при этом смещается). Понятно, что в силу

симметрии есть планеры, распространяющиеся вдоль любой диагонали квадрата в

обоих направлениях.

Впрочем, некоторые конфигурации могут передвигаться не вдоль диагоналей, а

по вертикальным и горизонтальным прямым. Таковы, например, три «корабля»

показанные на рисунке 4. (Обратим внимание на то, что далеко не любая

конфигурация такого типа будет кораблем). Кстати, планер является кораблем

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

гаснут при дальнейшем движении кораблей.

Рис. 2. Примеры периодических структур (2-циклы), реализующихся в игре «Жизнь» (жаба, семафор, часы)

Рис 3. Планер (глайдер) – перемещающаяся конфигурация из 5 клеток

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

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

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

в сто клеток требует эскорта, состоящего из тридцати трех (!) кораблей. Итак, мы располагаем планерами и различными кораблями. Возникает вопрос,

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

разнообразны в зависимости от курса планера и его фазы при столкновении. Столкновение двух планеров или планера со стационаром может приводить к их

«аннигиляции». В столкновении может рождаться целый набор семафоров и стационаров.

Обратим внимание на следующую закономерность. Если конфигурация все время локализована в квадрате размером NxN, то она является набором стационаров и

циклов, период которых не превышает 2^N . В самом деле, каждая клетка может находиться в одном из двух состояний, а всего клеток в области N^2 , поэтому при t>2^N конфигурации начнут повторяться.

Рис. 4. Корабли – конфигурации, реализующиеся в игре «Жизнь», способные перемещаться

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

чем в остальных случаях. В игре «Жизнь» есть аналог такого поведения. Обратим внимание на конфигурацию, показанную на рисунке 5, называемую «r-пентемино».

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

Рис. 5. Конфигурация из 5 клеток, демонстрирующая эффект резонансного возбуждения (r-пентемино).

Рис. 6. Планерное ружье (катапульта) – конфигурация, генеририрующая за каждые 30 ходов планер.

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

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

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

качественно изменить поведение системы, привести к появлению новых видов. Именно поэтому игра «Жизнь» находит применение в экологических моделях, при

моделировании морфогенеза, в других биологических задачах.

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

конфигурации. Одну из них, называемую «катапультой» или «планерным ружьем», предложил в 1970 году Р. Госпер-младший. Видно, что катапульта через каждые 30 шагов повторяет себя и выпускает планер (см. рисунок 6). Планерное ружье заполняет пространство потоком планеров. Конуэй высказал гипотезу, согласно

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

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

Опровержение – планерное ружье.

Есть еще более сложные сообщества клеток, которые могут двигаться, оставляя за собой большой набор семафоров и стационаров. Одно из них — «паровоз» (он

имеет довольно сложную структуру). Поиск таких конфигураций – довольно трудоемкий процесс, требующий применения специальных алгоритмов и под силу

квалифицированным специалистам.

Также были найдены особые конфигурации, которые Джон Тьюки назвал «садами Эдема». «Сады Эдема» не могут возникнуть в ходе работы клеточного

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

предшественников, они не могут быть самовоспроизводящимися. Алви Р. Смит нашел способ применить теорему Мура к игре Конуэя и показал, что конфигурация по типу «садов Эдема» возможна и в «Жизни». Формулы, выведенные Муром, позволили Смиту утверждать, что подобная конфигурация всегда может быть

заключена в квадрат со стороною в 10 000 000 000 клеток. Приведенные примеры показывают, что в обсуждаемой дискретной системе

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

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

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

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

импульсов в игре «Жизнь» выступает планерное ружье. Наличие планера в потоке естественно интерпретировать как единицу, отсутствие как ноль. Столкновение

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

Для анализа ситуаций, возникающих в игре «Жизнь», применяется компьютер. В программе, моделирующей этот клеточный автомат, используется квадратная

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

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

• Условия рождения и смерти. Задаются четыре параметра (параметры можно менять в процессе игры): минимальное и максимальное количество соседей своей

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

• Соседями клетки могут быть любые клетки, находящиеся в квадрате 3х3 с центром в данной клетке.

Игра «Жизнь» нашла свое применение в биологии как игра «Аква-Тор», которая моделирует поведение системы, состоящей из двух популяций, условно

называемых «травоядные» и «хищники».

Задания Игра «Жизнь»

1) Стандартные правила

• Исследовать правила эволюции в игре. Рассмотреть динамику простейших популяций: одна клетка, две клетки, различные конфигурации из трех и

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

• Рассмотреть динамику всех вышеуказанных конфигураций.

• Рассмотреть динамику конфигураций на рис. 16, определить характер их поведения. В случае периодической динамики найти период колебаний.

• Найти свои собственные начальные конфигурации в игре «Жизнь», которые бы удовлетворяли следующим требованиям:

а) с течением времени популяция «погибает».

б) с течением времени в системе наблюдается становление стационарного состояния

в) после переходного процесса в системе наблюдается периодические колебания с периодом 2.

г) после переходного процесса в системе наблюдается периодические колебания с периодом 3.

д) после переходного процесса в системе наблюдается периодические колебания с периодом 4.

е) популяция за достаточно большое время (более 70 шагов) не приходит к какому-либо регулярному поведению или устойчивому состоянию.

• Исследовать динамику конфигурации под названием Глайдерное ружье. (рис. 6)

Рис. 16

2) Модифицированные правила

• Поместить на плоскость две популяции, каждая в конфигурации “r- пентамино”(рис. 16д). По графику статистики дождаться, пока обе выйдут на

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

• Исследовать столкновение двух глайдеров разных цветов. В чем отличие от случая одной популяции?

• Поместить на поле синий «блок». Изменить свойства синей популяции следующим образом: убрать из окрестности клетки одну угловую клетку и

установить модель 2323. Проследить несколько шагов эволюции конфигурации.

Объяснить полученный результат. Оценить скорость перемещения получаемого фронта.

• При этих же параметрах поместить на поле синий блок и красный блок со стандартными параметрами (модель 3323, окрестность 8 клеток). Исследовать

взаимодействие популяций, объяснить, почему синяя доминирует.

• добиться параметров, при которых единственная клетка на поле выживает и в своем развитие движется вверх по полю.

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

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