2.2 中国象棋博弈程序
为了理解计算机如何像人一样下棋，我们先看看人是怎样下棋的。
第一步，理解局面。当前局面双方子力及分布情况，双方走时情况，是否被将军，如被将军必须解将。
第二步，考虑走法。当前局面不止一种走法，同时走每一步棋都要考虑对手会如何应对，对手应对之后自己又能怎样应对，这样不断嵌套下去。一个选手能考虑走棋的深度（或者叫步数），与选手下棋能力有直接的关系。水平越高的棋手，考虑的步数越多。
第三步，判断。有多种走法的时候，棋手必须也只能选择一种走法。棋手如何从多种走法中选择呢，当然是选择对自己最有利的走法。这就引起了一个问题，棋手如何对多种走法的结果进行判断呢。
考虑走法与判断不是截然分开的两个阶段，可能是边想一个走法，边判断它可能的结果，如果结果明显太坏，则不会从这个走法进行更深的考虑。考虑走法的时候，棋手必须要理解行棋规则，不能走出违背棋规的走法。
棋手思考的过程可以用图2-2来表示。
图2-2 棋手走棋示意图
人脑的思考是走棋的核心，局面作为思考的输入条件，行棋规则和判断方法作为思考的辅助手段，最后得出最佳走法。
要想让计算机像人一样走棋，则必须让计算机理解棋手走棋的过程，进而模仿这一过程。将棋手走棋示意图变换一下，可以得到计算机走棋示意图，如图2-3所示。
图2-3 计算机走棋示意图
2.2.1 局面表示
在前面已经提到局面这个术语，那什么是局面？在日常生活中我们也常说局面，局面就是局势、形势、情况等的含义。在中国象棋博弈中，局面就是一盘棋经过若干回合之后当前所处的形势，可以有狭义和广义的理解。
狭义的局面包含：
1. 棋盘。在五子棋程序中，我们可以在10×10，15×15，20×20等的不同规格的棋盘上下；在围棋程序中，除了在标准的19×19棋盘上下以外，在博弈程序中我们也常常降低难度，在15×15，9×9等棋盘上下。但是对中国象棋而言，不可能有其他形势的棋盘，必须是10×9的格式。
2. 棋子。红黑双方所剩棋子及其在棋盘上的分布。
3. 当前该走棋一方。
广义的局面除了包含狭义局面的内容，还包含：
1. 双方所剩时间。正规比赛都有时间限制，棋手必须根据局面形势来合理分配所剩时间。博弈程序更要注意时间，因为搜索最佳走法一般都是递归函数，很消耗时间，必须控制时间及时退出递归，返回一个最佳走法。
2. 双方所剩走棋步数。很多比赛规定棋手必须在规定时间内走出规定的走法步数，所以必须记下还有多少步没有走，有利于棋手分配时间。
在象棋竞赛规则中就列举了如下5种计时方法：
（1）第一时限，每方在90分钟内必须走满40步。以后每15分钟内必须走满10步，直至对局结束。
（2）第一时限，每方在60分钟内必须走满30步。以后每10分钟内必须走满10步，直至对局结束。
（3）第一时限，每方在10分钟内必须走满40步。以后每5分钟内必须走满30步，直至对局结束。适用于快棋赛。
（4）每方每5分钟内必须走满30步，直至对局结束。——适用于快棋赛。
（5）每方时间包干使用，不计步数，先超时者判负。
当然可以根据比赛性质另外拟定计时规则，包干计时制则根据比赛天数、棋手多少来制定包干时间。
3. 局面是否将军。棋例细则第一条就规定，在任何情况下，均不许可单方面长将。记录局面是否将军有助于判断是否存在单方面长将。
4. 未吃子步数。规则规定，“符合自然限步的回合规定，即在连续60个回合中(也可根据比赛等级酌减)，双方都没有吃过一个棋子。”判为和棋。
5. 历史走法。记录历史走法，有利于判断是否存在长将、长杀、长捉，以及循环局面出现。
要让计算机走棋，必须首先要让计算机理解当前的局面。计算机不能像棋手看一眼就明白，它是无法看的，必须把局面表示成计算机能够理解的数据结构并存储在存储器中，这就是局面表示。必须把当前局面的所有信息，存储在存储器中。并且这些信息会随着比赛的进程及时更新，使存储器中存储着正确的局面信息。
局面表示注意事项：
存储方便：比赛一开始，要能在计算机中快速创建局面并保存起来。
修改方便：不论哪方走一步棋，局面就会发生改变，计算机要能快速在存储器中修改局面，使存储器始终保存最新的局面。
运算方便：局面表示方法的好坏，直接影响着走法生成、局面评估及搜索算法的效率。一种好的局面表示数据结构可以大大提高走法生成、评估函数及搜索算法的速度，使计算机思考得更快、更深。
2.2.2 走法生成
走法生成就是生成一个局面所有可能的走法。可以一次性生成所有走法，也可以分步骤生成走法，如先生成吃子走法，再生成不吃子走法。
中国象棋规则规定了每一种棋子的行棋方法，“马走斜日象飞田，车走直路炮翻山，兵卒过河横顺走，士象不离老王边”。同时还有一些特殊的棋例，如不能长打、长捉，照将必须解将，不能吃本方棋子，等等。计算机在思考走棋的时候必须考虑这些棋规，不然很容易就会违规的。
另外还要考虑棋盘边界，不能将棋子走到棋盘以外。棋手下棋是不可能走到棋盘以外的，因为边界外没有横竖交叉点。计算机程序不能直观的理解棋盘边界，必须通过边界条件来判断。
博弈程序在搜索最佳走法的时候，要反复调用走法生成的函数，所以走法生成函数的效率对程序影响比较大。
2.2.3 搜索算法
在一些简单的游戏中，棋子行棋空间小，局面变化不多，搜索空间不大，计算机可以很快穷举所有的可能。如Tic-Tac-Toe游戏，九个位置，双方轮流布棋，某方三个棋子连成一条线（直线，对角线）为胜，均无三子连成直线为平。
第1子有9种可能位置，第2子有8种可能位置，第3子有7种可能位置，……第8子有两种可能位置，最后一子只有1个位置。所以最大的搜索空间为：
9·8·7·6·5·4·3·2·1 = 362880
以CPU每秒运算1亿次，现在的计算机一眨眼功夫就可以搜索完毕。已经知道是，Tic-Tac-Toe游戏没有必胜局面，因此计算机玩这种游戏可以说永不言败。即使人掌握了一些基本技巧也很难说败。
但是中国象棋的局面变化实在是太多了，有时候一个局面可能走法达100多种，一般局面也有40多种走法。如表2-1列出了搜索空间与搜索时间随搜索深度的变化情况。每个局面按40种走法计，计算机运算能力按每秒运算108次（1亿次）计，或者说每秒搜索108个结点。
表2-1 搜索空间与搜索时间随深度变化表
要完全搜索10步棋需要3.3年，即使完全搜索7步棋也要27分钟。按一盘棋平均100步（50个回合）计，要完全搜索100步是绝对不可能的。
如何让计算机在有限的时间内搜索到更多的空间，搜索到更深的步数，是计算机博弈程序必须考虑的问题。这除了与计算机硬件有关之外，与搜索算法关系很大，这是因为在搜索树空间中有些分支是多余的，搜索的时候可以跳过某些分支。跳过的分支越多，搜索的速度越快，但漏掉最优解的可能性也在增加。搜索算法必须又快又准的找到最优解。
2.2.4 局面评估
一盘棋结束时，对棋手而言只有3种结果，胜、平、负。胜负很容易判断，一方吃掉另一方的将（帅），或者一方主动认输。平局可以是双方认和，也可以由裁判根据规则判和。如果搜索函数能搜索到棋局终了的状态，如像玩Tic-Tac-Toe游戏，那么局面评估只是简单的判别胜、平、负的关系，这花不了多少时间。正如前面所讲，花27分钟搜索7步都是不能容忍的，更何况搜索100步到棋局终了。显而易见，搜索必须在某个深度的结点上结束并返回上一层，这个结点并没有达到棋局结束（胜平负），应该给它一个值，反映局面状况，对红方有利还是对黑方有利，有多少优势。必须把这种优势量化，以便于不同结点的优势可以比较，以确定哪一个结点更好。
局面评估就是判断局面对红方（或者黑方，或者是当前走棋一方）的优势，并把优势进行量化。
假设红方获胜的局面分值为1（不论红方以多大的优势获胜），黑方获胜的局面分值为-1（不论黑方以多大的优势获胜），平局分值为0。所有可能局面的分值则在-1～1之间。局面评估分值是一个相对的概念，是一个红方（黑方）相对的优势情况。如果你愿意，也可以把分值设为从-100到100，也可以从-1000到1000。
局面评估函数模拟棋手在下棋时对局面的考虑。不同棋手对同一局面有不同的认识，程序也如此，不同程序员根据自己对象棋的理解写出的评估函数肯定也不一样。
评估函数对象棋程序实力的影响，是当在其他条件相同的情况下，评估越精确则走棋质量越高。一般根据程序的难易程度，考虑的因素有很大不同。
一般棋手不可能理解计算机内的数据结构，同样计算机也很难看懂普通的象棋棋盘，所以要实现人与计算机博弈程序的较量，必须要有一个中介，在人与计算机博弈程序之间传递信息。这个中介就是一个图形界面程序，它将局面及计算机走棋以图形界面展示给棋手，将棋手的走棋以特定数据结构传递给计算机博弈程序。
博弈程序可以自带一个图形界面，它接收用户（棋手）的输入，即棋手所走的棋，然后将自己思考后所走的棋以图形显示在屏幕上，展示给棋手。用于人机博弈的象棋博弈程序由五5大部分构成：
● 局面表示。
● 走法生成。
● 搜索算法。
● 局面评估。
● 图形界面。
如何让两个计算机博弈程序自动进行象棋比赛呢？不同的博弈程序采用了不同的数据结构来表示棋盘、局面、及走法，如何让一个博弈程序理解另一个博弈程序的走法呢？即使它理解，哪又如何与第3个、第4个博弈程序比赛呢，难道要让它理解所有可能的程序走法？这显然是不现实的，不过这也不是什么太大的问题，只要所有的博弈程序能够理解一种公共的棋盘、局面、走法表示，那它们之间就可以通信，如图2-4所示。
图2-4 机器对弈示意图
服务器在这里起着比赛裁判的作用，包括计时、判断一方是否违规、判和等。服务器程序必须要能理解公共数据结构，它可以是图形界面和非图形界面形式。一个博弈程序将走法转换成公共数据结构发送给服务器，服务器首先判断走法是否符合中国象棋规则，然后将走法发送给另一个博弈程序。
服务器程序与普通博弈程序的区别：服务器程序除了包括局面表示和走法生成外，还要计时，判和。可以不包含评估函数和搜索算法。博弈程序进行机器对弈时，并不需要自己在屏幕上捕捉对手的输入，所以不需要图形界面。常常把这种博弈程序叫做象棋博弈程序引擎。
博弈程序引擎包括：
● 局面表示。
● 走法生成。
● 搜索算法。
● 局面评估。
● 通信处理。