我目前正在使用 MinMax 算法来帮助评估给定游戏的最佳着法。我发现我偶尔会遇到移动永远重复的问题。让我们来玩一个游戏,比如西洋跳棋,一旦你有了国王,你就可以一直在棋盘上相同的两个空间之间移动你的棋子(假设其他玩家也在做同样的事情)。
假设我们有一块棋盘看起来像这样(请原谅 ASCII 艺术),其中 0 是棋盘上的正方形和破折号 - 是空格:
|-|-|-|
|-|0|-|
|-|-|-|
现在为了这个例子的目的,假设我们的移动深度是 5。我们还可以说获胜位置可以看到 3 次移动,并且首先让棋子移动到右下角。
然而,当棋子实际移动时,我们看到最小最大结果选择将其移动到右上而不是右下。然后对手下了他们的棋,出于争论的考虑,这并没有以有意义的方式改变棋盘的状态,然后我们再次下棋。在下一步移动中,引擎决定将棋子移回原来的位置。对手的动作并没有真正的影响。然后我们再次移动,引擎重复第一次移动到右上角,尽管右下角仍然是更好的移动。
那么,这里发生了什么?好吧,事实证明引擎完全知道要采取的最佳行动,但还有其他因素在发生:
所以引擎搜索中发生的事情是在其搜索树中遇到以下序列,这导致评估值说 X:
左上角->右下角->右下角->右下角->左下角仍然与理想位置相同。
在引擎命中以 右下角 移动开始的任何移动之前搜索以上内容,因此即使 右下 移动最终被评估为第一步,它不会导致比之前找到的更好的评估移动以 top right
开头的作品这种情况然后一遍又一遍地重复而实际上没有导致右下角移动发生,再次假设对手没有做出任何改变状态的移动并且为了争论起见,假设对手只是在不改变状态的位置之间切换棋子获胜结果。
我们可以更快地评估这一点的一种方法是简单地检查从该位置移动的获胜移动距离。但是,可以说它不是一个获胜的位置,而是一个很好的位置,接下来的两个位置(深度 4 和 5)不会对评估产生任何更有用的结果。在这种情况下,我不确定有助于避免这种情况的技术?
此时我没有尝试任何其他操作,除了我确实添加了一个功能,它检查以查看早先有“采取”操作的路径,因此当评估相同时,我们然后比较采取操作发生的位置和选择了那条路。但是,我不确定在 minimax 中是否有更标准的方法来处理这个问题?