基于树搜索的游戏AI:如何避免奖励稀疏的AI‘游荡’/‘拖延’？

Question

我的游戏AI使用的算法，搜索所有可能的未来状态，基于我可以采取的行动(极小/蒙特卡罗)。它使用评分系统对这些状态进行评估，选择得分最高的最终状态并遵循它。

在大多数情况下，这种方法效果很好，但当奖励很少时，效果却非常糟糕。例如:有一个理想的收藏对象，那就是我右边的3块瓷砖。自然的解决办法是右-右。

但是，我的算法搜索6转深。它将找到许多最终收集物体的路径，包括花费超过3圈的路径。例如，它可能会找到一条路径:向上->右->向下->右->右->向下，而是在第5圈收集对象。

因为在这两种情况下，最终的叶节点都会检测到所收集的对象，所以它自然不喜欢其中的一个。所以，与其在第一个拐弯处右转，倒不如往上、下、左。这一行为将在下一个回合中被重复，这样它基本上会在可收集的物体面前随意跳舞，只有运气才能让它踩到它。

这显然不是最优的，我想修复它，但是已经没有足够的想法来恰当地处理这个问题了。是否有解决这个问题的办法，或者是否有任何理论工作来处理这个问题？

我尝试过的解决方案：

• 使其在更早的回合中更多地值对象集合。虽然这是有效的，以击败评估‘噪音’，之间的差异必须是相当大的。第一轮的等级必须高于2，第二轮的等级必须高于3，等等。第一轮和第六轮的差距必须很大，以至于最终导致行为极其贪婪，这在大多数情况下都是不可取的。在具有多个对象的环境中，最终可能会选择在第1轮抓取对象的路径，而不是在第5和第6轮获取对象的更好路径。
• 将对象指定为目标和值距离。如果不轮流做，原来的问题就会继续存在。如果在轮流的基础上进行，每轮要求的重要性的差异再次使它变得过于贪婪。这种方法也降低了灵活性，并引发了其他问题。目标选择不是琐碎的，它破坏了极小极大样式算法的点。
• 在我的搜索中要深入得多，这样它就可以始终找到第二个对象。这将花费如此大的计算能力，以至于我不得不做出让步，比如更积极地修剪路径。如果我这样做，我将回到同样的问题，因为我将不知道如何让它更喜欢修剪5转版本而不是3回合版本。
• 对上一轮的计划给予额外的重视。如果它至少能够遵循次优路径，就不会有那么多问题了。不幸的是，这再次必须是一个相当强大的影响，它要可靠地工作，使它遵循次优路径在所有情况下，损害整体性能。

Answer 1

当对移动的最后一步的结果进行加权时，您是否在计算拾取对象所需的移动次数？

我猜想，你是在量化你的移动动作的每一步，如果这一步导致了一个物体的拾取，则给出一个+1。这意味着，在三个步骤中，我可以用上面的例子来获取对象，得到一个游戏场的+1状态，但是我也可以用4-5-6-x步骤来完成，得到相同的+1状态。如果在搜索的深度中只有一个对象是可到达的，那么算法很可能会从随机+1状态中选择一个，从而给出上述行为。

这是可以解决的，通过量化一个负的分数，每一个移动人工智能必须。因此，在3次移动中获得对象，将导致a-2，而在6次移动中获得对象，则将导致-5。这样，AI就会清楚地知道，最好是以最少的移动量得到目标，即3。