摘要：本文简单的介绍了计算机博弈算法。计算机博弈在某种形式上属于人工智能，而本文只介绍一下其中的一种简单形式——零和博弈，并给出了一个实例――黑白棋。
关键字：搜索，估值，剪枝，Alpha-Beta，零和博弈
引言
随着计算机处理速度的飞速提高，人们很早就提出了疑问：计算机是否会超越人类？世界国际象棋大师已被计算机打败，计算机已经超过了人类？看完本文，相信你会对计算机棋手的智能有所了解。
概念
什么是博弈？狭义地说，博弈中的博是指赌博，而弈就是下棋。赌博并不提倡，在这里所说的博弈就单指下棋。就一局棋而言，一方获胜，则另一方失利，在某些棋类中，如果双方僵持不下，则形成和棋。总之，在一局棋的任何一个时刻，一方获得的利益就相当于另一方的损失。也就是说，不会出现“双赢”的局面。这类问题被称为零和博弈，因为双方的所得加在一起等于0。
优胜劣汰
人类在下棋时一定会选择对自己最有利的走法，计算机也一样，人们编写的下棋程序也继承了人类的思考方法，即找到对自己最有利的走法。这种最有利的走法通常是可以赢得胜利的走法，比如象棋中某个走法可以将对方将死，又如黑白棋中棋子数多的一方胜利，那么我们的走法就要尽量是自己的棋子多，而对手的棋子少，当然，这样的黑白棋棋力很弱，后面会讲到这个问题。
搜索算法
但是棋类游戏不可能一步就决出胜负，象棋中不可能第一步就将对方将死；而对某个棋局的判断也不可能完全精确，在黑白棋中，初局时棋子多并不一定最终取得胜利，因为对手可能在后面的博弈过程中将局面扭转。想想人类下棋时，一般会假设我走这步，那么对手会怎样回应，如果对手回应了某一步，我再走哪一步，如果对手回应了另外某一步，我又该怎么走；然后再假设我走另外的某一步，如此反复下去。这个过程叫做搜索。
在这里我们要先回顾一下“树”这种数据结构以及树的遍历，如图一。
图一
图一是一个三层，12节点的树。树的遍历有深度优先遍历和广度优先遍历（如果对这些概念不清楚，请参考数据结构的书籍），深度优先遍历由于编程简单，内存占用小，在博弈中用的较多。现在我们假设一个棋局，计算机先走，它可以有若干种走法，而对应每种走法，计算机的对手又有若干种走法，将这句话展开，就得到了类似图一的一棵树。就拿图一来说，初始棋局是A，此时计算机有3种走法，分别导致棋局B、C、D，对于棋局B，计算机的对手有3种走法，分别导致棋局E、F、G，对于棋局C，对手的走法又导致棋局H、I，等等。
那么对于初始棋局A，计算机应该选择哪种走法呢？显然，计算机要选择B、C、D中对自己最有利的，对于这种有利与不利而言，计算机一般以分值来表示，比如对计算机越有利，分值越高，不少程序为了直观，将对双方平等的局面设为0分。但B、C、D局面并不是棋局结束，棋局还要继续下去，而且轮到对手走棋了，这时对于棋局B，对手也要从E、F、G中选择一个对他自己最有利的，对于棋局C，对手要从H、I中选择一个对他自己最有利的。注意，对对手最有利就是对自己最不利，因此，B的得分应该是E、F、G中最小的，C的得分应该是H、I中最小的，等等；而A的得分应该是B、C、D中最大的。这就是极大极小搜索的基本原理。
关于搜索，还有一个重要的问题，就是计算机的对手。在搜索过程中，计算机需要假设一个对手，而这个对手要是足够聪明的。那么这个对手是谁呢？实际上这个对手就是计算机自己。
如果我们将这棵树不停的扩展下去，直到棋局分出输赢，那么我们就建立了一棵完整的博弈树，称为最大最小树，树中包含了下棋过程中所有可能出现的棋局，而且树的叶子节点都是可以分胜负的棋局。这真是一个好办法，只要建立这棵完整的博弈树就可以找到一条通往胜利的路，真是太好了。但是稍加分析就知道，这棵树根本建立不起来。比如象棋，可以把一个棋子来回的移动，这棵树就没有了尽头；对于黑白棋来说，虽然棋局结束是肯定的，但是这棵树上的节点也是天文数字，即使1秒钟能生成10^10个节点，这棵树的生成时间也是天文数字。因此建立完整博弈树是完全不实用的。
局面估值
但是我们仍然会下棋，而且水平还不错，这是为什么呢？因为我们会估计，即对棋局进行评估。比如象棋的某个局面，我车马炮齐全，而你已经没有车了，那么这个局面显然对我有利。在黑白棋里，我的棋子比你多，那么就对我有利。（注：这个评估方法实际上很差，因为黑白棋存在吃子的问题，而且一步吃子可达到10个以上，所以当前局面对我有利，但下一个局面就不一定了，所以比较棋子个数的评估方法一般都是在最后一步使用，即所谓的终局）
在博弈程序中，我们也要把这个方法教给计算机。计算机只进行有限深度的搜索，到达某一深度时，将停止搜索，而改用对局面的静态估值，将这个估值作为节点的值。这样，计算机就可以考察若干步之后的局面，从而找到一个最佳的走法。当然，这个“最佳”是在对手和计算机同等聪明的情况下得出的。
很显然，对局面的估值无论怎样都不可能精确，否则就没有搜索的必要了。但估值必须要有大致精确的方向，只有这样才能让搜索引擎向着正确的方向搜索。不同程序的棋力差别也源自估值函数，在相同搜索深度的情况下，不同的搜索引擎决定了效率，而估值函数决定了棋力。
估值这部分和程序编写者自身的知识有很大的关系，很难想象一个对黑白棋不精通的人能写出棋力很强的程序。
综合应用
将搜索算法、走法生成和局面估值结合在一起就可以得到一个最简单的、可以实用的程序了。在这里用伪码的形式作个实例。
int MinMax(局面 p, int depth)//depth是搜索深度
{
int bestvalue, value;
//一般来说，这里有一个判断棋局是否结束的函数，一旦棋局结束就不必继续搜索了，直接返回极值。但由于黑白棋不存在中途结束的情况，故省略。
If(depth<=0)//叶子节点
{
返回估值(p);//直接返回对局面的估值
}
if(当前是计算机走棋)
{
bestvalue=-INF;//初始最佳值设为负无穷
}
else
{
bestvalue=INF;// 初始最佳值设为正无穷
}
for(每一个合法的走法)//走法的生成与具体问题紧密相关，具体方法省略
{
走一步棋;//局面p随之改变
value=MinMax(p, depth-1);//搜索子节点
撤销刚才的一步;//恢复局面p
if(当前是计算机走棋)
{
if(value>bestvalue)//取最大值
{
bestvalue=value;
if(是初始局面)
{
保存最佳走法;
}
}
}
else
{
if(value<bestvalue)//取最小值
{
bestvalue=value;
}
}
}
return bestvalue;
}
这个极大极小搜索有些繁琐，需要根据当前走棋方来分别进行极大和极小搜索。考虑到对手的利益就是自己的损失，这样就引出了负极大搜索算法。它没有极大极小那么容易理解，但却很简洁，不用判断当前走棋方。但负极大中的估值却是对走棋方敏感的，因此函数参数中需要有一个走棋方的参数
long NegaMax(局面 p, ing Side, int depth)//depth是搜索深度
{
int bestvalue, value;
If(depth<=0)//叶子节点
{
返回估值(p, Side);//直接返回对局面的估值
}
bestvalue=-INF;//初始最佳值设为负无穷
for(每一个合法的走法)//走法的生成与具体问题紧密相关，具体方法省略
{
走一步棋;//局面p随之改变
value= - NegaMax(p, opSide, depth-1);//搜索子节点，注意前面的负号，opSide是对手
撤销刚才的一步;//恢复局面p
if(value>bestvalue)//取最大值
{
bestvalue=value;
if(是初始局面)
{
保存最佳走法;
}
}
}
return bestvalue;
}
看到这里，读者完全可以编写出一个黑白棋的智能模块来了。只要加上走法生成和估值函数就可以了。在压缩包里有我写的一个最简单的黑白棋智能模块程序，如果装了BCB6就可以直接编译、试验了。当然，为了说明原理，这个实例程序没有做优化，速度很慢。读者可以自己想办法优化它，比如用10*10的棋盘以避免边界检查，或者用一维数组来表示棋盘，用比特棋盘技术等，速度更快，我估计优化能提高性能至少30%。另外，估值部分也过于简单，棋力非常弱，同样读者可以自己编写估值函数来提高棋力。还有比如终局搜索等方面，读者也可以自己搜索相关的资料。
搜索算法的加强
极大极小搜索的效率是很低的，因为要对所有的节点进行搜索，使得搜索节点数随着搜索深度的增加而剧增。假设每个局面有10种走法，那么搜索6层就要搜索10^6个节点，而9层则要搜索10^9节点，这种增长速度是无法忍受的。幸好，这个问题是可以解决的，这就是Alpha-Beta剪枝。
以下内容基本摘自黑白棋世界网站( http://blacwet.yeah.net )
请看一个搜索树的片段，节点表示落子点，节点边上的数字是该节点的值。
现在，我们假设先搜索e3-f2 f3 f4 f5 f6，再搜索c3-c2 d3 e6 f5，再c5-b6 c6 d6 e6 f6。这样我们会发现，在搜索完e3分支后，根节点（就是初始棋局）的值是(-1)，参见极大极小搜索算法。搜索到d3分支后就不用再搜索e6和f5了，因为如果接下来的值比d3大，就不会赋值给c3，如果比d3小，赋值给c3后也不会赋值给根节点，因为根节点取最大值，现在根节点是(-1)，不会取更小的值。同样，搜索到d6后就不用再搜索e6和f6了。也就是说，搜索到小于等于(-1)的值后就不用再搜索了。
在搜索过程中，电脑下棋结点的当前最优值被称为α 值（即初始棋局的值），对手下棋结点的当前最优值被称为 β值（即例子中C3的值）。在搜索开始时，α 值为负无穷，β值为正无穷，在搜索过程中，α 值递增， β值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于β 值，则发生剪枝。
int AlphaBeta(局面 p, int depth, int alpha, int beta)//depth是搜索深度
{
int value,bestvalue;
//一般来说，这里有一个判断棋局是否结束的函数，一旦棋局结束就不必继续搜索了，直接返回极值。但由于黑白棋不存在中途结束的情况，故省略。
If(depth<=0)//叶子节点
{
返回估值(p);//直接返回对局面的估值
}
for(每一个合法的走法)//走法的生成与具体问题紧密相关，具体方法省略
{
走一步棋;//局面p随之改变
value=MinMax(p, depth-1, alpha, beta);//搜索子节点
撤销刚才的一步;//恢复局面p
if(当前是计算机走棋)
{
if(value>alpha)//取最大值
{
alpha=value;
bestvalue=alpha;
if(是初始局面)
{
保存最佳走法;
}
if(alpha>=beta)
{
return beta;//剪枝
}
}
}
else
{
if(value<beta)//取最小值
{
beta=value;
bestvalue=beta;
if(alpha>=beta)
{
return alpha;//剪枝
}
}
}
}
return bestvalue;
}
同样，Alpha-Beta也有类似负极大的简洁形式，这是实用程序中是最常用的。
long NegaAlphaBeta(局面 p, ing Side, int depth, long alpha, long beta)//depth是搜索深度
{
int value;
If(depth<=0)//叶子节点
{
返回估值(p, Side);//直接返回对局面的估值
}
for(每一个合法的走法)//走法的生成与具体问题紧密相关，具体方法省略
{
走一步棋;//局面p随之改变
value= - NegaAlphaBeta(p, opSide, depth-1, -beta, -alpha);//搜索子节点，注意前面的负号，opSide是对手
撤销刚才的一步;//恢复局面p
if(value>=alpha)//取最大值
{
alpha=value;
if(是初始局面)
{
保存最佳走法;
}
if(alpha>=beta)
{
break;//剪枝
}
}
}
return alpha;
}
需要注意的是Alpha-Beta剪枝对搜索顺序极为敏感，就上面的棋局来说，如果搜索c5时的顺序是c5-d6 b6 c6 e6 f6，那么就会将四个节点都剪枝，注意剪枝不仅剪去了节点本身，而且也将那些节点下的子树也都剪枝了，但如果是c5-b6 c6 e6 f6 d6，就一个节点也没有剪枝。在节点排列最坏的情况下，Alpha-Beta和极大极小是一样的，都要搜索全部节点。因此，根据某些信息来对节点排序是非常重要的。
我没有写Alpha-Beta的程序例，这对看懂了极大极小算法和Alpha-Beta剪枝的原理的读者来说很容易，自己把代码写出来，对自己是一个实践的机会，有很大的帮助。
除了Alpha-Beta，还有多种加强的方案，如PVS，MTD(f)，MPC等，还有置换表，历史启发等多种技术。推荐一本书《PC游戏编程（人机博弈）》，里面讲了很多种方法，并有中国象棋程序例。
看到这里，是不是有自己写一个智能程序的想法呢？和自己的程序下一盘棋，看看是人厉害还是程序厉害。我自己下棋的水平不高，会的棋类也不多，想来想去最后决定用黑白棋作为实例来写这篇文章。以下内容是给黑白棋初学者看的，高手完全可以自己编写估值函数，和你们的程序比试去吧。
黑白棋初学者指南
用这个标题是因为在国内了解黑白棋的人好像并不多，这里顺便就把黑白棋的游戏规则也讲一下。要编写出好的程序，自己首先要精通它。为了让读者集中精力设计智能部分，我将智能模块和界面、输赢判断程序分开了，这样大家只要实现一个DLL就可以了。
下棋方法
黑白棋的棋盘是一个有8*8方格的棋盘。下棋时将棋下在空格中间，而不是像围棋一样下在交叉点上。开始时在棋盘正中有一白一黑四个棋子交叉放置，黑棋总是先下子。
下子的方法是：把自己颜色的棋子放在棋盘的空格上，而当自己放下的棋子在横、竖、斜八个方向內有一个自己的棋子，则被夹在中间的全部会成为自己的棋子。并且，只有在可以翻转棋子的地方才可以下子，而且，当有棋可走时必须走棋。如果棋盘上没有地方可以下子，则该对手连下。
棋局结束条件
双方都没有棋子可以下时棋局结束，棋子多的一方获胜。
计分方法
现行的规定是：双方分先下偶数局数的棋(如4局)，胜1分，负0分，平0.5分，分数多的取胜。假如分数一样，就以棋子数目来计算胜负。那么棋子数目怎么判断呢？如果双方将棋盘下满，当然好判断。如果棋局结束，黑棋有34个子，白棋有30个子，那么黑棋胜34-30=4个子。但是如果棋盘没下满呢，如黑棋有34个子，白棋有27个子。此时有两种计分方法：日本的计分法是，剩余的空格全部给胜方，那么黑棋胜34+3-27=10个子。欧洲的计分法是，剩余的空格双方各得一半，那么黑棋胜(34+1.5)-(27+1.5)=7个子。
估值技术
前面已经说过，对局面估值是决定棋力的根本因素，像例子程序中的直接比较双方棋子个数的估值方法是相当弱的，那么怎样估值才好呢？目前的黑白棋程序使用的估值方法大致有三种，基于棋子位置价值的估值、基于行动力的估值和基于模板的估值。基于模板的估值由于我不了解，说不出个所以然来。这里就讲一下另两种估值方法。
1、基于棋子位置价值的估值
很多人刚学会黑白棋的时候往往贪多，总想吃掉对方更多的棋子，结果往往输得很惨。但他们逐渐就会发现要领，四个角落上的棋子永远不会被翻，因此角落上的棋子有很高的价值，而边上的棋子也不容易被翻，价值也较高，特别的，如果某个角落上有自己的棋子，那么紧靠这个角落的三个棋子也有较高的价值。这就是基于棋子位置价值的估值的基本原理，棋盘上的每个位置有不同的价值，角落的价值最大，要防止对手占据角落，自己就要避免走在角落周围，因此在角落上没有棋子时角落周围的价值应该很低，但如果角落上已经有自己的棋子，情况又不同了。所以，一般来说要为自己和对手各准备一张棋子位置价值表，并且还要设计成动态的，即每次估值前先根据当前棋局来调整这两张价值表。
这种估值方法实现起来很简单，速度也快，因此在很多初学者编写的程序中使用。使用这种估值方法的程序棋力不强，但由于多由初学者编写，它还是有可能击败它的作者的。
2、基于行动力的估值
更好的估值方法是根据行动力和潜在行动力来估值。首先介绍这两个概念。行动力是指一个局面上可以下棋的地方的多少，比如某个局面有10个地方可以走棋，那么行动力就是10。潜在行动力一般指对手棋子周围的空格数，因为只有对手棋子旁边的空格处才是可能可以走棋的地方，因此在一个局面上，对手旁边的空格越多对自己越有利，这就是潜在行动力估值。
在实际的程序中，行动力估值一般要和棋子位置价值联合使用。有时虽然行动力不高，但每一个地方都是好棋，那也是值得的。
总之，原则就是给自己留下好棋，而要让对手没有好棋可走。这种估值方法比较强，编写的好的话，初学者一般都下不赢自己的程序。
终局搜索
黑白棋有其自身的特点，就是棋局一定会结束，并且棋局什么时候结束也是确定的。在棋局结束前的十几步，剩下的空格往往都在角落上，而这正是双方争夺的重点地区。这种离棋局结束的十几步称为终局。而采取行动力的估值方法常常导致一个结果，就是自己的棋子非常少（请考虑一下这是为什么）。而黑白棋的胜负仅有棋子个数决定，这样行动力估值在终局时有些不适用。
其实黑白棋的终局是非常简单的，只需考虑棋子个数就可以了，其他的因素都不用考虑了，这样估值速度会提高很多，搜索深度也能更深一些，一般终局搜索10层是轻而易举的，好的程序可以搜索20层左右。
实际编程时，一般是首先统计棋局中空格的个数，如果大于某个值（比如12）就调用综合各种估值的搜索函数，否则直接进入终局搜索，并且终局搜索的深度设为12，这样程序就能一直搜索到棋局结束。采用这种方法，一般人是很难下赢程序的，尤其是在终局，如果程序在终局开始时判断出你已经输了，那你就肯定输了，而且一般会输得更惨。
文章到这里就结束了，感谢黑白棋世界网站（http://blacwet.yeah.net），让我学到了很多关于黑白棋的知识。最后，祝大家都能写出强力的黑白棋程序！
2004-09-23 北京
实例可以到我主页下载。
