在大约一个月的时间里，我一直在解决新游戏中最困难的技术问题之一
Dicey Dungeons ，这是游戏最终发行版的改进型AI。 这是一个相当有趣的工作，而且对我来说，其中很多是新手，所以我决定为它写一些内容。
首先，我将说明：我不是计算机理论方面的专家，而是只有一个学习过足够编程知识以制作视频游戏的人中的一个，然后我从培训中毕业，只抓住了我需要的东西。 通常，我可以自己解决问题，但是真正的程序员很可能不会批准我的决定。
我试图以足够高的抽象水平撰写文章，以便即使对于非程序员而言，基本思想也很清楚。 但是我不是这种事情的专家，所以我对理论的解释可能是错误的。 在原始评论中写信给我，我将很乐意进行更改！
好吧，让我们从解释任务开始！
挑战赛
如果您还没有玩过《骰子龙与地下城》，我将简单介绍一下游戏：这是一个带有甲板建造的RPG，其中每个敌人都有一套执行不同动作的武器地图。 另外，他们掷骰子！ 然后他们将这些骰子放入武器中以造成伤害，或制造各种状态效果，或进行治疗，或防御伤害等。 这是一个小青蛙如何使用大剑和小盾的简单示例：
一个更复杂的例子：所有职业的杰克都有一个扳手，可以将两个骰子放在一起（即3 + 2将得到5，而4 + 5将得到6和3）。 他还有一把锤子（Hammer），如果对他施加六点，会给玩家带来“震撼”的效果；还有一个豌豆射手（Pea Shooter），伤害很小，但确实有“倒数”，然后在那里，它适用于几个动作。
另一个重要的复杂因素是：游戏具有改变对手能力的状态效应。 其中最重要的是电击，它会随机禁用武器。 可以通过在其上使用附加的立方体和“燃烧”来消除冲击，从而使立方体着火。 当多维数据集在燃烧时，可以使用它们，但是每次使用将消耗2个健康点。 这是一个聪明的杂工在我震惊和燃烧他所有的武器和立方体时所做的事情：
当然，游戏中还有很多东西，但是要获得一个总体思路，这就足够了。
因此，我们的任务是：如何让AI为自己的动作选择最佳动作？ 他如何找出要放出哪些燃烧方块，要用来减轻冲击的方块以及要保留重要武器的方块？
和他以前一样
长期以来，Dicey Dungeons中的AI仅遵循一条规则：他从左到右查看所有武器，确定可以用在他身上的最佳立方体，然后再使用它。 效果很好，但也有例外。 因此，我添加了新规则。
例如，我通过查看所有不受震动影响的武器来应对震动，并选择消除震动后将在其上使用的立方体，然后将该立方体标记为“保留”以备将来使用。 我用这样的方式来刻录多维数据集：我检查了是否有足够的健康来将它们放出，并随机选择是否执行此操作。
我为我能想到的一切添加了规则，结果得到了似乎有效的AI！ 实际上，令人惊讶的是，不同规则的交织表现得如此出色-Dicey Dungeons中的AI可能并不总是做出正确的决定，但至少总是可以接受的。 至少对于仍在开发中的游戏而言。
但是随着时间的流逝，不断增加新规则的系统开始崩溃。 人们发现了使AI行为愚蠢的漏洞。 例如，采用正确的方法，您可以胜过一位老板，这样他就永远不会攻击玩家。 我添加的纠正情况的规则越多，发生的奇怪事情就越多-一些规则与其他规则发生冲突，边界情况开始出现。
当然，解决方案之一是添加新规则，一个一个地考虑每个任务，并创建新的if构造来处理它们。 但是我认为通过这种方式，我只是将真正的解决方案搁置一旁。 该系统的局限性在于它仅担心一个问题：“我
下一步将采取什么行动？” 她从来没有向前看过，也没有试图暗示一种特定的聪明组合
会带来什么。
所以我决定重新开始。
经典解决方案
尝试查找有关游戏AI的信息，最有可能会遇到经典解决方案的第一件事-创建
minimax算法。 这是有关如何将其用于开发国际象棋AI的视频：
minimax的实现如下：
首先，我们创建游戏的最简单抽象版本，其中包含游戏中特定时间点的所有必要信息。 我们称它为
董事会 。 在国际象棋的情况下，这些是所有棋子的当前位置。 对于Dicey Dungeons，这是骰子，武器和状态效果的列表。
然后，我们创建
一个值函数 ，用于测量特定游戏配置（即特定
棋盘）的游戏进行得如何。 例如，在国际象棋中，棋子位于其原始位置的棋盘的等级为0。 吃对手的棋子的棋盘的值为1分，输掉自己的棋子的棋盘的值为-1分。 而我们确认对手的棋盘将在无数个点上进行评估，或类似的结果！
然后，从该抽象板开始，我们模拟我们可以进行的所有可能动作，从而为我们提供了新的抽象板。 然后，我们模拟
这些板上所有可能的移动的完成程度，依此类推，根据需要执行许多步骤。 这是来自
freecodecamp.org的类似解决方案的绝佳示例：
我们创建了两个玩家都可以进行的所有可能动作的图形，并向其应用值函数以评估游戏的进行情况。
在这一点上，Dicey Dungeons与minimax有所不同：minimax来自游戏的数学理论，其目的是在世界上寻求最佳动作的系列中，对手试图使自己的得分最大化。 之所以这样称呼该算法，是因为它使对手玩牌时的玩家损失最小化，从而最大程度地赢得了他的获胜。
但是在《骰子地牢》中会发生什么？ 实际上，我不在乎我的对手会做什么。 为了使游戏令人兴奋，人工智能进行逻辑动作就足够了-确定将骰子应用于武器的最佳方法，这样战斗才算公平。 换句话说，只有“最大”对我很重要，而没有“迷你”。
也就是说，对于AI Dicey Dungeons来说，做出一个好的举动，足以让我创建这张可能的走势图，并找到得分最高的棋盘，然后做出通往这一点的动作。
敌人的轻而易举
好吧，让我们继续示例！ 让我们再看一次青蛙。 她如何
决定下一步要做什么？ 她
怎么知道所选的动作是最好的？
实际上，她只有两个选择。 将1放在宽剑上，将3放在盾上，或者相反。 她显然认为最好放3而不是1。但是为什么呢？ 因为她研究了所有可能的结果：
如果您在剑上放1，那么我们将获得438分。 如果您在上面加3，我们将获得558分。 太好了！ 因此，通过放置剑3，我获得了更多积分，问题得以解决。
这些眼镜从哪里来？ Dicey Dungeons中的评估系统目前考虑以下方面：
- 损坏：最重要的因素是每造成1点伤害就得100点。
- 毒药：人工智能认为重要的状态效应几乎与伤害一样重要-每种毒药90。
- 产生其他状态影响：例如，震动，燃烧，减弱等。 每个人花费50分。
- 奖励状态效果：为玩家增加积极的状态效果，例如防御等，每个花费40点。
- 使用武器：使用任何类型的武器均需花费10分，因为如果没有其他方法成功，则AI只能尝试使用所有东西。
- 倒计时减少：要激活某些类型的武器（例如，豌豆射手），骰子上的总金额就足够了。 因此，AI每减少一个倒数点就获得10点。
- 骰子上的点：骰子上每未使用的点数，AI可获得5分，即1分获得5分，6分获得30分。 这样做是为了让AI不想使用您不需要使用的多维数据集，因此AI的动作与人类的动作非常相似。
- 持续时间： AI每回合损失1点，因此长距离动作的价值略小于短距离动作的价值。 这样做是为了在存在两个相同价值的动作时，AI选择最短的动作。
- 治疗：恢复一个健康点仅需花费1点，因为尽管我希望AI认为这一点很重要，但我并未真正监控自己的健康。 总有事情要做，更重要！
- 奖励积分：可以将它们添加到任何步骤中，以迫使AI做他本来不会做的事情。 使用非常适度。
最后，有两种特殊情况-如果被攻击目标的健康状况不佳，则将花费一百万分。 如果健康状况以AI结束，那么它的成本将降低一百万点。 这意味着AI绝不会意外杀死自己（例如，通过偿还生命值非常低的骰子），或者永远不会错过可以杀死玩家的举动。
这些数字并不理想-以当前的未解决问题为例：
640，642，649 ，但这并不是很重要。 即使近似准确的数字也足以刺激AI正确地执行或多或少的操作。
敌人更艰难的举动
青蛙的情况是如此简单，以至于即使我糟糕的代码也可以在0.017秒内找出所有选项。 但是，情况变得更加复杂。 让我们再次看一看所有行业的例子。
它的决策树“有点”棘手：
不幸的是，即使在相对简单的情况下，复杂性的爆发也会很快发生。 在这种情况下，在我们的图形中，我们得到了2,670个需要检查的节点，这比青蛙的情况要花费更长的时间-可能需要一到两秒钟。
这主要是由于组合的复杂性-例如，最初使用缓解震动的方法中的哪一个都没有关系，算法将其视为两个单独的解决方案，并为每个解决方案创建完整的分支解决方案树。 结果，我们得到了一个完全不需要复制的分支。 选择要赎回的积木，消除武器的震动以及使用程序时，也存在类似的组合问题。
但是，即使我们找到并优化了这些不必要的分支（在一定程度上我也做了），总会有一个问题解决方案的所有可能置换的复杂性导致庞大，缓慢的决策树，对它的评估将花费无穷的时间。 因此，这是此方法的第一个严重问题。 这是另一个：
万能钥匙。 将立方体分成两个。这种重要的武器（和类似武器）会导致AI问题，因为其使用的结果是
不确定的 。 如果我在上面放六个，我可以得到五个和一个，或者四个和两个，或者也许两个三元组。 我不知道这一点，所以要制定一个考虑到这一点的计划非常困难。
幸运的是，Dicey Dungeons可以很好地解决这两个问题！
现代解决方案
蒙特卡洛树搜索（MCTS）方法是一种概率决策算法。 下面是一个有点奇怪的视频，尽管如此，它很好地解释了基于蒙特卡洛方法的决策原理：
实际上，MCTS不会将所有可能的移动都添加到图形中，而是会检查随机移动的序列，然后跟踪已证明更好的移动。 借助一个名为“最高可信度上限”的公式，他可以神奇地确定决策树的哪些分支是“最有希望的”：
顺便说一下，我从一篇
非常有用的文章中采用了这个公式，该
文章关于使用蒙特卡洛方法搜索树木 。 不要问我它是如何工作的！
MCTS的神奇之处在于，为了找到最佳解决方案，我们通常不需要对所有内容进行笨拙的搜索，并且可以使用与minimax中相同的抽象板/移动仿真系统。 也就是说，我们有点同时使用两种算法。 这正是我在Dicey Dungeons中使用的方案。 首先，她尝试完成决策树的完整部署，这通常不会花费很多时间，并且可以带来最佳结果。 但是，如果树看起来太大，那么我们将回滚到使用MCTS。
MCTS具有两个非常酷的功能，非常适合Dicey Dungeons：
首先，该方法理想地具有不确定性。 由于它是一次又一次地执行，并从每次运行中收集数据，因此我只是让它以自然的方式模拟未定义的运行，例如使用主键，并且在多次运行之后，该方法将创建一个相当正确的点数范围，此点的范围是此运行的结果。
第二，他可以给我部分解决方案。 实际上，使用MCTS时，您可以执行任意数量的模拟。 从理论上讲，如果不停地执行它，它将收敛到与minimax完全相同的结果。 但是，对我来说更重要的是，我可以使用MCTS在有限的思考时间内获得良好的解决方案。 我们执行的搜索越多，找到的“解决方案”就越好，但是对于Dicey Dungeons，通常只有几百次搜索就足够了，而只需要一秒钟的时间。
有趣的相关主题
因此，这就是Dicey Dungeons中的敌人决定如何杀死您的方式！ 我想将此系统添加到游戏v0.15的下一版本中！
我显示的图表来自哪里，包括在Twitter上：
我通过为
GraphML编写导出程序来创建它们，
GraphML是一种可以由许多不同工具读取的开源图形文件格式。 （我强烈推荐使用出色的
yEd 。）
解决此问题的部分方法是允许AI模拟动作，这本身就是一个有趣的难题。 结果，我实现了一个动作脚本系统。 现在，对手正在使用不同类型的武器。 他们执行以下小脚本：
这些小脚本由基于
haxe的hscript解析器和表达式解释器执行。 这部分很难实现，但是付出了努力：它使游戏超级易于创建mod。 我希望游戏发行后，人们可以使用此系统开发自己的武器，也就是说，他们可以将他们几乎可以想象的一切添加到游戏中。 此外，由于AI足够智能，可以评估传递给它的任何动作，所以敌人将能够弄清楚如何使用玩家将创造的任何修改过的武器！