学位论文 > 优秀研究生学位论文题录展示

计算机中国象棋界面和搜索引擎的设计与实现

作　者: 张红军
导　师: 钱富才
学　校: 西安理工大学
专　业: 控制理论与控制工程
关键词: 中国象棋计算机博弈数据结构搜索算法界面制作
分类号: TP18
类　型: 硕士论文
年　份: 2009年
下　载: 55次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  3-4
Abstract  4-8
1 绪论  8-14
  1.1 课题的研究背景  8
  1.2 中国象棋计算机博弈的发展  8-11
    1.2.1 中国象棋简介  8-10
    1.2.2 中国象棋博弈的发展现状  10-11
  1.3 中国象棋计算机博弈关键技术  11-12
  1.4 本文架构  12-14
2 数据结构  14-24
  2.1 棋局状态的表示  14-21
    2.1.1 棋盘坐标  14-18
    2.1.2 棋盘索引数组  18-19
    2.1.3 棋子索引数组  19-20
    2.1.4 双向映射数组  20-21
  2.2 基于比特向量的位行位列技术  21
  2.3 着法生成  21-24
    2.3.1 棋盘扫描法  22
    2.3.2 模板匹配法  22
    2.3.3 预置表法  22-23
    2.3.4 基于位行位列的预置表法的性能测试  23-24
3 搜索算法研究与改进  24-46
  3.1 博弈树与博弈思想  24-25
  3.2 搜索策略与搜索算法  25-26
  3.3 搜索与博弈性能  26
  3.4 Alpha-Beta搜索(Alpha-Beta Search)  26-29
  3.5 PVS(Principal Variation Search)  29-31
  3.6 MTD(f)  31-33
    3.6.1 MTD(f)算法的原理  31-33
    3.6.2 测试实验研究  33
  3.7 迭代深化(Iterative Deepening)  33-35
    3.7.1 迭代深化的工作原理  34-35
    3.7.2 迭代深化的空间复杂度和时间复杂度  35
    3.7.3 迭代加深的性能测试  35
  3.8 针对水平线效应的改进算法  35-38
    3.8.1 静态搜索(Quiescence Search)  36-37
    3.8.2 选择性延伸(Selective Extension)  37-38
  3.9 置换表搜索(Transposition Table Search)  38-41
    3.9.1 Zobrist哈希技术与置换表搜索  38-41
    3.9.2 置换表的存储替换策略  41
    3.9.3 置换表的作用  41
  3.10 历史启发(History Heuristic)  41-43
  3.11 重复检测(Repetition Detection)  43
  3.12 增强算法效率测试  43-44
  3.13 本文搜索主体架构  44-46
4 界面制作  46-54
  4.1 界面基本框架  46-47
  4.2 对弈双方用时信息  47-48
  4.3 着法显示  48-50
    4.3.1 中国象棋记录法  48-49
    4.3.2 着法显示  49-50
  4.4 悔棋和还原  50-51
  4.5 打开与保存  51-52
  4.6 "XUTChess"中国象棋博弈程序架构  52-54
5 总结与未来展望  54-56
  5.1 总结  54
  5.2 未来的展望  54-56
致谢  56-58
参考文献  58-60

计算机中国象棋界面和搜索引擎的设计与实现

内容摘要

全文目录

相似论文