2、着法生成(Move Generation)
着法生成就是找到某个局面所有合法的走法。它与棋盘表示的数据结构密切相关，一般需要大量繁琐的判断，伴随着搜索进行，并且调用频繁，是相当复杂而且耗费运算时间。在一定程度上形成了程序的性能瓶颈。当前为了提高着法生成的效率通常采用以空间换时间的方法:与先求出棋子的在某位置的所有走法。 3、评估函数(Evaluation Function)
评估函数就是对博弈过程中实际局面的好坏做出判断或打分，它影响着博弈局发展的趋势。目前象棋程序的静态评价函数主要有子力价值，子力灵活性，子力对棋盘的控制，和一些对棋局影响比较大的重要特征计算几部分组成。它与着法生成一样十分耗费运算时间，如何加速评估函数的速度十分关键。 4、搜索技术(Search Techniques)
搜索技术与算法是象棋博弈系统程序的核心，是决定搜索效率的关键所在。再好的硬件也无法实现“象棋不败算法”。如何在成指数递增的状态空间中寻求最优解，是象棋博弈系统的一个重要的方向。“蛮力搜索”肯定是不可取的。如何有选择地搜索，既瞄准最有希望的方向局部加深，又不遗漏其它存在最优解的可能。目前主要是使用α-β剪枝算法加上迭代深化、置换表、历史启发等策略的综合应用。 5、开局库(Opening Book)
把开局几步的走法建成数据库供程序直接取用。实践表明无论搜索引擎如何出色，在开局搜索过若干层后，得到的可能只是一些很笨拙的开局。直接从开局库中取就可以大大加快开局时的运行速度和提高开局的质量。开局库一般是采用zobrist哈希技术加以实现。
6、机器自学习(Machine Learning)
机器自学习之一是针对评估函数。对弈过程机器自动调整评估函数参数的权值进行优化，发现一些棋子之间潜在的联系:之二是采用模式识别，学习的过程是通过对博弈过程的识别统计，自行丰富模式库中的内容，以提高程序的博弈性能。 1.4本文的主要工作
本文的主要工作是将博弈策略应用到中国象棋程序的设计与实现上，建立一个完整的中国象棋计算机博弈系统，研究工作主要集中在以下几个方面： 1、棋盘表示与走法生成
从操作速度(性能)以及使用方便与否考虑，本象棋博弈系统从带位行位列信息的扩展棋盘——棋子联系数组着手进行研究。然后根据棋盘表示获得所有棋子的走法预生成数组。在产生走法时直接从中取出数据，进行少量判断以得到该棋子的合法走步。 2、估值函数
如何快速有效的对一个局面进行评估需要从速度和知识的两个角度进行考虑:一般知识越多估值越准确，但速度也慢下来。本系统采用通用的静态估值方式，同时在估值时结合走法预生成数组，使估值的速度有很大提升。 3、搜索技术
博弈树搜索技术它很大程度上独立于具体的计算机博弈程序。本文讨论了α-β剪枝搜索算法及其各种增强手段：包括窗口原则、置换表(内存增强)；历史启发表(节点顺序调整)；迭代深化(时间控制)等。如何把各种增强手段有机组合起来达到最优，文章对基于迭代加深、置换表、历史启发的Negascout算法进行改进。 1.5论文结构
第一章阐述了选题背景，课题的国内外研究现状及课题的主要工作和文章的章节安排。
第二章第一部分首先介绍中国象棋程序的一些基本数据结构，着重研究了扩展的棋盘——棋子联系数组棋盘；在此基础上实现所有棋子的走法预生成数组，以提高搜索过程中走法产生的效率。第二部分研究本系统的着法生成，包括预置表法和模板匹配法，进一步提高了搜索效率。第三部分描述本系统的评价函数架构，着重描述了静态估值方法，分析了其不足，并提出了解决之道。包括子力分数、子力灵活度评价、棋盘控制等并与走法预生成数组结合以提高估值速度。第四部分实现了博弈树的α-β剪枝算法并简要介绍各种搜索策略。第五部分阐述了开局库的设计原理。
第三章给出实验环境和程序实现。 第四章是全文的总结及展望。
2 系统的分析和设计
2.1数据结构（Data structure）
数据结构是一个程序的骨架，选择一种好的数据结构可以使程序的运行效率大大提
高。
2.1.1 棋盘的基本表示法（Board Representions）
棋盘表示就是使用一种数据结构来描述棋盘上的信息，以便程序知道博弈的状态。棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率，研究人员针对中国象棋提出了多种不同的表示方法。
中国象棋的棋盘表示中最典型的是用一个10×9的二维字节(byte)数组，数组中每个元素代表棋盘上的一个交点，其值表明这个交点上放置的是一个什么棋子或是没有棋子
从棋子的角度考虑，如果把棋盘看成是一个平面坐标系，可以知道每一个棋子的位置信息:小于10的横坐标和小于11的纵坐标;又在棋盘上最多32个棋子，故可以用一个32个字节的一维数组表示所有32个棋子的位置，其中每个字节的高4位表示该棋子的横坐标，低4位表示棋子的纵坐标。而己被吃掉的棋子用坐标范围以外的数表示。这样棋盘信息就被装入这32个字节中。当然也可以把棋盘看作一维的，每个元素保存直接的位置信息。
两种棋盘表示方法：一是做一个棋盘数组；二是做一个棋子数组。棋盘数组中由棋子的位置获得棋子的类型可以在常数时间内完成，但由棋子的类型获得棋子的位置需要遍历；在棋子数组中由棋子的类型获得棋子的位置可以在常数时间内完成，但由棋子的位置获得棋子的类型操作繁琐。如果一个程序同时使用这两个数组，那么获得棋子的类型和棋子的位置都可以在常数时间内完成。这就是“棋盘·棋子联系数组”，它的技术要点是:
(l) 同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。
(2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。在棋盘上删除一个棋子，需要做两个操作(分别修改棋盘数组和棋子数组)。同样，添加一个棋子时也需要两个操作。
“棋盘·棋子联系数组“最大的优势是：对于着法产生过程，可以逐一查找棋子数组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的数量(每方只有16个棋子能走)比棋盘格子的数量(90个格子)少得多，因此联系数组的速度要比单纯的棋盘数组快很多。同时“棋盘——棋子联系数组”是很多改进的棋盘的基础。 ·2.1.2 改进型棋盘结构
在计算机上面，位运算比一般的加减乘除及取余运算快得多。如果能在寻找棋子 和定位棋子上使用位运算代替加减乘除和取余，这将很大程度上提高运算速度。所以，人们把“棋盘——棋子联系数组“进行扩展：把棋盘做成16×16的大小，这样得到行号可以用16除，得到列号可以对16取余（和15进行运算），这比除以10和对9取余操作要快得多。如图2.1（红色格子都被标上“出界”的标志，目标格在这些格子上就说明着法无效）：
图2.1 扩展的棋盘
这种棋盘的更大的好处是：
(1) 它可以防止棋子走出棋盘边界。由bool型棋盘数组（属于棋盘的位置为true，否则为false），判断棋子是否走出棋盘边界只要返回该数组对应的值即可，速度快。
(2) 对于是否在城池内可以用bool型城池数组判断，因为是否在城池内的判断会非常频繁，直接用该数组会很高效。
(3) 判断是否过河的方法非常简单：只要设定特定的表达式，当表达式为假表示已过河，否则没过河。
(4) 还可以非常方便的判断棋子是否在己方。 2.2 着法生成（Move Generation）
着法生成就是要产生所有有效的着法，让电脑棋手在这些着法中选择最好的着法，并判断人类棋手是否符合走棋规则。着法生成是博弈程序中一个相当复杂而且耗费运算时间的方面，要生成所有着法只能用穷举。中国象棋大约每一步可以有45个着法。 通过良好的数据结构和走法预生成，可以显著地提高生成的速度。 2.2.1 模板匹配法
当动子确定以后，其“落址”和“提址”的相对关系便确定下来了，这样可以为某些动子设计其着法生成的“模板”，只要匹配到提址，便可以迅速找到落址。图2.3给出了马的匹配模板。
图2.2 马的匹配模板
将马对准提址，“O”表示符合“马走日”规则的落址，“x”表示“蹩马腿”的制约条件，通过查找模板匹配数组，实现“本方子则止，对方子则吃”，完成“提——动——落——吃”内容的确定。
对马的着法生成使用模板匹配法时，只要写出符合马行棋规则的模板匹配数组和马腿的模板匹配数组，在生成着法时通过查找这两个数组就可以实现。显然，这比扫描整个棋盘，通过计算得到合法落址要快速的多。同样的，可以对象、将、士、卒使用模板匹配生成着法。 2.2.2 预置表法
它是把所有可能的着法预先存储起来，在生成着法时，用查表取代计算。中国象棋每种棋子的行棋规则不同，生成每种棋子的着法和整个棋盘棋子的分布密切相关，如果建立每种棋子最大可能着法的小型数据库，用查询取代复杂的判断，那么也可以在很大