基于Android系统的中国象棋人机博弈的应用研究

发布时间：2018-03-19 22:15

本文选题：中国象棋　切入点：人机博弈　出处：《武汉科技大学》2013年硕士论文　论文类型：学位论文

【摘要】：人工智能的应用范围非常广泛，计算机博弈（也称机器博弈）被认为是该领域最具挑战性的研究方向之一。人类在对计算机博弈研究取得成果的同时，极大地推动了人工智能的发展。棋类博弈作为计算机博弈的代表，对其研究显得尤为重要。在中国象棋的人机博弈中，如何使计算机更快更具有杀伤力地同人类对战以达到最终战胜人类的目的，是目前该领域研究的热点问题。本文详细地介绍了构建计算机博弈系统的相关技术——数据结构、着法生成以及局面评估方式。重点介绍了计算机博弈系统的搜索算法，包括基础的极大极小算法、alpha-beta算法以及高级搜索算法比如PVS、静寂搜索以及空着裁剪等，，并通过分析表明着法顺序会影响对博弈树结点的搜索。一个完整的计算机博弈系统包括界面设计和搜索引擎两大部分。论文选择了合适的数据结构，通过比较采用模版匹配法生成所有着法，综合考虑棋子自身价值和棋子所处位置两方面的因素得到棋子子力价值表并作为局面评估的依据，并对各类搜索算法适当组合，共同完成了搜索引擎部分。最后，基于Android开发平台，成功地搭建了中国象棋的计算机博弈系统。并在该系统中测试了各组合算法在不同的搜索深度下搜索的结点数以及耗费的时间。实验证明采用启发算法比如置换表、历史表、杀手启发在搜索展开前优化着法顺序可以提高搜索效率，将高级搜索算法同启发算法相结合形成的算法搜索效率较高。
[Abstract]:The application of artificial intelligence is very extensive, computer game (also known as machine game) is regarded as one of the most challenging research directions in this field. As the representative of computer game, it is very important to study chess game. How to make the computer fight with human beings more quickly and hurtlessly in order to win the final victory is a hot issue in this field. This paper introduces in detail the related technology of constructing computer game system-data structure, method generation and situation evaluation method, especially the search algorithm of computer game system. It includes the basic Maxima beta algorithm and advanced search algorithms such as PVS, silent search and empty clipping. The analysis shows that the order of the algorithm will affect the search of game tree nodes. A complete computer game system consists of two parts: interface design and search engine. Considering the value of the pieces themselves and the position of the pieces, the value table of the force of the pieces is obtained and used as the basis for the evaluation of the situation, and the search engine part is completed together by the proper combination of all kinds of search algorithms. Based on Android development platform, The computer game system of Chinese chess is successfully built, and the number of nodes and the time consumed by each combination algorithm under different search depth are tested in this system. The experiment proves that heuristic algorithms such as permutation table, history table, etc. The search efficiency can be improved by optimizing the algorithm sequence before the search is unfolded, and the search efficiency is higher by combining the advanced search algorithm with the heuristic algorithm.
【学位授予单位】：武汉科技大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP18

【参考文献】