Evo, часть 2 — о скрещивании

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

В продолжение поста «Аналог игры «Жизнь» — Evo» хотелось бы дать более подробное описание команд «языка генов», который используется в Evo, и поделиться своими соображениями по методам скрещивания особей в этой игре.

Генетический код

Генетический код особей в Evo представляет собой последовательность байт практически неограниченной длины. При этом каждый байт трактуется как команда для клеточного автомата. У автомата 2 ленты: команд и памяти. Соответственно есть два указателя cmd_ptr и mem_ptr. В качестве ОЗУ животного используется переменная data, размерностью в 1 байт (8 бит).
На текущий момент есть следующие команды:

• 9 команд управления исполнением «генетического» кода:
  
  1. nop — ничего не делать
  2. move_cmd_left — передвинуть указатель команд влево
  3. move_cmd_right — передвинуть указатель команд вправо
  4. jump_to — сдвинуть указатель команд вправо на Х позиций (следующий за командой байт трактуется как signed char, то есть отрицательные значения сдвинут указатель влево)
  5. jump_to_ifz — то же, что и jump_to, но при условии, что значение data == 0
  6. jump_to_ifnz — то же, что и jump_to, но при условии, что значение data != 0
  7. start — то же, что и nop, просто метка для начала какого-то обособленного куска (начало функции)
  8. restart — сбрасывает значение cmd_ptr в 0
  9. end — конец функции, заставлет искать дальше по ленте метку start, с которой продолжить выполнение (если метки нет, то cmd_ptr=0)
• 8 команд, позволяющих живности осмотреться вокруг себя (результаты сохраняются в ОЗУ живности, в переменной data):
  
  1. eye_up_distance — получить значение дистанции до ближайшего объекта вверх
  2. eye_down_distance — получить значение дистанции до ближайшего объекта вниз
  3. eye_left_distance — получить значение дистанции до ближайшего объекта влево
  4. eye_right_distance — получить значение дистанции до ближайшего объекта вправо
  5. touch_up — получить значение типа ближайшего объекта вверх
  6. touch_down — получить значение типа ближайшего объекта вниз
  7. touch_left — получить значение типа ближайшего объекта влево
  8. touch_right — получить значение типа ближайшего объекта вправо
• 10 команд управления памятью живности:
  
  1. move_mem_left — сдвинуть указатель mem_ptr влево
  2. move_mem_right — сдвинуть указатель mem_ptr влево
  3. save_to_mem — сохранить в текущую ячейку содержимое ОЗУ живности (data)
  4. load_from_mem — загрузить значение из текущей ячейки в ОЗУ живности (data)
  5. add_mem — прибавить к data значение текущей ячейки памяти
  6. sub_mem — вычесть из data значение текущей ячейки памяти
  7. set_mem_ptr — установить mem_ptr равным значению ОЗУ
  8. data_clear — очитстить ОЗУ
  9. data_inc — инкрементировать значение в ОЗУ
  10. data_dec — декрементировать значение в ОЗУ
• 12 команд для действий, которые живность может делать (передавать сигналы объекту World):
  
  1. action_move_left — живность двигается влево
  2. action_move_right — живность двигается влево
  3. action_move_up — живность двигается влево
  4. action_move_down — живность двигается влево
  5. action_eat_left — живность пытается съесть объект слева
  6. action_eat_right — живность пытается съесть объект слева
  7. action_eat_up — живность пытается съесть объект слева
  8. action_eat_down — живность пытается съесть объект слева
  9. action_wait — живность ждёт, пропуск хода
  10. action_suicide — живность самоуничтожается
  11. action_split — живность делится клонированием
  12. 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 и лепить новую ДНК, просто собирая воедино функции от разных организмов. Это заставит живности пытаться как-то структурировать код.
• Есть вариант брать в цикле по байту от каждого организма пока ДНК их не кончится. Получится некий такой Франкинштейн, но свойства его будут весьма интересны.

Вот пожалуй и все варианты, которые сходу приходят мне в голову. Над наследованием памяти ещё не думал.
А! Вот ещё о чем забыл. Как вы считаете, что лучше?

1. По истечению Х раундов брать Y самых-самых и скрещивать их. При этом убить всю популяцию, мир заселить этими Y особями и их потомками.
2. Каждые Х раундов брать Y (от 2 до 5, скажем) самых сильных и скрещивать их, добавляя их потомство в популяцию.
3. Третий вариант — тот который придумаете вы и напишете в комментариях.

Размышлений на тему не густо, конечно, но я надеюсь на богатое воображение хабражителей.
Спасибо. Жду отзывов.