我读过(例如,http://radagast.se/othello/Help/order.html),首先搜索每个级别的最佳移动(可以使用迭代深化找到)使搜索速度更快。
在不使用太多额外内存和 CPU 时间的情况下,如何搜索可能的最佳动作?
我读过(例如,http://radagast.se/othello/Help/order.html),首先搜索每个级别的最佳移动(可以使用迭代深化找到)使搜索速度更快。
在不使用太多额外内存和 CPU 时间的情况下,如何搜索可能的最佳动作?
基本上有两种策略:
动态移动排序使用来自先前搜索的信息,或者因为您再次转置到相同的位置,或者您已经在先前不太彻底的搜索中到达了该位置。就是你提到的迭代加深的思想,不断的增加搜索距离。
动态移动排序非常强大。有很多方法可以做到这一点,但最常见的两种是换位表和杀手级动作:
转置表缓存有关先前搜索的信息,尤其是找到的最佳移动。当再次到达相同位置时,您可以立即从之前的搜索中搜索最佳移动。很多时候,通过更深入的搜索,它被确认为最佳举措。
Killer move 使用类似的方法,并具有额外的优势,即他们可以使用来自相似但不相同位置的知识。然而,移动排序的杀手移动的质量通常比来自转置表的移动更差。这就是为什么它们通常在换位移动之后被搜索。
但是,如果以前的搜索没有信息怎么办?通常,您有一些特定领域的知识可用于静态移动排序。例如,在国际象棋中有许多经验法则。一是捕捉动作比非捕捉动作更有可能是最佳动作。有更复杂的策略(例如,静态重新捕获分析),但您必须小心,因为更复杂的计算也会减慢搜索速度。
通过结合静态和动态移动排序,国际象棋引擎通常可以猜出该位置的最佳移动,命中率超过 90%。
如果您先验地知道如何搜索最佳着法,那么您一开始就不需要进行搜索。您可以做的事情通常需要您尝试解决的游戏中的一些专业知识。例如,在跳棋中,您可能会尝试先评估所有会导致 K 的动作,然后再评估不会出现 K 的动作。