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

Question

我正在尝试为小游戏的AI实现MCTS算法。该游戏是一个RPG模拟。 AI应该决定在战斗中发挥什么样的动作。这是一场转身基地战（FF6-7风格）。没有涉及的运动。

我不会详述，但我们可以放心地假设，我们可以确定地知道在任何特定情况下轮到玩家时会选择什么样的动作。

当一方没有活着的单位时（4v4），游戏结束。它可以采取任何转数（也可能永远不会结束）。在伤害计算中有很多RNG元素可以处理（攻击可以命中/不命中，暴击与否，有很多proc可以“处理”或不可以，buff可以有％值发生等等。 ..）。 单位有大约6个技能，每个技能都可以给出分支因子的概念。

我已经构建了一个初步版本的MCTS，目前给出的结果很差。我遇到了几件事情：

我的一个主要问题是如何处理我的动作的非确定性状态。我已经阅读了几篇关于这方面的文章，但我仍然处于黑暗中。

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

我有添加的想法X孩子也有同样的举动，但似乎也没有得到很好的答案。它使RNG曲线平滑一些，但如果X的值与特定RNG的百分比相比太大/太小，则可以将它移向相反的方向。因为我得到了多个RNG帕尔移动（命中改变，暴击几率，处理某个东西的百分比......），我无法找到满足每种情况的X的体面值。更多的是一种比其他任何东西都更糟糕的援助。

同样每个RNG元组增加1个节点{击中或未命中，暴击与否，proc1与否，proc2与否，等等}每一步都应该覆盖每一种可能的情况，但有一些重大的缺点：5 RNG只有这意味着2^5节点才能考虑每次移动，所以计算太多了。如果我们设法创建它们，我们可以为它们分配一个概率（与节点元组中每个RNG元素的概率相关）并在选择阶段使用该概率。这应该总体上，但在CPU上真的很难：/

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

你有什么想法如何解决这个问题？

算法的一些其他方面躲避我：

我不能做一个完整的播出，直到一个结束状态，因为A）它会采取很多我的计算时间和B）有些战斗可能永远不会终止（设计）。我有2个解决方案（我可以混合使用） - 随机播放X轮 - 使用评估功能尝试评分情况。

即使我只考虑健康点来评估我没有找到一个好的评估函数来为给定的情况返回一个可靠的值（1-4个单位之间的玩家和相同的怪物;我知道他们的HP电流/最大值）。令我困扰的是，战争的长度/权力差距可能会有很大差异。这意味着Hp有时候会有0.01％的变化（比如长时间比赛，比如老板），有时候这个变化不大（当玩家比他低时，他们会选择一个低级别区域）。

战斗力和Hp差异的差异意味着我的Biais参数在UCB选择过程中很难解决。我目前使用的东西很低，比如0.03。任何东西> 0.1和探索因子是如此之高，以至于我的树被深度构建深度：/

现在我还在模拟阶段使用偏移方式来选择移动：选择移动，玩家会在情况中选择，随机选择AI，导致模拟偏向于玩家。我已经尝试过使用一个纯粹的随机一个，但它似乎给更糟糕的结果。你认为有一个偏差的模拟阶段是否违背了算法的目的？我倾向于认为这会给人工智能带来悲观的看法，并且不会对最终结果产生太大影响。也许我错了。

欢迎任何帮助:)

Answer 1

我认为这个问题是这样的StackOverflow的范围太广，但我给你的一些想法：

1. 在树搜索中使用随机或概率通常是称为expectimax搜索。你可以在第4章中找到Expectimax Approximation with Monte-Carlo Tree Search的一个很好的摘要和伪代码，但是我会推荐使用带expectimax扩展名的正常minimax树搜索。有一些修改如Star1, Star2 and Star2.5可以获得更好的运行时间（类似于alpha-beta修剪）。

   它归结为不仅有决策节点，而且还有机会节点。每个可能的结果的概率应该是已知的，并且每个节点的期望值乘以它的概率以知道它的实际期望值。

2. 每移动2^5个节点很高，但不是不可能高，特别是对于较少的移动次数和较浅的搜索。即使是1-3的深度搜索也会给你一些的结果。在我的俄罗斯方块人工智能中，有大约30种不同的可能动作需要考虑，我计算出以下三个部分的结果（对于每种可能的情况）以选择我的动作。这在2秒内完成。我相信你有更多的时间来计算，因为你在等待用户输入。

3. 如果你知道玩家是什么动作是显而易见的，你的AI应该不是很明显吗？

4. 您不需要考虑单个值（hp），您可以使用几个加权不同的因子来计算预期值。如果我回到我的俄罗斯方块AI，有7个因素（凹凸不平，最高的一块，孔的数量......），计算，加权和加在一起。为了得到权重，可以使用不同的方法，我使用遗传算法来查找导致大多数行被清除的权重组合。