中国象棋博弈算法研究

阿里郎

中国象棋博弈算法研究

中国象棋博弈算法研究.doc (963 KB, 下载次数: 4)

2016-4-15 22:23 上传

点击文件名下载附件
下载积分: 金钱 -1

摘 要

计算机博弈是人工智能研究的一个重要分支，被专家门称为人工智能界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成果，这些成果在人工智能领域产生了重要影响。国际象棋计算机博弈研究已经有了五十多年的历史，IBM公司在1997年开发出了超级计算机“深蓝”战胜了当时世界国际象棋大师卡斯帕罗夫，标志其水平已达到国际象棋世界冠军水平。而中国象棋的历史更为悠久，虽然中国象棋计算机博弈研究起步晚于国际象棋，但起点高，国际象棋计算机博弈研究的成果为我们提供了很多的借鉴技术。近年来随着研究的不断深入，中国象棋计算机博弈越来越成为继国际象棋后计算机博弈研究的热点之一。

本文在对目前主流的计算机博弈技术进行全面的综述后，对构成计算机博弈系统的四个组成部分进行了优化和改进，特别是针对静态估值算法不能应对局势变化的固有缺点，提出了动态局势再评估算法。在此之上实现了一个中国象棋计算机博弈系统，论文主要研究了以下3方面的问题：

第一、对计算机博弈系统的四个组成部分及基础技术进行了研究，包括数据结构，着法生成，搜索算法，估值算法。

第二、研究了建立在Alpha-Beta搜索算法基础之上的各种优化技术。主要讨论了窗口探测，静寂搜索，历史启发，深层迭代，Null Move5个方面的优化方法，并根据实验结果结合置换表技术提出了具体的组合方案。

第三、论文针对目前广泛使用的静态估值算法不能应对局势变化的固有缺点，提出了动态局势再评估算法。通过引入“局势因子”，使得估值算法根据当前局面形势做出攻防策略。

关键词：人工智能；中国象棋；博弈算法；动态局势再评估；局势因子

目录

第一章 绪论... 8

1.1选题背景和研究意义... 8

1.2中国象棋计算机博弈的发展历程... 9

1.3国内外研究现状... 10

1.4本文的主要工作和论文结构... 11

第二章 背景知识... 13

2.1数据结构... 13

2.1.1 棋盘表示... 13

2.1.2 置换表... 14

2.2着法生成... 15

2.3搜索算法... 16

2.3.1 博弈树的基本概念... 16

2.3.2极大极小算法... 17

2.3.3 负极大值法... 19

2.3.4 Alpha-Beta搜索算法... 20

2.4估值算法... 22

2.5本章小结... 23

第三章 搜索算法的优化... 24

3.1窗口探测... 24

3.1.1渴望搜索... 24

3.1.2 极小窗口算法... 25

3.2静寂搜索... 26

3.3历史启发... 26

3.4深层迭代... 27

3.5Null Move. 29

3.6内存优化... 29

3.7本章小结... 30

第四章 动态局势再评估算法... 31

4.1静态评估算法详述... 31

4.1.1 对子力和攻击性的评估... 31

4.1.2 对棋子位置附加值的评估... 31

4.1.3 对灵活性的评估... 32

4.1.4 对棋子的协调性和保护性的评估... 32

4.1.5 静态估值函数... 33

4.2静态估值函数的缺陷... 33

4.3局势因子及动态局势再评估函数... 33

4.4动态局势再评估算法的步骤... 36

4.5本章小结... 36

第五章 中国象棋计算机博弈系统——出棋制胜的设计与实现... 38

5.1系统设计... 38

5.1.1中国象棋通用引擎协议层(UCCI) 38

5.1.2 “出棋制胜”软件系统结构图... 39

5.2详细设计... 39

5.2.1 棋盘棋子表示... 39

5.2.2 着法生成... 40

5.2.3 搜索算法... 43

5.2.4 评估算法... 45

5.2.5 置换表... 45

5.3实验结果和相关问题的讨论... 46

5.4本章小结... 47

第六章 总结... 48

致谢... 49

参考文献... 50

Contents

Chapter 1 Introduction. 8

1.1Research Topics’ Background and Significance. 8

1.2Chinese Chess Computer Game’s Developing Process. 9

1.3The Status Quo at Home and Abroad.. 10

1.4The Main Work and Structure of this thesis. 11

Chapter 2 Background Knowledge. 13

2.1Date Structure. 13

2.1.1 Chess Board Expression. 13

2.1.2 Transposing Table. 14

2.2Moves Generation. 15

2.3Search Algorithms. 16

2.3.1 game tree’s concept 16

2.3.2 Minimax Algorithm.. 17

2.3.3 Negamax Algorithm.. 19

2.3.4 Alpha-Beta Algorithm.. 20

2.4Evaluate Algorithm.. 22

2.5Chapter Summary. 23

Chapter 3 The Optimization of SearchAlgorithm.. 24

3.1Window Detection. 24

3.1.1 Eager Search. 24

3.1.2 Principal Variation Search. 25

3.2Quiescence Search. 26

3.3History Heuristic. 26

3.4Interative Deepening. 27

3.5Null Move. 29

3.6Memory Optimization. 29

3.7Chapter Summary. 30

Chaper 4 Dynamic Situation EvaluateAlgorithm.. 31

4.1Static Evaluate Algorithm.. 31

4.1.1 The Evaluation of The Chessman’s Value. 31

4.1.2 The Evaluation of The Chessman’s Position. 31

4.1.3 The Evaluation of The Chessman’s Movability. 32

4.1.4 The Evaluation of The Chessman’s Compatibility. 32

4.1.5 Static Evaluate Method. 33

4.2Static Evaluate Method’s Disadvantage. 33

4.3Decision Factor and Dynamic Situation Evaluate Algorithm.. 33

4.4The Steps of Dynamic Situation Evaluate Algorithm.. 36

4.5Chapter Summary. 36

Chaper 5 Chinese Chess ComputerGame System.. 38

5.1System Design. 38

5.1.1 Universal Chinese Chess Protocol (UCCI) 38

5.1.2 The Structure of The System.. 39

5.2Detailed Design. 39

5.2.1 Chess Board Expression. 39

5.2.2 Moves Generation. 40

5.2.3 Search Algorithms. 43

5.2.4 Evaluate Algorithm.. 45

5.2.5 Transposing Table. 45

5.3The Experimental Results and Discuss Related Issues. 46

5.4Chapter Summary. 47

Chapter 6 Summary. 48

Acknowledgement 49

References. 50