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

基于连珠模式的六子棋机器博弈关键技术研究

作　者: 徐长明
导　师: 马宗民
学　校: 东北大学
专　业: 计算机应用技术
关键词: 机器博弈 六子棋 CPBIM 博弈树搜索 估值函数
分类号: TP18
类　型: 博士论文
年　份: 2010年
下　载: 34次
引　用: 0次
阅　读: 论文下载
 

内容摘要


机器博弈是人工智能学科的一个重要课题,是人工智能的“果蝇”,是检验利用智能方法解决复杂问题效果的试金石,其研究内容与人工智能和人类智慧都具有紧密的相关性。早在上世纪60年代,Semual采用自学习方法编写的西洋跳棋程序就战胜了人类高手,一度引发了空前的轰动。在2005年,吴毅成教授首先提出了六子棋,其难度远远超过五子棋。由于Go-Moku和Renju这两种常见的五子棋博弈问题已经被成功地破解,六子棋便成为k子棋机器博弈研究中的新的挑战性问题。必须指出,已有的五子棋和六子棋机器博弈研究对相应棋类的复杂度均有着不同程度的高估,这反映了k子棋机器博弈的相关研究存在着重大的缺陷。以六子棋的机器博弈问题为对象,针对其研究现状,本文提出了基于连珠模式的六子棋机器博弈模型——CPBIM,旨在纠正现存研究成果之中的误区,进而提高k子棋机器博弈的研究水平。在CPBIM的基础上,围绕着机器博弈的关键性技术,对包括数据和知识的表示、搜索算法、估值方法、着法生成和排序等各个方面,分别展开了深入的研究。本文的创新性研究成果主要包括：(1)提出了一种基于“连珠”模式的六子棋机器博弈模型—CPBIM (Connection-Pattern Based Incremental Model),并将该模型推广到一族k子棋中。首先,提出了一种不同于传统模式的新模式——连珠,从而在局面的表示及分析方面,直接改善了程序的效率。接着,为了让连珠更好地表达领域的高级知识,提出了从低级的具体知识自动地推导出高级的抽象知识的方法,得到了一个严格且完善的连珠分类体系。然后,为了有效地解决k子棋博弈复杂度被严重高估的问题,提出了一种交叉点类型体系,从而保证程序有能力从众多候选点中过滤掉那些对博弈结果毫无影响的候选着法,还为实现高效的着法排序提供了关键性的支持。最后,为了加强博弈程序对高级知识的利用和提高程序的执行效率,结合连珠的非负整数表示法,提出了基于连珠来构建知识库的方法。(2)将迭代加深(Iterative Deepening)思想应用于威胁空间搜索(Threat SpaceSearch)中,提出了DFID-TSS (Depth First Iterative Deepening Treat Space Search)搜索。新的搜索算法找到的解的路径总是最短的；在求解能力不变的条件下,新算法的平均执行时间也大为缩短。(3)为利用CPBIM所提供的领域知识来改进搜索效率,在PN(Proof Number)搜索算法的基础上,提出了PN#搜索算法。PN#在PN总是倾向于搜索一棵稀疏的博弈树的基础上,还鼓励算法更优先地和更深入地搜索较好的分枝。PN#不但提高了搜索速度,降低了内存需求,而且在算法的实现上与PN同样简洁。(4)将神经元网络与TD(λ)算法相结合,引入到估值函数的设计当中,提出了一种以先验知识引导的估值函数自学习方法。该方法不仅避免了单纯采用自学习方法时出现的收敛速度慢等问题,还易于实现。此外,为降低无用样例对学习结果的负面影响,提出用有选择的可学习序列代替完整的棋谱作为学习样例。(5)针对连珠棋候选着法多、着法排序代价高的特点,提出了分类且逐步着法排序的方法,借此来降低着法排序的高昂代价。其中,对于同类着法的排序问题,还提出了新的排序机制,在不影响区分度的情况下,将评估值的取值范围尽可能地缩小,从而能够以高效的桶排序替代常用的选择排序。(6)在开局库设计、时间控制等方面,结合六子棋或机器博弈问题的特点,在充分考虑到性能与代价之间的平衡之后,均提出了相应的优化方法。上述模型、方法及算法均已被成功地运用于六子棋机器博弈软件NEUConn6之中。在国际和国内的一系列机器博弈竞赛当中,NEUConn6都取得了良好的成绩,从实践上有力地说明了本文研究工作的正确性、有效性和实用性。

全文目录


摘要  5-7
Abstract  7-13
第一章 绪论  13-27
  1.1 研究背景与动机  13-15
  1.2 国内外相关研究的现状与分析  15-22
    1.2.1 机器博弈研究的现状  15-17
    1.2.2 机器求解博弈问题的优势和劣势  17-22
  1.3 研究目标与意义  22
  1.4 本文工作  22-27
    1.4.1 研究内容  23-24
    1.4.2 论文的组织结构  24-27
第二章 相关理论基础  27-49
  2.1 机器博弈的研究对象和内容  27-29
    2.1.1 研究对象的分类  27-28
    2.1.2 本文的研究对象——k子棋  28-29
  2.2 机器博弈的基本概念和术语  29-35
    2.2.1 博弈树  29-31
    2.2.2 搜索树  31-33
    2.2.3 复杂性度量  33
    2.2.4 树与图  33-35
  2.3 基本的搜索技术及其原理  35-47
    2.3.1 极大极小策略和搜索  35
    2.3.2 α-β搜索  35-37
    2.3.3 (α,β)窗口  37-39
    2.3.4 深度优先的迭代加深搜索  39-40
    2.3.5 面向着法排序的启发式方法  40-41
    2.3.6 面向窗口的α-β搜索改进算法  41-44
    2.3.7 可变深度搜索  44-47
  2.4 本章小结  47-49
第三章 基于"连珠"模式的k子棋机器博弈模型  49-85
  3.1 引言  49-51
  3.2 连珠  51-56
    3.2.1 连珠的若干相关属性  51-55
    3.2.2 连珠的形式化表示  55-56
  3.3 连珠的估值  56-65
    3.3.1 连珠估值的二步法  57-58
    3.3.2 连珠的类型  58-62
    3.3.3 求解全部连珠类型的算法  62-65
    3.3.4 构造连珠知识库  65
  3.4 连珠之间的演化  65-70
    3.4.1 升变  65-67
    3.4.2 升变间的比较和连珠类型的抽象估值  67-69
    3.4.3 直接升变的简化  69-70
    3.4.4 降格  70
  3.5 空交叉点的价值  70-75
    3.5.1 空交叉点的价值  70-74
    3.5.2 空交叉点的复合类型  74-75
  3.6 模型的数据结构  75-78
    3.6.1 CPBIM模型  75-76
    3.6.2 潜在的连珠  76-77
    3.6.3 连珠和潜在连珠在局面中的形式化描述  77-78
  3.7 增量方法  78-81
    3.7.1 棋盘的基本操作  78-79
    3.7.2 增量的状态改变  79
    3.7.3 增量的状态恢复  79-81
  3.8 实验  81-83
  3.9 本章小结  83-85
第四章 求解博弈理论值为目标的搜索算法  85-109
  4.1 引言  85-86
  4.2 TSS搜索  86-98
    4.2.1 迫着的广泛性  86-87
    4.2.2 六子棋的TSS简介  87-88
    4.2.3 算法的形式化描述  88-90
    4.2.4 TSS的扩展——Anti-TSS策略  90-91
    4.2.5 DFID-TSS搜索算法  91-95
    4.2.6 实验  95-98
  4.3 PN搜索  98-107
    4.3.1 算法的非形式化描述  99-102
    4.3.2 阈值的改进  102-104
    4.3.3 实验  104-105
    4.3.4 结果和分析  105-107
  4.4 本章小结  107-109
第五章 面向机器博弈的TD学习算法研究  109-121
  5.1 引言  109-110
  5.2 TD(λ)学习  110-111
  5.3 估值函数  111-114
    5.3.1 手工调整参数  111-112
    5.3.2 权值调整自动化——BP神经元网络  112-113
    5.3.3 整合先验知识与神经元网络的估值函数  113-114
  5.4 自学习训练程序TDLConn6  114-118
    5.4.1 自学习训练方案  115-116
    5.4.2 训练集的生成  116-117
    5.4.3 可学习状态序列的截取  117-118
  5.5 实验  118-119
    5.5.1 "零知识"自学习训练  118
    5.5.2 先验知识引导的自学习训练  118-119
    5.5.3 学习效果分析  119
  5.6 本章小结  119-121
第六章 NEUConn6的设计与实现  121-135
  6.1 NEUConn6体系结构  121-123
  6.2 着法生成、排序和选择  123-125
  6.3 搜索算法  125-126
  6.4 估值函数  126-130
    6.4.1 基于局面的评估  126-128
    6.4.2 基于交叉点的评估  128-130
  6.5 开局库  130-132
    6.5.1 构造六子棋开局库  130
    6.5.2 影响开局库大小的因素  130
    6.5.3 开局库的存储方式和查询方式  130-132
    6.5.4 对称压缩  132
  6.6 时间控制  132-134
    6.6.1 时间分配策略的数学模型  132-133
    6.6.2 类Ponder技术  133-134
  6.7 本章小结  134-135
第七章 结束语  135-139
  7.1 本文的主要贡献与结论  135-136
  7.2 未来的工作  136-139
参考文献  139-147
致谢  147-149
攻博期间参加的科研项目  149-151
攻读博士期间发表的论著  151-153
附录A NEUConn6的竞赛成绩  153-155
附录B NEUConn6的版本更迭情况  155-156

相似论文

  1. 六子棋中基于BP-TD学习的局面估值方法研究,TP18
  2. 基于数据库自学习的中国象棋研究,TP18
  3. 基于剪枝策略的中国象棋搜索引擎研究,TP391.3
  4. 非合作博弈问题的数值分析,O225
  5. 五子棋人机对战系统设计,TP18
  6. 六子棋机器博弈研究与开发,TP18
  7. 博弈树搜索技术在牌类网络游戏中的应用,G899
  8. 基于改进博弈树的黑白棋设计与实现,TP18
  9. 基于博弈树的自动入侵响应决策系统分析与设计,TP393.08
  10. 六子棋计算机博弈系统的研究与实现,TP18
  11. 基于智能算法的六子棋博弈行为选择的应用研究,TP18
  12. 基于多自动机复合多子类机器博弈及其估值方法研究,TP18
  13. 基于机器博弈的无人战斗机的空战建模与仿真,V325
  14. 中国象棋计算机博弈中搜索算法的研究与改进,O225
  15. 六子棋计算机博弈关键技术研究,TP18
  16. 中国象棋机器博弈数据结构设计与搜索算法研究,TP391.3
  17. 基于学习的九宫问题求解方法及其应用研究,TP391.1
  18. 计算机国际象棋博弈系统的研究与实现,TP18
  19. RoboCup中型组足球机器人决策系统的研究,TP242
  20. 具有自学习功能的计算机象棋博弈系统的研究与实现,TP311.52
  21. 六子棋计算机博弈及其系统的研究与实现,TP311.52

中图分类: > 工业技术 > 自动化技术、计算机技术 > 自动化基础理论 > 人工智能理论
© 2012 www.xueweilunwen.com