现在计算机博弈正越来越受欢迎，它所具有的复杂性和挑战性吸引了许多学生和学者前去研究。西洋跳棋也称为国际跳棋，
目前64格西洋跳棋已被研究完善，100格西洋跳棋其复杂性和难度都有所提升，因此，人们更多地专注于100格西洋跳棋算法上的
研究。100格西洋跳棋双方子力较多，布局变化万千，走法更是多种多样，本文致力于研究布局、估值和搜索，运用博弈树理论、极大—极小值搜索、虚拟静态估值等方法设计一种比较完善的方案提高博弈水平。
2 西洋跳棋的规则与棋盘
本文中提到的西洋跳棋是指100格西洋跳棋。
2.1 基本规则
西洋跳棋规则相对比较复杂，棋盘是100格，上面有50个格可供棋子行走，如图1所示。对弈双方各有20颗普通棋子，当对方普通棋子走到自己方底线时就成为王子。在行棋过程中普通棋子只能向前走，当棋子具备连杀条件时必须连杀，当局面存在能吃掉对方棋子时必须吃子；王子可以向任意方向移动，比普通棋子更具有攻击力和防御力。当一方棋子被吃完或者没有可以移动的棋子时该方就输了。

图1 西洋跳棋100格
2.2 棋盘表示
西洋跳棋棋盘在程序中的常用表示方法有两种，一是二维数组表示棋盘，二是用比特棋盘。其中二维数组表示棋盘简单直观，易于访问，操作简单，比特棋盘访问效率高于数组棋盘，但是综合考虑各自优缺点后，本文选用10*10二维数组表示棋盘。
如图1所示，共有10*10个方格，故用10*10的（int型）二维数组表示，其中0表示空白（无棋子），1表示黑棋，2表示黑王，-1表示白棋，-2表示白王。当普通棋子成王后，其棋子图形会由圆形变成正方形以区分普通棋子与王，即黑王用一个黑色正方形表示，白王用一个白色正方形表示。
3 西洋跳棋的走法生成
走法生成用专门的走法生成函数表示，生成函数包含西洋跳棋基本规则，行棋时必须严格遵循这些规则，它是程序正确博弈的保证。走法生成函数本身不产生任何行棋信息，它只负责按规则行棋。当布局函数、估值函数和搜索函数配合完成后会产生最优走法的相关信息，然后把这些函数传递给走法生成函数，最后由走法生成函数行棋，如图2所
图2 走法生成过程
3.1 布局
布局是走法生成的关键部分，特别是开局决定着棋局后续发展的好坏。西洋跳棋棋子数量较多，布局时可以运用大量战术配合行棋规则，在博弈中往往可以反败为胜，使博弈时战斗激烈，精彩纷呈。布局既要考虑双方子力的差别，又要考虑当前这一步棋走完后对整个棋局的影响。布局可以采用虚拟走法，把每一颗能走棋子所有能走的方式都模拟走一遍，对走完后的局面做出评判，从所有能走方式中选取最优方式。布局时需要考虑的因素很多，要对局势整体把握，综合考虑，可运用的战术多种多样。例如布局可以利用能杀子时必须杀子规则来设置陷阱，牺牲一颗棋子换取对方多颗棋子。布局深度是决定棋局胜败的一个重要因素，行棋时要考虑棋局的未来发展。西洋跳棋是一种具有深度搜索的棋种，一步行棋往往能决定局势优劣甚至成败，估值深度可采用追踪方式，对能够移动的棋子各种行走轨迹追踪到底，分析该步行棋走后对后续局面造成什么影响。布局过程通过布局函数完成，完整的布局过程如图3所示。

图3 布局函数的形成过程
3.2 估值
在行棋过程中行棋者需要时刻掌握棋局的发展，掌握行棋方处于优势还是劣势，从而根据局势的优劣布局。估值可以分为静态估值和动态估值，估值方式采用估值函数评分，每个函数中有评分标准且相互之间不影响，分数可正可负可为零，棋子模拟行棋后调用估值函数评出相应的分数。估值时先把我方每一颗能走的棋子和能行走的方式都模拟走出来，再调用静态估值函数和动态估值函数给该模拟行棋估分并记录分数与行棋方式，找出所有方式中最高的分数，再比较所有能行走方式棋子中分数最高的棋子分数和行棋方式，最后生成相应的走法。估值过程如图4所示。

图4 估值过程
3.2.1 静态估值
静态估值时要考虑行棋过程中的多种特性，但估值深度有限，需要动态估值共同配合完成整个估值过程。
1.静态估值
行棋过程中，特性考虑的越多越完善，估值就越好。经过反复研究，本文主要考虑几种典型的特性进行研究。例如棋子分布阵型、棋子数量、子力分布、王的数量等。单个估值函数有独立的评分公式，依据各自的性能评分。特性估值函数采用计算双方特性差的方式，如双方棋子数量差、具有攻击力棋子数量差等，以求获得比较完整的估值信息。例如子力估值函数评分公式可以采用公式（1）~（4）。
Count_num=Black_num-White_num （1）
Attack_num=Black_num-White_num （2）
Defense_num=Black_num-White_num （3）
Fen_value=Count_num*value_1+Attack_num*value_2+Defense_num*value_3 （4）
其中公式（3）中，Black_num 表示黑方具有具有防御力棋子的数量，White_num表示白方具有防御力棋子的数量，Defense_num表示黑方和白方防御力棋子的数量之差。
公式（1）、公式（2）和公式（3）含义相似，分别表示棋子数量、具有攻击力棋子数量等不同的特性指标。
公式（4）中value_1、value_2、value_3等代表子力估值函数中棋子数量、具有攻击力棋子数量以及具有防御力棋子数量所占的权重，Fen_value表示加权后算出的分值。根据局势发展，这些权重会根据棋子数量、位置等动态改变值的大小。因为棋子在棋盘不同位置，面临不同阵型等因素都会使其具有不同价值，我们在估值时必须时刻给其打分才能比较完善的评出有价值的分数，其它特性估值函数都是运用相同的原理。
2. 静态估值深度
静态估值只考虑一步范围内的行棋估值，当行棋方模拟走出一步后就调用静态估值函数评出相应的分数。静态估值易于实现，考虑的范围广，当多个估值一起合作时会大大加强程序的博弈能力。但是静态估值毕竟没有深度，无法预测自己和对方行棋后对未来局面的影响，所以我们的估值必须要有深度。深度就是当我们行一步棋后模拟出对方和自己后面可以行棋的方式，当我们模拟完成后会评价该局面对我们是否有利，当有利时我们在实际行棋时就走这步棋，当对我们不利时就放弃这步棋，寻找其它对我们有利的行棋方式，深度对博弈程序来说非常重要，深度决定了博弈程序的思考能力，当深度越深时程序看的就越远，可以看出对方行棋中的意图和陷阱并提前预防，这样在博弈过程中就可以占有利地位。结合动态估值就可以完成深度搜索。
3.2.2 动态估值
动态估值涉及估值深度，可以通过具有一定搜索算法的博弈树完成深度搜索。
1.博弈树
博弈树是博弈程序设计中常用的一种搜索方法，它是行棋时生成的一棵可以完成记录行棋信息的树。在模拟行棋时模拟棋子所有可以行棋的方式并记录，树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面即生出新的结点，如此不断直到再无可选择的走法，即到达叶子结点（棋局结束），博弈树可以完整的记录行棋中的信息并将其保存到叶结点，再通过搜索算法进行访问。
2.动态估值
在博弈树中对每一层局面调用估值函数评分，找出每一层行棋中最好的行棋方式，记录每一层最高的分数走法生成，再求出每层的最优值。
因为西洋跳棋棋子数量较多，行棋时可以移动的棋子数量和方式也很多，所以涉及估值深度时要记录的信息量大，访问时耗费的时间也较多，利用博弈树可以很好的记录大量数据和快速访问，再结合合适的搜索算法能设计出很好的估值程序。
3.2.3 估值评分
估值最后对所有静态估值函数和所有动态估值函数用统一公式评分，如公式（5）。
Fen=ZiLi_value()*0.7500+Formation_value()*0.6500+Attack_value()*0.5250…… （5）
其中ZiL_value()、Formation_value()、Attack_value()表示棋子数量函数、阵型函数、攻击力棋子函数评分后返回的分值，0.7500,0.6500等系数代表每个估值函数的权重。
可以看出每个权重大小是固定且相互之间不同，这些权重系数需要经验获得。权重的不同说明每个特性估值函数的重要程度不同。模拟行棋后评出该步行棋的估值分数并记录。
估值可谓程序的大脑，在博弈过程中大多数的行棋都是估值决定的，所以估值的好坏直接决定着程序的博弈能力，在设计博弈程序的估值部分还可以加入许多其它算法以提高程序的能力。
3.3 搜索
搜索相当于程序的灵魂，在西洋跳棋博弈中搜索方式有很多，如Alpha-Beta 搜索、Min-Max搜索、负极大值搜索、MTD (λ) 搜索及PV 搜索等。搜索深度越深，程序就看的越远，能力就越强。各种搜索方式都有各自的优缺点，经过精心考虑比较，本文采用Min-Max搜索。以博弈树为基础，结合Min-Max搜索方式设计程序的搜索。