...

воскресенье, 29 июля 2018 г.

Создание «искусственной жизни» на компьютере

Всем привет. В статье хочу описать свой эксперимент по созданию «искусственной жизни» на компьютере.
Как это выглядит?


картинка кликабельна

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

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

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

Описание «мира ботов»


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

Боты могут перемещаться по восьми направлениям и прощупывать соседние с собой клетки.
Боты могут съедать других ботов, находящихся на соседней клетке.
Боты копят энергию и когда накопят заданное количество, от них отпочковывается их клон.
В клона записывается та же программа, что и в родителе, но в одном случае из четырёх случайным образом меняется один байт в программе. Это может никак не повлиять на поведение клона, так как не все команды в программе-геноме выполняются, большая часть генома может быть не задействована. Также это может вызвать ухудшение или улучшение способностей бота выживать в данном мире. В первом случае бот либо погибнет, либо не сможет оставить много потомков. В случае улучшения способностей бота, он с большей вероятностью оставит больше потомства, которое вытеснит менее удачных соседей.

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

Здесь я дал краткое представление о виртуальном мире ботов, достаточное для понимания дальнейшего материала. Собственно сам мир не столь важен, можно экспериментировать с разными мирами. Куда интересней, как устроен код-геном

Код-геном


Код-геном представляет из себя цепочку чисел. Каждое число — это какая то команда (в простейшем случае). Также есть указатель текущей команды (далее УТК), который показывает, какая команда будет сейчас выполняться и после выполнения команды, указатель перемещается к следующей команде. Если указатель вышел за край цепочки, то он появляется с противоположной стороны, то есть цепочка команд замкнута по кругу. Изначально я выбрал размер цепочки в 64 ячейки и назначил некоторым числам первые команды. Если числу не соответствует никакая команда, то это число является безусловным переходом. Когда УТК укажет на ячейку с подобным числом, то он увеличивается(переходит по цепочке команд вперёд) на это число. То, что число без назначенной команды является безусловным переходом очень удобно. При экспериментах можно спокойно назначать на свободные числа новую команду или убирать старую. Так как у меня длина цепочки 64 ячейки, то доступных чисел тоже 64 (от 0 до 63).

На рисунке схематично изображен геном первого бота в виде замкнутой по кругу ленты. Все ячейки забиты командой 23. Это команда «фотосинтез». После её выполнения, бот получает энергию в количестве, зависящей от глубины, где бот находится. Также на рисунке изображена схема выполнения кода. Стоит отметить, что команда, кроме выполнения основной функции, также отвечает за изменение УТК. После выполнения такой простой команды, как «фотосинтез», УТК увеличивается на единицу. В данном примере будут последовательно выполнены все команды в коде-геноме.

Допустим, что при появлении нового бота произошла мутация и в ячейку под номером 1 записалось число 63. После появления нового бота, его УТК равен 0, выполниться команда «фотосинтез», УТК увеличиться на 1. Теперь считывается число из ячейки 1 — это число 63. Этому числу не присвоено никакой команды, поэтому это безусловный переход. Сдвигаем УТК на 63 ячейки вперёд и теперь УТК снова указывает на команду «фотосинтез», в нулевой ячейке. Так будет повторяться по кругу. Заметьте, что внешнее поведение бота ни чем не будет отличаться от родителя, но использоваться будут только две ячейки из 64.

Теперь рассмотрим более сложные команды, требующие параметров.

Всего в мире ботов есть восемь направлений. Если нам нужна функция поворота, то можем использовать 8 команд, по одной команде для каждого направления.
Но у нас всего 64 числа (0..63) и на все необходимые команды просто не хватит чисел. Поэтому будем ипользовать параметры.

Например, мы присвоили числу 25 команду «поворот». Когда УТК укажет на ячейку с числом 25 (повернуть), то мы также берём следующее число. Из этого числа мы узнаем, куда надо повернуть. Число может быть от 0 до 63, а направлений 8. Что бы узнать направление, мы делим параметр на 8 и берём остаток от деления. Получиться одно из 8 значений (0..7) — это и есть направление, куда надо повернуть. Количество доступных чисел (64) кратно 8. Поэтому вероятность выбора одинакова для всех направлений. После выполнения команды, УТК перемещается не на одну ячейку, а на две, перепрыгивая параметр.

Стоить заметить, что УТК может прийти к ячейке, которая в другой раз служила параметром. Теперь значение из этой ячейки будет командой. Это сильно усложняет анализ кода человеком, зато «виртуальная машина», выполняющая код бота очень проста в реализации.

Допустим, нам нужна команда «сколько у меня энергии?» При выполнении этой команды, если энергии больше, чем получено в параметре, то переходим по одному адресу, если меньше, то по другому. Энергии может быть от 1 до 1000, а параметр от 0 до 63. Что бы обойти это ограничение, то при выполнении этой команды, параметр умножается на 15. Получаем такие варианты:
0, 15, 30, 45, 60… 945.
С полученным вариантом и сравниваем уровень энергии и по результатам сравнения к УТК прибавляется смещение. Значение смещений берётся из следующих ячеек после параметра.

Подробное истолкование картинки выше
Указатель текущей команды (УТК) равен 10.
Берём число из ячейки №10. Это 33, команда «сколько энергии?».
Берём число из следующей ячейки (УТК+1), это параметр, из него вычисляем число для сравнения.
14*15=210

Если энергии у бота больше или равно 210, то берется число по адресу УТК+2.
Там у нас число 23. Это число прибавляется к УТК.
10+23=33.
То есть УТК теперь равно 33 и следующей командой будет команда из ячейки №33

Если энергии у бота меньше, чем 210, то берется число по адресу УТК+3.
Там у нас число 8. Это число прибавляется к УТК.
10+8=18.
То есть УТК теперь равно 18 и следующей командой будет команда из ячейки №18

Некоторые команды, такие как «посмотреть», «сделать шаг», «съесть», «поделиться энергией» являются разветвителями. В зависимости от того, что было в клетке, на которое было направленно действие, дальнейшее выполнение кода пойдет по разным веткам.

Подробное истолкование картинки выше
Указатель текущей команды (УТК) равен 7.
Берём число из ячейки №7. Это 26, команда «шагнуть».
Берём число из следующей ячейки (УТК+1), это параметр, из него вычисляем направление для шага.
18 % 8 = 2

Если клетка, куда шагает бот, была пуста, то берется число по адресу УТК+2.
Там у нас число 0. Это число прибавляется к УТК.
7+0=7.
То есть УТК опять указывает на ячеёку №7. Бот будет двигаться в этом направлении, пока на пути не встретит препятствие.
Получился цикл

Если на клетке была стена, то берется число по адресу УТК+3.
Там у нас число 3. Это число прибавляется к УТК.
7+3=10.
То есть УТК теперь равно 10 и следующей командой будет команда из ячейки №10 То есть число в этой ячейке только что было ссылкой, а теперь будет выполняться, как команда.

Если на клетке была органика, то берется число по адресу УТК+4.
Там у нас число 43. Это число прибавляется к УТК.
7+43=50. То есть УТК теперь равно 50 и следующей командой будет команда из ячейки №50
Если на клетке был чужой бот, то берется число по адресу УТК+5. Там у нас число 24. Это число прибавляется к УТК. 7+24=31.
То есть УТК теперь равно 31 и следующей командой будет команда из ячейки №31

Если на клетке была родня, то берется число по адресу УТК+6.
Там у нас число 59. Это число прибавляется к УТК.
7+59=66.
То есть УТК теперь равно 66. Указатель вышел за диапазон возможных адресов, вычитаем из него 64 и получаем 2 Следующей командой будет команда из ячейки №2

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

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

Ещё несколько моментов.
Все боты в памяти оперативной памяти соединены в круговую цепочку и управление по очереди передаётся от одного бота к другому. Код бота выполняется, пока не будет выполнена завершающая команда. К таким командам относятся: «шагнуть», «съесть», «фотосинтез», «поделиться энергией» и так далее. Остальные команды (безусловный переход, «посмотреть», «повернуться», «сколько энергии?» и так далее) могут выполняться до 15 раз, после чего управление передаётся другому боту.

Когда отпочковывается новый бот, он встраивается в цепочку ботов перед предком.

Что в итоге получилось


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

Скриншоты сделаны на разных стадиях разработки. Там, где задний фон меняется с белого до синего, я ещё не ввел «минералы».

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

Самое начало. Появляются «лабиринты», цепочки ботов

Начинают появляться первые колонии

Колонии уже сформировались. Можно увидеть розовых и сине-зеленых любителей разнообразного рациона.
Любопытные диагональные поселения хищников.

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

Вновь родившийся бот получает свой цвет от родителя. Потом, в зависимости от рациона, цвет может изменяться.
Здесь видны красные скопления ботов. Они не кого не кушают и не получают энергию от Солнца, иначе бы позеленели.
Энергию они получают от распределения энергии по колонии. Своего рода паразиты. Когда у колонии начинаются проблемы, то паразиты быстро погибают.

Режим отображения энергии открывает новые стороны мира. Видно, как по разному распределяется энергия внутри колоний. Центральная колония имеет чёткие границы с левого края, но с правой стороны границы не имеет. Также с краев видна колония, где энергия идет по диагонали (так как мир по горизонтали замкнут в круг, то это одна и та же колония).

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

Начало массового вымирания. Красные боты переполнены энергией и они должны отпочкавать потомка, но свободного места нет и они погибают. Поедать органику боты тоже перестали. В итоге органика(бледно-розовая) заполнила всю верхнюю часть мира.

Размер созданного мира маленький, так как большая часть работы и экспериментов проводилось на 7-дюймовом планшете, но для подобных экспериментов, чем масштабнее мир, тем лучше. На первой фотографии в статье использован скриншот с клона моего проекта, переписанного RomanoBruno на языке Java. Здесь уже другой масштаб и скорость работы выше. Ссылка на этот проект в конце статьи.

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

Состояние мира перед вспышкой

Прошёл 21 ход после вспышки. Мир изрядно разрушен, большая часть ботов погибла.

Прошло ещё 347 ходов, мир возвращается к жизни.

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

Что дальше


Сейчас у меня частично написан, но временно заморожен из за нехватки времени, проект нового мира.
Энергию можно будет получить, поедая «траву». Можно съесть всю «траву» в определённом месте и она там появятся только разрастаясь из тех мест, где осталась.
Количество энергии, соответственно, будет обратно-пропорционально зависить от количества ботов и боты не смогут заполонить собой весь мир. Это позволит создать больший по размерам мир с естественной изоляцией разных групп ботов. Боты будут вынужденны перемещаться в поисках доступной еды.

Код-геном будет работать на тех же принципах, но добавяться некоторые дополнительные возможности.

  • Регистры и операции с ними.
  • Прерывания, одноуровневый стек и команда ret
  • Способы коммуникации между ботами.
бизнес проект

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


Заключение


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

Ссылки


Этот проект не единственный по данной тематике, но на момент создания я знал только об одном. Про него я прочитал в 93 году в журнале «Техника молодёжи». Статья меня зацепила. В то время у меня не было компьютера и я не предполагал, что когда-нибудь смогу реализовать подобное.
Ссылка на статью

Видео, где можно посмотреть разные варианты развития мира
www.youtube.com/watch?v=PCx228KcOow

Проект написан на интерпретаторе Pixilang
yadi.sk/d/rLamoeyt3NBRwL

Также проект переписан RomanoBruno на языке Java и выложен на GitHub
github.com/CyberBiology/CyberBiology

Группа ВКонтакте vk.com/cyberbiology

Let's block ads! (Why?)

Комментариев нет:

Отправить комментарий