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

中国象棋博弈系统的研究与实现

作　者: 危春波
导　师: 王海瑞
学　校: 昆明理工大学
专　业: 计算机软件与理论
关键词: 计算机博弈棋盘表示走法预生成估值函数博弈树搜索算法
分类号: TP311.52
类　型: 硕士论文
年　份: 2008年
下　载: 308次
引　用: 7次
阅　读: 论文下载

内容摘要

计算机博弈是人工智能的一个重要研究领域,对它的研究方兴未艾。本文对中国象棋计算机博弈系统中的关键技术作了研究,在此基础之上开发了一个完整的中国象棋博弈程序。论文的工作主要集中在以下几个方面:1.文章首先研究了中国象棋在计算机中的棋盘表示问题,并针对带位行位列信息的扩展棋盘-棋子联系数组棋盘实现所有棋子的走法预生成数组,以提高搜索过程中走法产生的效率。2.根据中国象棋的具体棋类知识讨论了如何定义一个针对局面优劣的评估机制,即估值函数:同时结合走法预生成数组提高估值的速度。3.重点研究了α-β剪枝算法及其改进策略,并针对基于迭代加深、置换表、历史启发的NegaScout综合算法进行改进;同时实现B~*算法。4.使用面向对象方法对系统进行分析与设计,并用UML语言对系统模型进行描述,最终实现系统。该系统使用先进的棋盘表示和改进的搜索算法,在实验中证明是有效的。同时系统的整体设计与开发遵循面向对象的方法,使得系统具有良好的复用性和扩展性。

全文目录

摘要  3-4
ABSTRACT  4-7
第一章绪论  7-12
  1.1 选题背景  7-8
  1.2 国内外研究现状  8-10
  1.3 课题的主要工作和章节安排  10-12
    1.3.1 课题的主要工作  10-11
    1.3.2 章节安排  11-12
第二章棋盘表示和走法生成  12-23
  2.1 棋盘表示(Board Representations)  12-16
    2.1.1 基本表示法  12-13
    2.1.2 改进型棋盘  13-16
  2.2 走法产生(Move Generation)  16-22
    2.2.1 走法产生伪代码及效率分析  16-17
    2.2.2 着法预生成  17-21
    2.2.3 合理走法的产生  21
    2.2.4 人类走法合理性判断  21-22
  2.3 小结  22-23
第三章局面估值  23-27
  3.1 估值函数(Evaluation Function)  23-25
    3.1.1 棋子固定价值  23-24
    3.1.2 棋子位置附加值  24
    3.1.3 棋子灵活性  24
    3.1.4 棋子对棋盘的控制  24-25
    3.1.5 棋子间的关系  25
  3.2 估值的速度与博弈性能  25-26
  3.3 估值与走法预生成数组相结合  26-27
第四章博弈树搜索技术  27-52
  4.1 博弈树(Game Tree)  27-28
  4.2 极小极大值算法(Minimax Algorithm)  28-31
  4.3 α-β剪枝算法及其改进策略  31-43
    4.3.1 α-β剪枝算法(Alpha-Beta Pruning Algorsthm)  31-34
    4.3.2 窗口原则(Window principle)  34-36
    4.3.3 置换表(Transposition Table)与哈希表(Hash Table)  36-39
    4.3.4 历史启发(History Heuristic)  39-40
    4.3.5 迭代深化(Iterative Deepening)  40-41
    4.3.6 其他问题  41-42
    4.3.7 各种改进策略作用于α-β剪枝算法的实验数据  42-43
  4.4 综合搜索算法及其改进  43-49
  4.5 B*算法  49-52
第五章系统设计  52-56
  5.1 面向对象的分析与设计简介  52-53
  5.2 UML简介  53-55
  5.3 类图  55
  5.4 系统的实现及用户界面操作  55-56
第六章实验与结果  56-65
  6.1 程序说明  56
  6.2 实验结果及分析  56-65
第七章总结与展望  65-67
  7.1 工作总结  65
  7.2 今后的工作  65-67
致谢  67-68
参考文献  68-71
攻读硕士学位期间发表的文章  71

中国象棋博弈系统的研究与实现

内容摘要

全文目录

相似论文