【作者】 张红军；

【导师】 钱富才；

【作者基本信息】 西安理工大学 ， 控制理论与控制工程， 2009， 硕士

【摘要】 计算机博弈是人工智能的一个传统研究领域。计算机博弈为人工智能提供一个实验平台,将人工智能的一些理论与方法应用于计算机博弈,可通过博弈水平的高低来检验这些理论与方法的有效性,研究计算机博弈所得到的成果也可推广至人工智能的其他领域。因此,二者相辅相成,相互促进。在国际象棋计算机博弈高度发展的今天,基于两个原因,中国象棋则具有得天独厚的发展优势。首先,它是世界上最流行最古老的棋类游戏之一,且现在已经存在较高棋力的中国象棋程序；其次,它的复杂度介于国际象棋与围棋之间。可以相信自1997年“深蓝”击败卡斯帕罗夫之后,中国象棋必将成为下一个拥有可以击败人类高手的软件程序的棋类游戏。本文在阅读了大量国内外相关文献的基础之上,结合现有的国际象棋以及中国象棋软件设计实例,介绍如何实现一款具有一定棋力且交互友好的中国象棋博弈软件程序,文中的主要工作如下：1.分析并总结了中国象棋计算机博弈的关键技术,包括：数据结构、搜索算法、评估函数以及博弈界面等；2.研究并设计了中国象棋博弈程序的数据结构,包括棋盘、棋子在计算机中的表示等,同时引入了位行位列技术、模板匹配法与预置表法等辅助数据结构以提高着法生成的效率,且对其进行了测试总结；3.研究并实现了建立在博弈树的极大极小搜索技术基础之上的各种优化方法,文中主要讨论了基于窗口探测、内存增强、节点顺序调整以及时间控制四个方面的优化方法；之后经过比较分析,文中选择并实现了辅以迭代深化、置换表、历史启发的MTD(f)搜索算法,极大地提高了计算机的“思考”效率,并进行测试总结；另外提出并实现了克制水平线效应的静态搜索、将军延伸以及兑子延伸使得计算机的“思考”更加稳定,进而采用Zobrist哈希技术解决了单方长将以及双方循环走棋的问题；4.应用VB设计并实现了中国象棋博弈软件的界面及辅助功能,包括悔棋、计时、着法显示等；5.系统的实现。更多还原

【Abstract】 Computer game is a traditional researching field of artificial intelligence (AI). It shows a test-platform for AI. Applying some theories and methods of AI in computer game, we can prove the validity of those by means of testing the level of game system. In turn, the fruits obtained through researching the computer game are used in the other realms of AI. So, they supplement and promote each other. Nowadays, Chess computer game has a long history, and come through tough research. For two reasons, Chinese chess is with intrinsic advantages in development. First, Chinese chess is one of the most popular and oldest board games worldwide, currently the strength of a Chinese chess program can be compared to that of human players. Second, the complexity of Chinese chess is between that of Chess and Go. We assume that after DEEP BLUE’s victory over Kasparov in 1997, Chinese chess will be the next chess-like board game at which will defeat a human top player.On the basis of lots of related references at home and abroad, and the existing examples of Chess and Chinese chess software, this paper presents how to realize a Chinese chess game software program with considerable strength and good human-computer interface, including the following works:1. Analyze and summarize the key techniques of computer game for Chinese chess, such as data structure, search algorithms, evaluation functions, and user interface etc.2. Study and design the data structures of Chinese-chess program, including the representation of chessboard and chessman in computer etc. At the same time, some assisting data structures, such as the BitFile and BitRank technique, the template matching method and prefabricated table method, are introduced and used to enhance the efficiency of moves’ generation. Furthermore, a series of tests and results are presents.3. Research deeply and realize several optimization algorithms based on Minimax search for game tree. In the article, four kinds of methods are summarized, including based window detection, memory-enhanced, nodes-sorting and time-control. Furthermore, as a result of comparison and analysis, the MTD(f) algorithm is selected and implemented with Iterative Deepening, Transposition Table and History Heuristic, which improves the efficiency of computer thinking markedly, and a series of tests and results are presents. In addition, Quiescence Search, Check Extension and Recapturing Extension reducing effects of the Horizon Effect are brought forward and implemented, which make computer’s thinking more stable. Finally, the unceasing checking for one-player and the repetition of moves for two-players are settled successfully by means of Zobrist hash technique.4. Design and realize the user interface and assisting functions such as tack-back, timing, displaying moves etc with VB.5. Implementation of system.更多还原