摘 要

本论文的主要成果包括两个部分，第一，我们设计了新的评估函数和训练学习，在改进使评估函数的基础上，提升了计算机博弈系统的效率。第二，针对莫里斯九子棋，我们提出了的相应的新的估值算法。

莫里斯九子棋是一款非常古老的智力博弈，其历史甚至可以追溯到公元前1400多年的古埃及时代。在国内文化里也是一款传统的棋类博弈^[7]，于公元前500多年在我国出现。机器博弈，相关研究在近几十年内已经有所进展突破。例如，前几年谷歌旗下的研究所DeepMind在围棋领域，相继击败了李世石和柯洁，引发了媒体的轰动。博弈程序的核心部分是搜索算法的设计和优化。强化学习则是人工智能学科板块的一项重要组成部分，研究对于外部条件变化可以自己产生一系列最终能导向最优结果的决策，充分凸显了智能的体现。

本次毕业设计将以搜索算法为研究对象，包括极小极大算法、负大极值算法等。本文将从莫里斯九子棋开始，对几种常用的搜索算法进行全面的总结，并以α-β剪枝算法为重点展开。本文以现有算法为参考，创新研究了α-β剪枝算法的一些新应用，并希望利用强化学习的相关进展实现智能博弈程序的提升。

本文的主要工作是：

1.首先介绍机器博弈这个领域的研究背景、现状、研究意义等；紧接着介绍莫里斯九子棋的相关概念，以及简要说明如何让机器实现智能九子棋博弈；最后总述文章的框架脉络，行文结构。

2.对最基本的机器博弈原理与理论基础进行说明，以及强化学习的基本原理和与计算机博弈的结合。设计新的评估函数和训练学习，评估函数的改进将会大大提升计算机博弈系统的效率；将强化学习引进与结合，针对莫里斯九子棋提出相应的新的估值算法；展示莫里斯九子棋自学习系统的实现和应用成果；并对本文所使用的数据集，实验平台做出说明。

3.对本文研究及相关领域进行总结与展望，总结本文研究成果与意义，并展望未来发展的可能性。

关键词：计算机博弈；莫里斯九子棋；α-β剪枝算法；估值

Abstract

The main results of this paper include two parts. First, we design a new evaluation function and training learning, which, on the basis of improving the evaluation function, improves the efficiency of the computer game system. Second, for morris nine chess, we put forward a corresponding new valuation algorithm.

The morris nine is a very old intellectual game, dating back to the time of ancient Egypt in 1400 BC. In the domestic culture, it is also a traditional chess game^[7], which appeared in China in 500 BC. Machine games, the relevant research in recent decades has made progress and breakthroughs. For example, in the past few years, DeepMind, a research institute affiliated with Google, has successively defeated lee sedol and ke jie in the go field, causing a media sensation. The core part of game program is the design and optimization of search algorithm. Reinforcement learning, on the other hand, is an important part of the discipline of artificial intelligence. The research on the change of external conditions can generate a series of decisions that ultimately lead to the optimal results, which fully highlights the embodiment of intelligence.

This graduation project will take search algorithm as the research object, including minimax algorithm, negative maximum algorithm and so on. This paper will start from the morris nine chess, a comprehensive summary of several commonly used search algorithms, and ben-to-gain pruning algorithm as the focus. Based on the existing algorithms, this paper innovated and studied some new applications of luben-earn pruning algorithm, and hoped to improve the intelligent game program by taking advantage of the relevant progress of reinforcement learning.

The main work of this paper is:

1. Firstly, the research background, current situation and significance of machine game are introduced. Then introduce the related concepts of morris nine chess, and briefly explain how to make the machine realize intelligent nine chess game. The last summary of the framework of the article context, writing structure.

2. The basic machine game theory and theoretical basis are explained, and the basic principle of reinforcement learning is combined with computer game. Design new evaluation function and training learning, the improvement of evaluation function will greatly improve the efficiency of computer game system; Based on the introduction and combination of reinforcement learning, a new valuation algorithm is proposed for morris nine chess. The realization and application of morris nine chess self-learning system are presented. The data set and experimental platform used in this paper are also explained.

3. This paper summarizes and prospects the research and related fields, summarizes the research results and significance, and looks into the possibility of future development.

Key Words：Computer games; Morris nine; Ben-tang pruning algorithm; The valuation

目录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 研究现状 1

1.3 研究意义 2

1.4 本文工作 3

1.4.1 研究内容 3

1.4.2 论文组织结构 3

第2章 机器博弈关键技术 5

2.1 基本概念 5

2.1.1 博弈树 5

2.1.2 递归 7

2.1.3 复杂度 7

2.2 研究对象属性分析 8

2.3 博弈系统构成要素 9

2.3.1 知识表示 9

2.3.2 着法生成 9

2.3.3 搜索技术 10

2.3.4 估值函数 10

2.4 莫里斯九子棋机器博弈建模 10

2.4.1 莫里斯九子棋简介 10

2.4.2 行棋规则 11

2.5 本章小结 12

第3章 莫里斯九子棋搜索算法研究 13

3.1 搜索算法简介 13

3.1.1 极大极小搜索算法 13

3.1.2 Alpha-Beta剪枝搜索算法 14

3.2 莫里斯九子棋博弈过程建模 16

3.2.1 莫里斯九子棋博弈博弈算法分析 16

3.2.2 极大极小值搜索 16

3.2.3 Alpha-Beta剪枝 17

3.2.4 局面估值 17

3.2.5 伪代码 18

3.2.6 莫里斯九子棋博弈的设计 18

3.3 莫里斯九子棋中的着法生成优化 20

3.3.1 基于强化学习的博弈树搜索 20

3.3.2 实验分析 20

3.4 优化算法的比较 21

3.4.1 系列优化算法简介 21

3.4.2 实验分析 23

3.5 估值函数的详细设计 23

3.5.1 棋型分析 23

3.5.2 棋型处理 24

3.5.3 算法的缺点 24

3.6 本章小结 25

第4章 博弈程序的设计与实现 26

4.1 系统设计 26

4.1.1 系统流程图 26

4.1.2 系统总体结构 27

4.2 系统实现 28

4.2.1 实现技术 28

4.2.2 系统界面 29

4.3 本章小结 29

第5章 总结与展望 30

5.1 本文的主要贡献与结论 30

5.2 未来工作与展望 30

参考文献 32

致 谢 34

第1章 绪论

1.1 研究背景

人工智能是一门集成发展、多位一体的交叉学科，包括信息理论、认知科学、控制科学、计算机科学、数学、行为科学、逻辑学等^[1]。它是一门多学科相互影响而发展起来的综合性学科。其重点放在了对于模式识别、NLP（自然语言处理）、分布式人工智能、机器学习、自动化编程、机器博弈等的研究上。

本文所讲述的机器博弈，是基于约翰纳什的著名研究成果——博弈论的。机器博弈，顾名思义，就是将机器相关的技术，也就是电脑技术，计算机技术，和博弈论相关的理论结合，做到两者的有机统一便是机器博弈。那么目标是什么呢？我们知道博弈的意思是对弈双方都希望自己的结果最优，机器博弈便是让机器去实现这个寻求双方最优的过程，非常美妙。