vc象棋游戏--智能中国象棋系统的设计与实现(编辑修改稿)

vc象棋游戏--智能中国象棋系统的设计与实现(编辑修改稿)内容摘要：

时间的方面 ，要生成所有着法只能用穷举。 中国象棋大约每一步可以有 45 个着法。 通过良好的数据结构 和走法预生成，可以显著地提高生成的速度。 模板匹配法 当动子确定以后，其“落址”和“提址”的相对关系便确定下来了，这样可以为某些动子设计其着法生成的“模板”，只要匹配到提址，便可以迅速找到落址。 图 给出了马的匹配模板。 图 马的匹配模板 将马对准提址，“ O”表示符合“马走日”规则的落址，“ x”表示“蹩 马腿”的制约条件，通过查找模板匹配数组，实现“本方子则止，对方子则吃”，完成“提 —— 动 —— 落 —— 吃”内容的确定。 对马的着法生成使用模板匹配法时，只要写出符合马行棋规则的模板匹配 数组和马腿的模板匹配数组，在生成着法时通过查找这两个数组就可以实现。 显然，这比扫描整个棋盘，通过计算得到合法落址要快速的多。 同样的，可以对象、将、士、卒使用模板匹配生成着法。 预置表法 它是把所有可能的着法预先存储起来，在生成着法时，用查表取代计算。 中国象棋每种棋子的行棋规则不同，生成每种棋子的着法和整个棋盘棋子的分布密切相关，如果建立每种棋子最大可能着法的小型数据库，用查询取代复杂的判断，那么也可以在很大 程度上加快着法生成的速度。 预置表看起来似乎很大，但是只需在程序开始运行时初始化一次就可以了 ，这些耗费对整个程序的影响不大，但是对着法生成的作用却是非常明显的。 图 即是以路向行向比特向量为索引的一个车的预置着法表的生成范例。 图中显示，该车位于某行第 4 列，棋子分布的布尔向量形式为 [010100100]，可以看出，此时车可能的吃子着法落址为 [010000100]，非吃子着法的落址为 [f0010110001]。 把车的列号和该行棋子的布尔分布作为输入，把吃子落址和非吃子落址作为输出，将输入和输出的关系写入一个预置表中，在使用时通过查表，就可以快速构成可行着法，而且可以区分开吃子着法和非吃子着法。 如 图 所示： 图 车的着法预置表范例 局面评估 局面估值就是通过既有的棋类知识来评估一个局面优劣的过程。 从象棋的棋力上考虑，在搜索之外，局面估值是最重要的部分，因为对实际局面的评价的好坏，影响着今后局势发展的趋势。 这一过程对具体的棋类知识依赖程度很深，但是仍有一般性的规律可循。 目前在计算机象棋博弈中常用的估值方法主要采用静态估值方法。 同时由于随着搜索层数的加深，叶子节点的数目迅速上升，估值函数被数以百万次的调用，花费大量的运算时间，如何提高估值函数的速度，也成了博弈性能改进的重要话题。 下面分别从这两个方面及其关系介绍局面 评估。 估值函数 （ Evaluation Function） 本系统的估值函数包括：棋子固定价值，棋子位置附加值，棋子灵活性，棋子对棋盘的控制，棋子间的关系几部分。 棋子固定价值指的是对棋盘中的每一个棋子，根据它的重要性和走法的丰富程度赋予其一个特定的值。 在棋盘上，棋子多者占优，棋子少者为劣。 根据经验，可以让一个 车价值为 500，一个马价值为 300，一个兵价值为 100 等等。 在中国象棋的对弈中，由于一般以将死对方的将 (帅 )作为结束，因此，通常赋值的规则是为将 (帅 )赋予一个远大于其他棋子的子力之和的值。 可以用下面的表达式求某一方的棋子固定值 SideValue=sum(PieceNum*PieceValue)；其中 PieceNum 是某种棋子的数量， PieceValue 是该种棋子的价值， sum 是对各种棋子的总价值求和。 如果红色的棋子价值总和大于黑色的棋子价值总和，通常这意味着红方的局势优于黑方。 而红黑双方的 SideValue 之差越大，红方的优势也就越大。 同样的棋子在不同位置上起的作用是不同的，最明显的是兵 (卒 )过河之前与之后它的作用和攻击力以及对对方的威胁显然是不一 样的，而当兵卒一旦到了底线附近，它对将 (帅 )的威胁度将大大下降。 棋子灵活性描述的是棋子的活动范围，即棋子向各处调动的可能性大小。 棋子的威力能否充分发挥，与灵活性直接相关。 本方棋子可以走的点越多，说明本方棋子的灵活性越大。 例如车在纵横线上遇到障碍物、马被周围棋子绊脚等，都降低了灵活性，也降低了威力的发挥，灵活性的计算是把棋子在棋盘上所能够移动到达的位置数作为灵活性计算，给予评分。 可以用下面的表达式求某一方棋子灵活性 : Mobility=Sum(MoveNum*MoveValue)； 其中， MoveNum 是 某种棋子的合法走法数量， MoveValue 是该种棋子每一走法的价值， sum 是对所有棋子的灵活性价值求和。 Mobility 就是所有棋子的灵活性分数。 一方 对棋盘控制的棋盘区域越多，那么他就越具有主动性。 在象棋中，如果一位置落在某方棋子的合法走步上，就可以认为被该方控制。 如果某一位置同时落在双方的合法走步上，可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。 能控制更多位置的一方应在这项评分上占优。 在中国象棋博弈中，每个棋子都不是孤立存在的，他们之间构成了各种相互关系。 如棋子 1 下一步将被吃掉，则应该给一 个负的附加值。 而如果周围有己方棋子对其进行了保护，也就是说，对方在理智的情况下不会去吃棋子 1，那么棋子 l 没有受到威胁，价值不变。 棋子关系的评估应考虑到该谁走棋的问题。 如果某个红马落在黑炮的合法走步之内，但此时轮到红方走棋，应认为红马受到的威胁较轻。 而如果此时轮到黑方走棋，就应认为红马受到的威胁很大，应减去一个相对较大的值了。 估值的速度与博弈性能 开发人员可以向估值函数加入大量的棋类知识，使之对于局面的评估更为精确。 但是，博弈系统的性能，速度，棋类知识一般满足下面的关系 ： Performance(性能 )=Speed(速度 ) Kowledge(知识 ) 且向估值函数加入越多的棋类知识，估值函数的速度也就越慢，因为所要进行的计算也相应增加。 因此过于简单的估值函数和过于复杂的估值函数同样性能不佳。 在同等的知识含量下，速度越快，性能越高。 在同等速度之下，知识量越大性能越高。 在速度和知识量二者的相互作用下，开发者要寻找的是一种平衡，是能够使性能最大化的速度和知识量。 使用终点估值 (end—point envaluation)，意思是当叶子节点到达时，使用估值函数对一个局面进行评估。 这样的方法思路清晰，容易设计， 而且模块间独立性高，同搜索算法的 耦合 度很低。 可以轻易的更换估值函数，只改动极少的代码 ； 你也可以随意使用任何估值方法来评估整个棋盘，最终给出估值，但这种方法的速度较慢。 估值函数的优化 目前最长使用的是优化估值参数的方法是利用大量的测试局面进行手工调整， 也是本文在优化评估函数时主要使用的手段。 这种方法是利用人类的象棋经验知识来调整参数值，比如，从经验上可以知道，一个车的价值要比一个兵大，给车赋予比兵大的数值，马炮则赋予位于其间的值。 马和炮的地位相当，给予它们相当的数值，以避免盲目换子 ；如果对弈中使 用了一些优秀的战术配合，那么就给予一定数值的奖励，等等。 将这些经验放进评估函数中反复对弈，然后不断修正参数，找出一组性能较高的参数。 (1)规格化 (Normalize) 如果只 是关心评价的顺序，而不怎么关心评价值，那么可以把每一项都乘以同样 的常数。 这就意味着，对某个特定的模块，例如兵的价值，可以硬性设一个值，其他值就可以表示成它们相当于多少个兵。 这个做法可以减少一个需要设定的参数。 (2)约束法 (Deduce Constraints) 通过考虑希望电脑作出怎样的判断，就可以确定一些参数。 例如在对弈中即使赚 到一个兵，用车换象或马还是坏的，但如果能赚到两个兵那还是好的，因为在考虑子力价值是要防止换单兵，鼓励换双兵。 这样的条件越多，合适的权重组合就越少。 在开始设定权重值的时候，这个方法通常可以得到合适的值，但是在后面仍然需要做一些调整。 (3)交手法 (Hand Tweaking) 这是调整评估函数时非常常用的方法，通过让程序对弈，来找到它的优势和弱点，猜测哪些参数会让程序更好，然后挑选新的参数。 这个方法可以很快得到合理的结果，但是需要对棋类知识有足够的了解，便于根据程序的对局来做分析，从而知道程序的问题在哪里。 手工调整是象棋引擎调整估值参数的主要手段之一，把人类的知识和经验尽量准确客观地“教授”给计算机，是提高棋力的普遍做法，虽然比较费时，但是很有效。 通过不断的试验、修改参数值，可以得到不错的结果。 但是人类的知识毕竟具有一定的局限性，评估函数也不能包含所有情况，参数之间往往又互相联系，调整某个参数可能解决了某类问题，但又可能给其它问题的解决带来麻烦，在这种情况下很难实现全局下的最优组合。 还有一种主要的优化方法是机器自学习： (1)爬山法 (HillClimbing) 爬山法通过对参数进行小范围的试探来寻找最优解 ，一次只能对参数作一点小改变，然后测试博弈程序的性能是否提高了，仅当性能提高时才采纳这个改变，需要重复很多次。 这种方法很慢，并且受初始采样值的限制，很容易陷入局部最优，即评价可能很差，但是任何很小的改变都会使评价更差。 (2)模拟退火 (Simulated Annealing) 模拟退火是一种基于蒙特卡罗 (Monte Carlo)算法的启发式随机搜索算法，它没有蒙特卡罗算法多次寻优的过程，也不像爬山法那样依赖初值。 在优化参数时，类似于爬山法，模拟退火法也是对权重做改变来提高成绩，如果所做的改变没有提高成绩 ，也会根据一个随机的几率采纳这个改变，试图跳出局部最优。 这个方法需要给定一些几率，从几 率高、梯度大的条件开始，然后逐渐减小。 模拟退火法比爬山法更慢， 是最终可能得到比较好的值。 (3)遗传算法 (Geic Algorithm， GA) 遗传算 法 是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性全局优化算法，因其模仿生物的遗传机制而得名，最早由美国密执安大学 于 1975 年提出，它通过染色体的复制，交叉，变异等操作，实现个体适应性的提高。 遗传算法可以同时维护多组较好的参数，通过向其中 添加一组新参数，通常是将从几组老参数中选出的值组合在一起作微小的变化，然后同几组老的参数比较孰优孰劣，将最坏的一组去 除。 遗传算法是从几组参数开始，而不是一组参数，具有很好的全局搜索能力，搜索速度也很快，而且此算法能将搜索重点集中于性能高的部分，能较快地求出最佳参数，鲁棒性也明显优于前两种算法，所以在计算机博弈中最有可能取得成功。 博弈树搜索技术 中国象棋博弈树非常庞大，完全建立博弈树是不可能的，唯一的解决方法就是让博弈树扩展到计算机运算可以接受的深度，然后对没有分出胜负的叶子节点给出一个尽量准确的打 分，表示此局面下取得胜利的可能性，这个打分是由评估函数计算给出的，将搜索树展开是着法生成的功能，而搜索引擎则是尽可能缩小树的规模，避免一切冗余的计算，这也是计算机博弈中搜索引擎研究的重点。 根据搜索策略，目前应用于计算机博弈的搜索算法一般可分为三类 ： (l)穷尽搜索 (Exhaustive Search)，这种搜索是没有抛弃任何可能成为最佳路径的搜索，不存在 风险，得到的最佳走法肯定是在现有评估函数下应该得到的，例如极大极 小值 搜索、α β 剪枝搜索及其变种等。 (2)选择性搜索 (Selective Search)，即裁剪搜索，这种搜索略去对一些着法的搜索， 冒着有可能 漏掉最佳走法的风险，而换来局部更深的搜索深度。 中国象棋中最常用 裁剪算法是空着裁剪 (Null Move)等。 (3)启发式搜索 (Heuristic search)利用象棋领域的知识 (启发信息 )设计搜索算法，着重对走法排序，以简化和加快搜索过程。 中国象棋中的启发算法有历史启发、杀手启发、置换表等。 基本搜索算法 极大极小值 方法 (Minimax Algorithm)是解决博弈树问题的基本方法。 香农教授早在1950 年首先提出了“极 大极小算法 ” ，奠定了计算机博弈理论的基础。 极大极小值算法的原则是 :博弈双方所要达到的目的相反，一方要寻找的利益是另一 方失去 的利益，博弈的一方总是希望下一步是子节点中取值最大者，而另一方 希望下一步是子节点中取值最小者。 在象棋博弈中，极大极小值算法体现在始终站在博弈一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方(有利于另一方 )的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间值分 数。 在这一方走棋的时候，选择价值最大的子节点走法，即实行“ Max 搜索”，另一方走棋则选择价值最小的子 节点走法，即实行“ Min 搜索”，这就是象棋博弈中的一个极大极小过程。 例如，如果红方为走棋方，它在偶数层的着法选择是要在其全部子节点中找到评估值最大的一个，实行“ Max 搜索”，称为 MAX 方，而其敌对方即黑方在奇数层的着法选择则是在其全部子节点中要找到评估值最小的一个，实行“ Min 搜索”，称为 MIN 方。 图 表示了一个极大极小搜索过程，粗箭头为最佳路径片段。 图 极大极小值算法示意图 由于完整的博弈树过于庞大，程序不能也没有必要搜索整棵博弈树的所有节点，而需要像人类棋 手一样有选择性地进行搜索，对 于一些已经确定不佳的走步可以将以它 根节点的子树剪掉 (cutoff/pruning)，以提高单位时间内搜索的节。