Аналог игры «Жизнь» — Evo

Приветствую вас, хабражители!

Недавно прочитал статью про игру Жизнь, и вспомнилось мне, что я в мае этого года начинал писать свой проект подобной направленности. Только вот интерес к нему за рутиной работы быстро угас, хотя написано было немало. И сейчас, вдохновлённый этой статьёй, я взял этот проект с пыльной полки и добавил несколько фич, о которых расскажу далее.
Вкратце, мой вариант имеет следующие условия:
  • жизнь развивается на поле 256*256 клеток;
  • на поле могут размещаться объекты трёх типов: живность, пища(назовем её травой) и камень (препятствие);
  • живность представляет собой фактически модифицированную машину Тьюринга, если точнее, то это больше похоже на Автомат с магазинной памятью, т.е. живность является «процессором», выполняющим свой «генетический» код;
  • живность имеет возможность совершать определенные действия (двигаться, есть, размножаться (пока только клонированием, мутации будут со дня на день, скрещивание в перспективе)), отдавая соответствующие команды;
  • наступив на траву, живность её вытаптывает;
  • для поглощения еды надо дать команду «Ешь в этом направлении!», находясь в соседней клетке;
  • живность имеет память, что позволяет строить циклы, условия и т.п., т.е. полная по Тьюрингу (поправьте меня, если не прав!), объем памяти неограничен;
  • живность может складывать и вычитать значения в уме, разрядность ограничена одним байтом;
  • существует возможность реализации генетических алгоритмов (пока не реализовано).
Кому интересны подробности, прошу под кат!

Краткое описание


Программу я обозвал Evo (git), поскольку изначально планировалось, чтобы организмы там эволюционировали. Но ничто не мешает самому описать алгоритм поведения живности и подгрузить его в программу. На текущий момент только правкой кода (в MainWindow::MainWindow()), но загрузка живностей будет реализована в скором времени.
Evo написана на С++/Qt. Работоспособность проверена только под Linux, хотя программа должна работать на любой платформе, которая поддерживается библиотекой Qt.
Для получения бинарника достаточно выполнить:
    git clone git@github.com:icoz/evo.git
    cd evo
    qmake
    make


Итак, при старте появляется окно с несколькими кнопками.Стартуем и наблюдаем как поле заполнилось цветами.


Поясню, что какой цвет имеет:
  • пустота — белая;
  • камень — красный;
  • трава, конечно же, зелёная;
  • а синим я выделил живность.

При старте генетический код живности генерируется с помощью ДСЧ. Так что никакого волшебства нет. Правда, позже волшебство появляется! Что-то произвольно сгенерированное начинает ползать, жрать друг друга, да и подножный корм тоже.
Есть несколько простых правил:
  • Каждые 150 (по умолчанию) раундов на поле подкидывается от 100 до 1100 клеток травы для компенсации поедания и вытаптывания, причем для каждой травинки подыскивается исключительно незанятая клетка.
  • Каждые 500 (по умолчанию) раундов добавляется по 150 произвольно сгенерированных живностей, которые тоже начинают пытаться выживать.
  • При превышении численности населения свыше 1500 особей проводится чистка: убиваются все живности, у которых fitness == 0.

Логическое разбиение следующее.
Поле (класс Map) реализует функции хранения и перемещения объектов, а также фукнцию разбрасывания заданного количества пищи.
Мир (класс World) описывает взаимодействие живностей с окружающим миром.
Живности (экземпляры класса Animal) являются автоматами, программой которого является «генетический» код (и напомню, что каждая особь имеет память и возможность складывать и вычитать в уме). В процессе исполнения этого кода организм принимаетте или иные решения. Мир обрабатывает эти запросы (всё это реализовано посредством системы сигналов/слотов).

В случае приемлимого поведения живность премируется повышением параметра fitness. За поглощение травы fitness увеличивается на 1, за поедание другой живности — +10, за размножение — +50. Чем выше значение fitness, тем более успешен организм. Фактически, этот параметр описывает живучесть организма. Кстати, жду Ваших предложений по введению новых правил, чтобы усложнить этим милым существам жизнь и заставить их придумывать что-то новое.

Реализовано всё это безобразие так:

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

Что ещё хочется сделать


Список пожеланий таков:
  • Не хвататет ещё реализации генетических алгоритмов, чтобы можно было бы отбирать наиболее живучих особей и скрещивать их. Наиболее сложным в этом мне кажется реализация именно скрещивания, ведь фактически нам надо скрестить 2 набора байт-кода. (Если есть идеи алгоритмов — прошу в комменты).
  • Возможно, имеет смысл пересмотреть набор доступных команд.
  • Хотелось бы реализовать животным «зрение», т.е. возможность определять тип соседних ячеек
  • Можно доработать генератор, чтобы не совсем наобум шло генерирование живностей, а с учетом весов команд.
  • Рассмотреть варианты, как можно распараллелить вычисления для повышения быстродействия.
  • Написать редактор для «генетического» кода, чтобы удобно было самому разрабатывать живность.

Что будет сделано в ближайшее время


Список предстоящих изменений таков:
  • При размножении в «генетический» код будут вноситься мутации.
  • При нажатии «Save Current Picture» будет выдаваться запрос имени файла для сохранения текущей карты.
  • Можно будет подгружать сохраненных живтоных.
  • Возможность подгрузки из папки сразу нескольких живностей при старте (рабочее название — Autorun-папка).

Напоследок


Пока начинал писать эту заметку у меня в фоне крутилась эта программка (на пеньке четвертом и не было проведено оптимизаций по скорости работы). На тот момент я достиг для живности значения fitness = 3441. Для этого у меня пожило и умерло более 210000 особей, и прошло более 6500 раундов.
Для получения действительно интересных живностей, которые чего-нибудь интересное умели, надо (по моим оценкам) не менее 10^6 раундов. Может у кого комп помощнее, покрутит? Но интереснее, конечно, станет когда будут реализованы генетические алгоритмы и более интеллектуальный генератор первоначальных наборов. Ну и при дополнении генерируемых живностей особями, написанными живыми людьми. Это даст неплохой старт для следующих поколений.
Погоняв же программу на core i5 я довольно быстро получил гуляющие стада. Живучесть уже достигала 10390 единиц!
Интересно наблюдать за этими милыми тварюшками. Даже сопереживать начинаешь им.
Напоследок вот несколько интересных «жизненных» картинок. Видны пути миграции популяций, образование стад.



Самый серьёзный результат — 36480 (это после 10 часов работы и 2*10^6 раундов):

Качайте, запускайте, наблюдайте!
Кому интересно, можете сами попробовать написать ботов и посмотреть, кто сильней!

На этом всё. Спасибо за внимание!

Баг-репорты и предложения новых фич приветствуются.

UPD: мутация уже реализована на базовом уровне.
UPD2: Баг-трекер
UPD3: спасибо dtf за бинарники для Windows
UPD4: спасибо dtf за новые бинарники для Windows

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 61

    0
    А куда баг-репорты отправлять?
    Выполнил:
    git clone git@github.com:icoz/evo.git
    cd evo
    qmake
    make
    ./evo
    

    получил Segmentation fault. Очень хотелось посмотреть на живность.
      0
      Странно. Будтье добры, сообщите пожалуйста:
      1) ОС, версия
      2) версию Qt
      3) компилятор, версия
        0
        И еще: были ли какие-либо предупреждения компилятора при сборке?
          0
          1) Arch Linux, все обновления
          Linux jet 3.6.3-1-ARCH #1 SMP PREEMPT Mon Oct 22 10:23:56 CEST 2012 x86_64 GNU/Linux
          2) Qt стоит из репозитория, вот этот:
          extra/qt 4.8.3-4 [installed]
          A cross-platform application and UI framework
          3) судя по всему собирался он при помощи g++ (GCC) 4.7.2 вот лог pastebin.com/uA36ZJCs
            +1
            Всё. Баг повторил. Тоже segfault.
            Разбираюсь.
              +1
              Есть. Баг вылечил.
              Пару отладочных строк не заеомментировал, от этого падало.
                0
                Все отлично, запустилось!
                  +1
                  Приятных наблюдений!
                    0
                    Кстати, если запустить и тут же нажать Quit, тоже Segmentation fault
                      0
                      Уже исправлено. Обновитесь.
      0
      У меня тоже Arch.
      Работоспособность проверялась на двух машинах с арчем: x86 и x86_64.
        0
        Спасибо за работу. Как хорошо что кто-то занимается, а главное пишет про это. Скоро хаб Qt Software разбухнет от постов про клеточные автоматы.
          0
          А живность может поменять направление в котором она движется со временем? У меня на данный момент все сводится к тому, что они движутся фронтом из левого нижнего угла в правый верхний поглащая все на своем пути.
          Есть еще небольшие группы двигающиеся перпендикулярно основной, но их осталось немного, видать всех сожрали.
            0
            Ну пока самой эволюции там немного. Только небольшие мутации при клонировании.
            Скоро добавлю срещивание.
            +2
            Спасибо, интересная тема.
            Не отказался бы от готового бинарника под windows.
              +2
                0
                Увы, не хватает MSVCP100.dll (возможно, что не только её).

                По теме — респект автору! И за реализацию такой интересной темы, как клеточные автоматы — и за Qt.
                Обработка «миром» запросов от «живности» через сигналы/слоты и впрямь напрашивалась ;)
                  0
                  World имеет сигнал tick(), который запускает следующий цикл работы всех Animal, получивших этот сигнал.
                  У Animal есть несколько сигналов, задающие действия, которые живность производит. Эти сигналы получает World и двигает/размножает/и т.д. соответствующих особей.
                    +1
                    Странно, в прямых зависимостях её нет. В любом случае, www.microsoft.com/en-us/download/details.aspx?id=5555 должно помочь.
                      0
                      Спасибо, но я уже скачал эту dll-ку отдельно :)
                      С ней всё заработало, больше ничего не потребовалось.
                      0
                      Сработала установка DLL по этой ссылке: www.cyberforum.ru/system-soft/thread428108.html (на WinXP 32)
                        0
                        Для производительности от этого скорее всего нужно будет отказываться.
                        0
                        Спасибо, все отлично работает.
                      +11
                      Ноосфера что-то в последнее время полна «жизнью» :) Как раз на днях заделал такую реализацию классической версии на WebGL:



                      Есть редактор правил, разные кисти, даже машина Тьюринга.
                        +5
                        Потрясающе красиво! Надо такой скринсейвер сделать!
                        За такую заставку под Linux — автору пиво поставлю.
                          +2
                          screensaver powereater
                        0
                        Чем ваша программа принципиально отличается от NetLogo? Вот пример с волками и овцами, дописывай все что душе угодно за пару строк. Можно даже в браузере попробовать.
                          0
                          Судя по описанию, концептуально — ничем.
                          Только там есть деление на 2 категории: волки и овцы, а у меня — нет.
                          Таким образом мои животные могут есть как траву, так и других животных.

                          Только я не искал аналогов, когда писал.
                          Это что называется «just for fun».
                            0
                            По-моему, основное концептуальное отличие — что в случае с evo.exe — весь алгоритм поведения животных может изменяться, а не быть заранее заданным с некоторыми переменными параметрами.
                              0
                              Согласен.
                          0
                          А не хотите добавить многопоточность, думаю можно существенно скорость эволюции поднять?
                            0
                            Я уже над этим думал. Но первый пункт ограничении в скорости — это отрисовка.
                            А второй — работа системы сигналов/слотов. Как оптимизировать её — не знаю. Только полностью переделывать архитектуру программы.
                            Сейчас правки можно вносить быстро — архитектура позволяет.
                              +1
                              Я еще не вникал в код, но похоже, что как раз отрисовку можно сделать в отдельном потоке без переделки всей архитектуры. Один поток будет полностью заниматься расчетом эволюции, а второй периодически обращаться к первому, копировать текущее положение всех объектов и спокойно отрисовывать их. Время блокировки второго потока — минимально, переделка — не большая, сложность особо не увеличится.
                                0
                                Сейчас для повышения производительности введен параметр «отрисовка раз в Х раундов».
                                Как говорит профилировщик — теперь сдерживающим фактором является система сигналов/слотов.
                                0
                                У меня почему то и одно ядро плохо нагружает, где то 40%.
                                Завтра буду вникать в код и оптимизировать. Мне кажется там где то завязка на UI.
                                  0
                                  Есть успехи?
                              +2
                              Мне кажется, что у меня что-то пошло не так %) всего 180К раундов, а уже лучшая живучесть, которая была достигнута, 350335, кажется у меня тут зародился тиранозавр :)
                                0
                                Ссылочка на это чудо: rghost.ru/41196763
                                  +1
                                  Круто! У меня больше 36000 не было.
                                  Когда сделаю скрещивание, то ваш индивид будет первым осеменителем!
                                    0
                                    145K, max fitness 43474
                                    0
                                    Когда-то делал очень похожую штуку, но мне тогда не хватило вычислительных мощностей для интересных результатов. Вот всё думаю, а можно ли как-нибудь краудсорсить ресурсы для такой задачи? Мы бы тогда не каждый на своем компьютере запускали, а могли бы общий мир моделировать.
                                      0
                                      Но как минимум надо с оптимизировать текущий вариант и глянуть сколько мощности реально не хватает.
                                        0
                                        Не хватает для чего?
                                        Для того, чтобы за секунду по 1000 раундов просчитывать вместо 100?
                                        Для того, чтобы создать искусственный разум?

                                        Спрашиваю только потому, что интересно чего хотите добиться вы?
                                          0
                                          Да для того, что бы приходит к наиболее сильному животному и смотреть как оно устроено.
                                        0
                                        Тогда для начала надо отказаться от поля 256*256.
                                        Затем придумать схему для распределенного вычисления. Самое сложное там, на мой взгляд, межнодовое взаимодействие. Плюс должен быть тогда какой-то центральный сервер, где будет само поле, по которому будут перемещаться особи. Я бы предпочел что-нибудь децентрализованное.

                                        Да и для интереса надо бы замутить какую-нибудь вещь типа лабиринта, а не просто точки, разбросанные по полю.
                                          +1
                                          А что если все оставить как есть, но обмениваться только наиболее интересными индивидами между нодами? Тогда, по идее, лучшие особи будут выводиться максимально быстро :)
                                            –1
                                            Вообще очень логично — вырастил у себя лучшего монстра — отправил в общий репозиторий.

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

                                                Там периодически генерируются просто произвольные особи. Они могут получиться намного мощнее уже существующих. И с ними будет срещиваться весь имеющийся арсенал.
                                          0
                                          Можно было бы еще ввести систему рейтингов — по длительности работы программы и что бы через определенный промежуток времени, например 24 часа программа отправляла результат своей работы на сервер
                                            0
                                            Для этого сервер для начала сделать надо…
                                              0
                                              Было бы желание, а сообщество поддержит. Тема то интересная)
                                            +2
                                            У знакомого нету аккаунта тут, попросил ответить вам.
                                            Прочитал вот про вашу Evo, решил написать.
                                            Я сам уже больше года в свободное время что-то подобное делаю.
                                            Правда, изначальный подход отличается. Не клеточный автомат, а
                                            попытка работать на уровне инстинктов/условных рефлексов и осознания
                                            окружения. Соответственно особи должны не «разрабатываться в коде»,
                                            а «воспитываться с детства».
                                            Особенно повеселило то, что особей про себя я тоже «живностью»
                                            называю. :)
                                            Отличий, конечно — много. Все же я с этим, думаю, побольше сидел — уже под полмегабайта исходников написано.
                                            Поле намного больше (с масштабированием), плотное использование
                                            многопоточности, в т.ч. отрисовка в отдельном потоке. (Да, кстати, для
                                            отрисовки я почти сразу использовал OpenGL — скорость значительно
                                            выше.) Есть то самое «зрение», причем просчитывается (не)видимость за
                                            препятствиями/стенами (и в сочетании с плавным, «не по клеткам»,
                                            движением особей, это порядочно жрет ресурсы).
                                            Кстати, еще совет насчет скорости — в какой-то момент понимаешь, что
                                            все же «маловато будет». :) Я вот для некоторых блоков пытаюсь
                                            использовать OpenCL. Но там тоже свои подводные камни — и логика
                                            программирования другая, и нужно хранить как можно больше в памяти
                                            видеокарты, т.к. перекачка в системную память и обратно очень
                                            медленная (единицы гб/сек).

                                            Ну и, у меня с самого начала была идея заточки под онлайн. :)
                                            И те самые идеи, что сейчас пошли уже в комментах — межнодовое
                                            распределенное взаимодействие, лабиринты, отбор лучших особей для
                                            заселения… :))
                                            И ощутимая часть уже написана. (Например, погонять особь по случайному
                                            лабиринту размером с футбольное поле довольно интересно — она ведь
                                            помнит путь, где уже ходила!)

                                            Надеюсь, что я все же осилю это до какого-то вменяемого результата,
                                            ибо рутины — как правильно замечено — море.
                                              0
                                              По описанию — интересно. А ваш знакомый результаты не хочет опубликовать где-нибудь? Можно без исходников, просто в виде бинарников.
                                                0
                                                Ну с таким подходом можно изначально разрабатывать модель эволюции с реализацией на CUDA. Там и производительность выше будет.
                                                Я же не ставил целью имитацию эволюции. Я сделал набор искусственных правил, органичивающих живность, и наблюдаю как она подстраивается.
                                                Очень интересно смотреть как реагируют стада на резкое сокращение количества травы.
                                                Или как отдельные особи начинают резко плодиться, когда появляется большое количество еды.

                                                Но звучит очень интересно. С удовольствием поигрался бы.
                                                  +1
                                                  Вот архив.
                                                  В нем два бинарника на 16 и 128 «особей».
                                                  «Результаты вообще» публиковать еще рано. Не во что пока поиграть.
                                                  Есть только части, которые я в основном по отдельности тестирую.

                                                  Из того, что можно показать — вот, например, полугодовой давности
                                                  сборка с лабиринтом. Можете погонять живность, если интересно.


                                                  От себя добавлю, зум колесиком, но его поведение не совсем как в играх и к сожалению пока не хватает удобного способа перемещения в плоскости, кроме как уменьшил/увеличил. Выбор юнитов левой кнопкой, а правой отправка в пункт назначения.
                                                    0
                                                    Ах да, мне напомнили про навигацию в плоскости.
                                                    Можно навести курсор к краю экрана.
                                                  +1
                                                  Думаю, всем будет интересно, если ваш товарищ напишет статью о том, с какими подводными камнями сталкивался при разработке.
                                                  Да и инвайт за это, думаю. без особых проблем получит.
                                                    0
                                                    Я думаю он пока в этом не сильно заинтересован, да и как я он сам написал
                                                    «Результаты вообще» публиковать еще рано. Не во что пока поиграть.

                                                      0
                                                      Большую статью про разработку я сейчас точно писать не буду. Хотя бы потому, что эта разработка не дошла хотя бы до альфа-версии.
                                                      И с камнями я сталкиваюсь до сих пор и постоянно. (Главный — «памяти мне дайте, памяти, да побольше»! 2ГБ на процесс катастрофически мало. Но может в рабочей версии на динамически изменяемое поле хотя бы в несколько «квадратных километров» и на полсотни особей этой памяти хватит...)

                                                      Думаю, можно будет написать статью тогда, когда тестовая версия будет доступна для скачивания — тогда материала будет побольше и он будет более предметным.
                                                    0

                                                    Only users with full accounts can post comments. Log in, please.