Пишем ИИ для Виндиниума на одноплатных компьютерах. Часть 3: от теории к практике. Эффективно охотимся за рудниками в ПП

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

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

Но перед этим немного о возвышенном: janvarev ^[1] запустил очень удобный лидерборд ^[2], по которому можно отследить свой рейтинг среди игроков, которые играли в течение десяти дней. Присоединяйся и ты! Первые пять пользователей Гиктаймса, которые 30 сентября в лидерборде займут место выше, чем Zonko 0.11, получат золото открытку из Москвы! Я бедный студент, живу на стипендию Единственное условие — никнейм бота должен совпадать с никнеймом в Гиктаймсе (или хотя бы очень походить).

→ Часть 1 ^[3]
→ Часть 2 ^[4]

Потенциальные поля...

Для начала необходимо понять, что такое потенциальные поля (ПП), для этого нам нужны эта ^[5] и эта ^[6] статьи.

В целом, ПП можно представить как карту распространения сигнала от объекта на все клетки поля, огибая преграды. Вот, к примеру, распространение поля возле игрока R (id=4), чем темнее, тем слабее поле.

Существуют реализации с использованием псевдокода ^[7], что позволяет работать над ПП с большинством языков программирования.

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

Теперь посмотрим на эту задачу полноценно:

1. Получаем от сервера информацию о состоянии игры;
2. Добываем координаты таверн, игроков, рудников — значимых игровых объектов;
3. Считаем потенциальное поле всех игровых объектов, складываем в общий словарь вида: Координата поля - id объекта - значение поля;
4. Используя магию, получаем решение, в какую сторону пойдем в этот раз.

Теперь будем работать по пунктам:

1. Информация о состоянии игры

Тут говорить, честно говоря, не о чем. На официальном сайте доступны наборы для быстрого старта на 28 языках программирования. К слову, очень легко обойтись и без них, ведь там всего-лишь POST-запросы и работа с json. Для python существуют модули requests и json, которые сделают всю грязную работу сами. Во второй части был приведен код, который работает с ответами сервера.

2. Добываем координаты игровых объектов

Здесь нужно сказать пару слов:

1. Координаты всех четырех игроков доступны в game - heroes - hero_id - pos;
2. Таверны и спаунпоинты — единственные неизменные объекты на карте. Они не перемещаются, не переходят из одних рук в другие. Их расположение можно запомнить раз и навсегда;
3. Координаты рудников придется доставать из карты каждый раз, ибо они имеют свойство менять своего хозяина;
4. Затем всё это упаковываем в один словарь «название — координата», при этом рудники и таверны следует пронумеровать.

3. Просчитать потенциальные поля

Выше я сказал, что для реализации потенциального поля на своем ЯП нет преград. Лично мне понравилось очень лаконичное и быстрое решение отсюда ^[8], стоит только часть функции 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. Магия

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

Довольно топорно, неоптимизированно, однако для начала пойдет. Это был один из самых первых набросков ИИ для Zaraza 0.1. Попробуйте запустить ИИ, следуя этим инструкциям, и увидите проблеск разума. За тем, как играет ИИ по таким правилам, можно посмотреть здесь ^[9], здесь ^[10] и здесь ^[11]. Становится понятно, что на больших картах, где нечасто приходится встречаться с врагами, ИИ может потягаться с драчунами, просто избегая встреч, а на средних и маленьких картах, где столкновения неизбежны, этот зачаток интеллекта не может сражаться с другими ИИ. Нужно провести работу по оптимизации движка.

Исследование объектов: рудники

Рассмотрим способы, с помощью которым можно искать рудники на карте:

Способ 1 — идти к самому ближайшему руднику

Плюсы:
+ Самый простой способ.

Минусы:
— Все остальные составляющие этой затеи

Комментарий:
Если стоим на перепутье с одинаковым расстоянием до двух ближайших рудников, можно выбирать любой.

Три боя, выложенные чуть выше, раскрывают всю нежизнеспособность этого способа. Лишние ходы, нелогичные движения, наворачивание кругов — всё пестрит избыточностью.

Способ 2 — добавить веса за хороший выбор

Плюсы:
+Теперь ИИ будет выбирать количественно более приятный способ.
+ Легко реализуется.

Минусы:
— Существует способ и получше.

Комментарий:
Этот способ действительно невероятно хорош. Мы будем искать не самый близкий вариант, а самый хороший в краткосрочной перспективе. Для реализации можно использовать сложение всех весов при формуле, к примеру, 600/(n+1), где n- расстояние до объекта. Это поможет точно дойти до лучшего места при равном расстоянии, а также делает более привлекательными точки с большим количеством рудников. При этом стоит сделать сам рудник, к примеру, с весом 1000 единиц, ибо в противном случае клетка рядом с двумя рудниками будет обладать аналогичной привлекательностью, что и сам рудник (600/1 = 600/2 + 600/2). Средний показатель очков Эло за 100 битв увеличился с 1550 до 1833 только с изменением способа поиска рудников, это говорит о многом.

Способ 3 — какой-то план, которому он следует

Часть карты, где такой способ будет действенным

Алгоритм таков:

1. Составляем список всех рудников, которые мы можем завоевать с текущим количеством здоровья (чтобы успешно захватить рудник, нужно обладать минимум 21 единицей здоровья. Очевидно, нас хватит максимум на 4 рудника).
2. Мысленно идем до каждого рудника, завоевываем.
3. Теперь повторяем пункт 1 и 2, начиная от места завоевания определенного рудника ровно до тех пор, пока у нас не будет список всех возможных сценариев по захвату близлежащих рудников (а у учеток количества здоровья, можно захватить не более четырех рудников), можно построить даже дерево таких комбинаций. Благо, расстояние от каждой точки до рудника у нас есть.
4. Можно также посмотреть дальше — оценить расстояние до таверны, ведь она является жизненно необходимой вещью в этом круговороте.
5. Выбрать самый вкусный вариант

Плюсы:

+Существенно более хороший способ поиска рудников.
+ Ищет оптимальные «цепи» для поиска рудников.
+ Самый эффективный способ, если бы не существование соперников.

Минусы:
— Может быть несколько ресурсозатратным.
— Не учитывает деятельность врагов.

Комментарий:
У этого способа есть достоинства, которые нельзя не принимать во внимание. Если поработать в этом направлении, то можно достичь значительного успеха, даже уложившись в ресурсы одноплатника. В качестве оценивающей функции можно использовать затраченное количество ходов и количество захваченных рудников или, к примеру, (полученное количество золота)/(потраченное количество ходов). Здесь может быть много интересных идей.

Способ Geektimes

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

Но как убедиться, что изменение в движке бота сделало его лучше?

Собрать статистику за 50/100/250 игр!

Определимся с собираемым материалом. Для меня выбор был прост:

— viewUrl — ссылка, по которой можно просмотреть бой
— место, которое мы заняли в бою
— соотношение нашего золота и золота победителя как показатель успешности боя
— текущее количество очков Эло
— выбыли ли мы из игры преждевременно (это может случиться, если были проблемы с интернетом или если мы пересекли лимит в 1 секунду на отправку решения)
— размер карты (который нередко коррелирует с выигрышным местом)

Теперь необходимо выбрать способ сохранения данной информации. Если выбирать из простого, есть два варианта: .scv ^[12] и Google Forms. Стоит сказать, что GF может быть более удобным вариантом, так как он из-под коробки добавляет временную метку и статистика доступна онлайн. Как заносить ответы в форму можно поискать по запросу «submit google form язык_программирования».

Задача на дом

А пока пользователям Гиктаймса вопрос номер 2:

На скриншоте представлен кусок карты:
Q — наш игрок
S — вражеский спаунпоинт

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

Заключение

Вот так, шаг за шагом, можно создать смелого и могучего воина, который скрестит свои мечи с адептами альфа-бета отсечения и минимакса на равных!

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

→ Ссылка на Vindinium ^[13]
→ Ссылка на сабреддит Vindinium ^[14] — очень полезная вещь, там можно услышать ответы на очень интересные и заковыристые вопросы.
→ Ссылка на мой гитхаб с небольшими старыми наработками по Vindinium ^[15]

Автор: Раковский Станислав

Источник ^[16]