Что в голове у змейки? Обучение нейросети играть в «Snake» генетическим алгоритмом

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

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

Давно, попадалась игра, где надо было программировать змеек путём описания того что видит голова в квадрате три на три (емнип) и змейки кушали не яблоки а хвосты друг друга. С приятелем устраивали сражения. Правда оказалось что идеальной змейки не получается, а выходит "камень-ножницы-бумага"

Интересно было бы сравнить с реализацией обучения с подкреплением, насколько будет отличаться эффективность обучения?

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

Сам когда то и плотно занимался генетическом алгоритмом.

Наблюдал похожее поведение как и Вас.

Генетика имеет тенденцию скатываться в ближайшие минимумы, откуда трудно выбираться.

Можно пробовать варьировать мутацию на плато. Это сходно с learning rate для back propagation.

Можно варьировать сколько поколений переживает лучшее решение.

Можно натренировать одну популяцию. Затем разделить на две. И тренировать их с разными уровнями мутации. Время от времени скрещивать между собой представителей популяций.

Можно усложнить функцию цели. Учмтывать не только количество съеденных яблок. Но и факторы косвенно влияющие на достижение цели. Положительно или отрицательно. Собрать их воедино и подобрать веса.

Советую почитать книги Александра Маркова по эволюции. Там вы найдёте схожие графики приспособляемости :-) И примеры факторов подстёгивающих эволюцию

Классно!

Я лет пять назад сделал подобное для танчиков-минеров: https://github.com/skuznetsov/smart_minesweepers

Лет 20 назад вплотную увлекся ГА.

В процессе скрещивания вычислял насколько близки родители (Инцест). Чем более похожи родители, тем сильнее увеличивал коэффициент мутаций. Чем меньше похожи, тем сильнее уменьшал мутации (вплоть до 0,0001). На одной из простых задач на пару дней(?) запустил задачу подбора оптимальных параметров скорости изменения мутаций. Т.е. сделал один ГА над другим ГА. И знаете к чему пришел алгоритм? На практике это было так: ГА выходит на плато, все потомки очень похожи, в этот момент начинает резко увеличиваться число мутаций (самая лучшая особь предыдущего поколения копируется без мутаций и скрещивания, поэтому она гарантированно не пострадает). Из-за большого числа мутаций особи "взрываются" - у них сильно падает приспособленность. В этот момент коэффициент мутаций падает почти до нуля и начинается обычный отбор (с пониженной мутацией). Такие волны увеличивали шанс найти оптимальное решение. Так же в ряде случаев помогает оптимизация методом имитации отжига (или одним из градиентных методов) лучшей особи (оптимизация лидера). https://imageman72.livejournal.com/tag/ГА

В твоём случае я сделал бы немного иначе. Пусть ГА подбирает структуру сети, а обучение нейронки делал бы обычными методами (так быстрее). В результате работы мы получили бы самую эффективную по размеру/скорости нейросетку. Только нужно понять насколько извращенную (нетрадиционную) структуру нейросети мы хотим получить и реализовать превращение генотипа в фенотип. Функция приспособленности будет иметь несколько слагаемых: размер нейросети + скорость обучения нейросети (мы ведь хотим побыстрее учить нейросеть?) + рекорд нейросети на поле и т.п.

Добавьте штраф за пройденное расстояние (но что бы профит от съедания одного "яблока" был выше штрафа за максимально возможное пройденное расстояние)