Клеточные автоматы. Часть II. Вариации игры "Жизнь".

Источник:

Игра «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году. К 2014 году претерпела многочисленные модификации и усовершенствования. Рассмотрим основные моменты работы, возможности создания и применения аналогов классической игры...

Джон Конвей заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом, который пытался создать гипотетическую машину, которая может воспроизводить сама себя. Джону фон Нейману удалось создать математическую модель такой машины с очень сложными правилами. Конвей попытался упростить идеи, предложенные Нейманом, и в конце концов ему удалось создать правила, которые стали правилами игры «Жизнь».

Правила

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

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

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

Фигуры

Вскоре после опубликования правил, было обнаружено несколько интересных шаблонов (вариантов расстановки живых клеток в первом поколении), в частности: r-пентамино и планер (glider).

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

Конвей первоначально предположил, что никакая начальная комбинация не может привести к неограниченному размножению и предложил премию в 50 долларов тому, кто докажет или опровергнет эту гипотезу. Приз был получен группой из Массачусетского технологического института, придумавшей неподвижную повторяющуюся фигуру, которая периодически создавала движущиеся «планеры». Таким образом, количество живых клеток могло расти неограниченно. Затем были найдены движущиеся фигуры, оставляющие за собой «мусор» из других фигур.

К настоящему времени более-менее сложилась следующая классификация фигур:

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

Моделирование естественного отбора

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

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

Геном представлен массивом из 9 чисел-генов, каждое из которых может принимать значение 0 (ген молчит) или 1 (ген активен). Первое (нулевой элемент) определяет привлекательность точки с 0 соседей, второе — с 1 соседей и так далее до 8. Если ген активен, поле с соответствующим числом соседей рассматривается клеткой как привлекательное для перемещения. Если молчит, в такую точку клетка перемещаться не будет.

Например, если у клетки геном [0,1,1,0,0,0,0,0,0], она будет стараться переместиться в точку, у которой есть 1 или 2 соседа. А если такой нет, останется на месте. Из точек с одинаковой привлекательностью выбирается случайная.

Геном отражается в цвете клеток. Чем более красная клетка, тем больше она любит одиночество. Чем более синяя, тем больше любит компанию. Чем более зелёная, тем ближе она к «золотой середине» — предпочтению 2 или 3 соседей.

При зарождении новой клетки она получает такой же геном, как у той из 3 её соседок, которая сходила последней («кто ~~последний~~ завершил комбинацию, тот и папа»).

Порядок хода клеток — случайный.

После чего он написал реализацию задумки на JavaScript.

Первыми вымирают «мизантропы» — красные, затем «дружелюбные» синие, остаются 3 группы, каждая из которых имеет полезные гены.

Но у салатовых 2 полезных гена, а у остальных по одному, поэтому в итоге они побеждают, заполняя всё пространство.

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

Что автор ожидал увидеть, и что получилось на самом деле.

Клетки, «постигшие правила жизни» и стремящиеся занять положение с 2 или 3 соседями, очевидно, должны были иметь преимущество и размножаться шустрее, чем их собратья, которым меньше повезло с генами. Но в итоге из-за перенаселённости должно было возникнуть некое равновесие численности. Я надеялся, что как в классической «Жизни» будут выделяться устойчивые геометрические или генетические комбинации, и возможно, получится понаблюдать симбиоз клеток с разными генами.

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

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

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

Имея 4 активных гена, можно получить 2 довольно долго сосуществующие популяции.

Новая реализация от другого автора: имитация отношения "хищник-жертва".

Будет полезно: использование быстрого преобразования Фурье.

Для тех кто может больше: Жизнь на плоскости Лобачевского.

«Жизнь» в 3D

Единственное, что отличает этот клеточный автомат от самого примитивного это то, что было необходимо распараллелить вычисления. В дальнейшем, правда, будет добавлено еще кое-что, но пока не будем об этом. Клеточный автомат (далее КА) для наших целей должен быть синхронным. К счастью, даже при параллельной реализации алгоритма это не создает никаких неудобств. При работе с OpenMP достаточно просто поместить цикл, вычисляющий значение КА в блок #pragma omp for {}.

Визуализатор

Было бы не плохо, если бы все это можно было увидеть воочию. Для этого использовался OpenGL с библиотекой freeglut. Необходимо, чтобы игровое пространство можно было вращать, приближать и отдалять. Управление осуществляется при помощи мышки и клавиатуры. Мышь поворачивает, клавиатура двигает. Так же с клавиатуры происходит управление самой «Жизнью». Так как для восприятия трехмерного пространства требуется больше времени, чем для двухмерного, было решено переходить к очередному шагу по нажатию на клавишу.
Первые тесты визуализатора прошли успешно. Но при попытке задать массив из 100*100*100 (или больше) клеток, каждый кадр отрисовывался вплоть до 8 секунд. Это не дело. Тут автор вспомнил про пирамиду видимости. К сожалению, отрисовка по этой самой пирамиде занимала почти такое же время, так как большую часть времени пространство полностью было видно. При приближении к центру этого пространства и дельнейшем движении за него время отрисовки уменьшалось значительно.

Внешние воздействия

Не хватает внешних факторов, влияющих на размножение клеток. В качестве такого фактора была выбрана температура.
Если кратко, то есть некая температура, назовем ее оптимальной, при которой выживаемость и рождаемость максимальные. При уменьшении и увеличении температуры выжить становится труднее. Но просто задать температуру было бы не интересно. И снова прибегнем к КА. В начальном состоянии температура сконцентрирована в центре пространства. С течением времени «теплый воздух» равномерно распределяется по всему пространству. Достигается это диффузией. Да не простой, а целочисленной. В данном случае это заключается в том, что некоторая часть температуры в клетке остается, а остальной частью соседние клетки обмениваются. Такой клеточный автомат уже не может быть синхронным, так как было ты странным, если бы все клетки одновременно поменялись… А чтобы его можно было запрограммировать под несколько процессов, необходимо прибегнуть к хитрости – перейти от асинхронного КА к блочно-синхронному. Смысл в том, что каждому процессу выделяется некоторый блок. Внутри этого блока КА является асинхронным. Но между собой блоки синхронизируются. На картинке клетки одного цвета просчитываются в одно время.

Целочисленная диффузия:

#pragma omp parallel shared(Size, BlockSize, Int_Temp, PosCell, PosNbr, DiffKoeff)\

  private(CellNum, NbrNum, x, y, z, Cell1, Cell2, Rem1, Rem2, Mov1, Mov2)

    {

    CellNum = rand() % 27;

#pragma omp for

  for (x = 1; x < Size; x += BlockSize)

    for (y = 1; y < Size; y += BlockSize)

      for (z = 1; z < Size; z += BlockSize)

      {

      NbrNum = rand() % 6;

      Cell1 = Int_Temp[(x + PosCell[CellNum][0] + Size) % Size] \

        [(y + PosCell[CellNum][1] + Size) % Size] \

        [(z + PosCell[CellNum][2] + Size) % Size];

      Cell2 = Int_Temp[(x +PosCell[CellNum][0] + PosNbr[NbrNum][0] + Size) % Size] \

        [(y + PosCell[CellNum][1] + PosNbr[NbrNum][1] + Size) % Size] \

        [(z + PosCell[CellNum][2] + PosNbr[NbrNum][2] + Size) % Size];

      //DiffKoeff определяет, какой процент температуры 

      //останется в клетке, а какой перейдет в соседнюю.

      Rem1 = Cell1 * (float)(1.0 - DiffKoeff);

      Rem2 = Cell2 * (float)(1.0 - DiffKoeff);

      Mov1 = Cell1 * DiffKoeff;

      Mov2 = Cell2 * DiffKoeff;

      if ((float)Cell1 * DiffKoeff - (float)Mov1 > (float)(rand() % 10) / 10.0)

        Rem1++;

      else if ((float)Cell1 * DiffKoeff - (float)Mov1)

        Mov1++;

      if ((float)Cell2 * DiffKoeff - (float)Mov2 > (float)(rand() % 10) / 10.0)

        Rem2++;

      else if ((float)Cell2 * DiffKoeff - (float)Mov2)

        Mov2++;

      Int_Temp[(x + PosCell[CellNum][0] + Size) % Size] \

        [(y + PosCell[CellNum][1] + Size) % Size] \

        [(z + PosCell[CellNum][2] + Size) % Size] = Mov2 + Rem1;

      Int_Temp[(x +PosCell[CellNum][0] + PosNbr[NbrNum][0] + Size) % Size] \

        [(y + PosCell[CellNum][1] + PosNbr[NbrNum][1] + Size) % Size] \

        [(z + PosCell[CellNum][2] + PosNbr[NbrNum][2] + Size) % Size] \

        = Mov1 + Rem2;

      }

    }

Дальнейшие перспективы

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

Результаты

Теперь, наконец, можно перейти к самому интересному.
Сначала программа тестировалась без температурного слоя, так как к тому времени его просто не было. К сожалению, программа не имеет нормального интерфейса, и мне пришлось написать генератор тестов. Он не представляет особого интереса. Единственная его задача – сделать в центре игрового пространства кубик из клеток. Ниже представлены кубики 3х3х3, 4х4х4 и 5х5х5. Здесь представлены только некоторые шаги, чтоб сложилась общая картина происходящего.

3х3х3, шаг 1:

3х3х3, шаг 4:

3х3х3, шаги 5 и 6:

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

4х4х4, шаг 1:

4х4х4, шаг 10:

4х4х4, шаг 100:

Дальше практически ничего не меняется.

5х5х5, шаг 1:

5х5х5, шаг 4:

5х5х5, шаг 7:

5х5х5, шаг 8:

На следующем шаге не остается ни одной живой клетки.

Теперь к кубику 4х4х4 добавим температуру. Температурный слой представлен в виде центрального среза. Красный цвет – оптимальная температура, желтый – чуть ниже нормы, розовый – низкая. Игровое пространство имеет размеры 50х50х50, в центре расположен куб 40х40х40 с оптимальной температурой. Вот что получилось.

Шаг 1:

Шаг 10: