Пользователь
0,0
рейтинг
8 октября 2012 в 15:25

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

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

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

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


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

Есть «вселенная», представленная в виде квадрата, разбитого на квадратные же поля. Поле может быть пустым, либо на нём может жить клетка. Каждый «день» игры рассчитывается новое поколение клеток по следующим правилам:
  • на пустом поле, рядом с которым ровно 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
карма
44,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (44)

  • +7
    К сожалению, для рождения новой клетки нужны 3 родителя.
    Для «честного» моделирования жизни нужно, чтобы было 2 родителя, а каждый ген чтобы выбирался из родительских случайным образом с вероятность 1/2. При этом «проигравший» ген также должен запоминаться и на следующем этапе учитываться с вероятностями 1/4, 1/8 и тд.
    Хотя, с 3 родителями можно поэкспериментировать со степенями 3
    • 0
      Да, модель можно долго усложнять, углубляясь в детали генетики, но я решил остановиться на такой детализации. Главное что принцип «правильное поведение ведёт к передаче генов потомку» сохранился.
    • 0
      Ниже в комментариях предлагают гексагональное поле. Я вот тоже о нём подумал: соседних ячеек становится шесть, а не восемь — возможно, в таких условиях рождение клетки от двух родителей будет иметь право на жизнь.
  • +1
    Мне в свое время, нравилось играть с начальным существом, то есть искать конфигурацию, которая проживет как можно дольше. Конечно, с постепенным увеличением количества начальных клеток. Очень увлекательно!
    • +1
      Это да, вокруг «Жизни» столько всего наворотили за 40 лет: и классификацию организмов, и поиски конкретных…
      • +2
        Кстати, я после недавнего упоминания «Жизнь» на Хабре, купил настольную игру «Эволюция», отличная игра оказалась :)
        • +2
          Да, отличная игрушка, у меня тоже есть. :) А я в размышления об эволюции втянулся после того как прочёл «Рождение сложности» Александра Маркова.
          • 0
            Это того Маркова, который создал Марковские цепи?
            • +1
              Не, тот был Андрей, математик, и умер почти век назад, а этот — Александр, биолог, вполне бодр и весел. :)
  • +1
    А если ген потомка определять из генов предков голосованием (каждый бит отдельно)? Тоже все сведется к (2,3)?
    • +1
      Мне кажется, да, только медленнее. Это же 100% выигрышная комбинация.
  • +6
    есть крутая прога для моделирования мультиагентных систем ccl.northwestern.edu/netlogo/, там есть куча предустановленных алгоритмов поведения (например модели сегрегации Шелла, модель распространения слухов, игра жизнь и т.д), и встроенный язык для программирования агентов

    если вам интересно моделирование такого рода как в статье, то думаю вам будет интересна прога -)
    • +1
      Спасибо, посмотрю.
    • 0
      Шеллинга (Schelling) только
      • 0
        чорт точно -)
  • +3
    Желаю Вам поскорее выздороветь! Попробуйте жизнь на треугольных клетках и для трехмерных сеток.
    • +1
      Спасибо, стараюсь. :)
      Я если эту тему буду дальше обдумывать, скорее, пойду в сторону более сложных алгоритмов поведения.
    • 0
      Да, тоже люблю все обобщать :)
      Еще можно на гексагональных сетках!
      И как насчет того, чтобы вместо плоскости использовать сферу?
      • 0
        На сфере не развернешься. Самая большая полурегулярная решетка — 120 треугольников. Вот на плоскости Лобачевского — раздолье! Хм…
      • 0
        У меня есть похожая игра на сфере, только сетка нерегулярная, использую ячейки Вороного. Даже в аппстор выкладывал, американцы не осилили)
        • 0
          А она у вас только для устройств Apple? Было бы интересно посмотреть. Не могли бы вы ее выложить куда-нибудь?)
          • 0
            Я ее игрушкой сделал для детей, работает только для iPhone. Там отдельные ячейки давить надо, когда они теряют соседей. Не очень интересно.
        • +1
          А можно ссылку?
  • +1
    великолепная статья и пример, очень хорошая тема. так держать!
    • 0
      Спасибо. :)
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    «Креационизм» интересный, а на работающей модели, сделанной более года назад на JS, можно увидеть ещё 2 альтернативных и давно признанных правил «Жизни», поставив галочки напротив "DayNight" или "Sidorov's". Сначала было сделано для тестирования движка, а потом стало интересно, как ведут себя другие версии «Жизни», и были прикручены они.
    • 0
      Статья habrahabr.ru/post/111686/ и прямая ссылка на модель spmbt.kodingen.com/lifeConway.htm.
    • 0
      Да, я видел вашу реализацию, когда искал, что на Хабре писали про «Жизнь» (было интересно, который я по счёту тут человек, реализовавший её на JS и Canvas :) ). Хорошая статья, и жалко, что часть картинок уже не отображается.
      • 0
        Странно, у меня отображаются все картинки, сколько ни открываю.
        • 0
          У меня в таблице «Жизнь случайно заполненного начального поля, 100 шагов» первые две не показывает. Остальные сейчас прогрузились. Может, Радикал подглючивает…
    • 0
      Хм, алгоритм DayNight генерирует очень реалистично выглядящую «карту» Каждое скопление выглядит как отдельный материк/остров и края почти идеально подходят. Интересно, кто-нибудь уже пробовал использовать игру жизнь с этим алгоритмом для генерации карты материков? :)
  • +2
    Меня в свое время поразил Муравей Лэнгтона. А именно то, как с помощью такого небольшого набора правил достигается такое сложное и непредсказуемое поведение.
  • –1
    Здесь должна быть какая-нибудь шутка насчёт QR-кода и ДНК
  • 0
    У вас в коде нигде ошибки нет? Если пронаблюдать «классическую» жизнь, то можно заметить, как закрашенные точки возникают на пустом месте, где рядом нет никаких соседей.
    • 0
      Всякое может быть… Сейчас понаблюдал, не получилось отловить такого. Попозже ещё посмотрю. Точно место пустое, не край квадрата (там могли повлиять соседи с противоположного края)?
      • 0
        Да с краю. Похоже именно так и есть.
  • –1
    По-моему неплохой генератор случайных чисел
  • +1
    По-моему, если снова нажать старт, старая не прекращается, а начинают работать 2 игры параллельно.
    • 0
      В смысле, не нажимая «Пауза», нажать «Старт», а потом ещё раз «Старт»? Да, действительно. Спасибо, поправлю.
  • +1
    Получилось очень похоже на реальные опыты с бактериями. Одноклеточные не обмениваются геномами, а буквально клонируют себя. И в результате, если в популяции появляется мутант, более приспособленный к среде обитания, то он через несколько сотен поколений размножается в неимоверных количествах и вытесняет всех остальных.

    Вот, например, статья про кишечную палочку
  • +1
    А еще можно в Google ввести «conways game of life». Забавный результат получается.
  • 0
    А что бывает в тех случаях, когда нескольким организмам приглянулась одна клетка? Один заменяется другим?
    • 0
      Они ходят по очереди: каждый выбирает позицию и сразу в неё перемещается. Соответственно, следующий туда встать уже не сможет.

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