如何在高度不确定的系统上运行MCTS？

Question

我试图为一个小游戏的人工智能实现一个MCTS算法。这个游戏是一个rpg模拟游戏。AI应该决定在战斗中要玩什么动作。这是一个转基地战斗(FF6-7风格)。不涉及任何运动。

我不会详细讨论，但我们可以放心地假设，当轮到他上场的时候，我们可以肯定地知道在任何特定的情况下，球员的选择是什么。

游戏结束时，一方没有单位活着(4v4)。它可以进行任意次数的转弯(也可能永远不会结束)。在伤害计算和技能处理中有大量的RNG元素(攻击可以命中/命中，暴击与否，有很多过程可以“触发”或“不”，水牛可以有%值发生等等)。单位大约有6个技能，每个技能提供一个分支因子的概念。

我已经建立了一个初步版本的MCTS，给出了糟糕的结果。我有几件事有问题：

我的主要问题之一是如何处理我的动作的非确定性状态。我看过几篇关于这件事的报纸，但我仍然不知道。

一些人建议确定游戏信息并在其上运行MCTS树，重复过程N次以覆盖广泛的可能的游戏状态，并使用该信息来做出最终决定。最后，它以一个巨大的因子乘以我们的计算时间，因为我们必须计算N倍的MCTS树而不是一棵树。我不能相信这一点，因为在战斗过程中，我有数千个RNG元素: 2^1000 MCTS树来计算我已经与其中一个进行斗争的位置，这不是一个选项:)

我有一个想法，增加X的孩子为同样的举动，但这似乎也不是一个好的答案。它使RNG曲线平滑一点，但如果X的值与特定RNG的百分比相比太大/太小，则它可以向相反的方向移动。由于我得到了多次RNG标准移动(命中变化，暴击机会，百分比等)我找不到满足每一种情况的一个像样的X值。比其他任何东西都更像坏带子。

同样，为每个RNG元组添加一个节点{命中或误击、crit或not、proc1或not、proc2或not……}对于每一种可能的情况都应该包括在内，但也有一些严重的缺点:只有5 RNG机制，这意味着每次移动都要考虑2^5节点，计算起来太麻烦了。如果我们设法创建它们，我们可以为它们分配一个概率(链接到节点元组中每个RNG元素的概率)，并在我们的选择阶段使用该概率。这在总体上应该是可行的，但在cpu上却非常困难:/

我也不能将它们“合并”在一个节点中，因为我无法根据两种不同的游戏状态精确地平均玩家/怪物的值，并且在移动处理过程中平均移动的结果本身是可行的，但是需要大量的简化，这对代码来说是痛苦的，而且无论如何都会损害我们的准确性。

你有什么办法解决这个问题吗？

算法的其他一些方面也在逃避我：

我无法完成一个完整的比赛，直到一个结束状态，因为A)它将花费我大量的计算时间和B)一些战斗可能永远不会结束(通过设计)。我有两个解决方案(我可以混合)-做一个随机的播放X转身-使用一个评估功能，尝试和得分的情况。

即使我只考虑生命值来评估，我也找不到一个很好的评估函数来返回给定情况下的可靠值(玩家在1-4个单位之间，怪物在1-4个单位之间；我知道他们的hp当前/最大值)。令我困扰的是，战斗的长度/力量差异很大。这意味着惠普有时会发生0.01%的变化(例如，对于一场长时间的比赛对老板而言)，有时这只是微不足道的变化(当玩家的lvl区域比他低时)。

电源和Hp之间的差异意味着我在UCB选择过程中的Biais参数很难修复。我现在用的东西很低，比如0.03。任何大于0.1的东西，勘探因子都很高，所以我的树是由深度构成的:/

现在，我也在使用一种偏置的方法来选择我的模拟阶段的移动:它选择玩家在情况下会选择的移动，并为AI选择随机的移动，从而导致一个对玩家有利的模拟偏倚。我试过对这两种方法都使用纯随机的方法，但结果似乎更糟。你认为有一个偏置的模拟阶段会违背该算法的目的吗？我倾向于认为这只会给AI一个悲观的观点，不会对最终结果产生太大的影响。也许我想错了。

欢迎任何帮助:)

Answer 1

我认为这个问题对StackOverflow来说太宽泛了，但是我要给大家一些思考：

1. 在树搜索中使用随机或概率通常称为期望最大搜索。在第4章中，您可以为蒙特卡罗树搜索的前谱逼近找到一个很好的摘要和伪代码，但是我建议使用一个普通的minimax树搜索，并使用expectimax扩展。对于更好的运行时，有一些类似于Star1，Star2和Star2.5的修改(类似于α-beta剪枝)。 它归结为不仅有决策节点，而且有机会节点。每个可能的结果的概率应该是已知的，每个节点的期望值与它的概率相乘，从而知道它的实际期望值。
2. 每移动2^5个节点高，但不可能高，特别是对于低移动数和浅搜索。即使是1-3个深度搜索也会给你一些结果。在我的俄罗斯方块AI中，有30种不同的可能的移动需要考虑，我计算了以下三个部分的结果(每个可能的)来选择我的移动。这是在2秒内完成的。我相信您有更多的时间来计算，因为您正在等待用户的输入。
3. 如果你知道玩家的动作是显而易见的，那对你的AI来说是不是也很明显？
4. 您不需要考虑单个值(hp)，您可以有几个加权不同的因素来计算期望值。如果我回到我的俄罗斯方块人工智能，有7个因素(颠簸，最高的作品，洞数，.)计算、加权和加在一起。为了获得权重，您可以使用不同的方法，我使用了一种遗传算法来找到权重的组合，从而使大多数行被清除。