|
alpha= val; 内容来自www.paper51.com
} 内容来自论文无忧网 www.paper51.com
returnalpha; paper51.com } 内容来自论文无忧网 www.paper51.com 2.4 历史启发及着法排序 paper51.com 既然Alpha-Beta搜索算法是在“最小-最大”的基础上引入“树的裁剪”的思想以期提高效率，那么它的效率将在很大程度上取决于树的结构——如果搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此时“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情况，这时的Alpha-Beta搜索已和“最小-最大”搜索别无二致了）。因而，要想保证Alpha-Beta搜索算法的效率就需要调整树的结构，即调整待搜索的结点的顺序，使得“裁剪”可以尽可能早地发生。 内容来自www.paper51.com
可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面（如个别无关紧要的棋子位置有所不同）也是较好的。由J.Schaeffer所提出的“历史启发”（History Heuristic）就是建立在这样一种观点之上的。在搜索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历史得分”，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法（“历史得分”高的走法）排在前面，这样Alpha-Beta搜索就可以尽可能早地进行“裁剪”，从而保证了搜索的效率。 内容来自www.paper51.com 对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并排序的空间复杂度为O(n)，时间复杂度为O(nlog2n)，具有较高的效率。 内容来自www.paper51.com 2.5 局面评估 http://www.paper51.com 前文已经讲过了棋局表示、着法生成、搜索算法（包括搜索辅助）， 在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断和评价。因而搜索与局面评估是整个下棋引擎的核心。 paper51.com 首先，先介绍一下在局面评估中需要考虑的因素。就不同的棋类可能要考虑的因素略有差异。在中国象棋中所要考虑的最基本的几个因素包括如下四点： paper51.com 1、子力总和 http://www.paper51.com
子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值500的话，那可能马值300，卒值80等等。所以在评估局面时，首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。 copyright paper51.com |