Генетический алгоритм, нейросеть играет в догонялки

Нейронка (#) учится убегать от бота (@). Изначально она вообще не знает - что нужно делать. Однако, с каждым следующим поколением, эволюционным путем формируется требуемый паттерн поведения. На видео можно наглядно пронаблюдать, как с каждым поколением ей это удается все лучше и лучше. Это лишь один из запусков, в другой раз - поведение может быть иным, например - сетка может бегать вдоль стены по кругу.

Модель

Есть две точки. Со значениями x,y. На видео - это сетка (#) и бот (@).

Поведение бота определенно заранее. Он двигается в сторону сетки с максимальной скоростью. Как только бот настигнет сетку - игра окончена. Количество очков зависит от того, как долго сетка сможет убегать. Я ограничил в 10000 тактов макс, чтобы не зависло. Когда сетке удастся набегать 10000 тактов - это победа.

И у сетки и у бота есть максимальная скорость и размер (5). Скорость бота - 1, сетки - 2. Сетка может двигаться с любой скоростью в пределах максимальной. Бот - всегда с максимальной. Поле ограничено: 400х225.

Нейронка

Тут все просто как два пальца. Feedforward сеть. На вход 4 значения: угол и расстояние между ботом и сеткой, и положение x,y сетки на экране. Нормализация: угол делится на ПИ, расстояние - на диагональ поля. Положения на экране делятся на ширину и высоту поля. Получается нормализованный вектор в 4 значения.

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

Два скрытых слоя, по 12 нейронов на каждый. Связи между каждым слоем - полные (full join) - каждый нейрон входного слоя с каждым нейроном выходного.

Выходной слой - 2 значения. Угол движения сетки и скорость. Активация через гиперболический тангенс. O(x)=tanh(sum(x)+bias)

Исходные значения весов и bias задаются случайно, в диапазоне [-0.5; 0.5]

Мутация

Обучается сетка без учителя. На каждое поколение (ограничил 10000 макс) - создается уникальная среда и мутации. Сначала создается мутация, есть 5% шанс, что bias или вес изменятся. Сила изменения bias (смещения) - 0.4, веса - 0.4. Т.е. вес и смещение изменится на случайную величину в диапазоне [-0.2, 0.2]. Всего на каждое поколение создается 20 мутантов. Каждый играет в изолированной среде, мутант победитель дает следующее поколение.

Каждый мутант играет 5 игр. Тот, что в сумме наберет наибольшее количество очков - побеждает. Каждую игру положение и сетки и бота - случайное.

Реализация

Писал на C#. Изначально делал на JS, но возникла потребность в производительности, обучение - ресурсозатратный процесс. Сетка учится избегать бота в среднем за 750-1200 поколении. Особо сильно с оптимизацией не запаривался - но думаю, вполне возможно достичь 2-5 минут на полное обучение при текущей конфигурации. Т.о. доказана возможность обучения через игру. (Up: ~400 поколений в минуту после распараллеливания)

В главном потоке происходит непрерывная генерация новых поколений, в параллельном - демонстрация хода игры в консоль последнего победителя. Так же выводится: длительность текущей игры; оставшееся количество поколений; угол и скорость сетки. Могу залить исполняемый файл - если кому хочется поиграться - пишите.

Дальнейшие планы

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

В целом - тренд на онлайн игру "Нейромоны". Тренер нейромона обучает, размножает, скрещивает и меняется ими с другими тренерами. Нейромоны могут играть на турнирах с нейромонами других тренеров. На сервере создается уникальный уровень для того или иного типа игры, нейромоны зарабатывают победы, рейтинг и места в турнирных таблицах. В общем, как игра "покемоны" - но с реальной обучаемой моделью и абсолютно уникальной сеткой внутри. Эффективность задается не только "типом" покемона и его статами, а реальной приспособленностью к тем или иным игровым ситуациям. Для тренера - зиро кодинг и контроль, лишь менеджмент и стратегическое планирование. А так - просто делаю Zomoby, но которая играет сама в себя еще больше. Это кста камень в огород Gaijin Entertainment - мне тогда их тимлид сказал, мол сама в себя играет. И тут бац - 5 лет спустя стреляет Vampire Surivors.

GUI буду реализовывать по остаточному принципу. Задача тривиальная, т.к. на клиент передается история состояний игрового поля. Затем GUI просто ее отрисовывает - как в примере с консолью. При этом и сетевой код не проблема для гигантских баталий - нейронки игроков уже есть в базе, нужно лишь запустить игру хоть с 500 участниками и отдать на GUI историю.

Благодарю за внимание.

UP: Все то-же, но сетка достигла 5000 тактов на ~200 поколении за ~30 сек.

После чего я добавил на вход изменение сетки в пространстве (значения dx,dy, которые отражают, как сильно сдвинулась сетка в пространстве. Если уперлась в стену - независимо от ее скорости - двигаться не будет, поэтому dx=0 или dy=0). Сетка нашла решение на 5000 тактов за (примерно) 135 поколений и 16 секунд.