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

в 11:53, , рубрики: diy или сделай сам, Raspberry Pi, vindinium, игры, искусственный интеллект, одноплатный компьютер

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

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

image

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

Часть 1
Часть 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как конечный этап выглядит у меня:

{'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+ объектами, приходится параллелить).

Многопроцессность для питона

Использую модуль concurrent.futures, очень поманила простота работы с процессами и потоками.
Как разбиваю задачу:

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. Магия

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

Стартовый набор для сборки не самого умного ИИ

Для того, чтобы проверить, что мы до сих пор делаем всё правильно, предлагаю такую простую, но не лишенную изъянов, схему:

  1. Возьмем пять точек от нашего объекта: (x,y) — Stay, (x-1, y) — North, (x+1, y) — South, (x, y-1) — West, (x, y+1) — East. Исключим те точки, которые упираются в барьеры ("##").
  2. Для каждой из оставшихся точек:
    • Найдем значение сигнала от ближайшей таверны, ближайшего не нашего рудника(=наименьшее значение сигнала по выбранным категориям);
    • Возьмем 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*расстояние;

  3. Выбираем точку с наибольшим значением answer, отправляем направление.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Плюсы:

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

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

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

Способ Geektimes

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

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

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

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

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

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

Задача на дом

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

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

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

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

Заключение

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

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

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

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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js