- PVSM.RU - https://www.pvsm.ru -
Серия статей по написанию ИИ для многопользовательской онлайн игры жанра рогалик.
Часть 1 [1].
В этой части статьи рассмотрим подходы по созданию логики для ИИ, немного поговорим о целеполагании каждого законопослушного бота, а также определимся с выбором языка программирования и напишем немного кода.
Для того, чтобы создать ИИ, необходимо разобраться в устройстве игрового мира.
Vindinium — многопользовательский пошаговый рогалик. У каждого из четырех игроков есть один герой, который может перемещаться по карте. Цель состоит в том, чтобы игроки собрали максимальное количество золота в течение заданного количества ходов (каждый игрок делает 300 ходов за игру, таким образом, вся игра состоит из 1200 ходов). Игроки должны взять под свой контроль золотые рудники для производства золота; однако рудники защищены гоблинами. Когда игрок побеждает гоблина, он становится владельцем рудника и получает одно золото за ход. Кроме того, гоблин теперь защищает рудник от других игроков.
Герои могут сражаться друг с другом. Выживший в бою получает контроль над всеми золотыми рудниками своего противника. Убитый герой немедленно возрождается со всем своим золотом, однако все рудники переходят в руки убийце.
Наведываясь в таверну, герои могут купить пиво за 2 единицы золота, таким образом восстанавливая свои очки здоровья.
Цель состоит в том, чтобы создать компьютерную программу (бота), которая играет в игру Vindinium как можно более разумно. Рекомендуется использовать один из стартовых наборов для большого числа языков программирования [2] в качестве отправной точки.
Карты создаются случайным образом. Каждый игровой объект на карте кодируется с использованием двух символов. Пример карты:
+----------------------------------------+
|######$- $-############$- $-######|
|###### ## ## ######|
|####[] #### #### []####|
|## #### ## ## #### ##|
|#### $- $- ####|
|########## @1 @4 ##########|
|############ #### #### ############|
|$-##$- ############ $-##$-|
| $- $-################$- $- |
| ######################## |
| ######################## |
| $- $-################$- $- |
|$-##$- ############ $-##$-|
|############ #### #### ############|
|########## @2 @3 ##########|
|#### $- $- ####|
|## #### ## ## #### ##|
|####[] #### #### []####|
|###### ## ## ######|
|######$- $-############$- $-######|
+----------------------------------------+
##
— Непреодолимый лес
@1
— Первый герой
[]
— Таверны
$-
— Золотой рудник (ничейный)
$1
— Золотой рудник (принадлежащий первому герою)
Сгенерированные карты симметричны и всегда содержат 4 таверны и 4 героя.
Герои могут перемещаться на одну клетку за каждый ход и иметь следующие показатели:
Бот должен отдавать один приказ за ход. Возможные приказы: Стоять на месте
(Stay
), На север
(North
), На юг
(South
), На восток
(East
) или На запад
(West
). Как только приказ исполнен, герой остается на своем месте или перемещается на одну клетку в заданном направлении.
Если герой:
После того, как герой переместился (или решил остаться на месте), произойдут следующие вещи:
Герои немного нервничают и никогда не упускают возможности ударить друг друга большими мечами. В конце хода героя, если есть враг на расстоянии одного квадрата в любом направлении, герой его атакует. Например, в этой ситуации, в конце хода первого героя (@1
):
########
##@1@2##
## @3##
########
Игрок 1 атакует второго игрока, но не трогает третьего, потому что третий стоит на расстоянии двух клеток от него.
Нападающий не теряет единиц здоровья, обороняющийся теряет 20 единиц.
Если обороняющийся умирает (см .: Смерть героя), нападающий получает контроль над всеми золотыми рудниками проигравшего.
После своего хода и сражений с другими героями (если таковые были), игрок получает одну единицу золота за каждый подконтрольный рудник.
Затем герой теряет одну единицу здоровья, ибо любое действие вызывает у него жажду.
Обратите внимание, что герои не могут умереть от жажды. В худшем случае, значение их здоровья падает до единицы.
Когда здоровье героя падает до нуля, он умирает. Герой немедленно появляется на карте на своей точке возрождения, с полным запасом здоровья (100 единиц). Герой теряет контроль над всеми своими золотыми рудниками, но сохраняет все свое накопленное золото. Будьте осторожны, когда герой возвращается на точку возрождения, любой противник, который находится в этой клетке, автоматически умирает. Таким образом, вам следует избегать пребывания на клетке возрождения одного из героев ...
Герой не может умереть от жажды. Жажда может оставить героя с одной единицей здоровья, но не убить его.
Игра заканчивается, когда достигается максимальное количество ходов(обычно 300). Победителем является герой с наибольшим количеством золота. Если у двух игроков одинаковое количество золота, победителя нет.
Система оценки относительной силы игроков использует Рейтинг Эло [3]. Идея такова: лучше быть первым, чем вторым, лучше быть вторым, чем третьим, и так далее. Надеюсь, принцип понятен.
Вы можете одновременно запускать несколько экземпляров ваших ботов и, в общем-то, использовать любые меры, которые, по вашему мнению, подходят для достижения доминирующего лидерства. Боритесь!
Стоит отметить еще пару аспектов, которые не были описаны в правилах, но выявлены опытным путем:
Исполнение приказа
— Бьем ближайших врагов
— Теряем 1 единицу здоровья от жажды
. А что случится, если в ходе исполнения приказа мы умрем (в игре можно это сделать, только умерев в сражении с гоблином)? Мы возрождаемся (и мгновенно убиваем игрока, который стоит сейчас на нашем спаунпоинте), но теряем возможность ударить ближайших врагов, а также не теряем 1 единицу здоровья вследствие жажды.Виндиниум — публичная игра, ее полезной стороной является то, что мы можем заглянуть в профиль любому игроку и посмотреть последние сто боев с его участием. "Отлично! Самое время использовать нейронные сети, ведь у нас есть 50 топ-игроков, возьмем из них 10 самых сильных, в каждом из 100 последних боев содержится ~300 моментов, когда игрок должен был принимать решение, итого около 200-300 тысяч единиц материала для обучения! А еще можно каждую ситуацию вращать по часовой стрелке, отзеркаливать, etc, чтобы получить еще больше материала для обучения и закрепить результат, это даст нам аж целых 4.8-7.2 миллионов единиц материала" — раздался голос разума. Да, действительно, такая идея имеет право на существование. К тому же, у нейронных сетей есть много достоинств.
Однако подростковый максимализм во мне хочет пойти более сложным путем — не возлагать поиск закономерностей на нейронную сеть, а сделать эту работу самостоятельно, в лоб, полагаясь на интуитивную более высокую пластичность данного решения.
Итак. Деревья решений, альфа-бета отсечение, минимаксы… слишком ресурсоёмкие задачи! На сабреддите виндиниума несколько разработчиков, раскрывая завесу тайны своих ботов, уже использовали это решение, и наверняка не в таких спартанских условиях. К сожалению, в этой сфере вряд ли удастся что-либо сделать лучше, чем у остальных.
Начитавшись статей про эволюционные, генетические алгоритмы, решающие деревья, я откопал тайное знание — потенциальные поля. Подробнее о них можно почитать здесь [5] и здесь [6]. Данная идея показалась очень даже рабочей, ведь потенциальное поле — планарный граф, в каждое звено помещается функция, которая зависит от входных данных (в частности — расстояния от объекта, но никто не мешает сделать больше условий). Всё это прекрасно ложится в реалии виндиниума — тебе не нужно искать путь до объекта, если это уже заложено в алгоритме.
Давайте понаблюдаем за боями топовых персонажей. Перед началом выберем фаворита, будем следить за ним, болеть за него, журить за неправильные решения в стиле "а вот я бы так поступил на этом месте...". Спустя десяток боев уже можно сделать первый набросок, что такое законопослушный ИИ (условия проверяются по порядку):
Вопрос-ответ:
(1) Многофункциональность. Проще изменять параметры, добавлять новые функции. Следишь такой за своим персонажем, радуешься, а тут бац — и видишь, что в определенный момент можно было поступить совсем иначе, более благоразумно, — пишем новое правило или изменяем старое. (2) Также мы знаем точно, каким решением руководствовалась программа во время выбора определенного хода. (3) Потенциальные поля хорошо себя показали в рогаликах как основа для искусственного интеллекта ботов.
В лидерборде на 27 месте висит Zaraza 0.1
— ИИ на потенциальных полях, который руководствуется всего лишь тремя инстинктами — бездумно захватывать всё, что попадется на своем пути, не просыхать в барах и осторожно вести себя с врагами. Если последите за его движениями, то увидите, как хорошо он воюет, хотя это просто невероятно для ИИ, которое базируется на трех простых правилах и ему даже в снах не привидится какое-либо сложное поведение. Более того, сейчас я работаю над Zonko 0.11
, которая является сильно улучшенной версией выпивохи Zaraz'ы, в нее можно встроить намного более сложное поведение за счет улучшенного взаимодействия с полями — прямо как в новомодном GPS. Но, как оказалось, она прожорливо относится к ресурсам, поэтому сейчас происходит процесс ее оптимизации… Но это я отвлекся, сейчас мы говорим о строгих ограничениях, строгих правилах строгих (...).
Итак, а теперь язык программирования… Лично я сейчас мечусь между Python3 (быстрая разработка, легко читается, давно знаком с ним, есть pypy3 (быстрый оптимизированный интепретатор), jupyter ("тетрадки", в которых можно спокойно писать куски кода и их оптимизировать до бесконечности); но pypy/pypy3 не работает под ARM 64bit, да и вообще ARM больше не поддерживают, и сам язык в силу своей природы уступает компилируемым) и Golang (тоже быстрая разработка, легко понимается, большой уклон на бэкэнд, многопоточность и мультипроцессность, выполняется быстрее питона; но придется привыкать к отсутствию интерактивной среды, к статической типизации).
Основную функцию, которая общается с сервером, можно представить в таком виде:
# в глобалях находятся переменные train_url, arena_url, userkey, добытые из config.py
from config import train_url, arena_url, userkey
import requests, random, json, time
def start(is_train = True, debug = True, show_decision = True):
# Получаем информацию
if is_train:
r = requests.post(train_url, data={"key":userkey})
else:
r = requests.post(arena_url, data={"key":userkey})
timer = time.time()
data = json.loads(r.text)
if debug or show_decision:
print('viewUrl:', data['viewUrl'])
print('Размер карты:', data['game']['board']['size'])
#цикл
while True:
if debug:
print('Turn', data['game']['turn'])
# Вызываем функцию принятия решения
direction = random.choice(['North', 'South', 'East', 'West', 'Stay'])
if show_decision or debug:
print('Решение хода',str(data['game']['turn'])+':', direction)
# Возвращаем ответ на сервер, проверяем коды состояния, завершаем игру.
if debug:
print('Время:',time.time()-timer)
r = requests.post(data['playUrl'], data={'key': userkey, 'dir': direction})
timer = time.time()
if r.status_code != 200:
print('Request code :', r.status_code)
print('Reason:', r.reason)
break
data = json.loads(r.text)
if data['game']['finished']:
print('Game finished.')
break
Но рекомендуется использовать готовые разработки, ссылки на которых можно найти на официальном сайте Vindinium.
Extra 1: Очень хочу почитать о разработках искусственного интеллекта на основе Виндиниум от других людей, ибо так можно понять всю многогранность решения этиой задачи. Для того, чтобы получить сводку боя в формате json (это может быть полезно для отладки проведенных боев), надо ссылку на бой вида http://vindinium.org/fd96vc2z [8] преобразовать в ссылку вида http://vindinium.org/events/fd96vc2z [9]. Но не советую мучить сервер игры, пытаясь достать сотни боев топовых игроков, воспользуйтесь ссылкой выше.
Extra 2: Если кто-то хочет попробовать свою наработку в Виндиниум загнать в ограничения NanoPi Neo2 или Orange Pi Zero, я могу предоставить возможность поработать с данными одноплатными компьютерами.
→ Ссылка на Vindinium [10]
→ Ссылка на сабреддит Vindinium [11] — очень полезная вещь, там можно отследить мои движения по Виндиниуму
→ Ссылка на мой гитхаб с небольшими наработками по Vindinium [12]
В следующей части будем настраивать потенциальные поля, работать с потенциальными картами, писать условия и накладывать всё это на современные реалии.
Автор: rakovskij_stanislav
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/raspberry-pi/262147
Ссылки в тексте:
[1] Часть 1: https://geektimes.ru/post/291823/
[2] один из стартовых наборов для большого числа языков программирования: http://vindinium.org/starters
[3] Рейтинг Эло: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B9%D1%82%D0%B8%D0%BD%D0%B3_%D0%AD%D0%BB%D0%BE
[4] Ссылка на оригинал: http://vindinium.org/doc
[5] здесь: https://habrahabr.ru/post/262181/
[6] здесь: https://habrahabr.ru/post/307368/
[7] ссылка: https://drive.google.com/file/d/0B2C275mx0Ol8RVM4UnZpdVk5cms/view?usp=sharing
[8] http://vindinium.org/fd96vc2z: http://vindinium.org/fd96vc2z
[9] http://vindinium.org/events/fd96vc2z: http://vindinium.org/events/fd96vc2z
[10] Ссылка на Vindinium: http://vindinium.org/
[11] Ссылка на сабреддит Vindinium: https://www.reddit.com/r/vindinium/
[12] Ссылка на мой гитхаб с небольшими наработками по Vindinium: https://github.com/rakovskij-stanislav/Vindinium_Zaraza
[13] Источник: https://geektimes.ru/post/291879/
Нажмите здесь для печати.