1、1本科毕业论文(科研训练、毕业设计)题 目：中国象棋游戏博弈算法的研究与实现姓 名：学 院：软件学院系：软件工程专 业：软件工程年 级： 学 号：指导教师： 职称： 年 月I摘 要计算机博弈是人工智能研究的一个重要分支，它的研究为人工智能带来了很多重要的方法和理论，产生了广泛的社会影响和学术影响。国内外对博弈的研究已经较为广泛。近年来随着研究的不断深入，计算机中国象棋博弈越来越成为继国际象棋之后计算机博弈研究的热点之一。本文在对计算机博弈关键技术进行了全面的综述之后，围绕计算机中国象棋博弈中的若干关键问题进行了研究和改进，在此之上开发了一个中国象棋博弈系统，论文主要研究了以下 3 个方面的问题
2、:第一、研究了一些博弈的关键技术，包括数据结构，着法生成，搜索技术，估值函数等。第二、重点优化了数据结构和着法生成两大模块。第三、引入开局库，提高了开局走法效率和准确性，并介绍了所用的引擎协议。本文实现的象棋系统，通过对数据结构和着法生成部分的改进和增强，提高了棋力，具有一定的使用和研究意义。关键词：中国象棋；人机博弈；置换表；着法生成IIAbstractComputer Game artificial intelligence research is an important branch of the study of artificial intelligence has brought
3、 many important methods and theory, produce a wide range of social and academic impact. Game at home and abroad to study have been more extensive. In recent years, with the continuous deepening of research, the computer has increasingly become a Chinese chess game after following the International C
4、omputer Chess Game One of the focuses of research. Based on the key technologies of computer games conducted a comprehensive Review, Chinese chess game on the computer in a number of key issues have been studied and improved, in this development on a Chinese chess game system, the following major re
5、search papers 3 Aspects of the problem: First, study the game a number of key technologies, including data structure and take the law generation, search technology, such as the valuation function. Second, focus on optimizing the structure and the data generated by taking the two modules. Third, the
6、introduction of the first to raise the first walk of efficiency and accuracy, and on the engine used by the agreement. In this paper, to achieve the chess system, through the data structure and take part generated by the improvement and upgrading, increased Qili, a certain significance of the use an
7、d research.Key words: Chinese chess, human-computer game; transposition table; steps generated III目录第一章 绪论.11.1 课题研究的背景 、目的及意义 .11.2 主要研究内容 .11.3 本文架构 .21.4 本章小结 .3第二章 博弈关键技术.42.1 数据结构 .42.2 着法生成 .52.3 搜索算法 .72.3.1 博弈树的基本概念.72.3.2 极大极小算法.82.3.3 负极大值法.102.3.4 Alpha-Beta 搜索算法 .112.4 估值函数 .122.4.1 评估函数
8、的构成.122.4.2 棋子关系的评估.132.5 本章小结 .14第三章 数据结构与着法生成的优化.153.1 数据结构的优化 .153.1.1 棋盘表示的优化.153.1.2 位棋盘.163.1.3 置换表.173.1.4 Zobrist 键值 .183.1.5 历史表.193.1.6 着法生成预处理.193.2 着法生成的优化 .203.2.1 预置走法表.20IV3.2.2 位棋盘法.203.2.3 着法生成器的实现对比分析.213.3 本章小结 .22第四章 开局库与引擎协议.234.1 实现开局库的方法 .234.1.1 用 FEN 串的形式表示的开局库 .234.1.2 用哈希值
9、形式表示的开局库 .244.2 引擎协议 .254.2.1 通讯方法.254.2.2 引擎协议特点.254.3 本章小结 .26第五章 中国象棋博弈系统的设计与实现.275.1 系统结构组织 .275.2 系统详细设计 .285.2.1 棋子和棋盘的表示.285.2.2 着法生成器的设计.305.2.3 搜索引擎的设计.325.2.4 估值函数的设计.345.3 本章小结 .35总结.36参考文献.37致谢.38VContentsChapter 1 Introduction .11.1 research the background, purpose and significance .11.
10、2 chess program “to move to victory“ .11.3 framework paper.21.4 Summary of this chapter.3Chapter 2 Game key technologies .42.1 Data Structure.42.2 generation moves.52.3 search algorithm .72.3.1 The basic concept of the game tree.72.3.2 minimax algorithm.82.3.3 negative great value method .102.3.4 Al
11、pha-Beta search algorithm .112.4 valuation function.122.4.1 evaluation function.122.4.2 pawn of the assessment.132.5 Summary of this chapter.14Chapter 3 optimization of DS and production .153.1 data structure optimization .153.1.1 chessboard that the optimization.153.1.2 bitboard .163.1.3 replacemen
12、t table .173.1.4 Zobrist keys.183.1.5 history table.193.1.6 moves generated pretreatment .193.2 take the optimization of production.20VI3.2.1Preferences Act walk Table .203.2.2 BitBoard method.203.2.3 follow the law generator to achieve comparative analysis .213.3 Summary of this chapter.22Chapter 4 start library the engine agreement .234.1.1 used FEN string expressed in the form of the first library.234.1.2 used hashvalue expressed in the form of the first library .244.2 engine agreement.254.2.1 communication.254.2.2 features of the engine agreement .
