Приветствую вас, читатели!
В продолжение поста «Аналог игры «Жизнь» — Evo» хотелось бы дать более подробное описание команд «языка генов», который используется в Evo, и поделиться своими соображениями по методам скрещивания особей в этой игре.
Генетический код
Генетический код особей в Evo представляет собой последовательность байт практически неограниченной длины. При этом каждый байт трактуется как команда для клеточного автомата. У автомата 2 ленты: команд и памяти. Соответственно есть два указателя cmd_ptr и mem_ptr. В качестве ОЗУ животного используется переменная data, размерностью в 1 байт (8 бит).
На текущий момент есть следующие команды:
- 9 команд управления исполнением «генетического» кода:
- nop — ничего не делать
- move_cmd_left — передвинуть указатель команд влево
- move_cmd_right — передвинуть указатель команд вправо
- jump_to — сдвинуть указатель команд вправо на Х позиций (следующий за командой байт трактуется как signed char, то есть отрицательные значения сдвинут указатель влево)
- jump_to_ifz — то же, что и jump_to, но при условии, что значение data == 0
- jump_to_ifnz — то же, что и jump_to, но при условии, что значение data != 0
- start — то же, что и nop, просто метка для начала какого-то обособленного куска (начало функции)
- restart — сбрасывает значение cmd_ptr в 0
- end — конец функции, заставлет искать дальше по ленте метку start, с которой продолжить выполнение (если метки нет, то cmd_ptr=0)
- 8 команд, позволяющих живности осмотреться вокруг себя (результаты сохраняются в ОЗУ живности, в переменной data):
- eye_up_distance — получить значение дистанции до ближайшего объекта вверх
- eye_down_distance — получить значение дистанции до ближайшего объекта вниз
- eye_left_distance — получить значение дистанции до ближайшего объекта влево
- eye_right_distance — получить значение дистанции до ближайшего объекта вправо
- touch_up — получить значение типа ближайшего объекта вверх
- touch_down — получить значение типа ближайшего объекта вниз
- touch_left — получить значение типа ближайшего объекта влево
- touch_right — получить значение типа ближайшего объекта вправо
- 10 команд управления памятью живности:
- move_mem_left — сдвинуть указатель mem_ptr влево
- move_mem_right — сдвинуть указатель mem_ptr влево
- save_to_mem — сохранить в текущую ячейку содержимое ОЗУ живности (data)
- load_from_mem — загрузить значение из текущей ячейки в ОЗУ живности (data)
- add_mem — прибавить к data значение текущей ячейки памяти
- sub_mem — вычесть из data значение текущей ячейки памяти
- set_mem_ptr — установить mem_ptr равным значению ОЗУ
- data_clear — очитстить ОЗУ
- data_inc — инкрементировать значение в ОЗУ
- data_dec — декрементировать значение в ОЗУ
- 12 команд для действий, которые живность может делать (передавать сигналы объекту World):
- action_move_left — живность двигается влево
- action_move_right — живность двигается влево
- action_move_up — живность двигается влево
- action_move_down — живность двигается влево
- action_eat_left — живность пытается съесть объект слева
- action_eat_right — живность пытается съесть объект слева
- action_eat_up — живность пытается съесть объект слева
- action_eat_down — живность пытается съесть объект слева
- action_wait — живность ждёт, пропуск хода
- action_suicide — живность самоуничтожается
- action_split — живность делится клонированием
- action_split_mutate — живность делится клонированием, но с некоторыми мутациями
Пример программы
В принципе такого набора команд достаточно, чтобы делать циклы и ветвления. Другой вопрос, что описывать алгоритмы на таком языке не так удобно, как на С++, например.
Но для примера покажу Вам программу, которая заставляет живность двигаться по квадратной спирали:
start
action_split
load_from_mem //load from var1
move_mem_right //save var2
data_dec
save_to_mem
move_mem_right //save to var3
data_dec
save_to_mem
//right
action_move_right
data_dec
jump_to_ifnz
AnimalCommand(-3)
//up
load_from_mem
data_dec
save_to_mem
action_move_up
data_dec
jump_to_ifnz
AnimalCommand(-3)
//left
load_from_mem
data_dec
save_to_mem
action_move_left
data_dec
jump_to_ifnz
AnimalCommand(-3)
//down
load_from_mem
data_dec
save_to_mem
action_move_down
data_dec
jump_to_ifnz
AnimalCommand(-3)
//dec var2
move_mem_left
load_from_mem
data_dec
save_to_mem
jump_to_ifnz
AnimalCommand(-33)
move_mem_left // restore var1
end;
В память же загружаются 3 значения: 10, 0, 0. Алгоритм пояснять не буду. По-моему всё довольно очевидно.
Этот код вы можете найти в mainwindow.cpp:117.
О мутациях
Мутации в игре сейчас реализованы так. По желанию организма размножиться клонированием с мутацией создается клон. Клон подвергается мутациям в количестве от 0 до 9 (на усмотрение великого рандома). Для каждой мутации великий рандом выбирает один из 4 вариантов:
- 1 произвольный байт кода заменяется на произвольное значение
- к ДНК прибавляется произвольный байт
- от ДНК откусывается байт в произвольной позиции
- в ДНК в произвольную позицию вставляется произвольный байт (свежий коммит)
О скрещивании
Теперь перейдём к размышлениям о том, как нам скрещивать два организма. Их код может быть разной длины, они могут иметь разную память.
- Первое, что напрашивается на ум, это просто слепить 2 ДНК в одну большей длины. Но в таком случае вторая часть алгоритма может не функционировать вовсе, или же работать крайне редко. Что ж, хорошо — будет фактически рецессивным геном.
- Можно взять скажем 3 произвольных точки на каждом ДНК и собрать новую по принципу: кусок 0-1 от первой ДНК, 1-2 от второй, 2-3 от первой, 3-4 от второй. Причём куски могут быть и нулевой длины.
- Можно искать метки start|end и лепить новую ДНК, просто собирая воедино функции от разных организмов. Это заставит живности пытаться как-то структурировать код.
- Есть вариант брать в цикле по байту от каждого организма пока ДНК их не кончится. Получится некий такой Франкинштейн, но свойства его будут весьма интересны.
Вот пожалуй и все варианты, которые сходу приходят мне в голову. Над наследованием памяти ещё не думал.
А! Вот ещё о чем забыл. Как вы считаете, что лучше?
- По истечению Х раундов брать Y самых-самых и скрещивать их. При этом убить всю популяцию, мир заселить этими Y особями и их потомками.
- Каждые Х раундов брать Y (от 2 до 5, скажем) самых сильных и скрещивать их, добавляя их потомство в популяцию.
- Третий вариант — тот который придумаете вы и напишете в комментариях.
Размышлений на тему не густо, конечно, но я надеюсь на богатое воображение читателей.
Спасибо. Жду отзывов.
Автор: icoz
