黑白棋回溯算法及论文

•Alpha-Beta剪枝(Alpha-Beta pruning) 对于一般的最大最小搜索，即使每一步只有很少的下法，搜索的位置也会增长非常快；在大多数的中局棋形中，每步平均有十个位置可以下棋，于是假设搜索九步(程序术语称为搜索深度为九)，就要搜索十亿个位置(十的九次方)，极大地限制了电脑的棋力。于是采用了一个方法，叫“alpha-beta剪枝”，它大为减少了检测的数目，提高电脑搜索的速度。各种各样的这种算法用于所有的强力Othello程序。(同样用于其他棋类游戏，如国际象棋和跳棋)。为了搜索九步，一个好的程序只用搜索十万到一百万个位置，而不是没用前的十亿次。 •估值 这是一个程序中最重要的部分，如果这个模块太弱，则就算算法再好也没有用。我将要叙述三种不同的估值函数范例。我相信，大多数的Othello程序都可以归结于此。 棋格表：这种算法的意思是，不同的棋格有不同的值，角的值大而角旁边的格子值要小。忽视对称的话，棋盘上有10个不同的位置，每个格子根据三种可能性赋值：黑棋、白棋和空。更有经验的逼近是在游戏的不同阶段对格子赋予不同的值。例如，角在开局阶段和中局开始阶段比终局阶段更重要。采用这种算法的程序总是很弱(我这样认为)，但另一方面，它很容易实现，于是许多程序开始采用这种逼近。 基于行动力的估值：这种更久远的接近有很强的全局观，而不像棋格表那样局部化。观察表明，许多人类玩者努力获得最大的行动力(可下棋的数目)和潜在行动力(临近对手棋子的空格，见技巧篇)。如果代码有效率的话，可以很快发现，它们提高棋力很多。 基于模版的估值 ：正如上面提及的，许多中等力量的程序经常合并一些边角判断的知识，最大行动力和潜在行动力是全局特性，但是他们可以被切割成局部配置，再加在一起。棋子最少化也是如此。这导致了以下的概括：在估值函数中仅用局部配置(模版)，这通常用单独计算每一行、一列、斜边和角落判断，再加在一起来实现。 估值合并：一般程序的估值基于许多的参数，如行动力、潜在行动力、余裕手、边角判断、稳定子。但是怎么样将他们合并起来得到一个估值呢？一般采用线性合并。设a1，a2，a3，a4为参数，则估值s：=n1*a1+n2*a2+n3*a3+n4*a4。其中n1，n2，n3，n4为常数，术语叫“权重”(weight)，它决定了参数的重要性，它们取决于统计值。