发布时间 : 星期六 文章黑白棋更新完毕开始阅读
3. 方案实施
3.1数据结构设计
现在有如图示的这样一个棋局，轮到电脑下棋。现在它发现有这样三个地方可以下：e3,c3,c5。这三种下法分别会形成三种局面：A、B、C。如果是人在下棋，就会思考：那一种下法更好呢？比如A被别人占角，B没什么变化，C占了别人的角。当然棋手会选择下C。电脑也是如此，它会对每一种棋局评一个分，比如它判断，如果被别人占角，就减80分，相反占别人的角就加80分。那么A=-80分,B=0分,C=80分。电脑会选择下C。电脑程序对棋局评分的部分，称为“估值函数”(Evaluation Function)。真正的估值函数当然不会这么简单。它会用到技巧篇提到的如行动力、潜在行动力、余裕手、边角判断、稳定子等综合因素来判断。具体的估值函数，我会在“估值函数”一节中详细讲述。
初始棋局(-1)
------------------+------------------ | | | e3 c3 c5 (A) (B) (C)
接下来，如果人就这么判断。那么它顶多也就是个初学者。为什么呢？因为它不会推理，碰到对手弃角之类的战术，如“边角判断”中示例的一些情况，就输得一塌糊涂了。当然，可以告诉电脑，碰到“边角判断”中的几种情况，就如何如何下。但是，真实的棋局是非常复杂的，电脑（也包括人脑）几乎不可能对动态的棋局给出静态的评估。因为实际对局总会出现这样那样的情况，是无法预先估计的。碰到这些情况，人就会向后推几步，看一看会是怎样的一个局面。一些棋类大师往往可以推十几步甚至更深。电脑也是如此。
还是刚才那一幅图的演化。 甲方下棋 - 乙方下棋 -
初始棋局
------------------+------------------ | | | e3 c3 c5
-----+----- ----+---- -----+----- | | | | | | | | | | | | | | f2 f3 f4 f5 f6 c2 d3 e6 f5 b6 c6 d6 e6 f6 +84+36+12 +5 -1 +11 -1 +6 +6 +6 +0 -5 +3 +5
电脑在自己下棋以后，把对手的下棋情况也推理出来。然后加以评分。（最下一排是电脑评估的得分）这一次电脑又如何下呢？这时电脑假设对手是高手。如果电脑下e3，对手就会下对电脑最不利的情况f6。同样，电脑下c3，对手就会下d3，电脑下c5，对手就会下d6。这三种情况，c5是最不好的(因为c5的下一步d6的得分最低)，c3与e3一样。因此电脑会下c3或者e3。用程序化的语言这样描述：
如上图所示棋局，设电脑为白棋，推理深度为2，可以形成如下的树：（数字为节点值）
初始棋局 -
白棋下棋之后 -
黑棋下棋之后 估值
初始棋局(-1)
------------------+------------------ | | | e3(-1) c3(-1) c5(-5) -----+----- ----+---- -----+----- | | | | | | | | | | | | | | f2 f3 f4 f5 f6 c2 d3 e6 f5 b6 c6 d6 e6 f6 +84+36+12 +5 -1 +11 -1 +6 +6 +6 +0 -5 +3 +5 结果:应该下e3或c3
具体实现的伪算法类似于经典的八皇后问题。
还有几种alpha-beta算法的改进型，最广泛采用的是NegaScout，(Alexander Reinefeld发明)，但它和一般的alpha-beta剪枝算法没有根本的不同。其他的还有PVS和SSS*。下面举例说明。
还是基于刚才的棋形，假设先搜索e3-f2 f3 f4 f5 f6、再c3-c2 d3 e6 f5、再c5-b6 c6 d6 e6 f6，即从左至右的顺序的深度优先搜索。则搜索到d3分枝之后，就不用搜索e6和f5了。因为如果接下来的值比d3大，就不会赋值给c3，如果比d3小，赋值给c3后，也不会赋给根节点，因为根节点取最大的值，现在根节点的值是-1，不会取更小的值。同样的，搜索d6后，也不用搜索e6、f6了，也就是说，搜索到比-1还小的值之后，就不用搜索了。
在搜索过程中，电脑下棋结点的当前最优值被称为α 值（即初始棋局的值），对手下棋结点的当前最优值被称为 β值（即例子中C3的值）。在搜索过程中，α 值递增，β值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于β 值，则发生剪枝。
初始棋局(-1)
------------------+------------------ | | | e3(-1) c3(-1) c5(-5) -----+----- ----+---- -----+----- | | | | | | | | | | | | | | f2 f3 f4 f5 f6 c2 d3 e6 f5 b6 c6 d6 e6 f6 +84+36+12 +5 -1 +11 -1 +6 +6 +6 +0 -5 +3 +5
这是一个程序中最重要的部分，如果这个模块太弱，则就算算法再好也没有用。这里将要叙述三种不同的估值函数范例。大多数的黑白棋程序都可以归结于此。
这种算法的意思是，不同的棋格有不同的值，角的值大而角旁边的格子值要小。忽视对称的话，棋盘上有10个不同的位置，每个格子根据三种可能性赋值：黑棋、白棋和空。更有经验的逼近是在游戏的不同阶段对格子赋予不同的值。例如，角在开局阶段和中局开始阶段比终局阶段更重要。
这种更久远的接近有很强的全局观，而不像棋格表那样局部化。观察表明，许
多人类玩者努力获得最大的行动力(可下棋的数目)和潜在行动力(临近对手棋子的空格，见技巧篇)。如果代码有效率的话，可以很快发现，它们提高棋力很多。和另一种人类的策略一样，许多基于行动力估值的程序同时还有一些边角配置的知识，试图在中盘早期使棋子最少。
正如上面提及的，许多中等力量的程序经常合并一些边角判断的知识，最大行动力和潜在行动力是全局特性，但是他们可以被切割成局部配置，再加在一起。棋子最少化也是如此。 这导致了以下的概括：在估值函数中仅用局部配置(模版)，通常单独计算每一行、一列、斜边和角落的模板，再线性叠加在一起来实现。并且，配置情况的值非常依赖于游戏的不同阶段。比如，一条边有3321种配置情况((3^8-3^4)/2+3^4)，每种情况的分值好坏在游戏的不同阶段都不相同。分值基于强力玩者和程序的游戏结果统计，他们存于数据库中，游戏启动时自动调入。 常见的有这样一些模板： 数据表
名称 类似区域 配置数 去掉对称后的配置数
corner5x2 a1:e2 3^10=59049 (3^10-3^5)/2+3^5 = 29646 diag5 a5:e1 3^5 =243 (3^5 -3^3)/2+3^3 = 135 diag6 a6:f1 3^6 =729 (3^6 -3^3)/2+3^3 = 378 diag7 a7:g1 3^7 =2187 (3^7 -3^4)/2+3^4 = 1134 diag8 a8:h1 3^8 =6561 (3^8 -3^4)/2+3^4 = 3321
edge2x a1:h1 + b2 + g2 3^10=59049 (3^10-3^5)/2+3^5 = 29646 hor2 a2:h2 3^8 =6561 (3^8 -3^4)/2+3^4 = 3321 hor3 a3:h3 3^8 =6561 (3^8 -3^4)/2+3^4 = 3321 hor4 a4:h4 3^8 =6561 (3^8 -3^4)/2+3^4 = 3321
triangle a1:a4:d1 3^10=59049 (3^10-3^5)/2+3^5 = 29646
般程序的估值基于许多的参数，如行动力、潜在行动力、余裕手、边角判断、稳定子(见技巧篇)。但是怎么样将他们合并起来得到一个估值呢？为了提高速度，一般的程序采用线性合并。设a1，a2，a3，a4为参数，则估值s：=n1*a1+n2*a2+n3*a3+n4*a4。其中n1，n2，n3，n4为常数，术语叫“权重”(weight)，它决定了参数的重要性，来自于统计值。
所的强力程序都采用了开局定式，许多顶级程序的定式大多来自IOS游戏。对于强力的