构建一个NetHack机器人：贝叶斯分析是一个好策略吗？

Question

我的一个朋友正在开始构建一个NetHack机器人（一种玩Roguelike游戏：NetHack的机器人）。有一个非常好的类似游戏Angband的工作机器人，但它部分工作是因为方便回到城镇并始终能够通过低级别获得物品。

在NetHack中，问题要困难得多，因为游戏奖励大胆的实验，并基本上构建为1,000个边缘情况。

最近，我建议使用某种天真的贝叶斯分析，就像垃圾邮件创建的方式一样。

基本上，机器人首先会通过尝试找到的每个物品或生物的每个可能的动作来建立语料库，并将存储该信息，例如，接近死亡、受伤或负面影响的程度。随着时间的推移，您似乎可以生成一个相当可玩的模型。

有人能指点我们应该从何处入手吗？我是否误解了贝叶斯分析的概念？

编辑：我的朋友发布了他的NetHack补丁的Github repo，允许使用Python绑定。它仍处于相当原始的状态，但如果有人感兴趣...

- danieltalsky

---

听起来很棒。用什么语言？ - Trevoke

他正在使用Python编写，使用Python NetHack绑定。 - danieltalsky

更正：他编写了Python绑定。 - danieltalsky

啊，真遗憾。我本来希望它是针对Ruby的。不过我想我总能学习Python...他有网站或者Github账号吗？ :) - Trevoke

他还没有释放他的绑定，但这是他的账户，您可以随时订阅它以便在他决定释放时获取： http://github.com/BenSmith/ - danieltalsky

Answer 1

尽管贝叶斯分析包含了更多内容，但垃圾邮件过滤器中广为人知的朴素贝叶斯算法基于一个非常基本的假设：所有变量本质上是彼此独立的。因此，例如，在垃圾邮件过滤中，每个单词通常被视为一个变量，这意味着假设如果电子邮件包含单词“viagra”，那么该知识确实会影响它也包含单词“medicine”（或“foo”或“spam”或其他任何单词）的概率。有趣的是，当涉及自然语言时，这个假设显然是错误的，但仍然能够产生合理的结果。

现在，人们有时绕开独立性假设的方法是定义技术上是事物的组合的变量（例如搜索标记“购买viagra”）。如果你知道要查找的特定情况，这可能有效，但一般来说，在游戏环境中，这意味着你通常无法记住任何东西。因此，每次你必须移动、执行操作等，都完全独立于你迄今为止所做的任何其他事情。我认为，即使对于最简单的游戏，这也是一种非常低效的学习方法。

我建议使用q-learning。大多数示例通常只是简单的游戏（如学习在避开墙壁、陷阱、怪物等情况下导航地图）。强化学习是一种在线无监督学习类型，在可以建模为代理与环境交互的情况下（如游戏或机器人），表现非常好。它试图在环境中的每个状态下找出最优动作（其中每个状态可以包括所需的任意数量的变量，远不止“我在哪里”）。然后，关键是保持足够的状态来帮助机器人做出正确的决策，而不必为先前所有可能的组合都指定一个明确的状态“空间”点。

更具体地说，如果您要构建一个象棋机器人，您可能会遇到麻烦，因为尝试基于所有先前的移动创建决策策略会导致棋子移动的所有可能组合集增长得非常快。即使是在棋盘上每个棋子位置都是一个较简单的模型，状态空间仍然非常大，因此您必须找到一种简化跟踪的方法。但请注意，您确实可以跟踪某些状态，以便您的机器人不会一次又一次地尝试将左转变成撞墙。

这篇维基百科文章充斥着术语，但这个教程更好地将概念转化为现实世界的例子。

唯一的问题是你需要能够定义奖励作为正向“强化”。也就是说，你需要能够定义机器人试图达到的状态，否则它将会无限制地继续下去。

- Rob Van Dam

Answer 2

有先例：巨大的rog-o-matic程序成功地玩了rogue，甚至几次带着Yendor护身符回来。不幸的是，rogue只发布了二进制版本，没有源代码，所以它已经死了（除非您可以在MicroVAX上设置4.3BSD系统），这使得rog-o-matic无法玩任何克隆版。它会挂起，因为它们模拟的不够接近。

然而，我认为rog-o-matic是我有史以来最喜欢的程序，不仅因为它所取得的成就，还因为其算法的可读性和可理解性。它使用了“遗传继承”的方法：新玩家会从前一对成功玩家中继承一些偏好组合，加上一些随机偏移量，然后与机器进行比较。更成功的偏好会向基因池上移动，而不成功的则下降。

现在很难找到源代码，但搜索“rogomatic”将为您指引道路。

- martinwguy

---

我的朋友很感激被指向Rog-o-matic。我仍然希望有人能就贝叶斯算法在这个目的上的适用性提出意见。 - danieltalsky

@martinwguy - rog-o-matic现在可以使用了，感谢Roguelike Restoration项目- http://rogue.rogueforge.net/ - Kornel Kisielewicz

Answer 3

我认为贝叶斯分析可能无法帮助你，因为NetHack的大部分内容都高度依赖于上下文。很少有行动是总是一个坏主意的；在“正确”的情况下，大多数行动也可以拯救生命（极端的例子是吃鸡蛇草：除非你挨饿并且当前变形成了一种抗石头怪物，否则吃鸡蛇草是正确的做法）。其中一些“几乎不好”的行动是赢得游戏所必需的（例如，在1级楼梯上来，或者故意落入陷阱到达Gehennom）。

你可以尝试在“元”级别上进行设计。将机器人设计为在各种“基本行为”中随机选择。然后尝试衡量这些机器人的表现。然后提取似乎促进生存的行为组合；在广泛的游戏语料库以及它们的“成功水平”中，贝叶斯分析可以做到这一点。例如，如果存在“拿起匕首”和“避免与怪物近战”的行为，我会认为分析会显示这两个行为很好地配合：拾取匕首却不使用它们的机器人，以及试图向怪物投掷导弹而没有收集这些导弹的机器人，可能表现得更差。

这在某种程度上模仿了学习游戏玩家经常在rec.games.roguelike.nethack中提出的问题。大多数问题类似于：“我应该喝未知的药水来识别它们吗？”或“在深入地牢之前我的角色应该达到什么级别？”对这些问题的答案严重依赖于玩家正在做什么，没有好的绝对答案。

这里一个困难的点是如何衡量生存的成功。如果你只是尝试最大化死亡前的时间，那么你会偏爱从不离开第一层的机器人；这些机器人可能活得很长，但永远不会赢得游戏。如果你通过角色死亡前到达多深的地下来衡量成功，那么最好的机器人将是挖掘者（他们从一开始就有镐）狂热地挖掘。

- Thomas Pornin

Answer 4

显然有很多Nethack机器人存在。 查看此列表：

- davr

---

该死...他那里还有一些很酷的机器人 :'(这是主页面的archive.org链接，不幸的是，他们没有机器人列表的子页面: http://web.archive.org/web/20100817092911/http://taeb.sartak.org/ - davr

抱歉，现在已经可以了；它会重定向到规范的URL，即http://taeb.github.io/bots.html。 - sartak

Answer 5

在NetHack中，未知的操作通常具有布尔效果——要么你赢了，要么你输了。贝叶斯网络基于"模糊逻辑"值-一个动作可能以给定的概率获得收益。因此，你不需要贝叶斯网络，只需要一个"已发现的效应"列表以及它们是好还是坏。

没必要再吃一遍Cockatrice了，对吧？

总的来说，这取决于你想要给机器人多少"知识"作为起点。你想让他通过"艰苦的方式"学习所有东西，还是会一直向他提供剧透直到他咕嘟咕嘟地饱为止？

- Kornel Kisielewicz

---

没有问题提供剧透，但是创建剧透信息的手工劳动量很大。我是说，Angband机器人显着使用剧透。实际上结果才是最重要的，但即使拥有全世界的剧透，也需要创建许多规则。此外，我不同意NetHack中的操作是二进制的说法。有时甚至你都不知道一个动作的效果。我认为可以收集每个动作的一些统计数据，例如：死亡前的回合数，造成的损伤中的HP数量等。 - danieltalsky

另外，对于吃金龙鸡的情况...它会立即导致死亡，而且大多数这样的行为很快就会沉淀到“有助于生存的行为”的底部。 - danieltalsky

不幸的是，Angband比NetHack更加“有序” - Angband中的规则相对简单，并且没有太多硬编码的“特殊情况”（这是NetHack著名的地方）。我会再考虑一下。 - Kornel Kisielewicz

我认为这种事情的一个大问题是起始状态的巨大变化。如果机器人在学习阶段重新加载，那肯定会容易得多。 - Anon.

当然，Anon，但我认为这就是贝叶斯模型如此酷的原因。我在想，你可以通过统计分析某些行动和结果来进行决策。即使你第一次尝试的事情会让你死亡，也可能只是因为那时正好是满月（是的，在NetHack中跟踪月相），而其他条件可能是有益的。这样，你就可以比较决定下一步最有可能做的事情的统计利益和统计危害。 - danieltalsky

Nethack不是概率性的吗？你在想什么呢？在nethack规则中有很多非确定性，其中最重要的是未鉴定的物品。它可能是一枚生命拯救护符，但同样也可能是一枚勒颈护符。你真的认为因为机器人第一次得到了一枚生命拯救护符，他应该继续戴上他找到的每一枚护符吗？ - meriton