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

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

Модель

Есть две точки. Со значениями 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 секунд.