1. 博弈与计算科学
　　也许读者从几年前一些媒体的报道上听说过IBM的超级计算机深蓝与国际象棋最强者卡斯帕罗夫（Kasparov）的大战；也许读者在计算机上玩过和电脑下象棋、国际象棋乃至围棋的游戏。电脑棋手是如何进行思考的？它们是否具和人一样具有智能？
　　
　　在我看来，很多易于接触到的相关的论调都带有极大的误导性。
　　
　　记得小时候曾经听说这样的故事，电脑棋手和一个大师进行对弈，在形势不利、即将落败之际，电脑棋手放电致大师于死地。当然，现在无从考证真正的事实状况和信息来源，但这与其说是信息传播中的扭曲，倒不如说是谣言创造者丰富的幻想能力。如果电脑棋手聪明到这种地步，恐怕所有的人都不是计算机的对手。
　　
　　还有一个很有趣的说法，那就是和电脑棋手下棋时尽量走不符合常规的棋，那样计算机就会不知所措。真是这样的么？我想在看完了第3部分之后，这个问题就会迎刃而解。
　　
　　至于所谓超级计算机深蓝预测足球大赛冠军的言论，已经到了耸人听闻的地步。它的国际象棋下得还不错，但它绝对不可能用它下国际象棋的能力来预测比赛结果。
　　
　　类似下棋的问题被称为博弈问题。狭义地说，博弈中的博是指赌博，而弈就是下棋。赌博并不提倡，在这里所说的博弈就单指下棋。就一局棋而言，一方获胜，则另一方失利，在某些棋类中，如果双方僵持不下，则形成和棋。总之，在一局棋的任何一个时刻，一方获得的利益就相当与另一方的损失。也就是说，不会出现“双赢”的局面。这类问题被称为零和博弈，因为双方的所得加在一起等于0。
　　
　　博弈在计算机上的实现出现在计算机诞生后的十多年间。当人们试图用计算机来模拟人类智能之时，博弈成为了一个典型的问题。当时，人工智能的创始人之一A. L. Samuel编了一个计算机下西洋跳棋的程序。1959年，该程序战胜了设计者本人，1962年则击败了美国的一个州冠军。
　　
　　现在的世界上有各种各样电脑棋手。能够在普通计算机上运行的国际象棋程序已经达到了职业棋手的水平，就黑白棋而言，人类已经不是计算机的对手。但是就围棋而言，计算机与人进行抗衡的路还很遥远。
　　
　　如果电脑棋手战胜了人类棋手，那么是否就可以说它和人一样具有智能？这个问题，将放到最后进行讨论。我首先将向大家展示，电脑棋手是如何下棋的。
　　
　　2. 择优而行
　　电脑棋手下棋的原理，简单地说，就是选出它所认为最有利的下法。
　　|.....A
　　|.../ | \
　　|...B C D
　　|...4 3 -1
　　
　　我们来看上面这个图。假设在某一个时刻，摆在电脑棋手面前的是一个局面A。当然，电脑棋手懂下棋的规则，于是它发现一共有三种符合规则的下法（为了画图方便，所以少了一些，事实上，在国际象棋和中国象棋中，符合规则的下法一般为数十种，围棋则多达两三百种）。这三种下法将分别形成局面B、C、D。现在，我们假设电脑棋手能够判断局面的优劣，为每一个局面都计算一个分数，比如局面B的得分为4，局面C的得分为3，局面D的得分为-1。当然，我们可以作一些规定：分数越高局面越好，分数越低局面越差；当分数为0时表示双方均势，则正分表示电脑棋手方优势，负分表示电脑棋手处于劣势。于是，电脑棋手就选择对它最有利的下法，即第一种下法，最后形成了局面B。此时，在这种情况下，作为一个副产品，那就是局面A被认为是4分，因为后面两种下法对计算机而言是没有意义的，所以B的分数也就是A的分数。
　　
　　接下来的问题是计算机如何做到为每一个局面评出一个得分。这在下棋中被称为形势判断。
　　
　　现在以中国象棋或国际象棋为例（这个问题对围棋而言是很复杂的），最简单的形势判断就是评价以下棋局中双方的子力对比。例如，在中国象棋中，每个车记8分，每个马或炮记3.5分，每个兵、士、相都记1分，将帅无价，姑且记1000分，那么很容易就可以计算出双方的兵力，两者的差就形成了一种最简单的形势判断。当然，这种形势判断是十分粗糙的。
　　
　　稍稍复杂一些的形势判断，除了考虑子力优势之外，还要考虑局面优势。比如一方的马处于十分积极的盘河位置，而另一方的马则还留在原位没有跳出，两者之间显然存在着差距。这时，需要将这些差距折算成分数，加到形势判断中去。在计算机中，这是最通俗、或者说最常用的形势判断方法。
　　
　　一般说，对局面的形势判断可以用一个数学式子计算得出。举一个简单的例子：
　　
　　设在形势中一共考虑n个因素（或特征）。用xi表示第i个因素是否在当前的局面G中出现，如果出现则取1，没有出现则取0，比如第6个因素是指一方的第1个车，那么当这个车还存在时，x6=1，这个车不存在时，x6=0。用wi表示第i个因素在形势判断中所计算的分数，这被称为权重，例如一个车的分数为8，则w6=8。那么对局面G的形势判断为：
　　
　　| f(G)=W1*X1+W2*X2+...Wi*Xi=S(i=1 to i)WiXi
　　
　　符号S被称为累加符，如果读者以前不知道这个符号，只要看着上面的等式，将它想像为在for循环中套了一个加法的命令，就很容易理解了。这是为了书写方便而引入的符号。
　　
　　3. 搜索的魔术
　　如果形势判断十分准确，故事就简单地结束了。可惜的是，问题没有这么简单。我们（无论是计算机还是人类）永远不可能得到一个准确的形势判断。这是因为，形势判断是静态的，而棋局是动态的，要从静态的特征中获取动态的信息，这并非易事。当然，如果需要做到万无一失，那么在形势判断中，必须包括所有可以想到的对局面产生影响的因素，但这时，因素的数量是一个天文数字，我们既不可能对所有的因素都赋一个权重，也不可能在有限的时间内计算出局面的形势判断。
　　
　　我们回过来看，人在下棋时也不能一眼就对静态的局势作出准确的判断，笼统地说，他们往往需要向后面计算几步，看看在走了几步棋之后，局面的形势如何。这被称为“多算胜”，也就是说，谁看得越深远，谁就可以获胜。这个思维方式立刻被用到了计算机上。
　　
　　3.1 最小最大树
　　以第2部分中出现过的图为例，假设向后再多考虑一步，得到下图
　　|...........A
　　|........./ | \
　　|........B C D
　　|......./ | / \ | \
　　|.......E F G H I J
　　|.......5 3 2.5 2 -2 10
　　
　　这是一棵树。从图中看到，假设在三个局面B、C、D下，都恰好有两种符合规则的下法，可以形成局面E、F、G、H、I、J，而这些局面的形势判断已经得到了。电脑棋手的任务是利用这些已知条件，选择局面B、C、D的中对它最有利的一个局面。我们可以发现，局面J的得分最大，那么是不是应该选择局面D，以便形成对电脑棋手最有利的局面J呢？
　　
　　假设电脑棋手的对手（可能是人，也可能是一个计算机程序，现在为了便于说明问题时不产生混淆，假设对手是人）面对的是局面B，那么他一定会选择对自己最有利的下法。由于是零和博弈，对人最有利的下法就是计算机最不利的下法，那么在E和F之中，他会选择F。这时，如果电脑棋手选择局面B，那么对方就会选择F，最后电脑棋手得到的结果是3，也就是说，B的形势判断结果应该为3。同样道理，如果人处于C中，他会选择H，于是f(C) = f(H) = 2。同理，f(D) = -2。最后，发现是B的得分最高，因此电脑会选择B，此时f(A) = f(B) = 3。
　　
　　按前面的猜测，如果因为f(J)=10而计算机选择了局面D，那么对手就会选择I，最后计算机得到了最差的结果-2。
　　
　　从这里我们可以看出，在电脑棋手下棋的局面中，它总是选择下一个层次中由该局面衍生出的局面中得分最高的，而在对手下棋的局面中，它总是选择下一个层次中由该局面衍生出的局面中得分最低的。用数据结构中的术语，假设对于某一个局面，已经将在几步棋之后的所有可能形成的局面的得分都计算了出来，那么从这棵树的最底层一层层向上推，在对手下棋的层次中，每一个结点取其子结点的最小值，在电脑下棋的层次中，每一个结点取子结点的最大值。这就被称为最小最大树。
　　
　　最后，问题转化为对某一局面下衍生出的最小最大树的遍历。这种遍历用一个深度优先搜索就很可以处理了。在搜索的过程中，当前路径上的每一个结点上都保存着搜索到目前为止的当前最优值。搜索用一个递归函数实现，该函数的功能是计算某个结点的最优值。每当一个结点得到子结点的返回值时，就从当前最优值和返回值中选取一个更优的值作为当前最优值。当一个结点的子结点都搜索完毕之时，其当前最优值就是该结点的实际最优值，也就是这个结点的得分，这时，将这个值返回其父结点。下面给出最大最小搜索的伪码：