中国象棋博弈树搜索算法研究与实现

发布时间：2018-03-03 20:34

本文选题：计算机博弈　切入点：搜索算法　出处：《沈阳工业大学》2012年硕士论文　论文类型：学位论文

【摘要】：计算机博弈是人工智能的一个传统研究领域。计算机博弈为人工智能提供一个实验平台,将人工智能的一些理论与方法应用于计算机博弈,可通过博弈水平的高低来检验这些理论与方法的有效性,研究计算机博弈所得到的成果也可推广至人工智能的其他领域。二者相辅相成,相互促进。国际象棋计算机博弈已经比较成熟,历史悠久的中国象棋计算机博弈很多技术还不够成熟,随着对人工智能的深入研究,对中国象棋博弈的研究成为人工智能研究的热点之一。本文对中国象棋博弈树搜索算法以及博弈系统进行研究,介绍了中国象棋计算机博弈的关键技术,分析了数据结构设计和评估函数在系统中所起的作用。深入研究博弈树的特性以及基于α-β剪枝的博弈树搜索算法的改进策略,包括窗口原则、历史表法、置换表法、空着搜索等,结合不同的改进策略得到不同的搜索引擎,对这些引擎的性能进行测试,验证它们的剪枝效率。研究了静态搜索,在静态搜索中加入吃子走法排序和将军延伸,解决了博弈树搜索的水平效应。实现一个人机博弈系统,实现生成并显示棋谱,统计搜索引擎每次搜索的叶节点和所用的时间,结合不同的优化策略得到不同的搜索引擎,通过实验证明综合多种改进策略的搜索算法的剪枝效率得到了提高。选取剪枝效率较高的搜索引擎结合静态搜索提高棋力,让这些新的搜索引擎对弈,证明了剪枝效率最高的PVSHNTIQ搜索算法的棋力也最高。
[Abstract]:Computer game is a traditional research field of artificial intelligence. Computer game provides an experimental platform for artificial intelligence, and applies some theories and methods of artificial intelligence to computer game. The validity of these theories and methods can be tested by the level of game, and the results of computer game can be extended to other fields of artificial intelligence. Mutual promotion. Chess computer game has been relatively mature, Chinese chess computer game has a long history of many technologies are not mature enough, with the in-depth study of artificial intelligence, The study of Chinese chess game has become one of the hotspots of artificial intelligence. This paper studies Chinese chess game tree search algorithm and game system, and introduces the key technology of Chinese chess computer game. This paper analyzes the function of data structure design and evaluation function in the system, deeply studies the characteristics of game tree and the improvement strategy of game tree search algorithm based on 伪-尾 pruning, including window principle, history table method, replacement table method, etc. Empty search, combined with different improved strategies to obtain different search engines, test the performance of these engines, verify their pruning efficiency. The horizontal effect of game tree search is solved. To realize a man-machine game system, to generate and display chess spectrum, to calculate the leaf nodes and the time used in each search engine, and to obtain different search engines by combining different optimization strategies. The experiment proves that the pruning efficiency of the search algorithm integrated with various improved strategies has been improved. The search engine with high pruning efficiency and static search is selected to improve the chess ability, so that these new search engines can play chess. It is proved that the PVSHNTIQ search algorithm, which has the highest pruning efficiency, has the highest chess power.
【学位授予单位】：沈阳工业大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP391.3

【相似文献】