1
“理治棋壮”中国象棋计算机博弈引擎
关键算法分析与设计
“理治棋壮”中国象棋计算机博弈引擎开发小组
在《程序架构设计与主要算法概述》一文中，我们阐述了中国象棋计算机博弈涉及的主
要算法。下面就其中的关键算法进行深入分析，并说明其设计实现方法。
一、核心搜索算法
1、Principal Variable Search
搜索算法是计算机博弈程序的核心算法。如何选择适合的搜索算法，配以合理的剪枝条
件，是决定搜索效率的关键所在。博弈树不同于一般的搜索树，它是由对弈双方共同产生的
一种“变性”搜索树。应对这类问题，香农(Claude Shannon)教授早在 1950 年提出了极大-
极小算法（Minimax Algorithm）。这种算法常以一种形式上的改进——负极大值算法出现：
记我方节点值为正，对方节点值为负，双方在每一节点分别选择其子节点中绝对值最大的一
个。递归深度优先遍历有限层次的树，找到使起始节点绝对值最大的一个叶子节点，然后回
溯找到形成这一叶子节点的第一层子节点，作为最优解。
可以在博弈树深度优先搜索过程中记录 2 个附加值，α：我方搜索到的最好值，任何比
它更小的值就没用了；β：对于对手来说最坏的值。在搜索算法中，如果某个节点的结果小
于或等于α，那么它就可以抛弃；如果某个着法的结果大于或等于β，那么整个结点就作废
了，因为对手不希望走到这个局面。如 果某个节点值大于α但小于β，那么这个节点就是可
以考虑走。这便是所谓的α-β剪枝搜索。
