西洋跳棋智能程序设计
学 院
专 业
班 级
学 号
姓 名
指导教师
负责教师 计算机学院 计算机科学与技术
2016年6月
摘 要
随着社会发展，科技进步，电脑得以普及。电脑游戏伴随着网络和电脑的普及深深的吸引了很多玩家，特别是快节奏的生活，传统的两个人一张桌子的下棋方式逐渐被取缔，人机对弈棋牌类电脑游戏被越来越多的人认可。西洋跳棋作为一款益智类棋牌游戏，不仅可以休闲娱乐，达到游戏自身放松的目的，同时，可以锻炼玩家的思维能力。
计算机博弈是非常实际的计算机科学与技术研究课题，也是非常富有挑战性的人工智能领域的研究方向。西洋跳棋是一种平均分支因子较少的棋种，博弈树算法可以得到很好地应用。
本游戏是利用Qt 开发工具与C++开发语言，利用搜索算法设计最优落子的一款西洋跳棋人机博弈游戏。Qt 是一个多平台的C++图形用户界面应用程序框架，一种完全面向对象的的程序开发软件，具有很好地封装机制、较高的模块化程度和良好的应用性。C++是一种应用非常广泛的面向对象的计算机程序设计语言，利用C++语言在游戏中的编程，使得西洋跳棋游戏具有美观的界面，人机对弈方面电脑具有较高的智商。
本文主要是对西洋跳棋设计的详细阐述，分别从软件设计背景，需求分析，总体设计和详细设计深入的介绍了软件的开发，并通过对软件的调试分析详细介绍了软件的使用方法，同时，本文深入比较了多种搜素按算法在本设计中的应用。
关键词：西洋跳棋；人工智能；Qt ；C++
Abstract
With the development of society and the progress of science and technology, computer has been popularized. Computer games with the popularity of computer networks and deeply attracted a lot of players, especially the fast pace of life, traditional two table chess has gradually been banned, man-machine chess chess computer game is more and more people recognized. As a puzzle game of chess, checkers can not only entertainment, to achieve the goal of their game to relax, at the same time, you can exercise player's thinking ability.
Computer game is a very practical computer science and technology research, is very rich challenge in the field of artificial intelligence research direction. Checkers is an average branching factor less chess, the game tree algorithm can be applied well.
The game is using Qt development tools and C + + programming language, using search algorithms for the design of optimal Lazi a checkers human-computer game.Qt is a multi platform C + + graphical user interface application program framework, a fully object-oriented programming software, has a good encapsulation mechanism and high degree of modularization and good application of C + + is a kind of widely used object oriented computer programming language, using C + + language in game programming, makes checkers game with beautiful interface, man-machine chess electric brain has a higher IQ.
The main purpose of this paper is to checkers design are elaborated in detail, respectively, from the background of software design, demand analysis, general design and detailed design deeply introduced software development, and through the software debugging and analysis of the usage of the software are introduced in detail. At the same time, this paper with various search element according to the algorithm in the design of the application.
Keywords : checkers; artificial intelligence; Qt; C++
目 录
1 前言 ................................................................................................................................... 1
1.1 研究背景 . .................................................................................................................... 1
1.2 国内外研究状况 . ........................................................................................................ 1
1.3 研究内容 . .................................................................................................................... 2
1.4 课题意义 . .................................................................................................................... 2
2 需求分析及相关技术介绍 ............................................................................................... 3
2.1 软件设计总体目标 . .................................................................................................... 3
2.2 系统基本功能 . ............................................................................................................ 3
2.3 西洋跳棋游戏规则说明 . ............................................................................................ 4
2.4 相关技术介绍 . ............................................................................................................ 4
2.4.1 Qt软件简介 .......................................................................................................... 4
2.4.2 C++编程语言介绍 ................................................................................................ 5
2.5 系统技术需求 . ............................................................................................................ 5
3 系统分析及设计 ............................................................................................................... 6
3.1 系统总体设计 . ............................................................................................................ 6
3.1.1 模块化设计流程 .................................................................................................. 6
3.1.2 系统总体构成流程 .............................................................................................. 6
3.2 系统算法设计概述 . .................................................................................................... 7
3.3 系统特点及功能结构 . ................................................................................................ 7
3.3.1 系统特点 .............................................................................................................. 7
3.3.2 功能结构 .............................................................................................................. 7
4 详细设计 ........................................................................................................................... 9
4.1 游戏界面模块详细设计 . ............................................................................................ 9
4.2 棋盘设计模块详细设计 . .......................................................................................... 10
4.3 人机博弈模块设计详细设计 . .................................................................................. 12
4.3.1 博弈树算法设计 ................................................................................................ 12
4.3.2 局面评估设计 .................................................................................................... 12
4.3.3 走法生成 ............................................................................................................ 12
4.4 游戏规则模块详细设计 . .......................................................................................... 14
4.5 胜负判断模块详细设计 . .......................................................................................... 15
5 运行及调试 ..................................................................................................................... 17
5.1 开始界面调试情况 . .................................................................................................. 17
5.2 棋盘初始化调试情况 . .............................................................................................. 17
5.3 走棋调试 . .................................................................................................................. 18
5.4 胜负判断调试 . .......................................................................................................... 19
6 总结 ................................................................................................................................. 21
参考文献 ............................................................................................................................. 22
致 谢 ................................................................................................................................. 23
1 前言
1.1 研究背景
西洋跳棋的起源无法追溯，根据大多数棋艺史家的考证，现在认为西洋跳棋起源于法国的南部地区。当今，例如国际象棋等游戏规则在西方已经统一标准，拥有一套统一化的走棋规则，但西洋跳棋至根据地域不同今却流传着几十种不同的游戏规则，例如波兰跳棋、英国跳棋、中东跳棋等。西洋跳棋下棋过程特别注重玩家对整体棋局的掌控性。
西洋跳棋玩法种类繁多，本次设计采用最通用的西洋跳棋规则。双方轮流走子，玩家执红旗先行，人机轮流落子。规则规定：未成王的棋子只能沿斜线向对方左上或者右上前行一格(该格空出没有落子) ，且未成王的棋子只能前行不可后退。吃子时，对方的棋子在己方棋子斜对角格子的左上或者右上，且对方棋子左上或者右上格子没有其他棋子。加冕成王，游戏在双方底界设计了加冕线，当己方棋子到达对方底边界时，加冕成王，王棋与未成网的棋子区别在于王棋可以后退。胜负判断为两种情况，当一方棋子数量为零时，判断为对方游戏胜利；当双方棋子都无法移动后，由局面评估给出胜利一方。
1.2 国内外研究状况
当今，西洋跳棋在流行5000年的历史之后已经被计算机完全攻破。多年来，西洋跳棋一直被众多数学家、电脑学家和英国跳棋专家研究，取得了非常显著的成功。早在1989年，乔纳森·谢弗（Jonathan Schaeffer ）开始了西洋跳棋项目的研究，在1994年，谢弗的计算机程序已经可以击败当时人类最顶尖的西洋跳棋大师。在之后的研究中，乔纳森·谢弗联手艾伯特大学的学者共同研究出西洋跳棋程序“奇努克”，被誉为当今世界无法被战胜的跳棋程序。
自1950年，香侬首次提出国际象棋解决方案揭开机器博弈发展序幕之后，诸多计算机爱好者和科学家在此领域不断研究，在九十年代初期，计算机连续战胜很多棋道大师，特别是1997年“深蓝”战胜世界棋王，人工智能在计算机博弈方面取得辉煌的成就。之后的研究中，相继攻克中国象棋等众多棋类。2016年3月谷歌Alpha Go 与韩国与韩国棋手李世石进行的围棋比赛中计算机以4：1战胜对手获得胜利，人工智能在下棋程序又一次重大进步。
1.3 研究内容
西洋跳棋是一款规则简单，易于上手的游戏，由于游戏的特性，可以提高玩家对全局的把握能力，并且可以提高玩家逻辑思维能力。本次设计研究内容主要包括以下介个方面：
游戏界面设计：游戏界面的设计风格直接影响到玩家对游戏的兴趣，所以游戏界面设计在游戏设计中起到非常重要的作用，游戏界面设计主要为游戏开始界面。
游戏棋盘设计：本游戏棋盘设计为标准西洋跳棋10*10的棋盘设计，棋盘中100个格子黑白分明落子明确，玩家可以很容易掌握棋盘。
落子设计：落子设计分为玩家落子和电脑落子。玩家落子只需遵从游戏规则即可，电脑落子采用博弈树搜索算法，寻找最优落子方案。
局面评估设计：局面评估采用分类加权计算双方优势，最终判断局面胜负情况。
1.4 课题意义
目前，市面上棋牌类游戏种类繁多，例如中国象棋、跳棋等棋类游戏版本众多，但西洋跳棋游戏却在棋牌类游戏中特别少见，特别是网络上玩家可选择的西洋跳棋游戏制作简单，画面粗糙，加上许多让玩家不喜的广告，很难满足西洋跳棋爱好者的兴趣。因此需要一款设计画面精美，走棋风格合理的西洋跳棋程序来满足西洋跳棋爱好者的兴趣。
本设计在过程中注重界面设计，Qt 软件独特的界面设计功能在设计中可以为玩家设计出精美的界面，精美的开始界面有利于提高玩家的游戏乐趣。在游戏设计中，略高的电脑走法，使玩家不会感到枯燥，玩家在下棋过程中提高自身棋艺的同时，不仅可以起到放松的作用，还可以锻炼玩家的逻辑思维能力和智力。
2 需求分析及相关技术介绍
2.1 软件设计总体目标
西洋跳棋是一款益智类人机对弈棋类游戏。本款软件主要针对的用户为西洋跳棋爱好者和初学者玩家，玩家在使用软件过程中达到休闲娱乐，提高棋艺的目的。设计目标：
第一，界面设计独特新颖，轻松自然，可以吸引玩家，使玩家达到放松的目的； 第二，游戏难度适中，电脑走棋算法合理，适合初级玩家使用，使玩家在使用过程中可以达到提高棋艺的目的，但游戏难度不会过大，不可以让玩家使用过程中因游戏难度过高感到枯燥。
2.2 系统基本功能
本软件使用对象为游戏玩家，以界面新颖，风格独特，走棋合理的特点为主，软件应包括游戏开始界面，棋盘，棋子，人机博弈，局面评估，胜负判断等内容，设计分为五个模块：
1) 开设界面模块：用户进入游戏，首先是欢迎界面，既游戏开始界面，玩家点击开始游戏按钮，进入游戏。
2) 棋盘设计：玩家进入游戏后，生成初始棋盘，棋盘为10*10共一百个格子，棋盘设计格子为黑白两色分别交错排布，便与玩家区分，棋子设计要求与棋盘形成对比色彩，便于玩家操作。
3) 人机对弈模块：本模块为程序设计的核心模块，玩家落子后，电脑根据搜索算法找到最优落子方法，可与玩家进行对弈。
4) 下棋规则模块：本模块为西阳跳棋程序的基础模块，判断落子地方和吃子情况。
5) 胜负判断模块：本模块的目的是判断游戏胜负。
以上为游戏软件主要功能设计，系统功能模块如图2.1所示
图2.1 软件功能模块图
2.3 西洋跳棋游戏规则说明
1. 游戏双方轮流走棋。
2. 棋子为成为王棋前，棋子只能向左上角或者右上角且无人占据的格子斜走一格。吃子时，敌方的棋子必须在己方棋子的左上角或者右上角的格子，而且该敌方棋子对应的左上角或者右上角必须没有棋子。
3. 当棋子到了对方底线，该棋子就可以加冕成王棋，王棋可以向后移动。
4. 若一个棋子可以吃棋，则必须吃子。
5. 若一方无法行走或者所有棋子均被吃，则该方算输。
2.4 相关技术介绍
本软件利用Qt5.2.0软件编写，编程语言为C++计算机编程语言编写。
2.4.1 Qt 软件简介
Qt 是一个跨平台的C++应用程序和图形界面开发框架。于1991年由奇趣科技研发，2007年之后，Qt 跨平台开发战略得以迅速发展，现在广泛用于图形用户界面程序开发。
Qt 的特点：
优良的跨平台特性：Qt 支持多平台运行，在不同平台下无需修改源代码便可以生成特有的图形界面风格。
面向对象：由于Qt 拥有非常良好的封装机制，所以，Qt 的模块化程度较高，不同元件之间协同工作简方便。
丰富的应用程序接口(API):Qt拥有非常多的C++类。
除此之外，Qt 还拥有大量的开发文档，支持XML 技术。
自Qt4.6之后Qt 中引进Qt Quick ，开发人员与设计人员可以协同创建动画模式界面和应用程序。
Qt 拥有简单漂亮的界面，同时简单易学并且资料丰富，实用性很强。
2.4.2 C++编程语言介绍
C++编程语言是一种面向对象的程序设计语言，是由C 语言发展而来。C++继承了C 语言大部分特点，并在C 语言的基础上进行了完善，添加了类，C++能够与C 语言相互兼容。
C++编程语言的优势：
1．在高级语言中处理运行速度最快的面向对象程序设计语言，目前市面上大多数游戏软件都是又C++来实现的。 2．语言灵活，功能强大，特别是类层次结构的设计。
3．C++标准定义细致，具有严谨、精确的特性，语法思路参差分明，语法结构明确。
2.5 系统技术需求
本程序采用Qt 开发环境，编程语言使用C++编程语言的西洋跳棋游戏。
开发环境：Qt Creator5.2.0
运行环境：Windows7 x64
3 系统分析及设计
本章内容是在第二章的需求分析的基础上形成的程序设计蓝图，作为后续编码设计的依据。本章主要介绍了西洋跳棋程序开发的总体设计。
3.1 系统总体设计
3.1.1 模块化设计流程
根据需求分析，游戏设计需要六大模块，每个模块功能实现如下： 开设界面模块：设计开始界面。
绘制棋盘与棋子设计设计模块：绘制棋盘，设计棋子。 人机对弈模块：设计算法，实现人机对弈。 下棋规则模块：根据规则判断落子地方和吃子情况。 胜负判断模块：设计算法判断游戏胜负。
3.1.2 系统总体构成流程
西洋跳棋博弈软件构成如图3.1所示
图3.1 西洋跳棋博弈软件构成图
乙方为玩家，甲方为电脑。乙方遵循游戏规则落子，甲方通过对当前局面进行局面评估，然后进行博弈树搜索算法进行搜索，形成当前最优落子，生成走法并落子，甲、乙双方落子后，当前局面在棋盘显示，电脑循环对棋盘当前局面扫描，经当前局面反馈给甲方机器博弈系统，甲方重新进行局面评估，生成走法。
3.2 系统算法设计概述
西洋跳棋人机对弈模块为系统的核心模块，算法采用极大极小值算法，算法的本质思想是：一方总是寻找对己方最有利的的走法，而另一方总是寻找对对方最不利的走法，其搜索树如图3.2所示
图3.2 极大—极小搜索算法树
根据算法树可知Min 节点总是从其下一层Max 中挑选估值最小的节点进行估值，Max 节点刚好相反。在走棋过程中，遍历整颗搜索树，寻找对己方最有利的走法走子。
3.3 系统特点及功能结构
3.3.1 系统特点
1．具有和谐的界面。界面设计美观，简洁。
2．具有易操作性。本系统避免过多按钮在游戏中给玩家带来的不便，设计简单，已于操作。
3．适用于广大西洋跳棋爱好者，面向性广阔。 4．本系统是本地游戏，安全可靠
3.3.2 功能结构
通过上文需求分析和总体设计，本系统以5个模块为目标设计。其中，下棋规则模块为基础，为玩家和电脑落子提供基础规则，人机对弈模块为系统核心，本次设计
采用极大极小人机博弈搜索算法设计了合理的电脑落子算法，绘制棋盘模块和胜负判断模块为本次设计的前提，为游戏的可行性提供保障，最后是游戏界面设计，为整体游戏进行美化。其具体模块及主要功能结构图如图3.2所示
图3.2 西洋跳棋整体设计及主要功能结构图
4 详细设计
4.1 游戏界面模块详细设计
为了使游戏界面美观大方，从网络上选取图片，并用美图秀秀软件对所选图片进行美图修改，利用Qt 库自带的paintEvent(QPaintEvent *e)函数设计了游戏开始界面，开始界面采用绿色图片作为背景图片，一方面可以缓解玩家视觉疲劳，另一方面，背景颜色与开始游戏按钮色彩区分明确，使整体设计达到简单、美观的效果。游
图4.1 游戏界面模块流程图
程序运行首先进入游戏开始界面，点击开始游戏按钮，将进入游戏。界面设计尺寸长为10cm ，宽为8cm ，并在界面中添加“开始游戏”按钮，该按钮有Qt 编程工具中的界面布局工具完成，关键代码如图4.2所示
图4.2 界面设计模块开始游戏按钮添加关键程序
通过界面背景设计和按钮添加，开始界面模块设计完成，开始界面模块设计效果图如图4.3所示
图4.3 界面设计效果图
4.2 棋盘设计模块详细设计
该模块的主要功能是绘制棋盘和设计棋子，棋盘与棋子分为两种状态，一种是初始化状态，当点击开始游戏按钮后，进入游戏，此时，棋盘显示为初始化状态。初始化状态时，甲、乙双方各持有15枚棋子处于双方边界。另一种状态是走子或者吃子时，棋盘中棋子位置发生改变，甲、乙双方轮流走子，每次走子之后都将跟新一遍棋盘。棋盘绘制与棋子设计模块流程图如图4.4所示
图4.4 棋盘绘制与棋子设计模块
棋盘设计包括棋盘绘制和棋子设计在高性能的博弈设计中，比特棋盘应用较为广泛，西洋跳棋智能程序设计也采用比特棋盘设计而成。棋盘设计了10*10共100个格
子，其中50个格子用来落子，棋盘设计用4个64位无符号整型设计而成，如表4.2所示
表4.1 棋子位置与对应比特关系表
由四元素组生成棋盘，棋盘初始状态为, 棋盘设计效果图如图4.2所示
图4.5 棋盘设计效果图
4.3 人机博弈模块设计详细设计
4.3.1 博弈树算法设计
人机博弈模块为本次设计核心模块，而博弈树算法为本次设计核心算法。该模块设计主要目的是完成人机对弈过程。该过程设计核心算法为极大-极小搜索算法，算法的核心思想是，一方总是寻找对己方最有利的走法，另一方总是寻找对对方最不利的走法。在本次设计中，设计玩家为蓝色方，电脑为红色方，红色方为极大方，博弈树搜算算法设计的核心是红方通过搜索算法和局面评估函数找到对自己最有利的走法。计算机走棋由函数computer_go()设计完成。
4.3.2 局面评估设计
西洋跳棋是零和游戏，局面评估影响因素众多，本次设计主要对以下几个方面进行评估，分别为棋子和王棋的数量，处于安全位置的棋子和王棋的数量（安全位置是指处于底边或者边界无法被对方吃子的位置），可以移动的棋子和王棋数量，还有防御棋子数量和进攻棋子数量。估值函数设计思路为：
估值方法=电脑棋子数-选手棋子数-0.5*威胁棋子数(可能会被吃掉的棋子) 估值函数最重要的任务是找到威胁棋子，在程序中由CalValue （）函数设计完成。在设计中，函数InThreat （）判断该棋子是否有可能被对方棋子吃掉，判断标准是对该棋子左上、右上、左下、右下分别判断。函数InBoard （）则判断棋子当前位置是否处于边界。
4.3.3 走法生成
(1) 普通棋子走法生成
普通棋子走棋规则为棋子可沿对角线对方方向棋子周边移动一个，移动方向的格子为空。遇到吃子时，被吃的棋子周围有空格才可以吃子，其设计流程如下，普通棋子走棋流程图如图4.6所示
① 若棋子列表不为空，则从棋子列表中取出一个棋子；
② 对该棋子相邻四个方向进行判断，若存在对方棋子且对方棋子后方格子为空，则将该走法加入走法栈中，否则到第③步；
③ 若走法栈不为空，则从走法栈中取出一个走法；
④ 如果从棋子位置可以继续吃子，则按照第②步继续走子；
⑤ 否则若当前吃子数量大于最大吃子数量，则清空吃子走法列表； ⑥ 若当前吃子数量等于最大吃子数量，则将该走法加入走法列表； ⑦ 否则到第③步；
⑧ 若该走法最后一步落在加冕线上，则棋子加冕成王，否则到第①步； ⑨ 否则吃子走法终结
图4.6 普通棋子走法生成流程图
(2) 王棋走法生成
王棋是由普通棋子到达加冕线转换而来，因此王棋走法与普通棋子走法有部分相同，王棋走发生成流程图如图4.7所示，王棋走法流程如下，
① 若棋子列表不为空，则从棋子列表中取出一个棋子；
② 对该棋子相邻四个方向进行判断，若从在对方棋子且对方棋子为空，则将该走法加入走法栈中，
③ 将后面所有空格子走法加入走法栈中，否则到第④步； ④ 若走法栈不为空，则从走法栈中取出一个走法；
⑤ 如果从棋子位置可以继续吃子，则按照第②步继续走子；
⑥ 否则若当前吃子数量大于最大吃子数量，则清空吃子走法列表； ⑦ 否则若当前吃子数量等于最大吃子数量，则将该走法加入走法列表； ⑧ 否则到第④步； ⑨ 否则到第①步； ⑩ 否则吃子走法终结
图4.7 王棋走法生成流程图
4.4 游戏规则模块详细设计
本模块主要功能是实现游戏按照规则落子，西洋跳棋游戏规则为，游戏双方轮流走棋。棋子为成为王棋前，棋子只能向左上角或者右上角且无人占据的格子斜走一格。吃子时，敌方的棋子必须在己方棋子的左上角或者右上角的格子，而且该敌方棋子对应的左上角或者右上角必须没有棋子。当棋子到了对方底线，该棋子就可以加冕成王棋，王棋可以向后移动。若一个棋子可以吃棋，则必须吃子。若一方无法行走或者所有棋子均被吃，则该方算输。游戏规则在程序中有函数CanMove （）设计完成，普通走子规则由函数Computer_Can_Move（）生成，普通棋子吃子规则由函数
Computer_Can_Eat（）设计完成。代码if(_piece->GetStatus()!=piece::king) return false;完成了普通棋子不能后退，王棋可以后退的游戏规则。
游戏规则模块流程图如图4.8所示
图4.8 游戏规则模块流程
4.5 胜负判断模块详细设计
本模块设计主要是在游戏结束后判断玩家和电脑的胜负情况。胜负判断有两种情况，一种是一方无法走棋，则该方判定为输，另一种是一方在棋盘中棋子数目为零。胜负判断流程图如下图4.8所示
图4.9 胜负判断模块流程图
双方轮流落子之后，每次落子都会更新棋盘，根据流程图设计，首先由系统判定游戏是否结束，在程序设计中，游戏是否结束设计函数GameOver()判定，判定标准为一方棋子数目为零或者无法走子，判定游戏结束之后，判定玩家和电脑的赢家。
程序中函数IsHostWin()判定电脑是否取得胜利，玩家胜负判定由函IsAwayWin()设计，评定流程与计算机是否胜利流程相同，判定条件为客队棋子是否可以移动，计算机判定胜利过程流程图如图4.9所示
图4.10 计算机胜负判定流程图
5 运行及调试
5.1 开始界面调试情况
程序运行，进入游戏开始界面，如图5.1所示
图5.1 游戏开始界面
运行情况说明：程序运行，进入游戏开始界面，界面画质清楚，点击开始游戏按钮，进入游戏良好。
5.2 棋盘初始化调试情况
游戏开始，进入游戏，此时棋盘为初始化状态，如图5.2所示
图5.2 棋盘初始化界面
运行情况说明：棋盘初始化状态良好，按照详细设计，棋盘为10*10共100个棋格，棋盘底色为黑白两色，双方各15个棋子排布在双方底界。棋子与棋盘颜色分明。
5.3 走棋调试
玩家执蓝旗现行，电脑后手，走子按照规则沿斜对角线方向现行，每次移动一个棋子，可吃子，运行结果如图5.3，5.4所示
图5.3 普通棋子走棋图
图5.4 王棋走子运行图
运行情况说明：普通棋子走棋良好，遇到可吃棋子自动吃子，普通棋子到对方底线变成王棋，王棋走子状况良好，测试表如表5.1所示
表5.1走棋测试表
5.4 胜负判断调试
当一方棋子为零或一方无棋可走时，系统判断胜负并作出评断。
一方棋子数目为零时系统做出评判如图所5.5所示
图5.5 一方棋子数目为零系统做出胜负评判
当一方无法走棋时，电脑做出胜负判断如图5.6所示
图5.6 一方无法走棋时系统做出胜负评判图
运行结果说明：当一方棋子为零或者无棋可走时，系统做出胜负评判并作出提示，运行状况稳定。
6 总结
本章主要内容是对西洋跳棋智能程序设计的总结。本次设计应用C++编程语言，在Qt 开发平台设计编写，完成了游戏开始界面设计、棋盘绘制、棋子走法生成、胜负判断等项目，设计完成的西洋跳棋智能程序界面精美，走棋合理，操作简单，符合本次设计要求。
项目优势：
1. 优良的游戏界面。与网络上流传的西洋跳棋程序比较，本次设计拥有精美的界面设计，开始界面简单易用，避免了玩家错误点击导致无法运行的难题，同时棋盘棋子设计风格独特黑白底色的棋盘设计，玩家可以清楚的思考下一步走棋，红色与蓝色棋子色彩分明，玩家在走棋过程中能够清楚看清自己的棋子位置，便于掌控全局。棋盘与棋子形成强烈的色彩感，可吸引玩家。
2. 合理的走棋算法。本次设计采用经典的极大—极小搜算算法设计，在设计过程中，难度适中。设计中，较高的电脑棋艺水平可以提高玩家的棋艺水平，游戏设置水平适中，玩家在娱乐中不会感到枯燥。
项目不足：
1. 游戏设计中，注重走棋的设计，对娱乐性设计不足，缺少一些音乐文等娱乐项目。
2. 无法人人对战，按照设计要求，本次设计是人机对弈，在设计过程中，没有设计人人对弈模式，整体游戏有所欠缺。
本次毕业设计过程中，出现了很多问题，是对平时学习能力欠缺最直观的反映，在设计中，通过多方面的学习，完善了之前学习的不足，同时，设计中要求的Qt 软件在此之前没有使用过，通过本次设计，学会了使用新的工具。在设计中，不仅学到了许多技术，同时不断克服自身不够严谨的态度，收益良多。
参考文献
[1] 谭浩强.Java 语言程序设计(第三版)[M].北京:清华大学出版社,2008
[2] 焦尚斌，刘丁. 博弈树置换表启发式算法研究[J].计算机工程应用，2010（06）
[3] 王娇，徐兴和. 计算机博弈：人工智能的前沿领域—全国大学生计算机博弈大
赛[J].计算机教育.2012（07）
[4] 张利群. 五道棋计算机博弈程序设计[J].计算机工程.2010（10）
[5] 李天明. 并行计算机博弈系统设计与改进[J].电子制作.2014（21）
[6] 张颖，李祖枢. 棋类计算机博弈系统的主要研究方法及在6子棋上的应用[J].
重庆工学院学报（自然科学版）.2008（09）
[7] Mustapha Lakrib, Tewfik Sari. Time averaging for ordinary differential equations
and retarded functional differential equations[J]. Electronic Journal of Differential Equations, 2010, 2010(40,).
[8] Merrick J. DeWitt, Bradley S. Prall, Robert J. Levis. Orientational averaging in the
intense field tunnel ionization of molecules[J]. The Journal of Chemical Physics, 2000, 113(4).
[9] 李海峰．基于J2EE 技术开发高性能BBS 论坛［D ］. 上海：华东师范大学，2006
[10] 汪辉松，汪隽, 杜群, 曾贵华. Self-dual Codes Defined on Factor Graphs[J].Journal of Shanghai Jiaotong University.2007(04)
[11] 赵志宏, 李蓓蓓, 耿兆丰, 徐敏. Imitation of Fabric Flagging Based on Amplitude Modulation[J]. Journal of Donghua University(English Edition). 2007(06)
[12] 刘雅靖. 计算机博弈之六子棋的主要技术分析[J].电脑知识与术.2011(10)
[13] 汤云雄，董从民. 计算机博弈系统在中国象棋教学中的应用[J].科技信
息.2011(19)
[14] 张丽娜. 机器人功能与价格曲线的博弈[N].消费日报.2016-05-05 (A02)
[15] 马艳红. 手术机器人操作规范化管理“告急”[N].中国医药报.2016-03-29
(003）
[16] 梁莹. 广西首台“达芬奇”手术机器人上岗[N].广西日报.2016-04-13 (004)
致 谢
在本次毕业设计，首先感谢我的知道老师XXX 老师。XXX 老师具有严肃的科学态度，严谨的治学精神，精益求精的工作作风，我在她的身上学到了许多除知识之外的东西，对我今后影响意义深远。XXX 老师在我的本次毕业设计中提供了很大帮助，从选题开始，到毕设中存在问题的解决，XXX 老师事无巨细，亲力亲为的给予我详细解答，是我受益良多。由于本人之前态度懒散，不够认真，XXX 老师不厌其烦的提醒我，再跟胡老师的交流中，老师的谆谆教导及老师严谨的科研态度，时刻影响着我，是我克服了许多自身的不足，收获很大。XXX 老师知识渊博，毕设中出现了许多问题，老师给我的解决意见在设计中起到了非常重要的作用。在此，向XXX 老师表示衷心的感谢。
其次，要感谢在本次毕业设计中帮助过我的同学。身边的同学在自己时间很紧的情况下，依旧热心的帮助我，特别是刚开始软件的安装过程中，新软件的安装出新了问题，在与同学的探讨和同学的帮助下，最终解决了问题。同时，由于本次设计的算法难度很大，同学在我算法的选择上给了我很重要的意见，最后选择的算法非常合理，使得毕业设计顺利进行。在此，感谢所有帮助过我的同学。
最后，感谢学校，学院给予我的这次毕业计机会，在本次毕业设计中，我学到了很多东西，毕业设计过程中，我深刻感觉到自己平时的不足之处，这次毕业设计，我不仅对之前的知识有了进一步的生化，同时改正了许多自身的缺点。在此，感谢学校和学院给了我这次机会，是我成长。
感谢在本次毕业设计中辛苦工作的老师，不论是出题，还是答辩，老师都付出了很多，在此向向所有老师表示感谢。
即将毕业，四年的大学生活使我收获巨大，感谢学校的培养，感谢老师的关心，感谢同学的帮助。在今后的生活中，努力将自身所学回报社会，为母校争光。
西洋跳棋智能程序设计
学 院
专 业
班 级
学 号
姓 名
指导教师
负责教师 计算机学院 计算机科学与技术
2016年6月
摘 要
随着社会发展，科技进步，电脑得以普及。电脑游戏伴随着网络和电脑的普及深深的吸引了很多玩家，特别是快节奏的生活，传统的两个人一张桌子的下棋方式逐渐被取缔，人机对弈棋牌类电脑游戏被越来越多的人认可。西洋跳棋作为一款益智类棋牌游戏，不仅可以休闲娱乐，达到游戏自身放松的目的，同时，可以锻炼玩家的思维能力。
计算机博弈是非常实际的计算机科学与技术研究课题，也是非常富有挑战性的人工智能领域的研究方向。西洋跳棋是一种平均分支因子较少的棋种，博弈树算法可以得到很好地应用。
本游戏是利用Qt 开发工具与C++开发语言，利用搜索算法设计最优落子的一款西洋跳棋人机博弈游戏。Qt 是一个多平台的C++图形用户界面应用程序框架，一种完全面向对象的的程序开发软件，具有很好地封装机制、较高的模块化程度和良好的应用性。C++是一种应用非常广泛的面向对象的计算机程序设计语言，利用C++语言在游戏中的编程，使得西洋跳棋游戏具有美观的界面，人机对弈方面电脑具有较高的智商。
本文主要是对西洋跳棋设计的详细阐述，分别从软件设计背景，需求分析，总体设计和详细设计深入的介绍了软件的开发，并通过对软件的调试分析详细介绍了软件的使用方法，同时，本文深入比较了多种搜素按算法在本设计中的应用。
关键词：西洋跳棋；人工智能；Qt ；C++
Abstract
With the development of society and the progress of science and technology, computer has been popularized. Computer games with the popularity of computer networks and deeply attracted a lot of players, especially the fast pace of life, traditional two table chess has gradually been banned, man-machine chess chess computer game is more and more people recognized. As a puzzle game of chess, checkers can not only entertainment, to achieve the goal of their game to relax, at the same time, you can exercise player's thinking ability.
Computer game is a very practical computer science and technology research, is very rich challenge in the field of artificial intelligence research direction. Checkers is an average branching factor less chess, the game tree algorithm can be applied well.
The game is using Qt development tools and C + + programming language, using search algorithms for the design of optimal Lazi a checkers human-computer game.Qt is a multi platform C + + graphical user interface application program framework, a fully object-oriented programming software, has a good encapsulation mechanism and high degree of modularization and good application of C + + is a kind of widely used object oriented computer programming language, using C + + language in game programming, makes checkers game with beautiful interface, man-machine chess electric brain has a higher IQ.
The main purpose of this paper is to checkers design are elaborated in detail, respectively, from the background of software design, demand analysis, general design and detailed design deeply introduced software development, and through the software debugging and analysis of the usage of the software are introduced in detail. At the same time, this paper with various search element according to the algorithm in the design of the application.
Keywords : checkers; artificial intelligence; Qt; C++
目 录
1 前言 ................................................................................................................................... 1
1.1 研究背景 . .................................................................................................................... 1
1.2 国内外研究状况 . ........................................................................................................ 1
1.3 研究内容 . .................................................................................................................... 2
1.4 课题意义 . .................................................................................................................... 2
2 需求分析及相关技术介绍 ............................................................................................... 3
2.1 软件设计总体目标 . .................................................................................................... 3
2.2 系统基本功能 . ............................................................................................................ 3
2.3 西洋跳棋游戏规则说明 . ............................................................................................ 4
2.4 相关技术介绍 . ............................................................................................................ 4
2.4.1 Qt软件简介 .......................................................................................................... 4
2.4.2 C++编程语言介绍 ................................................................................................ 5
2.5 系统技术需求 . ............................................................................................................ 5
3 系统分析及设计 ............................................................................................................... 6
3.1 系统总体设计 . ............................................................................................................ 6
3.1.1 模块化设计流程 .................................................................................................. 6
3.1.2 系统总体构成流程 .............................................................................................. 6
3.2 系统算法设计概述 . .................................................................................................... 7
3.3 系统特点及功能结构 . ................................................................................................ 7
3.3.1 系统特点 .............................................................................................................. 7
3.3.2 功能结构 .............................................................................................................. 7
4 详细设计 ........................................................................................................................... 9
4.1 游戏界面模块详细设计 . ............................................................................................ 9
4.2 棋盘设计模块详细设计 . .......................................................................................... 10
4.3 人机博弈模块设计详细设计 . .................................................................................. 12
4.3.1 博弈树算法设计 ................................................................................................ 12
4.3.2 局面评估设计 .................................................................................................... 12
4.3.3 走法生成 ............................................................................................................ 12
4.4 游戏规则模块详细设计 . .......................................................................................... 14
4.5 胜负判断模块详细设计 . .......................................................................................... 15
5 运行及调试 ..................................................................................................................... 17
5.1 开始界面调试情况 . .................................................................................................. 17
5.2 棋盘初始化调试情况 . .............................................................................................. 17
5.3 走棋调试 . .................................................................................................................. 18
5.4 胜负判断调试 . .......................................................................................................... 19
6 总结 ................................................................................................................................. 21
参考文献 ............................................................................................................................. 22
致 谢 ................................................................................................................................. 23
1 前言
1.1 研究背景
西洋跳棋的起源无法追溯，根据大多数棋艺史家的考证，现在认为西洋跳棋起源于法国的南部地区。当今，例如国际象棋等游戏规则在西方已经统一标准，拥有一套统一化的走棋规则，但西洋跳棋至根据地域不同今却流传着几十种不同的游戏规则，例如波兰跳棋、英国跳棋、中东跳棋等。西洋跳棋下棋过程特别注重玩家对整体棋局的掌控性。
西洋跳棋玩法种类繁多，本次设计采用最通用的西洋跳棋规则。双方轮流走子，玩家执红旗先行，人机轮流落子。规则规定：未成王的棋子只能沿斜线向对方左上或者右上前行一格(该格空出没有落子) ，且未成王的棋子只能前行不可后退。吃子时，对方的棋子在己方棋子斜对角格子的左上或者右上，且对方棋子左上或者右上格子没有其他棋子。加冕成王，游戏在双方底界设计了加冕线，当己方棋子到达对方底边界时，加冕成王，王棋与未成网的棋子区别在于王棋可以后退。胜负判断为两种情况，当一方棋子数量为零时，判断为对方游戏胜利；当双方棋子都无法移动后，由局面评估给出胜利一方。
1.2 国内外研究状况
当今，西洋跳棋在流行5000年的历史之后已经被计算机完全攻破。多年来，西洋跳棋一直被众多数学家、电脑学家和英国跳棋专家研究，取得了非常显著的成功。早在1989年，乔纳森·谢弗（Jonathan Schaeffer ）开始了西洋跳棋项目的研究，在1994年，谢弗的计算机程序已经可以击败当时人类最顶尖的西洋跳棋大师。在之后的研究中，乔纳森·谢弗联手艾伯特大学的学者共同研究出西洋跳棋程序“奇努克”，被誉为当今世界无法被战胜的跳棋程序。
自1950年，香侬首次提出国际象棋解决方案揭开机器博弈发展序幕之后，诸多计算机爱好者和科学家在此领域不断研究，在九十年代初期，计算机连续战胜很多棋道大师，特别是1997年“深蓝”战胜世界棋王，人工智能在计算机博弈方面取得辉煌的成就。之后的研究中，相继攻克中国象棋等众多棋类。2016年3月谷歌Alpha Go 与韩国与韩国棋手李世石进行的围棋比赛中计算机以4：1战胜对手获得胜利，人工智能在下棋程序又一次重大进步。
1.3 研究内容
西洋跳棋是一款规则简单，易于上手的游戏，由于游戏的特性，可以提高玩家对全局的把握能力，并且可以提高玩家逻辑思维能力。本次设计研究内容主要包括以下介个方面：
游戏界面设计：游戏界面的设计风格直接影响到玩家对游戏的兴趣，所以游戏界面设计在游戏设计中起到非常重要的作用，游戏界面设计主要为游戏开始界面。
游戏棋盘设计：本游戏棋盘设计为标准西洋跳棋10*10的棋盘设计，棋盘中100个格子黑白分明落子明确，玩家可以很容易掌握棋盘。
落子设计：落子设计分为玩家落子和电脑落子。玩家落子只需遵从游戏规则即可，电脑落子采用博弈树搜索算法，寻找最优落子方案。
局面评估设计：局面评估采用分类加权计算双方优势，最终判断局面胜负情况。
1.4 课题意义
目前，市面上棋牌类游戏种类繁多，例如中国象棋、跳棋等棋类游戏版本众多，但西洋跳棋游戏却在棋牌类游戏中特别少见，特别是网络上玩家可选择的西洋跳棋游戏制作简单，画面粗糙，加上许多让玩家不喜的广告，很难满足西洋跳棋爱好者的兴趣。因此需要一款设计画面精美，走棋风格合理的西洋跳棋程序来满足西洋跳棋爱好者的兴趣。
本设计在过程中注重界面设计，Qt 软件独特的界面设计功能在设计中可以为玩家设计出精美的界面，精美的开始界面有利于提高玩家的游戏乐趣。在游戏设计中，略高的电脑走法，使玩家不会感到枯燥，玩家在下棋过程中提高自身棋艺的同时，不仅可以起到放松的作用，还可以锻炼玩家的逻辑思维能力和智力。
2 需求分析及相关技术介绍
2.1 软件设计总体目标
西洋跳棋是一款益智类人机对弈棋类游戏。本款软件主要针对的用户为西洋跳棋爱好者和初学者玩家，玩家在使用软件过程中达到休闲娱乐，提高棋艺的目的。设计目标：
第一，界面设计独特新颖，轻松自然，可以吸引玩家，使玩家达到放松的目的； 第二，游戏难度适中，电脑走棋算法合理，适合初级玩家使用，使玩家在使用过程中可以达到提高棋艺的目的，但游戏难度不会过大，不可以让玩家使用过程中因游戏难度过高感到枯燥。
2.2 系统基本功能
本软件使用对象为游戏玩家，以界面新颖，风格独特，走棋合理的特点为主，软件应包括游戏开始界面，棋盘，棋子，人机博弈，局面评估，胜负判断等内容，设计分为五个模块：
1) 开设界面模块：用户进入游戏，首先是欢迎界面，既游戏开始界面，玩家点击开始游戏按钮，进入游戏。
2) 棋盘设计：玩家进入游戏后，生成初始棋盘，棋盘为10*10共一百个格子，棋盘设计格子为黑白两色分别交错排布，便与玩家区分，棋子设计要求与棋盘形成对比色彩，便于玩家操作。
3) 人机对弈模块：本模块为程序设计的核心模块，玩家落子后，电脑根据搜索算法找到最优落子方法，可与玩家进行对弈。
4) 下棋规则模块：本模块为西阳跳棋程序的基础模块，判断落子地方和吃子情况。
5) 胜负判断模块：本模块的目的是判断游戏胜负。
以上为游戏软件主要功能设计，系统功能模块如图2.1所示
图2.1 软件功能模块图
2.3 西洋跳棋游戏规则说明
1. 游戏双方轮流走棋。
2. 棋子为成为王棋前，棋子只能向左上角或者右上角且无人占据的格子斜走一格。吃子时，敌方的棋子必须在己方棋子的左上角或者右上角的格子，而且该敌方棋子对应的左上角或者右上角必须没有棋子。
3. 当棋子到了对方底线，该棋子就可以加冕成王棋，王棋可以向后移动。
4. 若一个棋子可以吃棋，则必须吃子。
5. 若一方无法行走或者所有棋子均被吃，则该方算输。
2.4 相关技术介绍
本软件利用Qt5.2.0软件编写，编程语言为C++计算机编程语言编写。
2.4.1 Qt 软件简介
Qt 是一个跨平台的C++应用程序和图形界面开发框架。于1991年由奇趣科技研发，2007年之后，Qt 跨平台开发战略得以迅速发展，现在广泛用于图形用户界面程序开发。
Qt 的特点：
优良的跨平台特性：Qt 支持多平台运行，在不同平台下无需修改源代码便可以生成特有的图形界面风格。
面向对象：由于Qt 拥有非常良好的封装机制，所以，Qt 的模块化程度较高，不同元件之间协同工作简方便。
丰富的应用程序接口(API):Qt拥有非常多的C++类。
除此之外，Qt 还拥有大量的开发文档，支持XML 技术。
自Qt4.6之后Qt 中引进Qt Quick ，开发人员与设计人员可以协同创建动画模式界面和应用程序。
Qt 拥有简单漂亮的界面，同时简单易学并且资料丰富，实用性很强。
2.4.2 C++编程语言介绍
C++编程语言是一种面向对象的程序设计语言，是由C 语言发展而来。C++继承了C 语言大部分特点，并在C 语言的基础上进行了完善，添加了类，C++能够与C 语言相互兼容。
C++编程语言的优势：
1．在高级语言中处理运行速度最快的面向对象程序设计语言，目前市面上大多数游戏软件都是又C++来实现的。 2．语言灵活，功能强大，特别是类层次结构的设计。
3．C++标准定义细致，具有严谨、精确的特性，语法思路参差分明，语法结构明确。
2.5 系统技术需求
本程序采用Qt 开发环境，编程语言使用C++编程语言的西洋跳棋游戏。
开发环境：Qt Creator5.2.0
运行环境：Windows7 x64
3 系统分析及设计
本章内容是在第二章的需求分析的基础上形成的程序设计蓝图，作为后续编码设计的依据。本章主要介绍了西洋跳棋程序开发的总体设计。
3.1 系统总体设计
3.1.1 模块化设计流程
根据需求分析，游戏设计需要六大模块，每个模块功能实现如下： 开设界面模块：设计开始界面。
绘制棋盘与棋子设计设计模块：绘制棋盘，设计棋子。 人机对弈模块：设计算法，实现人机对弈。 下棋规则模块：根据规则判断落子地方和吃子情况。 胜负判断模块：设计算法判断游戏胜负。
3.1.2 系统总体构成流程
西洋跳棋博弈软件构成如图3.1所示
图3.1 西洋跳棋博弈软件构成图
乙方为玩家，甲方为电脑。乙方遵循游戏规则落子，甲方通过对当前局面进行局面评估，然后进行博弈树搜索算法进行搜索，形成当前最优落子，生成走法并落子，甲、乙双方落子后，当前局面在棋盘显示，电脑循环对棋盘当前局面扫描，经当前局面反馈给甲方机器博弈系统，甲方重新进行局面评估，生成走法。
3.2 系统算法设计概述
西洋跳棋人机对弈模块为系统的核心模块，算法采用极大极小值算法，算法的本质思想是：一方总是寻找对己方最有利的的走法，而另一方总是寻找对对方最不利的走法，其搜索树如图3.2所示
图3.2 极大—极小搜索算法树
根据算法树可知Min 节点总是从其下一层Max 中挑选估值最小的节点进行估值，Max 节点刚好相反。在走棋过程中，遍历整颗搜索树，寻找对己方最有利的走法走子。
3.3 系统特点及功能结构
3.3.1 系统特点
1．具有和谐的界面。界面设计美观，简洁。
2．具有易操作性。本系统避免过多按钮在游戏中给玩家带来的不便，设计简单，已于操作。
3．适用于广大西洋跳棋爱好者，面向性广阔。 4．本系统是本地游戏，安全可靠
3.3.2 功能结构
通过上文需求分析和总体设计，本系统以5个模块为目标设计。其中，下棋规则模块为基础，为玩家和电脑落子提供基础规则，人机对弈模块为系统核心，本次设计
采用极大极小人机博弈搜索算法设计了合理的电脑落子算法，绘制棋盘模块和胜负判断模块为本次设计的前提，为游戏的可行性提供保障，最后是游戏界面设计，为整体游戏进行美化。其具体模块及主要功能结构图如图3.2所示
图3.2 西洋跳棋整体设计及主要功能结构图
4 详细设计
4.1 游戏界面模块详细设计
为了使游戏界面美观大方，从网络上选取图片，并用美图秀秀软件对所选图片进行美图修改，利用Qt 库自带的paintEvent(QPaintEvent *e)函数设计了游戏开始界面，开始界面采用绿色图片作为背景图片，一方面可以缓解玩家视觉疲劳，另一方面，背景颜色与开始游戏按钮色彩区分明确，使整体设计达到简单、美观的效果。游
图4.1 游戏界面模块流程图
程序运行首先进入游戏开始界面，点击开始游戏按钮，将进入游戏。界面设计尺寸长为10cm ，宽为8cm ，并在界面中添加“开始游戏”按钮，该按钮有Qt 编程工具中的界面布局工具完成，关键代码如图4.2所示
图4.2 界面设计模块开始游戏按钮添加关键程序
通过界面背景设计和按钮添加，开始界面模块设计完成，开始界面模块设计效果图如图4.3所示
图4.3 界面设计效果图
4.2 棋盘设计模块详细设计
该模块的主要功能是绘制棋盘和设计棋子，棋盘与棋子分为两种状态，一种是初始化状态，当点击开始游戏按钮后，进入游戏，此时，棋盘显示为初始化状态。初始化状态时，甲、乙双方各持有15枚棋子处于双方边界。另一种状态是走子或者吃子时，棋盘中棋子位置发生改变，甲、乙双方轮流走子，每次走子之后都将跟新一遍棋盘。棋盘绘制与棋子设计模块流程图如图4.4所示
图4.4 棋盘绘制与棋子设计模块
棋盘设计包括棋盘绘制和棋子设计在高性能的博弈设计中，比特棋盘应用较为广泛，西洋跳棋智能程序设计也采用比特棋盘设计而成。棋盘设计了10*10共100个格
子，其中50个格子用来落子，棋盘设计用4个64位无符号整型设计而成，如表4.2所示
表4.1 棋子位置与对应比特关系表
由四元素组生成棋盘，棋盘初始状态为, 棋盘设计效果图如图4.2所示
图4.5 棋盘设计效果图
4.3 人机博弈模块设计详细设计
4.3.1 博弈树算法设计
人机博弈模块为本次设计核心模块，而博弈树算法为本次设计核心算法。该模块设计主要目的是完成人机对弈过程。该过程设计核心算法为极大-极小搜索算法，算法的核心思想是，一方总是寻找对己方最有利的走法，另一方总是寻找对对方最不利的走法。在本次设计中，设计玩家为蓝色方，电脑为红色方，红色方为极大方，博弈树搜算算法设计的核心是红方通过搜索算法和局面评估函数找到对自己最有利的走法。计算机走棋由函数computer_go()设计完成。
4.3.2 局面评估设计
西洋跳棋是零和游戏，局面评估影响因素众多，本次设计主要对以下几个方面进行评估，分别为棋子和王棋的数量，处于安全位置的棋子和王棋的数量（安全位置是指处于底边或者边界无法被对方吃子的位置），可以移动的棋子和王棋数量，还有防御棋子数量和进攻棋子数量。估值函数设计思路为：
估值方法=电脑棋子数-选手棋子数-0.5*威胁棋子数(可能会被吃掉的棋子) 估值函数最重要的任务是找到威胁棋子，在程序中由CalValue （）函数设计完成。在设计中，函数InThreat （）判断该棋子是否有可能被对方棋子吃掉，判断标准是对该棋子左上、右上、左下、右下分别判断。函数InBoard （）则判断棋子当前位置是否处于边界。
4.3.3 走法生成
(1) 普通棋子走法生成
普通棋子走棋规则为棋子可沿对角线对方方向棋子周边移动一个，移动方向的格子为空。遇到吃子时，被吃的棋子周围有空格才可以吃子，其设计流程如下，普通棋子走棋流程图如图4.6所示
① 若棋子列表不为空，则从棋子列表中取出一个棋子；
② 对该棋子相邻四个方向进行判断，若存在对方棋子且对方棋子后方格子为空，则将该走法加入走法栈中，否则到第③步；
③ 若走法栈不为空，则从走法栈中取出一个走法；
④ 如果从棋子位置可以继续吃子，则按照第②步继续走子；
⑤ 否则若当前吃子数量大于最大吃子数量，则清空吃子走法列表； ⑥ 若当前吃子数量等于最大吃子数量，则将该走法加入走法列表； ⑦ 否则到第③步；
⑧ 若该走法最后一步落在加冕线上，则棋子加冕成王，否则到第①步； ⑨ 否则吃子走法终结
图4.6 普通棋子走法生成流程图
(2) 王棋走法生成
王棋是由普通棋子到达加冕线转换而来，因此王棋走法与普通棋子走法有部分相同，王棋走发生成流程图如图4.7所示，王棋走法流程如下，
① 若棋子列表不为空，则从棋子列表中取出一个棋子；
② 对该棋子相邻四个方向进行判断，若从在对方棋子且对方棋子为空，则将该走法加入走法栈中，
③ 将后面所有空格子走法加入走法栈中，否则到第④步； ④ 若走法栈不为空，则从走法栈中取出一个走法；
⑤ 如果从棋子位置可以继续吃子，则按照第②步继续走子；
⑥ 否则若当前吃子数量大于最大吃子数量，则清空吃子走法列表； ⑦ 否则若当前吃子数量等于最大吃子数量，则将该走法加入走法列表； ⑧ 否则到第④步； ⑨ 否则到第①步； ⑩ 否则吃子走法终结
图4.7 王棋走法生成流程图
4.4 游戏规则模块详细设计
本模块主要功能是实现游戏按照规则落子，西洋跳棋游戏规则为，游戏双方轮流走棋。棋子为成为王棋前，棋子只能向左上角或者右上角且无人占据的格子斜走一格。吃子时，敌方的棋子必须在己方棋子的左上角或者右上角的格子，而且该敌方棋子对应的左上角或者右上角必须没有棋子。当棋子到了对方底线，该棋子就可以加冕成王棋，王棋可以向后移动。若一个棋子可以吃棋，则必须吃子。若一方无法行走或者所有棋子均被吃，则该方算输。游戏规则在程序中有函数CanMove （）设计完成，普通走子规则由函数Computer_Can_Move（）生成，普通棋子吃子规则由函数
Computer_Can_Eat（）设计完成。代码if(_piece->GetStatus()!=piece::king) return false;完成了普通棋子不能后退，王棋可以后退的游戏规则。
游戏规则模块流程图如图4.8所示
图4.8 游戏规则模块流程
4.5 胜负判断模块详细设计
本模块设计主要是在游戏结束后判断玩家和电脑的胜负情况。胜负判断有两种情况，一种是一方无法走棋，则该方判定为输，另一种是一方在棋盘中棋子数目为零。胜负判断流程图如下图4.8所示
图4.9 胜负判断模块流程图
双方轮流落子之后，每次落子都会更新棋盘，根据流程图设计，首先由系统判定游戏是否结束，在程序设计中，游戏是否结束设计函数GameOver()判定，判定标准为一方棋子数目为零或者无法走子，判定游戏结束之后，判定玩家和电脑的赢家。
程序中函数IsHostWin()判定电脑是否取得胜利，玩家胜负判定由函IsAwayWin()设计，评定流程与计算机是否胜利流程相同，判定条件为客队棋子是否可以移动，计算机判定胜利过程流程图如图4.9所示
图4.10 计算机胜负判定流程图
5 运行及调试
5.1 开始界面调试情况
程序运行，进入游戏开始界面，如图5.1所示
图5.1 游戏开始界面
运行情况说明：程序运行，进入游戏开始界面，界面画质清楚，点击开始游戏按钮，进入游戏良好。
5.2 棋盘初始化调试情况
游戏开始，进入游戏，此时棋盘为初始化状态，如图5.2所示
图5.2 棋盘初始化界面
运行情况说明：棋盘初始化状态良好，按照详细设计，棋盘为10*10共100个棋格，棋盘底色为黑白两色，双方各15个棋子排布在双方底界。棋子与棋盘颜色分明。
5.3 走棋调试
玩家执蓝旗现行，电脑后手，走子按照规则沿斜对角线方向现行，每次移动一个棋子，可吃子，运行结果如图5.3，5.4所示
图5.3 普通棋子走棋图
图5.4 王棋走子运行图
运行情况说明：普通棋子走棋良好，遇到可吃棋子自动吃子，普通棋子到对方底线变成王棋，王棋走子状况良好，测试表如表5.1所示
表5.1走棋测试表
5.4 胜负判断调试
当一方棋子为零或一方无棋可走时，系统判断胜负并作出评断。
一方棋子数目为零时系统做出评判如图所5.5所示
图5.5 一方棋子数目为零系统做出胜负评判
当一方无法走棋时，电脑做出胜负判断如图5.6所示
图5.6 一方无法走棋时系统做出胜负评判图
运行结果说明：当一方棋子为零或者无棋可走时，系统做出胜负评判并作出提示，运行状况稳定。
6 总结
本章主要内容是对西洋跳棋智能程序设计的总结。本次设计应用C++编程语言，在Qt 开发平台设计编写，完成了游戏开始界面设计、棋盘绘制、棋子走法生成、胜负判断等项目，设计完成的西洋跳棋智能程序界面精美，走棋合理，操作简单，符合本次设计要求。
项目优势：
1. 优良的游戏界面。与网络上流传的西洋跳棋程序比较，本次设计拥有精美的界面设计，开始界面简单易用，避免了玩家错误点击导致无法运行的难题，同时棋盘棋子设计风格独特黑白底色的棋盘设计，玩家可以清楚的思考下一步走棋，红色与蓝色棋子色彩分明，玩家在走棋过程中能够清楚看清自己的棋子位置，便于掌控全局。棋盘与棋子形成强烈的色彩感，可吸引玩家。
2. 合理的走棋算法。本次设计采用经典的极大—极小搜算算法设计，在设计过程中，难度适中。设计中，较高的电脑棋艺水平可以提高玩家的棋艺水平，游戏设置水平适中，玩家在娱乐中不会感到枯燥。
项目不足：
1. 游戏设计中，注重走棋的设计，对娱乐性设计不足，缺少一些音乐文等娱乐项目。
2. 无法人人对战，按照设计要求，本次设计是人机对弈，在设计过程中，没有设计人人对弈模式，整体游戏有所欠缺。
本次毕业设计过程中，出现了很多问题，是对平时学习能力欠缺最直观的反映，在设计中，通过多方面的学习，完善了之前学习的不足，同时，设计中要求的Qt 软件在此之前没有使用过，通过本次设计，学会了使用新的工具。在设计中，不仅学到了许多技术，同时不断克服自身不够严谨的态度，收益良多。
参考文献
[1] 谭浩强.Java 语言程序设计(第三版)[M].北京:清华大学出版社,2008
[2] 焦尚斌，刘丁. 博弈树置换表启发式算法研究[J].计算机工程应用，2010（06）
[3] 王娇，徐兴和. 计算机博弈：人工智能的前沿领域—全国大学生计算机博弈大
赛[J].计算机教育.2012（07）
[4] 张利群. 五道棋计算机博弈程序设计[J].计算机工程.2010（10）
[5] 李天明. 并行计算机博弈系统设计与改进[J].电子制作.2014（21）
[6] 张颖，李祖枢. 棋类计算机博弈系统的主要研究方法及在6子棋上的应用[J].
重庆工学院学报（自然科学版）.2008（09）
[7] Mustapha Lakrib, Tewfik Sari. Time averaging for ordinary differential equations
and retarded functional differential equations[J]. Electronic Journal of Differential Equations, 2010, 2010(40,).
[8] Merrick J. DeWitt, Bradley S. Prall, Robert J. Levis. Orientational averaging in the
intense field tunnel ionization of molecules[J]. The Journal of Chemical Physics, 2000, 113(4).
[9] 李海峰．基于J2EE 技术开发高性能BBS 论坛［D ］. 上海：华东师范大学，2006
[10] 汪辉松，汪隽, 杜群, 曾贵华. Self-dual Codes Defined on Factor Graphs[J].Journal of Shanghai Jiaotong University.2007(04)
[11] 赵志宏, 李蓓蓓, 耿兆丰, 徐敏. Imitation of Fabric Flagging Based on Amplitude Modulation[J]. Journal of Donghua University(English Edition). 2007(06)
[12] 刘雅靖. 计算机博弈之六子棋的主要技术分析[J].电脑知识与术.2011(10)
[13] 汤云雄，董从民. 计算机博弈系统在中国象棋教学中的应用[J].科技信
息.2011(19)
[14] 张丽娜. 机器人功能与价格曲线的博弈[N].消费日报.2016-05-05 (A02)
[15] 马艳红. 手术机器人操作规范化管理“告急”[N].中国医药报.2016-03-29
(003）
[16] 梁莹. 广西首台“达芬奇”手术机器人上岗[N].广西日报.2016-04-13 (004)
致 谢
在本次毕业设计，首先感谢我的知道老师XXX 老师。XXX 老师具有严肃的科学态度，严谨的治学精神，精益求精的工作作风，我在她的身上学到了许多除知识之外的东西，对我今后影响意义深远。XXX 老师在我的本次毕业设计中提供了很大帮助，从选题开始，到毕设中存在问题的解决，XXX 老师事无巨细，亲力亲为的给予我详细解答，是我受益良多。由于本人之前态度懒散，不够认真，XXX 老师不厌其烦的提醒我，再跟胡老师的交流中，老师的谆谆教导及老师严谨的科研态度，时刻影响着我，是我克服了许多自身的不足，收获很大。XXX 老师知识渊博，毕设中出现了许多问题，老师给我的解决意见在设计中起到了非常重要的作用。在此，向XXX 老师表示衷心的感谢。
其次，要感谢在本次毕业设计中帮助过我的同学。身边的同学在自己时间很紧的情况下，依旧热心的帮助我，特别是刚开始软件的安装过程中，新软件的安装出新了问题，在与同学的探讨和同学的帮助下，最终解决了问题。同时，由于本次设计的算法难度很大，同学在我算法的选择上给了我很重要的意见，最后选择的算法非常合理，使得毕业设计顺利进行。在此，感谢所有帮助过我的同学。
最后，感谢学校，学院给予我的这次毕业计机会，在本次毕业设计中，我学到了很多东西，毕业设计过程中，我深刻感觉到自己平时的不足之处，这次毕业设计，我不仅对之前的知识有了进一步的生化，同时改正了许多自身的缺点。在此，感谢学校和学院给了我这次机会，是我成长。
感谢在本次毕业设计中辛苦工作的老师，不论是出题，还是答辩，老师都付出了很多，在此向向所有老师表示感谢。
即将毕业，四年的大学生活使我收获巨大，感谢学校的培养，感谢老师的关心，感谢同学的帮助。在今后的生活中，努力将自身所学回报社会，为母校争光。