3.3走法生成
在走法生成器中，基本思想就是：扫描整个棋盘，当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法走法并存入走法队列。
“合法走法”包括以下几点：
(1)各棋子按其行子规则走子。
(2)走子不能越出棋盘的界限。
(3)走子的半路上不能有子阻拦（炮吃子除外）以及走子的目的点不能有本方棋子（不能自己吃自己）。
(4)将帅不能碰面。
产生了走法后将其存入走法队列以供搜索之用，由于会搜索多层（即考虑双方你来我往好几步）,所以在把走法存入走法队列的时候还要同时存储该走法所属的搜索层数。因此将走法队列定义为一个二文数组MoveList[8][80]，其中第一个数组下标为搜索层数，第二个数组下标为每一层的全部走法数。
关于搜索层数，我将数组下标设定为8，实际使用的是2到4。搜索层数的增加会显著提高引擎的下棋水平（当然计引擎的棋力在很大程度上也依赖于局面评估）。在手机模拟器上最多只能搜索4层，再多将导致搜索时间达到令人无法容忍的地步。
对于每一层的走法数，也就是当前下棋方针对当前局面的所有可选的合法走法，据有关数据统计在象棋实战中一般最多情况下也就五辣十种。定义第二个数组下标为80，应当可以保证十分的安全。
走法生成为搜索部分提供了“原料”，接下来的任务就交给搜索和局面评估了。
3.4 搜索算法
搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏，驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率（从某种角度上，它影响着引擎的下棋水平。因为，引擎必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多）。关于棋类对弈程序中的搜索算法，经前人的努力已形成了非常成熟的Alpha-Beta搜索算法以及其它一些辅助增强算法（还有众多基于Alpha-Beta算法的派生、变种算法）。鉴于目前知识储备、时间、精力等均达不到推陈出新、另开炉灶的要求，再加之前人的算法着实已相当完善，所以我在程序中直接借鉴了Alpha-Beta搜索算法并辅以了历史启发。
用一棵“博弈树”（一棵n叉树）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面（结点）根据不同的走法又产生不同的局面（生出新的结点），如此不断直到再无可选择的走法，即到达叶子结点（棋局结束）。中国象棋的博弈树的模型如图3-3所示:
图3-3 象棋博弈树
该树包含三种类型的结点：
(1)奇数层的中间结点（以及根结点），表示轮到红方走棋；
(2)偶数层的中间结点，表示本文来自辣文论文网轮到黑方走棋；
(3)叶子结点，表示棋局结束。
现在让引擎下棋，它应当选择一步对它最有利的走法（最终导致它取胜的走法）。获得最佳走法的方法就是“试走”每一种可能的走法，比较它们所产生的不同后果，然后从中选出能够产生对自己最有利的局面的走法。毕业论文http://www.751com.cn
结合上面所讲的博弈树，如果给每个结点都打一个分值来评价其对应的局面（这一任务由后面所讲的局面评估来完成），那么可以通过比较该分值的大小来判断局面的优劣。假定甲乙两方下棋，甲胜的局面是一个极大值（一个很大的正数），那么乙胜的局面就是一个极小值（极大值的负值），和棋的局面则是零值（或是接近零的值）。如此，当轮到甲走棋时他会尽可能地让局面上的分值大，相反轮到乙走棋时他会选尽可能地让局面上的分值小。反映到博弈树上，即如果假设奇数层表示轮到甲方走棋，偶数层表示轮到乙方走棋。那么由于甲方希望棋盘上的分值尽可能大，则在偶数层上挑选分值最大的结点——偶数层的结点是甲走完一步棋之后的棋盘局面，反映了甲方对棋局形势的要求。同样道理，由于乙方希望棋盘上的分值尽可能小，那么在奇数层上就选择分值最小的结点。这就是“最小-最大”(Mini-max)的基本思想。这样搜索函数在估值函数的协助下可以通过在奇数层选择分值最大（最小）的结点，在偶数层选择分值最小（最大）的结点的方式来搜索以当前局面为根结点、限定搜索层数以内的整棵树来获得一个最佳的走法。
上一页 [1] [2] [3] [4] [5] [6] [7] 下一页