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

Question

我正在尝试为一个小游戏的人工智能实现一个mcts算法。这个游戏是一个RPG模拟游戏。人工智能应该决定在战斗中要玩什么动作。这是一个回合基地战斗（ff6-7风格）。不涉及任何运动。
我不会详细说明，但我们可以放心地假设，当轮到球员上场时，我们肯定知道在任何给定的情况下，球员会选择什么动作。
游戏结束时，一方没有单位活着（4v4）。它可以转任意数圈（也可能永远不会结束）。在伤害计算和技能处理中有很多rng元素（攻击可以命中/未命中，暴击或不命中，有很多过程可以“触发”或不触发，buff可以有%的值发生等等）。
每个单位都有大约6项技能来给出分支因子的概念。
我已经建立了MCT的初步版本，目前效果不佳我有几个问题：
我的一个主要问题是如何处理我的动作的不确定状态我读了几篇关于这件事的文章，但我仍然一无所知。
有些人建议确定游戏信息并在其上运行mcts树，重复n次该过程以覆盖广泛的可能游戏状态，并使用该信息做出最终决定。最后，它确实乘以了我们计算时间的一个巨大因素，因为我们必须计算n次mcts树而不是1次。我不能相信这一点，因为在一场战斗中，我有成千上万的RNG元素：2^1000 MCTS树来计算我已经与之斗争的地方不是一个选项：）
我本来想在同一步中增加x个孩子，但这似乎也不能得到一个好的答案。它可以稍微平滑RNG曲线，但如果X的值与特定RNG的百分比相比太大/太小，则可以将其向相反的方向移动由于我得到了多个rng-par移动（命中变化，暴击几率，命中率等等），我找不到一个像样的x值来满足所有情况。比其他任何东西都更糟糕。
同样，为每个rng元组添加1个节点{hit or miss，crit or not，proc1 or not，proc2 or not，etc.}对于每个移动，应该覆盖所有可能的情况，但有一些严重的缺点：对于5个rng mecanism，仅意味着每个移动需要考虑2^5个节点，计算起来太多了。如果我们能够创建它们，我们可以为它们分配一个概率（与节点元组中每个rng元素的概率相关联），并在选择阶段使用该概率。这应该是一个整体的工作，但在CPU上是非常困难的：/
我也不能将它们“合并”到一个节点中，因为我无法根据两个不同的游戏状态精确地平均玩家/怪物属性的值，并且在移动处理过程中平均移动的结果本身是可行的，但是需要大量的简化，这对代码来说是一个痛苦，而且无论如何都会很快地损害我们的准确性。
你有什么办法解决这个问题吗？
算法的其他一些方面让我难以理解：
我不能做一个完整的播放直到一个结束状态，因为a）这将需要我的大量计算时间和b）一些战斗可能永远不会结束（按设计）。我有两个解决方案（我可以混合）
-随机播放x个回合
-使用评估功能尝试对情况进行评分。
即使我只考虑生命值来评估，我也没有找到一个好的评估函数来返回给定情况下的可靠值（玩家的生命值在1-4个单位之间，怪物的生命值在1-4个单位之间；我知道他们的生命值/最大值）。令我烦恼的是，战斗的时间长短/力量的差异很大。这意味着，有时候惠普0.01%的变化很重要（比如长时间与老板的比赛），有时候只是微不足道（当玩家建立了一个较低的等级区域时）。
战斗之间的力量和HP差异意味着我在UCB选择过程中的BIAIS参数很难确定。我现在用的是很低的值，比如0.03任何大于0.1的东西，而且勘探系数很高，所以我的树是按深度建造的：/
目前，我也在使用一种偏倚的方式来选择移动在我的模拟阶段：它选择的移动，玩家将选择的情况下和随机的一个人工智能，导致模拟偏倚有利于玩家我试过用纯随机的方法来处理这两个问题，但结果似乎更糟。你认为有一个偏倚的模拟阶段，工作的目的与alogorithm？我倾向于认为这只会给人工智能带来悲观的看法，不会对最终结果产生太大的影响也许我想错了。
欢迎任何帮助：）

Answer 1

我认为这个问题对于stackoverflow来说太宽泛了，但我会给你一些想法：
在树搜索中使用随机或概率通常称为expectimax搜索。您可以在第4章中找到Expectimax Approximation with Monte-Carlo Tree Search的良好摘要和伪代码，但我建议使用带有expectimax扩展名的普通minimax树搜索。有一些修改，比如Star1, Star2 and Star2.5以获得更好的运行时（类似于alpha-beta剪枝）。
归根结底，它不仅有决策节点，还有机会节点。每个可能结果的概率应该是已知的，并且每个节点的期望值与其知道其实际期望值的概率相乘。
每次移动2^5个节点是高的，但不是不可能高，特别是对于低移动数和浅搜索。即使是1-3个深度的搜索也会给你一些结果。在我的俄罗斯方块ai中，有大约30个不同的可能移动要考虑，我计算了下面三个部分（每个可能）的结果来选择我的移动。这是在2秒钟内完成的。我相信你有更多的时间来计算，因为你在等待用户的输入。
如果你知道玩家的动作是明显的，那对你的人工智能来说是不是也很明显？
您不需要考虑单个值（hp），您可以有多个权重不同的因素来计算期望值如果我回到我的俄罗斯方块人工智能，有7个因素（颠簸，最高块，洞的数量，…）是计算，加权和加在一起的。为了得到权重，可以使用不同的方法，我使用了一种遗传算法来找到权重的组合，从而清除了大多数行。