algorithm - Minimax:残局中分数相等怎么办？

Question

据我所知，最简单形式的 Minimax 算法的工作方式如下:自下而上遍历游戏树，如果轮到玩家，则将所有子节点的最大分数分配给当前节点，否则最低分数。叶子根据游戏输出进行评分，比方说赢+1，平0，输-1。最后选择导致得分最高的节点的着法。

当然遍历整个博弈树是不切实际的，所以使用了启发式。但假设我们接近游戏的尾声。然后我发现这种简单的方法存在一些问题。

例如，我们正在下棋，玩家(下白棋)已经走到了这个位置:

轮到玩家了。所以 Qg7 有一个 mate，因此 Qg7 的节点得分为 1。但是例如，Ke1 也是一个合法的移动。唯一的回复是c5，那么Qg7#还是可以的。因为 Qg7 得到 1 分，所以 c5 也是，Ke1 也是。

所以我们至少有两个得分为 1 的 Action (Ke1 和 Qg7)。假设算法考虑国王先走，并选择得分最高的第一步。这意味着，在这个位置上，玩家不会将死对手，而是会做随机的国王移动，直到对手实际上可以阻止将死(用后兵)。

根本问题是，一局将死 (Qg7) 与二局将死 (Ke1) 得分相同，因此玩家没有理由实际去一局将死。

这可以通过对 Minimax 算法进行简单的修改来避免:在分数相等的情况下，选择到达具有该分数的位置的较短路径。因此，最好将死一个。

我的问题是:我没有在任何与 Minimax 相关的资料中找到任何提及这一点，所以我对 Minimax 有什么误解吗？如果不是，这是解决此问题的常用方法还是有更好的方法？

Answer 1

我敢肯定您正确理解了 minimax。

我可能会做的事情是简单地在 minimax 函数中传递当前距离，并据此对输赢进行加权。通常应该首选更快的胜利(以减少看不见的情况的可能性)和更慢的失败(以允许对手犯错)。无论获胜是 1 还是任何正值，都没有太大关系 - 它仍然会被选为比 0 或 -1 更好。

如果您的胜利是启发式中的最大可能值 - 您仍然可以做类似的事情 - 只需稍微增加或减少它的权重，但仍然要大于所有其他非胜利值。

对于您的示例，这可能并不重要，因为当棋子接近提升时，您会检测到平局即将到来，然后您会采取制胜举措。但如果出现以下情况，则肯定会出现问题:

• 超出搜索深度的一系列不可避免的移动会导致最糟糕的结果(这是 minimax 的一个非常常见的问题，但如果它可能是可以避免的，那么这样做显然更好)
• 你这边有时间限制
• 您没有满足所有开奖条件(例如 3 个重复位置)