六子棋中基于BP-TD学习的局面估值方法研究

论文摘要

空间搜索能力与局面估值的准确性是决定棋类游戏水平高低的最重要的两个方面。六子棋游戏规则简单,但状态空间复杂度高,平均分枝因子大。该特点限制了六子棋程序中博弈树搜索所能够抵达的最大深度,这使得局面的估值就变得特别重要。估值是各种博弈问题中最难以处理的一个问题,局面估值的准确性往往直接决定了选择后继着法的策略的优劣。本文将TD算法与BP神经元网络相结合,首次将其应用于六子棋的局面估值中。该方法利用BP神经元网络做为局面的估值函数,通过TD算法直接从原始经验中学习,自动调整估值函数的参数,将BP神经元网络的有监督学习转换为无监督学习,避免了神经网络在有监督学习下调参容易受人类经验影响的缺陷,同时,BP神经元网络自适应性好,容错能力强,能够自动发现输入实例中与学习目标函数中最相关的特征,适合用于对六子棋复杂局面的估值。考虑到六子棋的特点,为了使TD学习更有效,本文还提出了一种两阶段的着法选择策略。第一阶段的策略是按BP网络置信度和备选着法的估值为其分配权重,然后按概率选择后继着法,具有较大权值的着法被赋予较高的概率；第二阶段的策略是最佳着法的极大极小选择策略。这两种策略的联合使用,使TDConn6在TD学习中兼有探索性和利用性特点。采用以上的方法和策略,本文实现了六子棋程序TDConn6, TDConn6从“零知识”开始学习,经过30000盘的自学习训练后,分别与博弈程序NEUConn6与NEU6Star各对弈1000次,所取得的胜率分别为64.7%和80.5%,从而验证了本文提出的方法和策略是有效的和实用的。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 六子棋的研究现状
• 1.3 研究意义
• 1.3.1 课题的提出
• 1.3.2 技术路线
• 1.3.3 研究意义
• 1.4 论文的组织结构
• 第2章 六子棋和TD学习
• 2.1 六子棋
• 2.1.1 六子棋简介
• 2.1.2 博弈程序NEU6Star
• 2.2 TD（λ）算法
• 2.2.1 增强学习简介
• 2.2.2 评价函数P（s,a）
• 2.2.3 TD（λ）算法
• 2.3 估值函数
• 2.3.1 传统的估值函数
• 2.3.2 基于BP神经元网络的估值函数
• 2.4 本章小结
• 第3章 TDConn6中估值算法与策略的研究
• 3.1 TDCONN6的框架结构
• 3.2 TDCONN6的BP-TD（λ）学习算法
• 3.3 TDCONN6的BP神经元网络
• 3.3.1 局面特征的抽取
• 3.3.2 BP神经元网络的设计
• 3.4 TDCONN6的两阶段着法选择策略
• 3.4.1 随机的着法选择策略
• 3.4.2 最优的着法选择策略
• 3.4.3 两阶段的着法选择策略
• 3.5 本章小结
• 第4章 系统实现与试验结果分析
• 4.1 开发环境和工具
• 4.2 系统实现
• 4.2.1 TDConn6总体功能的实现
• 4.2.2 TD学习模块的实现
• 4.2.3 着法选择模块的实现
• 4.2.4 自学习训练平台TDvs的实现
• 4.3 试验结果分析
• 4.3.1 BP神经元网络的可靠性验证
• 4.3.2 参数λ和α对TDConn6的影响
• 4.3.3 两阶段着法选择策略的性能分析
• 4.3.4 TDConn6的测试集
• 4.3.5 TDConn6与NEUConn6、NEU6Star的性能比较
• 4.4 小结
• 第5章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间的科研工作及获奖情况