前言

程序设计是计算机专业的必修课，从C到C++，再到可视化程序设计VC++。C/C++是大学计算机专业的基础语言课，不少程序员都是从C走上他们的程序设计之路的。大学课程主要从语法的角度讲解C/C++。具体是C讲述基础的语言设计方法，C++主要讲述面向对象程序设计方法，VC++则讲述基本的可视化程序设计的知识。太多的语法基础占据了语言课的大部分时间，学生学习后基本只能应付课后习题，要提高程序设计能力还有很长的路要走。学生一路走来，到毕业时很多人竟不能独立编写一个像样的程序。

数据结构，算法分析与设计则是计算机专业的主要课程，可许多学生学习之后竟然觉得数据结构无用。理论教学与实践的脱离使得学生只追求盲目的60分。很多计算机专业学生毕业之后没有独立程序设计的能力，无法从事计算机相关行业。

案例教学成为近年比较流行的教学模式。它将课本理论与实际项目开发结合在一起，提高了学生的动手能力和实践经验。实践证明，编写一个带有实际意义的项目是提高编程能力最高效的方法。如果能有一个项目将C、C++、VC++、数据结构、算法分析与设计结合在一起，提高学生的基础程序设计能力，同时又能掌握数据结构与算法的高级应用，必然为以后从事软件开发打下良好的基础。中国象棋程序就是这样一个项目，它综合了C、C++、VC++、数据结构、算法分析与设计等知识。象棋作为竞技体育同时又作为一个游戏，具有一定的趣味性。学生通过自己亲身参与游戏程序的编写可以提高学习的积极性。

中国象棋程序主要由局面表示、走法表示及生成、局面评估、搜索算法、界面控制等五大部分组成。

局面就是一盘棋经过若干回合之后当前所处的形势，包括棋盘、红黑双方所剩棋子及其在棋盘上的分布、当前该走棋一方、双方所剩时间、双方所剩走棋步数等内容。局面表示是象棋程序的基础，局面表示的好坏直接关系到走法生成、局面评估和搜索算法的效率，从而影响象棋程序得到的最佳走法。

象棋程序每一次思考的目的是获取一个最佳走法（至少在程序看来是最佳的）。要实现这一目的的简单方法就是生成全部所有可能的走法，然后再一个一个的比较，找出最佳的一个。实际上程序也是这样做的。

局面评估就是判断局面对红方（或者黑方，或者是当该前走棋一方）的优势，并把优势进行量化。由于象棋程序搜索复杂度太大，搜索函数不可能搜索到棋局终了的状态，所以必须在某个深度的结点上结束并返回上一层。这个结点并没有达到棋局结束（胜平负），应该给它一个值，反映局面状况，对红方有利还是对黑方有利，有多少优势。必须把这种优势量化，以便不同结点的优势可以进行比较，以确定哪一个结点更好。

中国象棋的局面变化实在是太多了，有时候一个局面可能走法达100多种，一般局面也有40多种走法。要完全搜索10步棋需要3.3年，即使完全搜索7步棋也要27分钟（按每秒搜索108个结点计）。按一盘棋平均100步（50个回合）计，要完全搜索100步是绝对不可能的。如何让计算机在有限的时间内搜索到更多的空间和更深的步数，是计算机博弈程序必须考虑的问题。这除了与计算机硬件有关之外，与搜索算法关系很大。这是因为在搜索树空间中有些分支是多余的，搜索的时候可以跳过某些分支。跳过的分支越多，搜索的速度越快，但漏掉最优解的可能性也在增加。搜索算法必须又快又准地找到最优解。

一般棋手不可能理解计算机内的数据结构，同样计算机也很难看懂普通的象棋棋盘，所以要实现人与计算机博弈程序的较量，必须要有一个中介在人与计算机博弈程序之间传递信息。这个中介就是一个图形界面程序。它将局面及计算机走棋以图形界面展示给棋手，将棋手的走棋以特定数据结构传递给计算机博弈程序。博弈程序可以自带一个图形界面，它接收用户（棋手）的输入，即棋手所走的棋，然后将自己思考后所走的棋以图形显示在屏幕上，展示给棋手。

笔者多年从事C、C++、VC++、数据结构、算法分析与设计的教学工作，同时也有多年的软件开发经验。此书以提高C/C++程序设计能力为主要目标，深入浅出地介绍中国象棋博弈中的基本算法，分析算法实现的关键技术，再逐步介绍各种高级技巧，使读者能够迅速领会象棋程序的特点，自己动手写出更高效的程序。

所有算法均配有示例程序，使读者能够由浅入深地掌握中国象棋程序的要领。将编程与下象棋的实践紧密结合，有较强的趣味性。读者如果具有一定的数据结构基础知识就更容易理解本书。

读者朋友如有任何疑问和建议，可以到如下网站的本书讨论区同笔者一起探讨：

http://www.pubeta.com

作 者

2009年3月