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

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


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


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


    image


    Игровой мир Vindinium


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


    Вольный перевод документации игры

    Описание


    Vindinium — многопользовательский пошаговый рогалик. У каждого из четырех игроков есть один герой, который может перемещаться по карте. Цель состоит в том, чтобы игроки собрали максимальное количество золота в течение заданного количества ходов (каждый игрок делает 300 ходов за игру, таким образом, вся игра состоит из 1200 ходов). Игроки должны взять под свой контроль золотые рудники для производства золота; однако рудники защищены гоблинами. Когда игрок побеждает гоблина, он становится владельцем рудника и получает одно золото за ход. Кроме того, гоблин теперь защищает рудник от других игроков.


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


    Наведываясь в таверну, герои могут купить пиво за 2 единицы золота, таким образом восстанавливая свои очки здоровья.


    Цель состоит в том, чтобы создать компьютерную программу (бота), которая играет в игру Vindinium как можно более разумно. Рекомендуется использовать один из стартовых наборов для большого числа языков программирования в качестве отправной точки.


    Карта


    Карты создаются случайным образом. Каждый игровой объект на карте кодируется с использованием двух символов. Пример карты:


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

    Легенда


    ## — Непреодолимый лес
    @1 — Первый герой
    [] — Таверны
    $- — Золотой рудник (ничейный)
    $1 — Золотой рудник (принадлежащий первому герою)


    Сгенерированные карты симметричны и всегда содержат 4 таверны и 4 героя.


    Герой


    Герои могут перемещаться на одну клетку за каждый ход и иметь следующие показатели:


    • Очки здоровья (HP): Каждый "свежий" игрок начинает с максимального значения = 100. Если HP падает до нуля, герой умирает (смотрите раздел "Смерть героя").
    • Золото: начиная с нуля, это показатель успешности героя. В конце игры герои будут оценены на основе их количества золота.
    • Количество золотых рудников.

    Направление движения


    Бот должен отдавать один приказ за ход. Возможные приказы: Стоять на месте (Stay), На север (North), На юг (South), На восток (East) или На запад (West). Как только приказ исполнен, герой остается на своем месте или перемещается на одну клетку в заданном направлении.


    Перемещение героя

    Если герой:


    • Пытается выйти за границы карты или пройти сквозь деревья, ничего не происходит.
    • Заходит в золотой рудник, он остается на месте и:
      • Если рудник уже принадлежит герою, ничего не происходит.
      • Если шахта ничейная или принадлежит другому герою, происходит бой с гоблином-стражем, охраняющим шахту. Герой теряет 20 очков жизни. Если он выживет, шахта его.
    • Наступает на другого героя, он остается на месте и ничего не происходит. Поединки героев решаются в конце хода.
    • Заходит в таверну, он остается на месте и заказывает себе поесть. Герой платит 2 золота и восстанавливает 50 единиц здоровья. Обратите внимание, что количество здоровья не может превышать 100 единиц.
    • Не отправляет приказ за отведенное ему время для принятия решения (1 секунду), он остается на месте до окончания игры, отправлять новые приказы становится невозможно. Обратите внимание, что он все равно может выиграть, если в конце игры у него больше золота, чем у других игроков.

    Конец хода


    После того, как герой переместился (или решил остаться на месте), произойдут следующие вещи:


    Сражения

    Герои немного нервничают и никогда не упускают возможности ударить друг друга большими мечами. В конце хода героя, если есть враг на расстоянии одного квадрата в любом направлении, герой его атакует. Например, в этой ситуации, в конце хода первого героя (@1):


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

    Игрок 1 атакует второго игрока, но не трогает третьего, потому что третий стоит на расстоянии двух клеток от него.
    Нападающий не теряет единиц здоровья, обороняющийся теряет 20 единиц.
    Если обороняющийся умирает (см .: Смерть героя), нападающий получает контроль над всеми золотыми рудниками проигравшего.


    Добыча золота

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


    Жажда

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


    Смерть героя


    Когда здоровье героя падает до нуля, он умирает. Герой немедленно появляется на карте на своей точке возрождения, с полным запасом здоровья (100 единиц). Герой теряет контроль над всеми своими золотыми рудниками, но сохраняет все свое накопленное золото. Будьте осторожны, когда герой возвращается на точку возрождения, любой противник, который находится в этой клетке, автоматически умирает. Таким образом, вам следует избегать пребывания на клетке возрождения одного из героев ...


    Герой не может умереть от жажды. Жажда может оставить героя с одной единицей здоровья, но не убить его.


    Конец игры


    Игра заканчивается, когда достигается максимальное количество ходов(обычно 300). Победителем является герой с наибольшим количеством золота. Если у двух игроков одинаковое количество золота, победителя нет.


    Рейтинг


    Система оценки относительной силы игроков использует Рейтинг Эло. Идея такова: лучше быть первым, чем вторым, лучше быть вторым, чем третьим, и так далее. Надеюсь, принцип понятен.


    Использование нескольких ботов одновременно


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


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


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


    • Если у нас меньше 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


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

    • +13
    • 7,9k
    • 2
    Поделиться публикацией
    Никаких подозрительных скриптов, только релевантные баннеры. Не релевантные? Пиши на: adv@tmtm.ru с темой «Полундра»

    Зачем оно вам?
    Реклама
    Комментарии 2
    • +2
      На харбре это такая фишка вставлять картинки никак не связанные с содержимым статьи?
      • 0

        Грифффииит!

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