【摘要】本文在概述计算机博弈，特别是中国象棋软件概况的基础上，分析了现有中国象棋博弈软件实现方法中存在的问题，设计了棋盘,棋子和评价函数的表示方法，应用VC和MFC设计并实现了博弈界面，在博弈树理论的基础上采用递归方法实现了α-β剪枝搜索。该程序用户界面良好，支持悔棋功能，具有一定的棋力。

关键词:中国象棋；博弈树；α-β剪枝；计算机博弈；VC；MFC

【Abstract】In this thesis, we first present a survey of the state of the art in Computer Game, especially Computer XiangQi software. Then aiming at addressing the existing problems in XiangQi software, we design a concise framework for XiangQi chessboard representation, static evaluation function and human-computer interface. Further, we implement the α-β pruning game tree search, the interface and the XiangQi game program MyChess in VC++ and MFC. This program with clear interface and tack-back function is user friendly. It is fair for beginner.

Key words：XiangQi; game tree; α-β pruning; Computer Game; VC ; MFC


目 录

第一章　绪论 1
1.1 中国象棋 1
1.2 国内外象棋软件介绍 2
1.3 中国象棋软件技术 3
1.4 本文工作重点 4
第二章　　常用搜索算法 5
2.1 概述 5
2.2 深度优先搜索 5
2.3 博弈策略 5
第三章　　棋局表示和走法规则的实现 13
3.1 棋盘和棋子的表示 13
3.2 走法规则的实现 13
第四章　　界面设计和走棋的实现 15
4.1 程序的基本功能 15
4.2 走棋的实现 15
4.3 悔棋功能的实现 16
4.4 胜负的判断 16
第五章　　博弈程序实现 18
5.1 列表和排序函数 18
5.2 估值函数 18
5.3 搜索算法函数 19
5.4 电脑下棋的最终实现 20
第六章　　总结 22
参考文献 23
附录代码 24
中文翻译资料 35
致 谢 43

毕业设计（论文）任务书[节选一部分]

一,原始依据（包括设计或论文的工作基础,研究条件,应用环境,工作目的等）
   人工智能(Artificial Intelligence)，英文缩写为AI，是一门综合了计算机科学,生理学,哲学的交叉学科。人工智能的研究课题涵盖面很广，从机器视觉到专家系统，包括了许多不同的领域。这其中共同的基本特点是让机器学会“思考”。为了区分机器是否会“思考”(thinking)，有必要给出“智能”(intelligence)的定义。究竟“会思考”到什么程度才叫智能？比方说，解决复杂的问题，还是能够进行概括和发现关联? 还有什么是“知觉”(perception)，什么是“理解”(comprehension)等等？对学习过程,语言和感官知觉的研究为科学家构建智能机器提供了帮助。现在，人工智能专家们面临的最大挑战之一是如何构造一个系统，可以模仿由上百亿个神经元组成的人脑的行为，去思考宇宙中最复杂的问题。或许衡量机器智能程度的最好的标准是英国计算机科学家阿伦·图灵的试验。他认为，如果一台计算机能骗过人，使人相信它是人而不是机器，那么它就应当被称作有智能。
  基于人工智能的博弈程序将人工智能和娱乐有机结合在一起。人工智能结合最强的博弈程序是国际象棋程序。参加国际象棋锦标赛的国际象棋程序可以看二十多步，而且，国际象棋程序可以不断学习，因此可以不断的提高水平。程序也不会象人那样下棋。一个名叫“深思”的国际象棋程序三分钟内可以思考一亿二千六百万步，而人类国际象棋大师平均只能思考不超过两步。哈波特·西蒙认为，人类国际象棋大师熟悉每一步可行的合适位置和小区域内位置关系。而计算机程序不考虑这些位置间的关系，只通过搜索所有可走的步来确定要走的下一步。而且计算机走的每一步都来自上一步的学习得到。一个运行在克雷计算机上的国际象棋程序拥有2600分等级分，相当于俄罗斯国际象棋世界冠军卡斯帕罗夫级别的水平。
  任何博弈过程都可表示成一株博弈树。博弈树的结点对应一个棋局，分支表示一步着法。特别地，根节点表示开始盘面，叶节点表示终局。终局可以是赢,输,和三者之一。在深度优先的最小最大值倒推过程中，博弈树的某些部分并不会产生有意义的值，因而无需扩展这一部分。α-β剪枝过程就是利用这一点，将生成后继与倒推估计值相结合，及时剪掉一些无用分支，从而提高了搜索效率。
  本设计项目拟将人工智能技术与中国象棋博弈相结合，应用博弈树的剪枝技术和最大最小值原理进行搜索，找出博弈的最佳着法，实现基本的人机对弈过程，在实践中更好地学习并掌握人工智能博弈技术。

... ...       ... ...（暂略）

第一章　绪论

1.1 中国象棋
  中国象棋是我国国粹，历史悠久，普及流行。下棋双方根据对棋局形势的理解和对棋艺规律的掌握，调动车马，组织兵力，协调作战在棋盘这块特定的战场上，进行着象征性的军事战斗。
棋盘和棋子
象棋是棋子共三十二个，分为红黑两组，各十六个，由对弈双方各执一组，兵种是一样的，分为七种：
红方：帅,仕,相,车,马,炮,兵
黑方：将,士,象,车,马,炮,卒
其中帅与将,仕与士,相与象,兵与卒的作用完全相同，仅仅是为了区分红棋和黑棋。
棋子活动的场所，叫做“棋盘”，在长方形的平面上，绘有九条平行的竖线和十条平行的横线相交组成，共九十个交叉点，棋子就摆在这些交叉点上。中间第五,第六两横线之间未画竖线的空白地带，称为“河界”，整个棋盘就以“河界”分为相等的两部分；两方将帅坐镇,画“米”字方格的地方，叫做“九宫”。
将或帅
移动范围：它只能在王宫内移动。
移动规则：它每一步只可以水平或垂直移动一点。
士
移动范围：它只能在王宫内移动。
移动规则：它每一步只可以沿对角线方向移动一点。
象
移动范围：河界的一侧。
移动规则：它每一步只可以沿对角线方向移动两点，另外，在移动的过程中不能够穿越障碍。
马
移动范围：任何位置
移动规则：每一步只可以水平或垂直移动一点，再按对角线方面向左或者右移动。另移动的过程中不能够穿越障碍。
车
移动范围：任何位置
移动规则：可以水平或垂直方向移动任意个无阻碍的点。
炮
移动范围：任何位置
移动规则：移动起来和车很相似，但它必须跳过一个棋子来吃掉对方的一个棋子。
兵
移动范围：任何位置
移动规则：每步只能向前移动一点。过河以后，它便增加了向左右移动的能力，兵不允许向后移动。
胜,负,和
对局中，出现下列情况之一，本方算输，对方赢：
帅（将）被对方“将死”，即被对方将军却无法应将；
自己宣布认输；
走棋超时；
走棋时循环反复向对方将军三次，违反“不得将三将”的规定。
出现以下情况，算和局：
一方提议作和，对方同意；
双方走棋出现循环反复达三次，符合“不变作和”的规定，双方又不愿变着时。[1]

1.2 国内外象棋软件介绍
  自从计算机的出现，人们就一直在研究将博弈移植到计算机上，让计算机和人对弈。国际象棋方面，深蓝早已家喻户晓，1996年，深蓝与卡斯帕罗夫对战，并且在首局成功战胜了这位世界大师。“我能够感受到来自棋桌对面一种新型的智慧。”——加里·卡斯帕罗夫　
  以下是几个比较有名的中国象棋软件：
  象棋大师Ⅱ
  该软件的DOS版本出现于20年前，是一个比较早的中国象棋软件，在当时同类象棋对弈软件中棋力最高的。该软件虽然只能在DOS下稳定运行，但它的棋力却不容小看。1985年，该象棋程序的Windows版本出现了即象棋大师Ⅲ。
  随着象棋博弈程序研究的发展，后来的中国象棋软件的棋力已经达到了大师级的水平。

  棋海无涯 软件作者：郑明政,叶剑峰
  特点：强大的电脑下棋功能(总会荣誉六段证书)；强大的后端棋谱资料处理；独特的棋谱搜寻,开局分析。
  获得荣誉：弈天快刀杯第五；弈天长征杯第三十五；6th,7thOlympia银牌；31th新秀杯第三；6th将帅杯五段赛冠军 (升四段)；7th将帅杯五段赛冠军 (升五段)；7th将帅杯六段赛亚军；7th将帅杯七段赛季军 (荣誉六段)；8thOlympia第五；2004世界电脑象棋赛第四；2004启泰杯六段赛第五(对7位五段2胜2和3负)；2004启泰杯七段赛第四(对8位六段3胜4和1负)。

  象棋奇兵(xqmaster) 软件作者：赵明阳
  主要特点：
1.搜索速度快。即使是用老的赛扬机器，也能很快搜索到高层，在快棋上具有明显的优势。
2.支持64位cpu 多处理器系统以及NUMA系统 在64位cpu上速度可以提升47%(需要64位OS支持)。在双cpu系统中，速度可以提升93%。
3.极强的攻杀能力。在复杂的对攻局面下，优化的延伸搜索能力使得本软件能够对当前局面认识得更清楚。善于从乱战中取胜是本软件的一大特点。
4.严谨的审局。重视子力位置和棋形，对牵制和多子归边均有详细的考虑，行棋比较人性化。

  谢谢大师(Xiexie master)　软件作者：Pascal
  该中国象棋软件棋力强大。目前出版的官方版xiexie master2.3.0，棋力已可挑战真正大师，是目前最强的中国象棋软件。在2003年11月份世界奥林匹克电脑软体比赛中(8th Computer Olympiad, 2003)，得到银牌奖。在2004年6月份在台湾的中国象棋软件争霸赛，更击败众多强大的棋软，荣获冠军。其特点：中残局实力强大。常在开局吃亏的情形下，在中局扭转局势，在处下风时，能顶住对手的强攻。学习能力强。凡是对手下的好棋都被它一一学会，下次相同情形时就使用出来。用家用它越多，会感觉它越来越强。不怕读秒。在残局时，很快就想到12层次以上。可调校它的智能引擎，使它更机器人化(战术好，但战略差)，还是更人性化(大局观好，战略强)。[2]

1.3 中国象棋软件技术
  在中国象棋软件中，核心是搜索技术，比较常见的有：a-b搜索,最小-最大搜索,迭代加深,置换表法。[2]
  另外，随着研究的进行，出现了一些新的高级搜索方法。这些方法都是“带置换表的启发式a-b搜索”的扩展，其中静态搜索和空着裁剪是消除“水平线效应”的基本手段，而期望窗口,主要变例搜索(PVS)和MTD(f)都是a-b搜索的改进。并非所有的棋类游戏都会用到这些方法，而且使用起来会有一些负作用，因此归入高级搜索方法一点也不过分。比较常用的是空着技术。
空着向前裁剪
  空着向前裁剪(Null-Move Forward Pruning)，运用可能忽视重要路线的冒险策略，使得象棋的分枝因子锐减，它导致搜索深度的显著提高，因为大多数情况下它明显降低了搜索的数量。它的工作原理是裁剪大量无用着法而只保留好的。

1.4 本文工作重点
1) 程序界面设计和实现。
2) a-b剪枝搜索的具体实现。
3) MFC编程实现人机对奕。
4) 悔棋功能的设计和实现。

第二章　　常用搜索算法

2.1 概述
  人工智能常用的搜索算法包括基本搜索算法和启发式算法。[3, 8]
2.2 深度优先搜索
  图的深度优先遍历的递归定义：
  假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
  图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2.3 博弈策略 ... ...       ... ...