Метод синтеза генераторов детерминированных тестов на сетях клеточных автоматов (СКА)

дипломная работа

1.5 Игра "Жизнь"

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

Рассматривается бесконечная плоская решётка квадратных ячеек-клеток. Время в этой игре дискретно (t=0, 1, 2,.). Клетка может быть живой или мёртвой. Изменение её состояния в следующий момент времени t+1 определяется состоянием её соседей в момент времени t (соседей у клетки восемь, четверо имеют с ней общие ребра, а четверо только вершины).

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

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

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

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

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

Следствием этих требований явились следующие правила игры "Жизнь":

1. Выживание. Каждая клетка, имеющая две или три соседние живые клетки, выживает и переходит в следующее поколение.

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

3. Рождение. Если число занятых клеток, с которыми граничит какая-нибудь пустая клетка, в точности равно трём, то на этой клетке происходит рождение нового организма.

Зададимся вопросами:

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

Каковы здесь законы организации структур?

Могут ли они взаимодействовать, и к чему это приводит? Выясним, какие закономерности являются следствиями представленных выше правил. Первая закономерность - свойство локализации - структуры, разделенные двумя "мёртвыми" (пустыми) клетками не влияют друг на друга. Вторая закономерность - система клеток, которую описывает игра "Жизнь", развивается необратимо. В самом деле, конфигурация в момент времени t полностью определяет будущее (состояние в моменты t+1, t+2 и так далее). Но восстановить прошлое системы по её настоящему не удаётся. Картина здесь такая же, как в одномерных отображениях, только прообразов у данной конфигурации может быть бесконечно много.

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

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

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

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

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

Теперь рассмотрим типичные структуры, появляющиеся в игре "Жизнь". Простейшими являются стационарные, то есть не зависящие от времени структуры (сам Конуэй называет их "любителями спокойной жизни"). Их примеры показаны на рис 1.8 С помощью этих стационарных структур можно получить множество других. В самом деле, если мы имеем такую структуру, то конфигурация, полученная поворотом на 900, также будет стационарной. Конфигурации в нижних рядах показывают, как можно достраивать определённые структуры до любых размеров. Используя свойство локализации можно строить "большие" стационарные структуры из "малых" - элементарных.

Рисунок 1.8 - Примеры стационарных структур, реализующихся в игре "Жизнь"

Можно считать, что стационарные структуры повторяют себя на каждом шаге по времени. Но есть и другие конфигурации, повторяющие себя через N шагов, так называемые N-циклы (периодические структуры). При эволюции различных сообществ часто встречается 2-цикл, называемый "семафором". Однако эффективные алгоритмы, позволяющие строить различные конфигурации с данным периодом N, по-видимому, в настоящее время не созданы. Эволюция взятых наугад начальных данных часто приводит к возникновению простейших локализованных структур (показанных на рис.1.8) и семафоров. Однако возможны и более сложные типы эволюции, например, когда сообщество клеток симметрично "достраивается", и возникают циклы большого периода, имеющие сложную форму.

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

Рисунок 1.9 - Планер

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

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

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

Более сложным образом конструируются другие элементы. Для анализа ситуаций, возникающих в игре "Жизнь", применяется компьютер.

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

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

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

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

Делись добром ;)