beta修剪在我的解决方案中用minimax去除随机性?
现有实施:
在使用minimax实现Tic-Tac-Toe时,我寻找可以获得最佳结果的所有框,并随机选择其中的一个,以便每次都不显示相同的解决方案。
例如。 如果返回的列表是[1,0,1,-1],那么在某个时刻,我将在两个最高值之间随机选择。
关于Alpha-Beta修剪的问题:
根据我的理解,当算法发现它从一条路径中获胜时,它不再需要寻找可能/可能不会导致获胜案例的其他路径。
那么,就像我觉得的那样,这是否会导致尽可能早地出现最佳解决方案,并且每次看起来都一样? 例如,在第一次移动时,所有移动都会导致平局。 那么每次都会选择第一个盒子?
我怎样才能像解决极小极点解决方案一样给解决方案带来随机性? 我现在想到的一种方法是将索引随机传递给alpha-beta算法。 因此,这个结果将是随机排序的职位列表中的第一个最佳解决方案。
提前致谢。 如果有关于此的一些文献,我很乐意阅读它。 如果有人可以为aplha-beta修剪发布一些很好的参考,那很好,因为我很难理解如何应用它。
要在alpha-beta修剪中随机挑选多个最佳解决方案(全部相同),可以在评估游戏状态时修改评估函数以添加非常小的随机数。 你应该确保该随机数的大小永远不会超过两种状态评估之间的真正差异。
例如,如果你的游戏状态的真实评价函数只能返回值-1
, 0
和1
,你可以在范围添加一个随机生成的数字[0.0, 0.01]
每场比赛状态的评估。
没有这个,alpha-beta修剪不一定只能找到一个解决方案。 从维基百科考虑这个例子。 在中间,您会看到两个解决方案的评估结果为6,因此可以找到多个解决方案。 我确实认为它仍然会找到导致在根节点处找到最佳解决方案的所有举措,但实际上并没有找到树中的所有解决方案。 假设在示例图像中,中间9
分的修剪节点实际上得分为6
。 它仍然会在那里被修剪,所以不会找到特定的解决方案,但是从根节点通向它的移动(根部的中间移动)仍然可以找到。 所以,最终,你将能够达到它。
一些有趣的笔记:
上一篇: beta pruning remove randomness in my solution with minimax?