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

Начнём с малого: допустим, мы создаем NPC, которые умеют собирать предметы по заданным правилам.  Наша цель: создать «крафтовый» интеллект, т.е. такой интеллект, который выбирает, что будет делать NPC из предметов в его инвентаре. Такую штуку можно попробовать реализовать с помощью конченных конечных автоматов, поведенческих деревьев (behaviour tree) или ещё как-нибудь. Но, когда рецептов много, ингредиенты пересекаются, а потребности NPC меняются, такое дерево очень быстро разрастется до трудноподдерживаемого состояния. А если у нас вдруг что-то поменялось в технологической схеме?

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

Крафтовая система

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

ITEMS = {
    'stone': {'stack': True, 'material': 'stone', 'nmat': 2, 'type': {'raw', 'hammer'}, 'cost': 0.0},
    'flint': {'stack': True, 'material': 'stone', 'nmat': 1, 'type': {'raw', 'cutter'}, 'cost': 0.0},
    'piece of leather': {'stack': True, 'material': 'leather', 'nmat': 2, 'type': {'raw'}, 'cost': 0.0},
    'vein': {'stack': True, 'material': 'leather', 'nmat': 1, 'type': {'rope'}, 'cost': 0.0 },
    'bones': {'stack': True, 'material': 'bone', 'nmat': 2, 'type': {'raw'}, 'cost': 0.0 },
    'piece of metal': {'stack': True, 'material': 'metal', 'nmat': 2, 'type': {'raw'}, 'cost': 0.0},
    'vegs': {'stack': True, 'material': 'fiber', 'nmat': 1, 'type': {'raw'}, 'cost': 0.0},
    'wooden stick': {'stack': False, 'material': 'wood', 'nmat': 2, 'type': {'raw', 'handle'}, 'cost': 0.0},
    'rope': {'stack': True, 'material': 'fiber', 'nmat': 1, 'type': {'rope'}, 'cost': 0.0 },
    'stone hammer': {'stack': False, 'material': 'stone', 'nmat': 2, 'type': {'hammer', 'weapon'}, 'cost': 2.0},
    'bone awl': {'stack': False, 'material': 'bone', 'nmat': 2, 'type': {'awl'}, 'cost': 0.0 },
    'bone knife': {'stack': False, 'material': 'bone', 'nmat': 2, 'type': {'cutter'}, 'cost': 0.0 },
    'bone spear': {'stack': False, 'material': 'bone', 'nmat': 2, 'type': {'weapon'}, 'cost': 2.0},
    'metal knife': {'stack': False, 'material': 'metal', 'nmat': 2, 'type': {'weapon', 'cutter'}, 'cost': 0.0},
    'leather ribbon': {'stack': True, 'material': 'leather', 'nmat': 1, 'type': {'rope', 'raw'}, 'cost': 0.0},
    'metal spear': {'stack': False, 'material': 'metal', 'nmat': 2, 'type': {'weapon'}, 'cost': 2.0},
    'stone axe': {'stack': False, 'material': 'stone', 'nmat': 2, 'type': {'weapon'}, 'cost': 2.0},
    'skin': {'stack': False, 'material': 'leather', 'nmat': 2, 'type': {'armor'}, 'cost': 4.0},
    'fibers': {'stack': True, 'material': 'fiber', 'nmat': 2, 'type': {'raw'}, 'cost': 0.0 },
    'bone necklace': {'stack': False, 'material': 'bone', 'nmat': 2, 'type': {'jewelry'}, 'cost': 2.0},
    'sling': {'stack': False, 'material': 'leather', 'nmat': 2, 'type': {'weapon'}, 'cost': 2.0},
    'wooden club': {'stack': False, 'material': 'wood', 'nmat': 2, 'type': {'weapon'}, 'cost': 0.0},
    'bone mace': {'stack': False, 'material': 'bone', 'nmat': 2, 'type': {'weapon'}, 'cost': 4.0},
    'leather shield': {'stack': False, 'material': 'leather', 'nmat': 2, 'type': {'armor'}, 'cost': 6.0},
    'metal mace': {'stack': False, 'material': 'metal', 'nmat': 2, 'type': {'weapon'}, 'cost': 5.0},
}

Код привожу на питоне, для таких вспомогательных утилит он оптимален. Удобно проверять наличие элемента в множестве, работать со строковыми индексами, при желании можно подключать фреймворки машинного обучения вроде Pytorch. В самом проекте на C++, естественно, никаких строк, все обращения к свойствам предметов или рецептов по их индексу.

Кроме предметов, есть рецепты. В рецепте указано, какой предмет получается, нужен ли инструмент (инструменты пересекаются с типами предметов) и какие нужны ингредиенты. Ингредиенты могут быть заданы по идентификатору (нужен конкретный предмет), по материалу (нужен определенный материал) и по типу (нужен определенный тип). Предмет в качестве материала можно использовать только если у него в типах есть ‘raw’ (сокращение от raw material – сырьё). Это единственный захардкоденный идентификатор, остальные типы, материалы и предметы могут называться произвольным образом.

RECIPES = [
    {'result': 'rope', 'tool1': {}, 'ingrs': [['id', 'fibers', 3]]},
    {'result': 'stone hammer', 'tool1': {}, 'ingrs': [['type', 'rope', 1], ['type', 'handle', 1], ['id', 'stone', 1]]},
    {'result': 'bone awl', 'tool1': {'cutter'}, 'ingrs': [['material', 'bone', 2]]},
    {'result': 'bone knife', 'tool1': {'hammer'}, 'ingrs': [['material', 'bone', 3]]},
    {'result': 'bone spear', 'tool1': {}, 'ingrs': [['type', 'rope', 1], ['type', 'handle', 1], ['id', 'bone awl', 1]]},
    {'result': 'metal knife', 'tool1': {'hammer'}, 'ingrs': [['material', 'metal', 2]]},
    {'result': 'leather ribbon', 'tool1': {'cutter'}, 'ingrs': [['material', 'leather', 2]]},
    {'result': 'metal spear', 'tool1': {}, 'ingrs': [['type', 'rope', 1], ['type', 'handle', 1], ['id', 'metal knife', 1]]},
    {'result': 'stone axe', 'tool1': {}, 'ingrs': [['type', 'rope', 1], ['type', 'handle', 1], ['id', 'flint', 1]]},
    {'result': 'skin', 'tool1': {'awl'}, 'ingrs': [['type', 'rope', 1], ['material', 'leather', 3]]},
    {'result': 'fibers', 'tool1': {'hammer'}, 'ingrs': [['id', 'vegs', 1]]},
    {'result': 'bone necklace', 'tool1': {}, 'ingrs': [['type', 'rope', 1], ['id', 'bone knife', 3]]},
    {'result': 'sling', 'tool1': {'awl'}, 'ingrs': [['type', 'rope', 1], ['material', 'leather', 2]]},
    {'result': 'wooden club', 'tool1': {'cutter'}, 'ingrs': [['id', 'wooden stick', 1]]},
    {'result': 'bone mace', 'tool1': {}, 'ingrs': [['id', 'wooden club', 1], ['id', 'bone knife', 2]]},
    {'result': 'leather shield', 'tool1': {'awl'}, 'ingrs': [['type', 'handle', 4], ['material', 'leather', 4]]},
    {'result': 'metal mace', 'tool1': {'hammer'}, 'ingrs': [['id', 'wooden club', 1], ['material', 'metal', 2]]},
]

Например, для каменного молота нужна одна веревка (любой предмет с ‘rope’ in type), одна рукоятка (любой предмет с ‘handle’ in type) и один камень (тут прямо именно камень, никаких вариантов). Обратите внимание, что рецепты – это список, а не словарь. Т.е. в принципе, может быть, сколько угодно рецептов, дающих один и тот же предмет. Если представить это в виде диаграммы получится следующая картинка:

Как вам? Хотите написать алгоритм под такую задачу? В данном примере граф сильно связанный: многие рецепты требуют веревку, а к этому типу относятся аж 3 предмета: веревка, жилы и кожаная лента. Привожу также саму функцию крафта craft_dict, которая находит индексы предметов в инвентаре (список/массив), которые будут использованы для крафта, и возвращает их, вместе с общим результатом (нет инструментов / нет ингредиентов / нет места / нет чего-либо / успех). Функция жадная, не ищет оптимальный вариант, а просто первый попавшийся. Для работы требует вспомогательную функцию for_craft, которая возвращает какое количество ингредиентов для рецепта данный предмет может дать:

# determine is this item (name, amount) can be used for craft? Return availiable number (in units of crafted items)
# comp is component of recipe: [type(id/material/type), name, number]
def for_craft(name: str, amount: int, comp: list):
    global ITEMS
    item = ITEMS[name]
    if comp[0] == 'id':
        if name == comp[1]:       
            return min(amount, comp[2])         # how much but not more than needed
        else:
            return 0

    elif comp[0] == 'material':
        if 'raw' in item['type'] and comp[1] == item['material']:     #  only for raw materials
            nmat = amount * item['nmat']   # availiable number of material
            return min(nmat, comp[2])
        else:
            return 0

    elif comp[0] == 'type':
        if comp[1] in item['type']:      
            return min(amount, comp[2])
        else:
            return 0

# verify posibility of craft by recipe index and determine items in invenory used for craft.
# greedy strategy, use the first suitable variant
# inventory is a list of [id, amount]
# RETURN result: 'no some', 'no tools', 'no room', 'no ingr' or 'success' and dictionary {index_in_inventory: used_number}
# in the case 'no ingr' also return a list of missed ingridients
def craft_dict(inv: list, recipe: int):
    global ITEMS, RECIPES, MAX_INV
    rec = RECIPES[recipe]
    l = len(inv)        # number of items in inventory

    # fast verification of impossibility
    if l < (len(rec['ingrs']) + (1 if rec['tool1'] else 0)):
        return 'no some', None        # no tool or no ingredients, we don't know exactly

    # 1: verify tools presence (if needed), greedy stategy, determine index of tool in inventory
    tool_ind = -1
    if rec['tool1']:
        for i in range(l):
            if rec['tool1'].issubset(ITEMS[inv[i][0]]['type']):
                tool_ind = i
                break
        if tool_ind == -1:
            return 'no tools', None

    # 2 looking for ingredients, skipping the index of tool
    ni = len(rec['ingrs'])      # number of ingredients
    mask = [True] * ni          # mask that we still search this component of the recipe
    needs = [comp[2] for comp in rec['ingrs']]      # list of needed components amount
    amounts = {}                # dictionary of amounts that we need to spend for each index
    i = 0
    while i < l and any(mask):
        if i != tool_ind:
            for j in range(ni):
                if mask[j]:
                    n = for_craft(inv[i][0], inv[i][1], rec['ingrs'][j])
                    if n:
                        dec = min(n, needs[j])      
                        needs[j] = needs[j] - dec
                        if not needs[j]:
                            mask[j] = False
                        if rec['ingrs'][j][0] == 'material':
                            amounts[i] = math.ceil(dec / ITEMS[inv[i][0]]['nmat'])
                        else:
                            amounts[i] = dec
                        break       # no need to verify another components
        i += 1

    if any(mask):       # loop is finished, but not all igridients are found:
        shortage = [ingr  for i, ingr in enumerate(rec['ingrs']) if mask[i]]
        return 'no ingr', shortage

    # verify room (only if inventory is full)
    if l == MAX_INV:
        no_room = True
        for k,v in amounts.items():
            if inv[k][1] == v:      # we will spend all these items and clear place for craft
                no_room = False
                break
        if no_room:
            return 'no room', None

    return 'success', amounts  # {index: number}

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

Реализация

Чтобы это реализовать будем оперировать не инвентарем и предметами, а их эмбеддингами. Эмбеддинги или скрытое представление – это такой тензор (обычно одномерный, т.е. вектор), который шифрует некую сущность. Пускай у нас будет эмбеддинг всего инвентаря и эмбеддинги предметов. И есть некая нейронная сеть, которая обновляет эмбеддинг инвентаря, всякий раз, когда мы добавляем и удаляем оттуда предмет. Так как эти события происходят не слишком часто, мы несколько снижаем вычислительную нагрузку. Да, тогда получается, что NPC должен кроме инвентаря хранить где-то его эмбеддинг, но это не такая уж большая плата за результат. Это обновление должно быть основано на каких-то очень простых правилах: сложениях/умножениях, чтобы выполнятся быстро.

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

Иногда у нас есть неприятная ситуация, когда разный предмет в одном рецепте может выполнять разные функции (подходить и по типу, и по айдишнику, например). Зачастую в этих ситуациях нейроночка считает, что сделать предмет можно, а на самом деле не хватает ингредиентов. Если не предоставить никакой обратной связи, то можно получить замкнутый цикл. NPC будет раз за разом пытаться сделать предмет, который нейронка советует сделать. Для решения этой проблемы я ещё ввел «эмбеддинг дефицита», который может блокировать рецепты. Он обновляется, когда функция крафта вернула «нет ингредиента» и снимается при добавлении некоторых предметов в инвентарь.

А что же оптимизировать?

Можно формально разделить нейронку на две части: первая отвечает на вопрос «какой из рецептов можно сделать?», а вторая – «какой нужно сделать?». Первую часть можно рассматривать как врожденное знание, незачем это оптимизировать в ходе игры, можно обучить этому нейронную сеть заранее и зафиксировать. Мы ведь не хотим, чтобы NPC сто лет пытался собрать самолёт из каменных топоров в духе reinforcement learning. А вот вторую часть можно сделать динамичной, зависящей от желаний NPC. Сейчас он хочет сделать одно, завтра – другое, в зависимости от текущих потребностей. Для этого предусмотрен режим «целевой предмет», в котором минимизируется количество операций, необходимых для крафта желаемого предмета.

Эксперимент

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

SOURCES = {'stone', 'flint', 'piece of leather', 'vein', 'bones', 'piece of metal', 'vegs', 'wooden stick'}

Какие мы можем посмотреть метрики? Failed Craft Rate: доля проваленных попыток крафта (ИИ пытается сделать предмет, но это невозможно). Craft Rate: отношение успешных попыток крафта к общему числу действий – показывает, насколько часто нейронка выбирает действие крафта.

Результаты

Привожу статистику решений для режима «целевой предмет». Делал 10 прогонов, каждый по 100 ходов, результаты усреднил. Failed Craft Rate равен 0 во всех случаях.

Привожу так же статистику созданных предметов для одного из прогонов в каждом случае:

{'fibers': 3, 'metal knife': 1, 'bone awl': 1, 'leather shield': 3}
{'metal knife': 1, 'wooden club': 9, 'fibers': 3, 'metal mace': 8}

Согласно рецептам, для создания кожаного щита нужно шило, вот NPC его и создает, а металлическая булава получается из дубинки. При этом NPC зачем-то создает волокна и металлический нож в ряде случаев. Но в целом я доволен результатом – ни разу нейронка не предложила сделать что-то, что невозможно сделать при данном инвентаре.

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

Достаточно лишь поменять объявление предметов и рецептов в скрипте, чтобы всё работало. Естественно, что это объявление можно вынести, например, в экселевский файл и заставить скрипт парсить его. Тогда можно будет вообще не прикасаться к коду.

Для простоты пускай на полу лежит только предмет А, задаём целевой предмет H и, вуаля, за 100 ходов NPC наштамповал: {'B': 18, 'E': 17, 'F': 17, 'G': 8, 'H': 4}; доля крафта - 64%; доля фэйлов – 0. Напомню, что целевой предмет можно задать динамически, делая поведение NPC более хитрым и непредсказуемым. А ещё можно разным NPC задать разные целевые предметы и предложить им обмениваться ими. Простор для фантазии огромен.

Итог и дальнейшие планы

Как видим, нейросетевой ИИ справляется с выбором рецепта крафта в конкретной ситуации. Он не предлагает делать то, что невозможно сделать и целенаправленно крафтит то, что задано.

Мне же не надо писать бесконечный набор правил if…then, и нет нужды переписывать все эти правила, если что-то поменялось в технологической схеме.

К сожалению, пока я не внедрил эту разработку в свой проект. Дело в том, что у меня технологическое дерево состоит не только из крафта. Например, металл можно получить из руды только в обжиговых печах, которые нужно строить. Сейчас NPC их строят и умеют ими пользоваться, но это реализовано традиционными алгоритмами. Планирую в скором времени сделать эмбеддинги построек и как-то подружить их с эмбеддингами предметов, чтобы нейросетевой интеллект мог принимать решения по всему технологическому процессу.

В идеале хочется сделать, чтобы NPCразвивался в буквальном смысле – постепенно учился какому-то сложному поведению, а не чисто формально увеличивал свои статы и открывал умения по достижению нужных циферок.