Серия статей по написанию ИИ для многопользовательской онлайн игры жанра рогалик, ограниченного производительностью одноплатного компьютера.
В этой части статьи мы посмотрим на один из самых понятных и послушных ИИ в рогаликах, напишем простые правила, которыми можно будет легко управлять, и поговорим о сборе статистики.
Но перед этим немного о возвышенном: janvarev запустил очень удобный лидерборд, по которому можно отследить свой рейтинг среди игроков, которые играли в течение десяти дней. Присоединяйся и ты! Первые пять пользователей Гиктаймса, которые 30 сентября в лидерборде займут место выше, чем Zonko 0.11, получат золото открытку из Москвы! Я бедный студент, живу на стипендию Единственное условие — никнейм бота должен совпадать с никнеймом в Гиктаймсе (или хотя бы очень походить).
Потенциальные поля...
Для начала необходимо понять, что такое потенциальные поля (ПП), для этого нам нужны эта и эта статьи.
В целом, ПП можно представить как карту распространения сигнала от объекта на все клетки поля, огибая преграды. Вот, к примеру, распространение поля возле игрока R (id=4), чем темнее, тем слабее поле.
Существуют реализации с использованием псевдокода, что позволяет работать над ПП с большинством языков программирования.
Расчет потенциальных полей для всех рудников, игроков и таверн — не очень тяжелая задача, с которой даже одноплатный компьютер справляется при должной пряморукости программиста.
Теперь посмотрим на эту задачу полноценно:
- Получаем от сервера информацию о состоянии игры;
- Добываем координаты таверн, игроков, рудников — значимых игровых объектов;
- Считаем потенциальное поле всех игровых объектов, складываем в общий словарь вида:
Координата поля - id объекта - значение поля; - Используя магию, получаем решение, в какую сторону пойдем в этот раз.
Теперь будем работать по пунктам:
1. Информация о состоянии игры
Тут говорить, честно говоря, не о чем. На официальном сайте доступны наборы для быстрого старта на 28 языках программирования. К слову, очень легко обойтись и без них, ведь там всего-лишь POST-запросы и работа с json. Для python существуют модули requests и json, которые сделают всю грязную работу сами. Во второй части был приведен код, который работает с ответами сервера.
2. Добываем координаты игровых объектов
Здесь нужно сказать пару слов:
- Координаты всех четырех игроков доступны в
game - heroes - hero_id - pos; - Таверны и спаунпоинты — единственные неизменные объекты на карте. Они не перемещаются, не переходят из одних рук в другие. Их расположение можно запомнить раз и навсегда;
- Координаты рудников придется доставать из карты каждый раз, ибо они имеют свойство менять своего хозяина;
- Затем всё это упаковываем в один словарь «название — координата», при этом рудники и таверны следует пронумеровать.
{'0_0': [4, 2],
'0_1': [4, 13],
'0_2': [11, 2],
'0_3': [11, 13],
'A_0': [3, 3],
'D_0': [12, 12],
'E_0': [12, 12],
'F_0': [3, 12],
'Q_0': [3, 3],
'R_0': [3, 12],
'S_0': [12, 3],
'W_0': [12, 3],
't_0': [3, 4],
't_1': [3, 11],
't_2': [12, 4],
't_3': [12, 11]}При этом первый символ ключа обозначает тип объекта, последний — количество одинаковых объектов. 0, 1, 2, 3, 4 обозначают рудники и их принадлежность какому-либо игроку (0 — нейтральный рудник, 3 — рудник, принадлежащий третьему игроку). Q, W, E, R — четыре игрока соответственно, A, S, D, F — их спаунпоинты. В качестве значения представлены координаты.
3. Просчитать потенциальные поля
Выше я сказал, что для реализации потенциального поля на своем ЯП нет преград. Лично мне понравилось очень лаконичное и быстрое решение отсюда, стоит только часть функции emit перенести в свой код, чутка доработав напильником. Нужно поделить все объекты на три категории:
— Пустота — сохраняет и распространяет дальше заряд поля. К таким объектам принадлежат спаунпоинты и пустые клетки. К слову, спаунпоинт должен распространять заряд, даже если на нем стоит персонаж.
— Барьер — не сохраняет и не распространяет дальше заряд поля. Такими объектами являются все препятствия, с которыми игрок не может взаимодействовать (отмечены на карте "##").
— Аккумулятор — сохраняет в себе значение заряда, но не распространяет дальше. Это нужно для того, чтобы поле огибало эти объекты. Такими объектами являются рудники, игроки, таверны В случае, если, к примеру, какой-то игрок заблокирует проход шириной в одну клетку, сигнал не сможет распространиться дальше.
Теперь, если есть смысл заморачиваться со скоростью работы, необходимо задачу разбить на N частей (в случае с одноплатным четырехъядерным компьютером N=3, чтобы сохранить одно ядро для основного процесса и для внутренних нужд операционной системы) и скормить карту и координаты процессам, чтобы получить потенциальные карты всех объектов (моя реализация на Python3 в один поток не справляется при размере карты 28х28 с 40+ объектами, приходится параллелить).
Как разбиваю задачу:
g = list(board.objects.keys()) # лист, содержащий ключи от словаря, представленного в спойлере выше
#магическое разбиение одного массива на три
if len(g)%3 == 0:
missions = (g[:len(g)//3], g[len(g)//3:2*len(g)//3], g[2*len(g)//3:])
else:
missions = (g[:len(g)//3+1], g[len(g)//3+1:2*len(g)//3+1] , g[2*len(g)//3+1:])
pot_field = zero_field(data['game']['board']['size']) # создаем пустое поле, в которое будем заносить результаты работы
with concurrent.futures.ProcessPoolExecutor(max_workers=3) as pool:
pp = []
for i in range(3):
#worker_layer решает потенциальные поля переданных ему объектов
pp.append(pool.submit(worker_layer, board, targets=missions[i], coors=targets))
for i in pp:
m = i.result()
# тут надо суммировать три поля в одно
if pot_field =='':
pot_field = m
else:
for key in pot_field.keys():
if key in m:
pot_field[key].update(m[key])
4. Магия
Теперь мы можем обратиться к любой точке карты, чтобы узнать расстояние объектов до нее.
- Возьмем пять точек от нашего объекта: (x,y) — Stay, (x-1, y) — North, (x+1, y) — South, (x, y-1) — West, (x, y+1) — East. Исключим те точки, которые упираются в барьеры ("##").
- Для каждой из оставшихся точек:
- Найдем значение сигнала от ближайшей таверны, ближайшего не нашего рудника(=наименьшее значение сигнала по выбранным категориям);
- Возьмем answer = 0;
- Воспользуемся правилом для ближайшего рудника:
- Если наше_здоровье <21 и расстояние_до_рудника==0, то answer-=100;
- Иначе если расстояние до шахты ==0, то answer+=990;
- Иначе answer+=49+mod(50, расстояние_до_шахты+1);
- Воспользуемся правилом для ближайшей таверны:
- Если наше_здоровье>80 и расстояние_до_таверны==0, то answer-=100;
- Иначе если наше здоровье >50 или количество_золота<2, то игнор;
- Иначе если расстояние_до_таверны==0, то answer+=100;
- Иначе answer+=mod(mod(200, наше_здоровье), расстояние_до_таверны+1);
- Воспользуемся правилом для каждого врага:
- Если наше_здоровье-здоровье_врага>-19 и количество_рудников>0 и расстояние==1, то answer+=80;
- наше_здоровье-здоровье_врага>-19 и количество_рудников>0 и расстояние==1, то answer+=100;
- Иначе если расстояние<4 и наше_здоровье<45, то answer+= -100+8*расстояние;
- Выбираем точку с наибольшим значением answer, отправляем направление.
Довольно топорно, неоптимизированно, однако для начала пойдет. Это был один из самых первых набросков ИИ для Zaraza 0.1. Попробуйте запустить ИИ, следуя этим инструкциям, и увидите проблеск разума. За тем, как играет ИИ по таким правилам, можно посмотреть здесь, здесь и здесь. Становится понятно, что на больших картах, где нечасто приходится встречаться с врагами, ИИ может потягаться с драчунами, просто избегая встреч, а на средних и маленьких картах, где столкновения неизбежны, этот зачаток интеллекта не может сражаться с другими ИИ. Нужно провести работу по оптимизации движка.
Исследование объектов: рудники
Рассмотрим способы, с помощью которым можно искать рудники на карте:
Способ 1 — идти к самому ближайшему руднику
Плюсы:
+ Самый простой способ.
Минусы:
— Все остальные составляющие этой затеи
Комментарий:
Если стоим на перепутье с одинаковым расстоянием до двух ближайших рудников, можно выбирать любой.
Три боя, выложенные чуть выше, раскрывают всю нежизнеспособность этого способа. Лишние ходы, нелогичные движения, наворачивание кругов — всё пестрит избыточностью.
Способ 2 — добавить веса за хороший выбор
Плюсы:
+Теперь ИИ будет выбирать количественно более приятный способ.
+ Легко реализуется.
Минусы:
— Существует способ и получше.
Комментарий:
Этот способ действительно невероятно хорош. Мы будем искать не самый близкий вариант, а самый хороший в краткосрочной перспективе. Для реализации можно использовать сложение всех весов при формуле, к примеру, 600/(n+1), где n- расстояние до объекта. Это поможет точно дойти до лучшего места при равном расстоянии, а также делает более привлекательными точки с большим количеством рудников. При этом стоит сделать сам рудник, к примеру, с весом 1000 единиц, ибо в противном случае клетка рядом с двумя рудниками будет обладать аналогичной привлекательностью, что и сам рудник (600/1 = 600/2 + 600/2). Средний показатель очков Эло за 100 битв увеличился с 1550 до 1833 только с изменением способа поиска рудников, это говорит о многом.
Способ 3 — какой-то план, которому он следует
Часть карты, где такой способ будет действенным
Алгоритм таков:
- Составляем список всех рудников, которые мы можем завоевать с текущим количеством здоровья (чтобы успешно захватить рудник, нужно обладать минимум 21 единицей здоровья. Очевидно, нас хватит максимум на 4 рудника).
- Мысленно идем до каждого рудника, завоевываем.
- Теперь повторяем пункт 1 и 2, начиная от места завоевания определенного рудника ровно до тех пор, пока у нас не будет список всех возможных сценариев по захвату близлежащих рудников (а у учеток количества здоровья, можно захватить не более четырех рудников), можно построить даже дерево таких комбинаций. Благо, расстояние от каждой точки до рудника у нас есть.
- Можно также посмотреть дальше — оценить расстояние до таверны, ведь она является жизненно необходимой вещью в этом круговороте.
- Выбрать самый вкусный вариант
Плюсы:
+Существенно более хороший способ поиска рудников.
+ Ищет оптимальные «цепи» для поиска рудников.
+ Самый эффективный способ, если бы не существование соперников.
Минусы:
— Может быть несколько ресурсозатратным.
— Не учитывает деятельность врагов.
Комментарий:
У этого способа есть достоинства, которые нельзя не принимать во внимание. Если поработать в этом направлении, то можно достичь значительного успеха, даже уложившись в ресурсы одноплатника. В качестве оценивающей функции можно использовать затраченное количество ходов и количество захваченных рудников или, к примеру, (полученное количество золота)/(потраченное количество ходов). Здесь может быть много интересных идей.
Способ Geektimes
Если есть задумка по поиску рудников, изложите его в комментариях, ибо мне мало что иное в голову приходит.
Но как убедиться, что изменение в движке бота сделало его лучше?
Собрать статистику за 50/100/250 игр!
Определимся с собираемым материалом. Для меня выбор был прост:
— viewUrl — ссылка, по которой можно просмотреть бой
— место, которое мы заняли в бою
— соотношение нашего золота и золота победителя как показатель успешности боя
— текущее количество очков Эло
— выбыли ли мы из игры преждевременно (это может случиться, если были проблемы с интернетом или если мы пересекли лимит в 1 секунду на отправку решения)
— размер карты (который нередко коррелирует с выигрышным местом)
Теперь необходимо выбрать способ сохранения данной информации. Если выбирать из простого, есть два варианта: .scv и Google Forms. Стоит сказать, что GF может быть более удобным вариантом, так как он из-под коробки добавляет временную метку и статистика доступна онлайн. Как заносить ответы в форму можно поискать по запросу «submit google form язык_программирования».
Задача на дом
А пока пользователям Гиктаймса вопрос номер 2:
На скриншоте представлен кусок карты:
Q — наш игрок
S — вражеский спаунпоинт
Программист Окноз решил добавить такое свойство: если у владельца вражеского спаунпоинта опасно малое количество очков здоровья, то спаунтпоинт начинает излучать отталкивающее потенциальное поле, которое не поощряет близкое нахождение возле этого спаунпоинта. Но игрок оказался в ловушке, став отличной добычей для вражеского игрока, как только он возродится. Окноз думает над тем, что же нужно сделать, чтобы таких ситуаций не случалось.
Есть догадки? Одно из возможных решений я напишу в комментариях под спойлером.
Заключение
Вот так, шаг за шагом, можно создать смелого и могучего воина, который скрестит свои мечи с адептами альфа-бета отсечения и минимакса на равных!
В следующей части рассмотрим возможные варианты поведения для таверн, спаунпоинтов, соперников, посмотрим, как складываются поля, что такое блокировка приоритетным полем, рассмотрим, стоит ли закрашивать тупики. И, конечно, пара слов о конкурирующих алгоритмах.
→ Ссылка на Vindinium
→ Ссылка на сабреддит Vindinium — очень полезная вещь, там можно услышать ответы на очень интересные и заковыристые вопросы.
→ Ссылка на мой гитхаб с небольшими старыми наработками по Vindinium
Автор: Раковский Станислав
