Игра «Жизнь» и моделирование естественного отбора

в 11:25, , рубрики: Conway's game of Life, Алгоритмы, естественный отбор, игра жизнь, искусственный интеллект, метки: , ,

Игра «Жизнь» и моделирование естественного отбораВалялся я на прошлой неделе в больнице. И так как обсуждать с дедушками в холле рецепт яблок, мочёных в капусте, и как хорошо на Покров гулять по заливным лугам — особого желания не было, пришлось придумывать себе развлечение.

Я задумался об игре «Жизнь», которую на Хабре не так давно вспоминали. Мне стало обидно за несчастные клетки, которые живут и умирают в зависимости от одних только начальных условий, и ничего сами для своего выживания сделать не могут. В результате я придумал расширение для правил игры, с которым можно моделировать не только изменение численности популяции, но и естественный отбор внутри неё.

Самые нетерпеливые сразу могут посмотреть, что получилось, а остальных прошу под кат за рассказом.

На всякий случай напомню правила классической «Жизни».

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

  • на пустом поле, рядом с которым ровно 3 живые клетки, зарождается новая клетка;
  • если у живой клетки есть 2 или 3 живые соседки, эта клетка продолжает жить;
  • если соседей меньше 2 или больше 3, клетка умирает (от «одиночества» или от «перенаселённости» соответственно).

Вселенная «тороидальная»: если зайти за её правый край, окажешься на левом, с верхом и низом то же самое.

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

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

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

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

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

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

При этом классическая Conway's Game of Life — это предельный случай, когда у всех клеток геном [0,0,0,0,0,0,0,0,0].

После чего я написал реализацию всей этой задумки на JavaScript: http://widgetok.ru/life/
Для сравнения расчёт проводится сразу для двух «вселенных». Слева — по моим правилам, справа — по классическим правилам Конвея. При запуске вселенные заполняются случайным образом. Можно настраивать размер, количество клеток на старте и количество генов, которые будут у каждой клетки активными.
Если кликнуть на клетку, внизу можно посмотреть её геном.

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

Вот пример, как обычно развивается популяция из клеток с 2 активными генами.
Вначале имеем разнообразие геномов. «Синей» клетке стать легче (за это отвечают 4 гена из 8), поэтому синий цвет преобладает.
Игра «Жизнь» и моделирование естественного отбора
Первыми вымирают «мизантропы» — красные, затем «дружелюбные» синие, остаются 3 группы, каждая из которых имеет полезные гены.
[0,0,1,1,0,0,0,0,0]
[0,0,0,1,0,0,0,1,0]
[1,0,0,1,0,0,0,0,0]
Игра «Жизнь» и моделирование естественного отбора
Но у салатовых 2 полезных гена, а у остальных по одному, поэтому в итоге они побеждают, заполняя всё пространство.
Во вселенной Конвея к этому моменту население сильно поредело, и оформились стабильные островки.
Игра «Жизнь» и моделирование естественного отбора

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

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

Реальность оказалась проще.

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

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

Чем больше активируется генов, тем больше в геноме «мусора», заставляющего клетку принимать неверные решения о направлении перемещения.
Имя 4 активных гена, можно получить 2 довольно долго сосуществующие популяции
[0,0,1,1,0,0,0,1,1]
[1,0,1,1,0,0,0,1,0]
Игра «Жизнь» и моделирование естественного отбора
8 активных генов — популяция балансирует на грани вырождения.
Игра «Жизнь» и моделирование естественного отбора
9 активных генов — увы, слишком много. Популяция гибнет.

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

Что можно было бы сделать ещё.
Сначала я думал включать все гены, а их значение сделать числом от 0 до 9, определяющим «величину» привлекательности поля. Но при этом результаты отбора получаются не такие наглядные, сложно определить, почему тот или иной геном победил.
Ещё можно заставить клетки мутировать, изменяя их геном или скрещивая при зарождении. Но, мне кажется, при текущих правилах всё равно победят «салатовые». Разве что заставить правила меняться со временем, как и в настоящей жизни… ;)

Автор: PsiBG

Поделиться

* - обязательные к заполнению поля