• В этот раз выбрана игра «Змейка».
• Создана библиотека для нейросети на языке Go.
• Найден принцип обучения, зависимый от «глубины» памяти.
• Написан сервер для игры между разработчиками.

Суть игры

Возможно, многие помнят игру «Змейка», которая шла стандартным приложением на телефонах Nokia. Суть её такова: по полю движется змейка, которая уменьшается, если не находит еду, либо увеличатся, если находит. Если змейка врезается в препятствие, то она погибает.

Я немного изменил правила: змейка не погибает, если врезается, а просто останавливается, продолжая уменьшаться. Кроме того, змейка может делиться пополам. Если у змейки осталось одна ячейка тела и она не нашла еду за 10 ходов, то она погибает, превращаясь в еду.

Мы будем обучать бота, который управляет змейкой. Если змейка разделится, то бот получит в управление ещё одну змейку, которая в свою очередь тоже может разделиться.

За основу взят эксперимент со змейками кибер-биолога Михаила Царькова.

Нейросеть

В рамках задачи была написана библиотека для нейросети на языке Go. Изучая работу нейросети, я использовать видео-дневник foo52ru и книгу Тарика Рашида – Создаём нейронную сеть.

Функция CreateLayer(L []int) создает нейронную сеть с необходимым количеством слоев и их размером. На каждом слое, кроме последнего, добавляется нейрон смещения. На первый слой подаем данные, а из последнего слоя получаем результат.

Пример:

CreateLayer([]int{9, 57, 3, 1})

Здесь мы создали нейронную сеть с девятью входами. Двумя скрытыми слоями по 57 и 3 нейрона и одним нейроном для получения результата. Нейроны смещения автоматически добавляются плюсом к тем, что мы задали.

Библиотека позволяет:

• Подавать данные на вход сети.
• Получать результат, обращаясь к последнему слою.
• Задавать правильные ответы и проводить обучение корректировкой весов связей.

Начальные веса связей задаются случайными значениями близкими к нулю. Для активации мы использовали логистическую функцию.

Обучение бота

Бот получает на вход поле размером 9х9 клеток, в середине которого находится голова змейки. Соответственно наша нейронная сеть будет иметь 81 вход. Порядок расположения клеток, подаваемых на вход, не имеет значения. Сеть при обучении «сама разберется», где что находится.

Для обозначения препятствий и других змеек я использовал значения от -1 до 0 (не включительно). Пустые клетки обозначались значением 0.01, а еда 0.99.

На выходе нейросети использовалось 5 нейронов для действий:

1. двигаться влево по оси Х;
2. вправо;
3. вверх по оси Y;
4. вниз;
5. делиться пополам.

Движение бота определял нейрон, который имеет самое большое значение на выходе.

Шаг 0. Рандомайзер

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

Шаг 1. Обучение без использования памяти

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

Для обучения подавались следующие значения:

• нашел еду: 0.99
• сделал движение в любом направлении: 0.5
• потерял клетку тела не найдя еду (для этого даётся 10 ходов): 0.2
• стоит на месте (ударился о препятствие или застрял): 0.1
• стоит на месте, имея одну клетку тела: 0.01

Пройдя такое обучение боты стали быстро обыгрывать рандомайзера, и я поставил задачу: создать ботов, которые будет обыгрывать этих.

А/Б тестирование

Для выполнения этой задачи была создана программа, которая делит змеек на две части в зависимости от конфигурации нейронной сети. На поле выпускалось по 20 змеек каждой конфигурации.

Все змейки, находящиеся под управлением одного бота, имели одну и ту же нейронную сеть. Чем больше было змеек в его управлении и чем чаще они сталкивались с разными задачами, тем быстрее проходило обучение. Если, например, одна змейка научилась избегать тупиков или делиться пополам, попав в тупик, то автоматически все змейки данного бота, приобретали эти умения.

Меняя конфигурацию нейронной сети можно получить хорошие результаты, но этого не достаточно. Для дальнейшего улучшения алгоритма я решил использовать память на несколько ходов.

Шаг 2. Обучение с использованием памяти

Для каждого бота я создал память на 8 ходов. В память было записано состояние поля и ход, который предлагал бот. После этого я проводил корректировку весов для всех восьми состояний, которые предшествовали ходу. Для этого я использовал единый коэффициент корректировки, независимый от глубины хода. Таким образом, каждый ход приводил к корректировке весов не один раз, а восемь.

Как и ожидалось, боты с памятью начали быстро обыгрывать ботов, которые обучались без использования памяти.

Шаг 3. Снижение коэффициента корректировки в зависимости от глубины памяти

Далее я попробовал снижать коэффициент корректировки, в зависимости от глубины памяти. За последний сделанный ход был установлен самый большой коэффициент корректировки весов. За ход, который предшествовал ему, коэффициент корректировки снижался и так далее по всей памяти.



Линейное снижение коэффициента корректировки в зависимости от глубины памяти привело к тому, что новые боты стали обыгрывать тех, у которых использовался единый коэффициент.

Далее я попробовал использовать логарифмическое снижение коэффициента корректировки. Коэффициент снижался в два раза, в зависимости от глубины памяти на каждый ход. Таким образом, ходы, которые были сделаны «давно», оказывали значительно меньшее влияние на обучение, чем «свежие» ходы.

Боты, имеющие логарифмическое снижение коэффициента корректировки, стали побеждать ботов с линейной зависимостью.

Сервер для ботов

Как выяснилось, улучшать уровень «прокачки» ботов можно бесконечно. И я решил создать сервер, где могли бы соревноваться разработчики между собой (независимо от языка программирования) в написании эффективного алгоритма для Змеек.

Протокол

Для авторизации нужно отправить GET запрос к каталогу «game» и указать имя пользователя, например:

.../game/?user=masterdak

Вместо «…» нужно указать адрес сайта и порт, где развернут сервер.

Далее сервер выдаст ответ в формате JSON с указанием сессии:

{"answer":"Hellow, masterdak!","session":"f4f559d1d2ed97e0616023fb4a84f984"}

После этого можно запросить карту и координаты змейки на поле, добавив к запросу сессию:

.../game/?user=masterdak&session=f4f559d1d2ed97e0616023fb4a84f984

Сервер выдаст примерно такой ответ:

{
    "answer": "Sent game data.",
    "data": {
        "area": [
            ["...большой числовой массив..."]
        ],
        "snakes": [
            {
                "num": 0,
                "body": [
                    {
                        "x": 19,
                        "y": 24
                    },
                    {
                        "x": 19,
                        "y": 24
                    },
					{
                        "x": 19,
                        "y": 24
                    }
                ],
                "energe": 4,
                "dead": false
            }
        ]
    }
}

В поле area будет указано состояние игрового поля с такими значениями:

0	//пустое поле
-1	//еда
-2	//стена
2	//голова змейки
1	//тело змейки

Далее последует массив со змейками, которые находятся в вашем управлении.

Тело змейки находится в массиве body. Как видно все тело змейки (включая голову — первая ячейка) в начале находятся на одной позиции «x»: 19, «y»: 24. Это связано с тем, что в начале игры змейки вылазят из норы, которая на поле определяется одной клеткой. Далее, координаты тела и головы будут отличаться.

Следующие структуры (пример на языке Go) определяют все варианты ответа сервера:

type respData struct {
	Answer  string
	Session string
	Data    struct {
		Area   [][]int
		Snakes []struct {
			Num    int
			Body   []Cell
			Energe int
			Dead   bool
		}
	}
}
type Cell struct {
	X int
	Y int
}

Далее необходимо отправить ход, который делает змейка, добавив move к GET запросу, например:

...&move=u

u — означает команду вверх;
d — вниз;
l — влево;
r — вправо;
/ — деление пополам.

Команда для нескольких змеек (например, для семи) будет выглядеть так:

...&move=ud/urld

Один символ — одна команда. Ответ должен содержать команду для всех змеек, находящихся под вашим управлением. В противном случае часть змеек могут не получить команду и будут продолжать старое действие.

Поле обновляется с интервалом 150 мс. Если в течение 60 секунд не поступит ни одной команды, сервер закроет соединение.

Ссылки

Дабы избежать хабраэффект, тем, кому будет интересно посмотреть, отправьте мне сообщение. В ответ я пришлю ip адрес своего сервера. Либо можете развернуть свой сервер, используя исходные коды программы.

Я не являюсь специалистом ни в программировании, ни в нейросетях. Поэтому могу допускать грубые ошибки. Код выкладываю «как есть». Буду рад, если более опытные разработчики, покажут на допущенные ошибки.

1. Библиотека для нейронной сети вместе с игрой «Крестики-нолики»
2. Snake Master – Server
3. Snake Master – Bot
4. SnakeWorld2

UPD
Временно выкладываю IP адрес сервера. Сейчас там запущен только один бот-рандомайзер (SnakeBot0). Надеюсь, сервер упадет не так быстро.