摘 要

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的设计者也指出，他让机器学会的仅仅只是围棋的规则，其他的方面全是计算机自己‘学习’。