Я пытаюсь реализовать алгоритм MCTS для ИИ небольшой игры. Игра представляет собой rpg-симулятор. ИИ должен решать, какие ходы играть в бою. Это пошаговая битва (стиль FF6-7). Движение не задействовано.
Я не буду вдаваться в подробности, но мы можем с уверенностью предположить, что мы точно знаем, какой ход выберет игрок в той или иной ситуации, когда наступит его очередь играть.
Игры заканчиваются, когда у одной из сторон нет живых юнитов (4 на 4). Это может занять любое количество ходов (также может никогда не заканчиваться). В вычислении урона и обработке умений много элемента ГСЧ (атаки могут попасть/промахнуться, нанести критический удар или нет, происходит множество проков, которые могут «срабатывать» или нет, баффы могут иметь процентное значение, чтобы произойти и т. д. ..). У юнитов есть около 6 навыков, чтобы дать представление о факторе ветвления.
Я создал предварительную версию MCTS, которая пока дает плохие результаты. У меня проблемы с несколькими вещами:
Одна из моих главных проблем заключается в том, как справляться с недетерминированными состояниями моих ходов. Я прочитал несколько статей об этом, но я все еще в темноте.
Некоторые предлагают определить информацию об игре и запустить для нее дерево MCTS, повторить процесс N раз, чтобы охватить широкий диапазон возможных состояний игры, и использовать эту информацию для принятия окончательного решения. В конце концов, время вычислений умножается на огромный коэффициент, поскольку нам приходится вычислять дерево MCTS N раз вместо одного. Я не могу полагаться на это, так как в ходе боя у меня есть тысячи элементов ГСЧ: дерево 2 ^ 1000 MCTS для вычисления, где я уже борюсь с одним, не вариант :)
У меня была идея добавить X детей для одного и того же хода, но, похоже, это тоже не приводит к хорошему ответу. Он немного сглаживает кривую ГСЧ, но может сдвигать ее в противоположном направлении, если значение X слишком велико или мало по сравнению с процентным соотношением конкретного ГСЧ. И поскольку я получил несколько ходов RNG par (изменение удара, шанс критического удара, процент срабатывания чего-либо и т. д.), я не могу найти приличное значение X, которое удовлетворяло бы всем случаям. Скорее плохая повязка, чем что-либо еще.
Аналогичным образом добавление 1 узла на кортеж RNG {попадание или промах, крит или нет, proc1 или нет, proc2 или нет и т. д.} для каждого хода должно охватывать все возможные ситуации, но имеет некоторые серьезные недостатки: только с 5 механизмами RNG это означает 2 ^ 5 узлов для рассмотрения для каждого хода, это слишком много для вычислений. Если нам удастся создать их все, мы можем присвоить им вероятность (связанную с вероятностью каждого элемента ГСЧ в кортеже узла) и использовать эту вероятность на этапе выбора. Это должно работать в целом, но очень тяжело для процессора :/
Я также не могу «объединить» их в один узел, так как у меня нет возможности точно усреднить значение статистики игрока/монстров на основе двух разных состояний игры, а усреднение результата хода во время самой обработки хода выполнимо, но требует много времени. упрощение, которое очень сложно кодировать и в любом случае очень быстро повредит нашей точности.
Есть ли у вас идеи, как подойти к этой проблеме?
Некоторые другие аспекты алгоритма ускользают от меня:
Я не могу выполнить полное воспроизведение до конечного состояния, потому что A) это займет много моего вычислительного времени и B) некоторые битвы могут никогда не закончиться (по замыслу). У меня есть 2 решения (которые я могу комбинировать): - Сделать случайное воспроизведение на X ходов - Использовать функцию оценки, чтобы попытаться оценить ситуацию.
Даже если я рассматриваю только очки здоровья для оценки, я не могу найти хорошую функцию оценки, которая возвращала бы надежное значение для данной ситуации (от 1 до 4 единиц для игрока и то же самое для монстров; я знаю их текущий хп/ максимальное значение). Что меня беспокоит, так это то, что бои могут сильно различаться по продолжительности / неравенству сил. Это означает, что иногда изменение ХП на 0,01% имеет значение (например, для долгой игры против босса), а иногда просто незначительное (когда игрок фармит низкоуровневую зону по сравнению с ним).
Разница в силе и HP между боями означает, что мой параметр Biais в процессе выбора UCB трудно исправить. в настоящее время я использую что-то очень низкое, например 0,03. Все, что > 0,1, и коэффициент исследования настолько высок, что мое дерево строится в глубину:/
На данный момент я также использую предвзятый способ выбора хода на этапе симуляции: он выбирает ход, который игрок выбрал бы в ситуации, и случайные для ИИ, что приводит к симуляции, предвзятой в пользу игрока. Я пытался использовать чистый случайный выбор для обоих, но, похоже, это дает худшие результаты. Считаете ли вы, что предвзятая фаза моделирования работает против цели алгоритма? Я склонен думать, что это лишь дало бы пессимистический взгляд на ИИ и не слишком сильно повлияло бы на конечный результат. Может я неправильно подумал.
Любая помощь приветствуется :)
