Пишем ИИ для Виндиниума на одноплатных компьютерах. Часть 2: логика принятия решения

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

Часть 1.
Часть 3.

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

Игровой мир Vindinium

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

+----------------------------------------+
|######$-    $-############$-    $-######|
|######        ##        ##        ######|
|####[]    ####            ####    []####|
|##      ####  ##        ##  ####      ##|
|####            $-    $-            ####|
|##########  @1            @4  ##########|
|############  ####    ####  ############|
|$-##$-        ############        $-##$-|
|  $-      $-################$-      $-  |
|        ########################        |
|        ########################        |
|  $-      $-################$-      $-  |
|$-##$-        ############        $-##$-|
|############  ####    ####  ############|
|##########  @2            @3  ##########|
|####            $-    $-            ####|
|##      ####  ##        ##  ####      ##|
|####[]    ####            ####    []####|
|######        ##        ##        ######|
|######$-    $-############$-    $-######|
+----------------------------------------+

########
##@1@2##
##  @3##
########

Ссылка на оригинал

Стоит отметить еще пару аспектов, которые не были описаны в правилах, но выявлены опытным путем:

• Если у нас меньше 21 единицы здоровья, но нападаешь на рудник, не принадлежащий тебе, то ты умираешь. Да-да, защиты от дурака нет, тут всё серьезно, как в самых настоящих сражениях. Если ты напал на ничейный рудник, все твои рудники становятся ничейными, а если на рудник одного из врагов, то твои рудники переходят в руки игрока, которому принадлежит этот рудник.
• Игра описывает такой порядок действий: Исполнение приказа — Бьем ближайших врагов — Теряем 1 единицу здоровья от жажды. А что случится, если в ходе исполнения приказа мы умрем (в игре можно это сделать, только умерев в сражении с гоблином)? Мы возрождаемся (и мгновенно убиваем игрока, который стоит сейчас на нашем спаунпоинте), но теряем возможность ударить ближайших врагов, а также не теряем 1 единицу здоровья вследствие жажды.
• Убив во время своего возрождения противника, стоящего на нашем спаунпоинте, мы захватываем его рудники, хе-хе.
• Карта имеет квадратный вид, длина карты принимает четные значения на отрезке [8, 28].

"Учитесь у своих врагов и вы поймете их сильные стороны"

Виндиниум — публичная игра, ее полезной стороной является то, что мы можем заглянуть в профиль любому игроку и посмотреть последние сто боев с его участием. "Отлично! Самое время использовать нейронные сети, ведь у нас есть 50 топ-игроков, возьмем из них 10 самых сильных, в каждом из 100 последних боев содержится ~300 моментов, когда игрок должен был принимать решение, итого около 200-300 тысяч единиц материала для обучения! А еще можно каждую ситуацию вращать по часовой стрелке, отзеркаливать, etc, чтобы получить еще больше материала для обучения и закрепить результат, это даст нам аж целых 4.8-7.2 миллионов единиц материала" — раздался голос разума. Да, действительно, такая идея имеет право на существование. К тому же, у нейронных сетей есть много достоинств.

• Весь материал для обучения легко парсится из открытого источника.
• Раскрывается широкий простор для размышления над компьютерным зрением:
  
  • Можно оставить всё как есть, будет 28*28 входных нейронов (если карта меньше — заполняем деревьями);
  • Можно центрировать каждый раз по положению героя (возможно принесет какой-либо удивительный результат);
  • Можно представить карту в виде графа, таким образом сильно облегчается работа нейронной сети по нахождению закономерностей; Этот вариант позволит нейронке быстро находить паттерны сложнейшего поведения и быстро понимать, почему, если у нас мало здоровья, мы идем к дальней таверне, если всего в паре клеток от нас есть другая таверна, пусть и впритык к ней стоит противник;
• Уже обученную нейронную сеть, если заранее задаться задачей потребления ресурсов, можно компактно разместить в 512 мегабайтах отведенных нам оперативной памяти (на самом деле получается около 480 мегабайт), да так, что мощности одноплатного компьютера хватит сполна для расчетов.

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

Итак. Деревья решений, альфа-бета отсечение, минимаксы… слишком ресурсоёмкие задачи! На сабреддите виндиниума несколько разработчиков, раскрывая завесу тайны своих ботов, уже использовали это решение, и наверняка не в таких спартанских условиях. К сожалению, в этой сфере вряд ли удастся что-либо сделать лучше, чем у остальных.

Начитавшись статей про эволюционные, генетические алгоритмы, решающие деревья, я откопал тайное знание — потенциальные поля. Подробнее о них можно почитать здесь и здесь. Данная идея показалась очень даже рабочей, ведь потенциальное поле — планарный граф, в каждое звено помещается функция, которая зависит от входных данных (в частности — расстояния от объекта, но никто не мешает сделать больше условий). Всё это прекрасно ложится в реалии виндиниума — тебе не нужно искать путь до объекта, если это уже заложено в алгоритме.

"Довольно специфичные вкусы"

Давайте понаблюдаем за боями топовых персонажей. Перед началом выберем фаворита, будем следить за ним, болеть за него, журить за неправильные решения в стиле "а вот я бы так поступил на этом месте...". Спустя десяток боев уже можно сделать первый набросок, что такое законопослушный ИИ (условия проверяются по порядку):

1. Не стоит ходить возле спаунпоинта врага, если у врага есть шанс умереть (т.е. если у нас может ждать бесславная смерть, стоя на спаунпоинте врага);
2. Глупо сражаться со своим врагом возле его спаунпоинта, ибо он всё равно аки феникс ясный возродится с полным запасом здоровья и снова попытается захватить наши честно награбленные рудники;
3. Если враг стоит вплотную к нам, а мы стоим возле таверны — время пьянствовать. Судя по многочисленным кровавым боям возле средства пропитания и релаксации, данное правило очень даже актуально;
4. Если мы не можем победить врага/врагов, но мы успеваем добежать до таверны — бежим;
5. Если мы не можем победить врага/врагов И не успеваем дойти до таверны, то:
   
   • Если мы можем самоубиться об ничейную ферму — убиваемся об нее. Выкуси!
   • Если мы можем умереть об майнилку человека с самым низким количеством золота — самовыпиливаемся об нее;
   • Если же нас ждет печальный конец, то мы нужно отнять у этого гада как можно больше здоровья, пусть долго будет помнить о своей ошибке!
6. Если есть враг, которого мы можем убить в пределах двух наших ходов и у него есть майнилки — атакуем;
7. Если есть враг, удаленный от всех майнилок больше, чем мы, и у него под контроллем 33% майнилок И мы можем его победить — идем побеждать, иначе идем пить пиво;
8. Захватываем фермы, если ничего другого не остается.

Вопрос-ответ:

• В чем его преимущества по сравнению с нейронными сетями, которые в сто крат лучше справятся с этой задачей, или деревьями, что знают все твои n следующих ходов наперед и уже разработали контрмеры, остается только функцию оценки хорошую применить?

• (1) Многофункциональность. Проще изменять параметры, добавлять новые функции. Следишь такой за своим персонажем, радуешься, а тут бац — и видишь, что в определенный момент можно было поступить совсем иначе, более благоразумно, — пишем новое правило или изменяем старое. (2) Также мы знаем точно, каким решением руководствовалась программа во время выбора определенного хода. (3) Потенциальные поля хорошо себя показали в рогаликах как основа для искусственного интеллекта ботов.

  
  
• Докажи, что твой подход действеннен, что твои намерения чего-то стоят.

• В лидерборде на 27 месте висит Zaraza 0.1 — ИИ на потенциальных полях, который руководствуется всего лишь тремя инстинктами — бездумно захватывать всё, что попадется на своем пути, не просыхать в барах и осторожно вести себя с врагами. Если последите за его движениями, то увидите, как хорошо он воюет, хотя это просто невероятно для ИИ, которое базируется на трех простых правилах и ему даже в снах не привидится какое-либо сложное поведение. Более того, сейчас я работаю над Zonko 0.11, которая является сильно улучшенной версией выпивохи Zaraz'ы, в нее можно встроить намного более сложное поведение за счет улучшенного взаимодействия с полями — прямо как в новомодном GPS. Но, как оказалось, она прожорливо относится к ресурсам, поэтому сейчас происходит процесс ее оптимизации… Но это я отвлекся, сейчас мы говорим о строгих ограничениях, строгих правилах строгих (...).

  
  
• Твои убеждения смехотворны, твоя вера слишком слаба! Я могу создать ИИ на название_метода, и он порвет тебя!
• Очень будет приятно послушать размышления других людей на эту тему. Более того, для тебя я уже сложил все бои топ-10 игроков, всего 1000 боев и порядка 1.000.000 ходов — ссылка (.zip — 33MB, RAW — 1.68GB). Предлагаю условия игры:
  
  • Регистрировать ботов под своими никнеймами в geektimes.
  • Пяти игрокам, набравшим наибольшее количество очков до 30 сентября, чем я или кто-либо другой среди изъявивших играть, я отправлю открытку из Москвы).

Итак, а теперь язык программирования… Лично я сейчас мечусь между 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 преобразовать в ссылку вида http://vindinium.org/events/fd96vc2z. Но не советую мучить сервер игры, пытаясь достать сотни боев топовых игроков, воспользуйтесь ссылкой выше.

Extra 2: Если кто-то хочет попробовать свою наработку в Виндиниум загнать в ограничения NanoPi Neo2 или Orange Pi Zero, я могу предоставить возможность поработать с данными одноплатными компьютерами.

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

В следующей части будем настраивать потенциальные поля, работать с потенциальными картами, писать условия и накладывать всё это на современные реалии.