Еще об эволюции гоночных автомобилей

image
Недавно на хабре проскочил пост, который напомнил мне о такой забавной и довольно интересной вещи, как BoxCar2D (Оригинал, Версия из поста), которую в первый раз я увидел пару лет назад, и которая меня порядком впечатлила. И уже тогда я подметил в ней один фатальный недостаток (вкратце — ее сделал не я), но в тот раз руки так и не дошли до его исправления. И вот теперь я решил это исправить.

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

Я остановился на таком варианте: каждая машинка обладает своим геномом, который содержит информацию о каждой из 8 вершин и каждом из 4 потенциальных колес. Также отдельный ген отвечает за то, какие потенциальные колеса вырастают у машинки на самом деле.
При скрещивании каждый ген берется случайным образом от одного из родителей, а также с определенной вероятностью может мутировать, получив случайное значение в заданном диапазоне. Особенный в этом плане только ген, определяющий, какие колеса вырастают, а какие нет. В нем мутация заключается в том, что может случайным образом поменяться состояние одного из колес (выросло — не выросло), либо информация о колесах может сдвинуться на бит вправо или влево.

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

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

Что из этого вышло

Итак, произвольным образом создаем популяцию машинок без колес, запускаем в наш мир и запасаемся попкорном.
Пусть первичные прото-машинки будут совсем без колес.
image

Они начинают свой жизненный путь и в какой-то момент замирают, будучи не способными продвинуться дальше по трассе. Для первых машинок и их недалеких потомков это будет происходить очень быстро. Для всех замерших машинок мы точно знаем их «приспособленность» и периодически производим «естественный отбор» описаным выше способом.

Сильное влияние имеет то, как часто мы проводим отбор. Чем больше машинок доступно для случайно выборки, тем получается честнее, но тем медленнее движется эволюция в целом. Методом научного тыка я выбрал границу в 1/6 популяции. Если количество закончивших свой жизненный путь машинок еще меньше этого значения, отбор не происходит.

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

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

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

Еще картинок
image
image
image




Что еще можно исправить/добавить (в порядке возрастания сложности)

  • Сделать больше параметров изменяемыми через интерфейс программы. Многие интересные вещи сейчас захардкодены.
  • Ограничить количество потомков одной особи. Сейчас машинка, уехавшая дальше всех плодит и плодит потомков, пока ее рекорд не будет побит. Надо усложнить ей жизнь.
  • Добавить еще генетической информации. Больше генов! Еще больше!
  • Сделать более умный механизм скрещивания генов. Например, как в вышеупомянутом JavaScript-овом симуляторе первые k генов от папы, а следующие n-k – от мамы.
  • Интересно будет так же попробовать определить критическую дистанцию между геномами так, чтобы особи, геномы которых сильно отличаются, теряли способность к скрещиванию между собой. Это позволит параллельно эволюционировать нескольким отдельным видам.
  • Ввести «поведение» машинок, диктуемое так же генами. Например, снизить скорость на крутом уступе и так далее.

Где все это брать?

Для заинтересовавшихся выкладываю скомпилированную версию и исходный код (вместе с solution для Visual Studio 2012)
4Shared:
Скачай и запусти (Win32) 1032 KB
Скачай и запусти (Linux) 1052 KB

https://github.com/shtras/BlindAM.git
Старые исходники 1868 KB
Старые исходники для Линукса 1362 KB

Dropbox:
Скачай и запусти (Win32) 1032 KB

Релизная сборка у меня тянет популяции из 300 и более особей. Вначале тормозит, пока они все не упадут на землю, а затем все гладко.
Камера двигается правой кнопкой мыши, колесико отвечает за зум.
Пробел включает/выключает паузу. Начинается симуляция на паузе.
Кнопками 'a' и 'd' можно соответственно увеличивать и уменьшать скорость симуляции. Полезно вначале до появления первых интересных особей.

Использованные технологии:
C++, Box2D, OpenGL, SDL

Update1: В папке res есть файл settings.txt. В нем можно настроить размеры окна игры.
Update2: Добавил версию для Линукса. Поправил баг, когда при повторном запуске без выхода из приложения не обнулялся seed
Update3: Вынес много-много настроек в меню. Изменил внешний вид трассы. Доработал рендеринг.
Новое меню
image
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 91

    +3
    Неплохо устранили недостаток :D
      +5
      Нужна linux версия! :)
        +1
        прекрасно под вайном работает
          +1
          у меня под вайном машинки просто лежат и все :(
            +3
            Забыл написать. Пробел включает/выключает паузу. Хотя, если лежат, значит упали, а значит пауза была выключена.
            В любом случае, в ближайшее время соберу нативную версию.
              0
              с пробелом заработало =) =)
                0
                О, спасибо, так гораздо лучше. Стоит добавить эту магическую клавишу в статью. Сидел минуты две ждал — думал что какая-то медленная эволюция.
          +3
          Сделайте, пожалуйста, изменение размера экрана, а то в мой рабочий 1600*900 ничего не вместилось
            0
            Да, тут я не подумал как-то. Сегодня вечером сделаю.
              +1
              Залил новую версию. В папке res теперь есть файл настроек settings.txt. В нем можно настроить размеры окна.
              +8
              Меня во всех этих «симуляторах» смущает то, что машинки не тратят ресурсы на мутации, то есть, «выращивание» двух колес ничем не отличается от «выращивания» восьми, а «выращивание» маленького колеса — от «выращивания» большого. В реальном мире это не так — чем больше организм, чем больше (качественно или количественно) у него те или иные приспособления, тем больше ресурсов ему нужно затратить на развитие всего этого безобразия (у того же Докинза в «Эгоистичном гене» это очень хорошо описано).

              В качестве костыля можно было бы добавить машинкам некоторое «топливо», часть которого расходуется на мутации, а часть — во время езды. Или придумать какую-то другую систему ресурсов.
                +2
                В результате появится StarCraft 4.5, в котором юниты обзаводятся необходимыми «приспособлениями» для выживания.
                Игроки будут смотреть за эволюцией своих юнитов в single режиме и выставлять лучшие популяции в мультиплеер ))
                  0
                  Зато наконец прекратятся споры про баланс!
                  +1
                  Мысль интересная. Правда, большой корпус не обязательно дает машинке преимущество, скорее наоборот. То есть, если тратить ресурсы именно на рост, это еще более подстегнет тенденцию к уменьшению размеров.
                  Я из этой оперы думал о том, что, например, максимальный крутящий момент на колесах может зависеть от размера корпуса, например. Так станет не выгодно прятать тоненький корпус между колес.
                  Или сделать функцию приспособленности зависимой также от времени, которое взяло у машинки добраться до финальной точки. Этим можно сэмулировать то, что она успевает съесть больше травы по дороге за меньшее время, чем ее менее расторопные товарищи.
                    0
                    Так у машинок же нет цели жрать друг друга, так что уменьшение размеров действительно логично.

                    С другой стороны, корпус можно как раз рассматривать как топливный бак, и давать машинке ограниченую «энергию».
                    • UFO just landed and posted this here
                        0
                        И это тоже, конечно, хотя сильно зависит от карты. На некоторых наоборот — большая машинка (особенно пузатая) рискует встать там, где мелкая проедет.
                        • UFO just landed and posted this here
                  +1
                  А можно как-нибудь окошко поменьше сделать, а то оно у меня больше рабочего стола и только minimize доступен ?
                    +6
                    Видео будет для ленивых?
                      0
                      Хорошая идея. Будет.
                      0
                      А можете скомпилировать для winxp sp3 (32bit)?
                      А то пишет, что не является приложением Win32
                        0
                        Попробуйте заменить экзешник на вот этот. Скомпилирован с тулсетом 2012 для Windows XP.
                          0
                          всё равно не работает
                            0
                            По ссылке поменялся файл. Извините, забыл и переписал.
                            Вот тот, который предназначался вам: файл.
                              0
                              При запуске:

                              «Assertion failed!

                              Program: C:\Games\Box2D\Engine.dll
                              File: auxFuncs.cpp
                              Line: 39

                              Expression: err == 0»

                              Если нажать «пропустить», то вроде работает, но шрифт, видимо, не прогрузился. Надписи отсутствуют
                                0
                                Это значит, что OpenGL какую-то ошибку выдал. А что в файлах error.log и info.log?
                                По хорошему надо бы и dll пересобрать с этим тулсетом, раз уж экзешнику помогло. Но это смогу только вечером дома.
                                  0
                                  info.log:
                                  Tue Jul 09 12:54:00 2013 Application started. Hello, World!
                                  Tue Jul 09 12:54:00 2013 Application version: 0.0.6.365 Release
                                  Tue Jul 09 12:54:00 2013 Starting renderer initialization
                                  Tue Jul 09 12:54:00 2013 SDL successfully initialized
                                  Tue Jul 09 12:54:00 2013 Video mode set
                                  Tue Jul 09 12:54:00 2013 OpenGL version: 1.5.0 — Build 6.14.10.4847
                                  Tue Jul 09 12:54:00 2013 Loading textures…
                                  Tue Jul 09 12:54:00 2013 Successfully loaded res/font2.png
                                  Tue Jul 09 12:54:00 2013 Successfully loaded res/gui.png
                                  Tue Jul 09 12:54:00 2013 Finished loading textures.
                                  Tue Jul 09 12:54:00 2013 Initialization successfully completed
                                  Tue Jul 09 12:54:00 2013 Switching to menu
                                  error.log:
                                  Tue Jul 09 12:54:00 2013 OpenGL error during main loop. Something bad happened OpenGL error: 1281
                                    0
                                    Где-то случилось GL_INVALID_VALUE.
                                    OpenGL version: 1.5.0 — с этим может быть проблема. Попробуйте обновить драйвера видеокарты.
                        +2
                        Эволюция остановилась на вот такой загогулине:


                        Минут 15 быстрые теряют там колёса, медленные просто застряют. Главное — все умирают на одной и той же дистанции, поэтому эволюция по сути практически остановилась.
                        Хабракат не сработал.
                          0
                          Всегда может произойти мутация, или несколько, которые помогут преодолеть загуголину. Рано или поздно на любой трассе появляется участок, непроходимый в принципе, но эта загогулина так не выглядит. Стоит подождать еще несколько раз по 15 минут :)
                          Какой seed вы использовали и на какой дистанции это произошло?
                            0
                            Нашлись уже смельчаки :) Seed не скажу (кстати — стоило бы выводить его и в режиме воспроизведения). Просто добил случайными символами после habrahabr, а остановить боюсь — все ведь заново придется начинать?
                            Дистанция — 420.
                            Кстати, хотел спросить — а надежность фиксации колес — это ген? Если нет, то стоило бы — очень продвинуло бы симулятор в плане достоверности.
                              0
                              Да, придется начинать заново.
                              Надежность фиксации — хардкод. Можно сделать и ген для нее, но тогда, я думаю, рано или поздно (скорее, рано) у всех он упрется в максимум, тут однозначно, чем крепче — тем лучше.
                                0
                                Можно связать его с мягкостью подвески.
                            +1
                            Мне кажется, что при ограниченной «вселенной» эволюция рано или поздной войдет в тупик, вопрос только во времени.
                              +1
                              Генная инженерия любой тупик преодолеет.
                                0
                                У машинок вырастут крылья, чтобы они могли «преодолеть» обрыв трассы?
                                  +4
                                  Нет, у них появятся мозги, и они будут с нескрываемым презрением обсуждать своих создателей.
                              0
                              Похоже на апокалипсис в масштабе машинок.
                              0
                              Час пролетел незаметно…
                                +4
                                Нужно ввести вирусы и горизонтальный дрейф генов.
                                  +1
                                  При маленькой популяции (50/5) почему-то быстро вырвались вперёд вот такие «трёхколёсные» мобильчики:

                                  image
                                    +1
                                    Linux версию хотелось бы увидеть!
                                      0
                                      Можно было бы проводить отбор среди одной популяции сразу на нескольких трассах, «поощряя» универсальность.
                                        0
                                        Нет ни какой разницы между одной трассой и несколькими: Трасса — это совокупность (или множество) «пар сегментов» с разными углами и требованиями к особям. Особь преодолевает не трассу, а именно пары сегментов. Разные трассы фактически будут одинаковыми.

                                        (Моя популяция застряла на 830.69 :)
                                          0
                                          По-моему, тут вовсе не пары играют роль, а группы сегментов сильно большего размера. Потому что, например, у меня машинки в одном месте на три почти отвесных сегмента после равнинки взбираются без проблем, а в другом, где перед этим небольшая горка из двух сегментов, застряли на весьма продолжительное время.
                                            +1
                                            Да, еще влияет скорость. А скорость зависит от того, как были пройдены предыдущие участки, так что я не прав.
                                              0
                                              Да, вектор скорости и пара сегментов, так будет точнее (не заметил, действует ли ещё момент инерции на машинку).

                                              БТВ. Удалось вывести популяцию одноколёсных, которые на 730 едут :)
                                              0
                                              Думаю, что когда происходит застревание на одном сегменте — эволюция тормозится, пока одна из мутаций не позволит преодолеть барьер.
                                              Если же барьер сильно сложней предыдущих участков, машинки так его могут и не преодолеть, потому что единичные улучшения недостаточны, и не фиксируются.
                                                0
                                                Я тоже так думал: у меня эволюция застряла на одной очень глубокой яме из двух сегментов, откуда машинки не могли выбраться без изменения ни размера, ни поведения на протяжении сегментов 15. Но через полчаса глянул, а они уже спокойно адаптировались (причём это при высокой приемственности в 50).
                                        • UFO just landed and posted this here
                                            +2
                                            Попробуйте нажать пробел.
                                            • UFO just landed and posted this here
                                            +17
                                            Вииииии!!!
                                            image
                                              +2
                                              вечерело. а машинки всё падали и падали ©
                                                +2
                                                Эти красавцы развились за час, на который я забыл о запущенной программе.
                                                Отметка 1100, преграды преодолевают почти вертикально стоя на заднем маленьком колесе.
                                                скрин



                                                Быть может сделать режим в котором наследник рождается не на старте, а где-нибудь по пути (в зависимости от положения родителей).
                                                Это, по идее, должно дать повышенную приспособленность к локальным условиям рельефа. Если при этом рельеф не «линейно повышает сложность вплоть до сумасшедших непроходимых колесами гор», а как-то чередуется, то на выходе будет интересная динамика смены приоритетов.
                                                  0
                                                  Интересная идея. Набросал прототипчик (посмотреть можно заменив экзешник на этот). Потомок рождается на месте отстающего родителя.
                                                  Популяция довольно быстро мигрирует вперед и особи рождаются приспособленными к новому месту рождения.
                                                    0
                                                    В некоторых местах это изменение позволило использовать новый способ преодоления препятствий — постепенно точка рождения потомка перемещалась по полю дальше. Не знаю, как объяснить, вот картинка:
                                                    Скрытый текст
                                                      0
                                                      Да, есть такая беда в этом случае. Точка рождения — немного выше, чем родитель, так что при сильном уклоне машинка может появиться наполовину в трассе. А если брать еще выше, то они все колеса пообломают при приземлении.
                                                        0
                                                        Мне больше понравился режим «катящейся безколесной кучи»
                                                        0
                                                        Стоило наверное рождать на месте кончины «аутсайдера». Т.о. «куча» не будет перемещаться «телепортами», а только своими силами.
                                                          0
                                                          Попробовал сейчас два варианта: рожать новых на месте, где умер самый неуспешный и на минимуме из текущих рекордов.
                                                          В первом случае всегда найдется уникум, который откатился чуть назад и помер, и вся популяция потихоньку двигается назад, пока не начинает рождаться как заведено в Спарте, прямо над пропастью.
                                                          Во втором вся популяция потихоньку движется вперед, потому что минимальный рекорд новой особи будет ее местом рождения, то есть не меньше, чем раньше. А может так случиться, что все, хоть понемногу, да прокатятся вперед.
                                                      +1
                                                      Лемминги?
                                                        0
                                                        Натолкнуло на мысль, было бы здорово иметь возможность автоматически сохранять gif с историей мутаций лидеров.
                                                          0
                                                          Каждая машинка берет свои гены от двух родителей, так что наглядно изобразить историю эволюции одной особи вряд ли получится.
                                                            0
                                                            Можно использовать лидеров — они всегда единственны.
                                                        0
                                                        Интересно, а трехмерную версию реально создать?
                                                          +2
                                                          Box2D — двухмерный физический движок. Если написать свой трехмерный, то реально :)
                                                            +1
                                                            Думаю, стоит написать в автоваз, иногда кажется, что они создают автомобили именно таким алгоритмом
                                                              +7
                                                              Маловероятно.
                                                              За 50 лет эволюции родилось бы что-нибудь хорошее.
                                                          0
                                                          Ввести «поведение» машинок, диктуемое так же генами. Например, снизить скорость на крутом уступе и так далее.
                                                          По мне, так это очень интересный пункт. Наблюдая за машинками из прошлой статьи я обратил внимание, что есть препятствия, которые преодолевают чуть более чем 0% машинок. Если позволить машинкам ускоряться и замедляться и заложить это в гены, то можно выводить популяции, адаптированные под конкретную трассу. Очень грустно наблюдать, как превосходная по дизайну машина валится на какой-нибудь яме, которая в принципе (при разгоне-торможении) может быть пройдена, но из-за неудачного соотношения с размером машинки, оказывается непреодолимой.

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

                                                              0
                                                              А у меня за ночь народ прошел очень подлую яму на 640, на которой постоянно отваливались колёса, но уперся в 777.57

                                                              Вот думаю останавливать или нет — вдруг родится кто-нибудь с парой дополнительных колес и выберется отсюда.
                                                                0
                                                                Предлагаю динамически красить трассу. Например окрашивать красным плиты в зависимости от процента погибшего на них народа. Еще можно красить по «посещаемости» — красить плиты в зависимости от процента доехавших машинок.
                                                                Было бы очень наглядно.
                                                                  +8
                                                                  У коллеги эволюция пошла по неожиданному пути :)
                                                                    0
                                                                    Кроты…
                                                                      0
                                                                      А мне больше летучих мышей напомнили.
                                                                      0
                                                                      В новой версии трасса гораздо толще, и гораздо меньше вероятность, что машинка родится не над трассой, так что такого быть больше не должно.
                                                                      0
                                                                      У меня нет дороги…
                                                                        0
                                                                        Уменьшите масштаб колесом мыши.
                                                                        0
                                                                        висит в таком состоянии и ничего не происходит:
                                                                        screenshot



                                                                        Вентилятор видеокарты при этом бешено работает. W8 x64.
                                                                          0
                                                                          Возможно симуляция на паузе. Для снятия паузы — нажать «пробел».
                                                                            0
                                                                            Странно, вертикальная синхронизация должна быть включена, такой fps быть не должен с ней. Возможно, особенности драйвера под W8.
                                                                            Насчет ничего не происходит, совет выше с пробелом помог? Пожалуй, стоит добавить виджет для скорости симуляции, чтобы было наглядно.
                                                                              0
                                                                              Про fps, на W8 при запуске с интегрированной видеокартой fps 400-600, с нвидией — 60
                                                                                0
                                                                                Да, симуляция, почему-то, на паузе при запуске и кнопка Follow the leader отжата, а камера выше трассы в этот момент находится. Всё теперь работает нормально.
                                                                                  0
                                                                                  Упало с такими параметрами:
                                                                                  image
                                                                                    0
                                                                                    Как конкретно упало?
                                                                                    Строку seed не разглядеть. Но слишком большие максимальная длинна ребра, скорость и крутящий момент.
                                                                                    Машинки будут рождаться наполовину в трассе и улетать с космической скоростью из-за огромных скоростей колес.
                                                                                    Да, на параметрах нет защиты от излишне изобретательного пользователя :)
                                                                                0
                                                                                Я смотрю, у вас в конце очень даже приличные экземпляры начали ездить)
                                                                                «Шах и мат, креационисты!».
                                                                                  +2
                                                                                    +1
                                                                                    А в виде нормального текста нет?
                                                                                      0
                                                                                      Не искал, не знаю

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