Как стать автором
Обновить

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

Время на прочтение14 мин
Количество просмотров12K
Всего голосов 54: ↑54 и ↓0+54
Комментарии17

Комментарии 17

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

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

НЛО прилетело и опубликовало эту надпись здесь

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

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

К сожалению мой аппаратно-программный комплекс в виде мозга и Nokia 3110 был не способен решать задачу графов в реальном времени. А еще клавиши зависали... :)

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

Скорее всего это Snake Batle

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории