Построение бота NetHack: является ли байесовский анализ хорошей стратегией?

Ответ 1

Хотя байесовский анализ охватывает гораздо больше, алгоритм Наивного Байеса, хорошо известный из спам-фильтров, основан на одном очень фундаментальном предположении: все переменные существенно независимы друг от друга. Так, например, при фильтрации спама каждое слово обычно рассматривается как переменная, поэтому это означает, что если в письме содержится слово "viagra", это знание влияет на вероятность того, что в нем также будет содержаться слово "лекарство" (или "foo 'или' спам 'или что-то еще). Интересно то, что это предположение совершенно очевидно неверно, когда речь идет о естественном языке, но все же удается добиться разумных результатов.

Теперь один из способов, которым люди иногда обходят независимость, состоит в том, чтобы определить переменные, которые являются технически комбинациями вещей (например, поиск маркера "buy viagra" ). Это может работать, если вы знаете конкретные случаи поиска, но в общем, в игровой среде, это значит, что вы вообще ничего не помните. Поэтому каждый раз, когда вам нужно двигаться, выполнять действие и т.д., Он полностью независим от всего, что вы сделали до сих пор. Я бы сказал, что даже для самых простых игр это очень неэффективный способ изучения игры.

Я бы предложил изучить вместо этого q-learning. Большинство примеров, которые вы найдете, как правило, просто простые игры в любом случае (например, научиться перемещаться по карте, избегая стен, ловушек, монстров и т.д.). Усиление обучения - это тип онлайн-обучения без надзора, который действительно хорошо работает в ситуациях, которые могут быть смоделированы как агент, взаимодействующий с окружающей средой, например игра (или роботы). Он делает это, пытаясь выяснить, какое оптимальное действие выполняется в каждом состоянии в среде (где каждое состояние может включать столько переменных, сколько необходимо, намного больше, чем просто "где я" ). Тогда трюк поддерживает только достаточное состояние, которое помогает боту принимать правильные решения, не имея отдельной точки в вашем "пространстве" для любой возможной комбинации предыдущих действий.

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

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

Единственный улов - это то, что вам нужно определить награды, чтобы обеспечить как положительное "подкрепление". То есть вам нужно определить состояния, к которым бот пытается добраться, иначе он будет просто продолжаться вечно.

Ответ 2

Существует прецедент: чудовищная программа rog-o-matic преуспела в игре с изгоями и даже вернулась с амулетом Йендора несколько раз. К сожалению, изгоев был выпущен только двоичный файл, а не источник, поэтому он умер (если вы не можете настроить систему 4.3BSD на MicroVAX), оставив rog-o-matic неспособным играть в какой-либо из клонов. Это просто зависает, потому что они недостаточно близки к эмоциям.

Однако, rog-o-matic, я думаю, моя любимая программа всех времен не только из-за того, что она достигла, но из-за читаемости кода и понятного интеллекта его алгоритмов. Он использовал "генетическое наследование": новый игрок наследовал бы комбинацию предпочтений от предыдущей пары успешных игроков с некоторым случайным смещением, а затем был бы выпущен против машины. Более успешные предпочтения будут мигрировать в генофонде и менее успешные.

Источник может быть трудно найти в эти дни, но поиск "rogomatic" установит вас на пути.

Ответ 3

Я сомневаюсь, что байесовский анализ заставит вас далеко, потому что большая часть NetHack очень контекстуальна. Очень мало действий, которые всегда являются плохими идеями; большинство из них также являются спасателями жизни в "правильной" ситуации (крайний пример - употребление каратриза: это плохо, если вы не голодаете и в настоящее время полиморфны в камнеустойчивое чудовище, и в этом случае еда каратриса - это правильная вещь). Некоторые из этих "почти плохих" действий необходимы для победы в игре (например, поднимаясь по лестнице на уровне 1 или намеренно попадая в ловушки, чтобы добраться до Геенном).

То, что вы могли попробовать, будет пытаться сделать это на уровне "meta". Создайте бота как случайный выбор среди множества "элементарных поведений". Затем попробуйте измерить, как эти боты тарифицируются. Затем извлеките комбинации поведений, которые, по-видимому, способствуют выживанию; байесовский анализ мог бы сделать это среди широкого корпуса игр наряду с их "уровнем успеха". Например, если есть поведение "подбирать кинжалы" и "избегать привлечения монстров в рукопашном бою", я бы предположил, что анализ покажет, что эти два поведения хорошо сочетаются: боты, которые выбирают кинжалы без их использования, и боты, которые пытаются бросить ракеты у монстров без сбора таких ракет, вероятно, будет хуже.

Это как-то подражает тому, что часто задают учащиеся геймеров в rec.games.roguelike.nethack. Большинство вопросов похожи на: "Я должен пить неизвестные зелья, чтобы идентифицировать их?" или "какой уровень должен быть моим персонажем, прежде чем идти в глубину в подземелье?". Ответы на эти вопросы в значительной степени зависят от того, что еще делает игрок, и нет хорошего абсолютного ответа.

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

Ответ 4

По-видимому, там есть большое количество ботов Nethack. Ознакомьтесь с этим предложением:

Ответ 5

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

Не нужно есть Какаприз снова, есть?

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