摘 要

2016年AlphaGo与世界围棋冠军、职业九段选手李世石进行了一场人机大战，最终以4:1的大比分差距战胜李世石。在2016年末，2017年初更是在中国棋类网站上以“大师”（Master）为注册账号与中日韩数十位围棋高手进行对决，连胜60局无一败绩。至此，人工智能的发展日益成熟。而游戏也是人工智能最初开发的主要阵地之一。

论文基于博弈树算法来设计手机国际象棋应用，使用Java语言来实现。主要实现的功能为人机对弈、可以选择不同难度的等级、能够保存当前棋局、能够支持新的开局和残局、残局还可以采用载入残局文件和手动布局。不用难度的等级通过控制博弈树的搜索深度来实现，残局通过载入数据库文件来实现载入残局。整个程序的关键算法是博弈树搜索算法，同时还通过α-β剪枝进行了一定程度的算法优化。

关键词：博弈树搜算算法、α-β剪枝、人工智能、国际象棋

Abstract

2016 AlphaGo and the world go championship, occupation nine players Li Shishi conducted a man-machine war, the final 4: 1 gap between the big victory over Li Shishi. At the end of 2016, 2017 is the beginning of the Chinese chess website to "Master" (Master) for the registered account and dozens of Chinese and Japanese players go to the showdown, winning streak 60 Bureau without a defeat. At this point, the development of artificial intelligence is becoming more and more mature. The game is also the artificial intelligence of the initial development of one of the main positions.

Based on the game tree algorithm to design mobile phone chess application, the use of java language to achieve. The main function of the realization of man-machine chess, you can choose a different level of difficulty, to save the current chess game, to support the new start and mess, the mess can also be used to load the residual file and manual layout. The difficulty level is achieved by controlling the search depth of the game tree, and the residue is loaded into the database file by loading the database file. The key algorithm of the whole program is the game tree search algorithm, and also through the α-β pruning to a certain degree of algorithm optimization.

Key Words：Game Tree Algorithm; α-βpruning; artificial intelligence; International chess

目 录

摘 要 I

Abstract II

1 绪论 1

1.1研究背景 1

1.2国内外研究现状 1

1.3论文主要工作 2

1.4论文结构 2

2系统分析 3

2.1需求分析 3

2.1.1游戏规则分析 3

2.1.2 功能性需求分析 5

2.2 可行性分析 6

2.3 技术方案介绍 6

2.3.1 安卓语言介绍 6

2.3.2 博弈树算法 6

3 系统设计 8

3.1 国际象棋功能模块划分 8

3.2 功能模块设计 8

3.2.1 游戏模块 8

3.2.2 设置模块 9

3.2.3 残局模块 10

3.3 启发式函数设计 11

3.4 SQL设计 11

3.4.1 正常模式下的SQL设计 12

3.4.2 残局模式下的SQL设计 13

4 关键问题和解决方案 14

4.1 初始棋局表示及棋子移动 14

4.1.1 初始棋局表示 14

4.1.2 棋子移动 14

4.2 棋局状态表示 15

4.3 博弈树算法的设计和优化 17

5系统实现 18

5.1功能展示 18

5.2特殊游戏规则展示 22

6总结和展望 27

6.1总结 27

6.2展望 27

参考文献 29

1 绪论

1.1研究背景

从深蓝到AlphaGo，人工智能的研究在不断的进步中。人工智能是计算机科学、控制论、信息论、神经生理学、语言学等多种学科互相渗透的而发展起来的一门学科。虽然人工智能发展历史已经超过了半个世纪，但是人们对它的定义还没有统一。尽管学术界有各种各样的说法和定义，但就其本质而言，人工智能是研究、设计和应用智能机器或智能系统，来模拟人类智能活动的能力，以延伸人类智能的科学^[11]。

随着人工智能的不断发展，围绕人工智能的基本理论和方法，例如人工智能的定义、基础、核心、要素、认识过程、学科体系及人工智能与人类智能的关系等，形成几个学派。

目前人工智能的主要学派有下述三家^[11]：

一、符号主义学派：符号主义认为人工智能的的研究应着重于功能的模拟方法，分析人类知识系统所具有的功能和机理，然后用计算机来模拟实现这些功能，从而实现人工智能。该主义力图同数理逻辑方法来建立人工智能的统一理论体系。

二、联结主义学派：联结主义认为人工智能的研究应该注重于结构的模拟，即模拟人类的生理神经网络系统，人为创造出一个‘大脑’，至今已经提出多种人工神经网络结构和多种学习算法。

三、行为主义学派：行为主义认为人工智能的研究方法应采用行为模拟方法，也认为功能、结构和智能行为是分不开的，不同的行为需要不同的控制结构并表现出不同的功能。

1.2国内外研究现状

目前人工智能的发展应用于机器学习、图像识别、数据分析、自动程序设计中。而人工神经网络是目前各大互联网公司最热门的研究领域，AlphaGo的设计者也指出，他让机器学会的仅仅只是围棋的规则，其他的方面全是计算机自己‘学习’。

人工智能产品近期仍将作为辅助人类工作的工具出现，多表现为传统设备的升级版本，如智能/无人驾驶汽车，扫地机器人，医疗机器人等。汽车、吸尘器等产品和人类已经有成熟的物理交互模式，人工智能技术通过赋予上述产品一定的机器智能来提升其自动工作的能力。但未来将会出现在各类环境中模拟人类思维模式去执行各类任务的真正意义的智能机器人，这类产品没有成熟的人机接口可以借鉴，需要从机械、控制、交互各个层面进行全新研发。

各国对于人工智能的发展也越来越重视，对其投入的资金也逐年增加高科技企业普遍将人工智能视为下一代产业革命和互联网革命的技术引爆点进行投资，加快产业化进程。

1.3论文主要工作

通过博弈树搜索算法来实现国际象棋游戏程序，主要完成以下工作：

1. 采用安卓语音来进行程序的设计
2. 设计博弈树的启发式函数，及其其它辅助性质的算法，并且采用α-β剪枝来优化博弈树搜索。
3. 对程序进行测试，找出问题，并提出解决方案。
4. 深入了解博弈树的搜索算法，对其算法进行优化设计，把递归算法变为非递归形式。

1.4论文结构

论文共为六章，主要内容分别为：

1. ：绪论。介绍人工智能的研究背景、意义及现状，简要介绍论文结构。
2. ：系统分析。分析了国际象棋游戏的游戏规则和特殊规则，简要进行了可行性分析。
3. ：系统设计。对程序的功能模块进行设计，对博弈树算法的启发式函数进行设计
4. ：关键问题及解决方案。提出在程序设计过程中出现的问题和它的解决方法。
5. ：系统实现。介绍了程序的实现。
6. ：总结与展望。总结了自己在毕业设计中的不足与收获，对于设计出来的程序还有那些可以改进的部分。

2系统分析

本章主要对国际象棋的游戏规则和最终实现目标进行了分析，其次进行了程序的可行性分析。

2.1需求分析

2.1.1游戏规则分析

要做一款国际象棋游戏，首先要了解国际象棋的棋局规则。经过查阅资料，整理出来以下规则：

1. 国王：国王只能走自身周围的格子（即只能走一格，横竖斜都可以），同时不能走向威胁自身安全的格子（即走了那一步会被吃）。王可以吃掉自己行动范围内的敌方棋子。
2. 皇后：皇后可以跨多个格子前进，但只能选择横跨，直跨，斜跨三种走法，同时不能够跨越棋子前进。皇后可以吃掉自己行动范围内的敌方棋子。
3. 象：象能斜跨多个格子前进，不能跨越棋子前进。可以吃掉自己行动范围内的敌方棋子。
4. 车：车能横跨和直跨多个格子前进，不能跨越棋子前进。可以吃掉自己行动范围内的敌方棋子。
5. 马：马只能走日子（即一个以六个格子组成的长为三个格子，宽为两个格子的长方形，马只能从这个长方形的一角走到对角线对应的对角格子），马可以跨越棋子前进。可以吃掉自己行动范围内的其他格子。
6. 兵：兵只能向敌方方向直行，初次行动可以选择前进两个格子（这一步不能跨越棋子前进），之后每次行动只能前进一个格子。兵可以吃掉自己前方斜向一个单位格子敌方棋子，在兵走到底时（即不能再向前前进一个格子）必须进行升变，可以升变的单位只有后、象、车、马。
7. 吃路过兵：如果对方的兵从初始位置一步走了2格，刚好形成本方有兵与其横向紧邻并列，则本方的兵可以立即斜进，把对方的兵吃掉，但不是占据它到达的格子，而是占据它经过的格子，就像它一步走一格时的情况一样。吃过路兵必须在对方的兵走出之后立即吃，隔了一步后就不能吃了。
8. 王车易位：在每个对局中，双方各有一次机会，可以同时移动己方的两个棋子王和车，作为一步棋，称为王车易位，简称易位。易位的方法是让王向车的方向移动两格，然后车越过王，放在与王紧邻的格子上。王向王翼易位时，车移动2格，称为短距离易位，如图2.1，简称短易位;王向后翼易位时，车移动3格，称为长距离易位，简称长易位，如图2.2。以下情况不能进行易位：
9. 王车之间有其他棋子。
10. 王正在被对方“将军”。
11. 王经过的位置或者到达的位置受到对方棋子的攻击。
12. 王或者车已经移动过（此情况本局内不能进行易位）。

图2.1短易位