论文总字数：23240字

摘 要

众所周知，中国象棋是一项古老的智力运动，也是一门正在不断向前发展的艺术。中国象棋在我国具有极其广泛的群众基础，据统计我国约有两亿人会下中国象棋。本文首先探讨了中国象棋棋盘和棋子的数据结构表示和棋子的走法生成问题。接着论述了有关博弈树的各种搜索算法及其改进方法，着重介绍了极大值极小值算法和alpha-beta搜索算法。在此之后对特定盘面的形式判断和估值函数进行了详尽介绍。最后介绍了开局库和残局库，用来增强系统的棋力。本系统的界面由MFC框架来实现。本系统拥有可视化界面且具备一定棋力。

关键词：中国象棋，博弈树，极大值极小值算法，估值函数，MFC

Abstract

As we all know, Chinese chess is an ancient intellectual movement and an art which is constantly moving  forward. Chinese chess has wide mass base and popularity in

 China. According to statistics, there are about two hundred million people who can play it. This paper firstly concentrates on the representation of chessboard and 

chess pieces in data structure and the problem of the formation of the pawn of chess 

pieces. Then we discuss the various relevant search algorithms of game tree and the 

improved method, specially introducing the minimax algorithm  and the Alpha-Beta

 search algorithm. After that it gives a detailed introduction of the judgment and 

evaluation function in a particular situation. Finally, we discuss the opening library 

and endgame database to enhance the ability of the system. The system interface is 

achieved by the MFC framework. It has a visual interface and has ability to play 

Chinese chess in a certain degree .

KEY WORDS: Chinese chess, game tree, the minimax algorithm, evaluation function, MFC

目录

摘要 I

Abstract II

第一章 绪论 1

1.1选题意义 1

1.2 研究现状 1

1.3 研究内容 1

1.4 论文组织结构 2

第二章 系统的设计与实现 3

2.1数据表示 3

2.1.1 棋盘的二维数组表示 3

2.1.2棋盘的一维数组表示 3

2.1.3比特棋盘 4

2.1.4本系统棋盘和棋子的表示 4

2.2走法产生器 5

2.2.1 如何产生 6

2.2.2 逐个产生与全部产生 6

2.2.3效率问题 6

2.2.4走法生成器的实现 7

2.3搜索引擎 8

2.3.1 博弈树 8

2.3.2 极大值极小值算法 9

2.3.3负极大值算法 10

2.3.4alpha-beta算法 10

2.4估值核心 14

2.4.1棋子的价值估值 14

2.4.2棋子的灵活性 15

2.4.3棋子关系的评估 15

2.4.4棋子的位置和对于棋盘的控制 15

2.4.5水平效应 15

2.4.6估值函数与搜索算法的关系 16

2.5操作界面 16

2.6系统的实现 16

2.7开局库 18

2.8残局库 19

第三章 系统测试和结果分析 20

3.1系统测试 20

3.2 结果分析 20

第四章 总结与展望 21

4.1 论文总结 21

4.2 工作展望 21

致谢 22

参考文献 23

第一章 绪论

1.1选题意义

博弈的本意就是下棋。如今，博弈已引申为在一定规则条件下，各博弈方从各自允许选择的策略中进行决策。计算机博弈属于人工智能领域。“博弈论”作为一门博大精深的学问已广泛应用于政治经济文化当中。中国象棋属于零和博弈游戏中的一种，也是在中国最广受大众喜爱的棋类游戏。中国象棋在我国已有千年历史，古称“象戏”或“橘中戏”。众所周知，中国象棋是一项古老的智力运动，也是一门正不断向前发展的艺术。因其用具简单，趣味性强，入门迅速，老少咸宜等特点，中国象棋在我国具有极其广泛的群众基础，据悉我国约有两亿人次会下中国象棋。中国象棋不仅可以锻炼下棋者的逻辑思维能力，还可以培养棋手坚韧不拔的品质和永不言败的精神。

在计算机出现之前，中国象棋这个游戏参与的双方均为人类，是人和人之间的一种游戏。然而，随着计算机的出现，游戏的双方可以变为人和计算机甚至双方都是计算机。人工智能这四个字对于现在的人们来说毫不陌生，其实，人们是从各种棋类博弈游戏开始接触研究人工智能的。人类下棋的思维过程大致是利用对规则的理解，经验和计算，尽力使局面朝有利于自身的方向发展。也正因为如此，棋类博弈自然而然的成为了人工智能的试验品。

1.2 研究现状

众所周知，人类最早是通过国际象棋来研究机器棋类博弈的。美国著名数学家香浓是国际象棋人机对弈理论的奠基人。上世纪五十年代末，国外就已研制出第一台与棋手公开对战的电子计算机。1974年开始，每年都会有大大小小的国际象棋软件大赛。最为著名的莫过于1997年，IMB研制的“超级深蓝”在与国际象棋第一人卡斯帕罗夫的六盘棋决战中获得了胜利，成为机器博弈历史上里程碑式的事件。从那时棋，国际象棋软件已经具备了人类国际特级大师的棋力了。

与国际象棋人机对弈相比，中国象棋机器博弈起步非常晚，大约在上世纪八十年代才开始。台湾大学许舜钦教授被誉为中国象棋机器博弈之父，他在1991的论文中总结了当时一切搜索算法，论述了许多算法的不足之处并解释了人们关于某些算法的曲解。许教授的这些学术成果为中国象棋人机对弈的发展起了重要的作用。上世纪九十年代后，随着单位和个人对中国象棋软件开发的不断重视，中国象棋的各种博弈软件如雨后春笋般发展起来，其中光谱公司的《将族》，吴身润的《中国象棋》在当时都享有盛名。进入二十一世纪，随着科技的不断发展，棋力越来越强功能越来越完善的中国象棋软件迎来了春天，其中“奇兵”，“象棋巫师”和“象棋旋风”最为有名。进二十年来，中国象棋博弈的研究常常通过比赛对弈的方式来验证各自研究的结果，2004年起在台湾成功大学举办了世界电脑象棋真霸赛，2009年该赛事于11月18至21日在由北大清华哈工大中科院组成的深圳大学城举办，促进了中国人工智能和高性能计技术，IT通讯等智能制造业的发展。^[6]

现如今，各类象棋软件在具有较强计算能力的机器上已经可以达到特级大师水平。然而，在当今科技水平下，棋类软件还不能完全代替人类，例如有些必胜残局软件赢不下来，在不装开局库的情况下软件开局往往走不出有效走法。因此，开发出更高效功能更全面的软件是不断向前发展的趋势。

剩余内容已隐藏，请支付后下载全文，论文总字数：23240字