非完备信息机器博弈中风险及对手模型的研究

发布时间：2017-04-20 02:08

  本文关键词：非完备信息机器博弈中风险及对手模型的研究，由笔耕文化传播整理发布。

【摘要】：人工智能是计算机领域的一个重要分支,其任务是研究使计算机胜任原本必须人的智力才能完成的工作。机器博弈作为人工智能的研究领域之一,是检验其发展水平的一个重要手段。它的研究为人工智能带来了很多方法和理论,产生了广泛的社会和学术影响。完备信息和非完备信息机器博弈是机器博弈领域的两个分支。非完备信息博弈的特点是博弈者在博弈过程中无法获得全部以及可信的局面信息。在非完备信息博弈中,博弈环境的真实状态往往是不可知的,参与其中的博弈者所掌握的信息是不对称和不完备的,这使得非完备信息博弈的研究更为复杂,更具有挑战性。相对于完备信息机器博弈,非完备信息机器博弈问题中的参与者因信息的不完备,策略选择面临必然的风险损失。同时,博弈者行为的个性化和非最优化的特点使之在策略选择中趋向不同的纳什均衡。实现有竞争力、高水平的非完备信息机器博弈系统,需要对以上问题展开分析,并寻求可行的解决方案。本文研究非完备信息机器博弈系统中风险模型及对手模型。研究的具体问题包括:大规模博弈树搜索,风险损失的评估与规避方法,对手建模。非完备信息条件决定了此类问题形成的博弈树规模非常巨大。蒙特卡洛博弈树搜索方法(MCTS:Monte-Carlo Tree Search)是解决大规模博弈树搜索的基本方法。UCT(Upper Confidence Bound Applied to Trees)算法为博弈树搜索过程中的分支选择过程提供了多种策略。本文实现了基于MCTS和UCT策略的非完备信息机器博弈系统策略选择方法。对不同的UCT算法策略进行分析和比对实验,讨论了UCT策略在博弈问题中的参数调整方法。非完备信息条件下,博弈者策略的预期收益与实际收益往往会产生偏差。其原因来自于对自身博弈环境判断的不准确性以及对对手行为预测的不准确性。本文提出博弈问题中的风险损失定义和估算方法。同时,结合UCT策略的置信搜索思想,提出了两者相结合的UCT-Risk策略。在实验中,该策略被证实在高风险特征的博弈问题中具有更好的效果。最后,提出了系统的风险策略选择模型。由于博弈信息的非完备性和不对称性,非完备信息博弈者趋向于不同的纳什均衡。建立对手模型,分析对手的个性化及聚类特征,建立更为高效的策略选择模型是近年来机器博弈领域的研究方向。本文还研究了对手建模的理论和算法,特别提出在棋盘类博弈游戏中的理论和应用方法。本文对对手建模过程中的对手聚类问题进行了深入探讨。使用KL(Kullback-Leibler)距离作为数据个体的聚类标准,提出了改进的群组聚类对手建模方法。该方法在保证对手聚类过程的准确性的基础上,减少对历史数据规模的依赖性,提高了历史数据的归类和分析能力。最后,本文讨论了非完备信息机器博弈系统的博弈信息获取、学习和系统评测方法,建立了一个可以支持大规模人机交互测试的机器博弈实验平台。基于测试平台积累的博弈数据,通过强化学习算法对机器博弈系统估值函数进行了训练,进一步提高了系统的博弈水平。
【关键词】：机器博弈 非完备信息 大规模博弈树搜索 风险模型 对手建模
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP18
【目录】：

• 摘要4-6
• ABSTRACT6-14
• 第1章 绪论14-28
• 1.1 人工智能和机器博弈14-20
• 1.1.1 研究背景14-15
• 1.1.2 国内外研究现状15-19
• 1.1.3 非完备信息机器博弈19-20
• 1.2 机器博弈的理论来源20-23
• 1.2.1 信息集20-21
• 1.2.2 纳什均衡21-23
• 1.3 课题研究的关键问题与创新点23-26
• 1.4 论文结构26-28
• 第2章 基于改进的UCT策略的蒙特卡洛博弈树搜索28-51
• 2.1 博弈树搜索28-30
• 2.1.1 基本搜索算法28-29
• 2.1.2 Alpha-Beta搜索29-30
• 2.1.3 历史启发算法30
• 2.2 非完备信息条件下的蒙特卡洛抽样算法30-36
• 2.2.1 蒙特卡洛抽样31-34
• 2.2.2 蒙特卡洛抽样在非完备信息博弈中的应用过程34-35
• 2.2.3 最佳走步链表的建立与查询35-36
• 2.3 蒙特卡洛博弈树搜索36-41
• 2.3.1 MCTS算法过程37-38
• 2.3.2 MCTS算法与经典博弈树搜索算法的比较38-41
• 2.4 MCTS算法过程中的节点扩展选择算法UCT41-45
• 2.4.1 K臂赌博机问题和UCB1算法41-42
• 2.4.2 博弈树节点扩展选择策略UCT42-44
• 2.4.3 UCT算法中的上限置信区间44-45
• 2.5 UCT算法策略比对及参数调整45-47
• 2.6 UCT策略性能对比实验47-49
• 2.7 本章小结49-51
• 第3章 非完备信息条件下的风险建模51-81
• 3.1 机器博弈问题中的风险损失及计算方法51-63
• 3.1.1 研究背景51-53
• 3.1.2 机器博弈问题中的风险分析53-55
• 3.1.3 风险损失出现概率55-57
• 3.1.4 非完备信息条件下风险损失估算方法57-58
• 3.1.5 实验分析58-63
• 3.2 基于风险损失估算方法的UCT-Risk策略63-66
• 3.3 基于风险占优策略的机器博弈决策模型66-79
• 3.3.1 理论背景67-68
• 3.3.2 风险占优决策模型68-72
• 3.3.3 基于对手建模方法改进的非完备信息预测72-77
• 3.3.4 实验分析77-79
• 3.4 本章小结79-81
• 第4章 对手建模中的棋盘类问题建模及对手聚类81-108
• 4.1 研究背景81-83
• 4.2 棋盘类博弈问题中的对手建模83-92
• 4.2.1 棋盘类博弈问题的位置相关性质83-84
• 4.2.2 棋盘类游戏布局估值方法84-87
• 4.2.3 对手分类实验和特殊对手建模方法87-88
• 4.2.4 对手类型预测方法88-90
• 4.2.5 实验分析90-92
• 4.3 基于KL距离的群组对手聚类方法92-104
• 4.3.1 Kullback-Leibler（KL）距离93-95
• 4.3.2 改进的群组对手分类方法95-99
• 4.3.3 实验分析99-104
• 4.4 世界扑克机器博弈大赛（ACPC）评测104-107
• 4.4.1 ACPC大赛简介104-105
• 4.4.2 HIT S Z?CS系统参赛情况介绍105-107
• 4.5 本章小结107-108
• 第5章 机器博弈系统的信息获取学习及性能评估108-122
• 5.1 机器博弈系统大规模图灵测试平台108-113
• 5.1.1 测试平台的研究意义108-109
• 5.1.2 机器博弈系统性能评估方法109-111
• 5.1.3 基于互联网的博弈信息获取技术111-113
• 5.2 基于强化学习方法的机器博弈系统信息学习113-121
• 5.2.1 强化学习方法简介113-115
• 5.2.2 强化学习中的Q学习算法115
• 5.2.3 非完备信息条件下的Q学习调整115-119
• 5.2.4 基于Q学习的四国军棋估值函数调整实验119-121
• 5.3 本章小结121-122
• 结论122-124
• 参考文献124-134
• 附录A 四国军棋和德州扑克简介134-141
• A.1 四国军棋和德州扑克134-141
• A.1.1 四国军棋简介134-137
• A.1.2 德州扑克简介137-141
• 攻读博士学位期间发表的论文及其他成果141-144
• 致谢144-146
• 个人简历146

【相似文献】

中国期刊全文数据库 前10条

1 徐心和;邓志立;王骄;徐长明;刘纪红;马宗民;;机器博弈研究面临的各种挑战[J];智能系统学报;2008年04期

2 张雪峰;连莲;徐心和;;基于有限自动机的“点点连格”机器博弈系统的建模与分析[J];沈阳建筑大学学报(自然科学版);2009年04期

3 徐长明;马宗民;徐心和;李新星;;面向机器博弈的即时差分学习研究[J];计算机科学;2010年08期

4 张小川;唐艳;梁宁宁;;采用时间差分算法的九路围棋机器博弈系统[J];智能系统学报;2012年03期

5 廖景亮;陈冬强;;机器博弈中搜索算法的研究[J];福建电脑;2012年10期

6 张振;庞海;;机器博弈及其搜索算法的研究[J];软件导刊;2008年07期

7 张振;顾治华;;机器博弈及其搜索算法的研究[J];电脑知识与技术;2008年24期

8 谷飙;;计算主义纲领与机器博弈的认知意蕴[J];南开学报(哲学社会科学版);2011年04期

9 徐长明;南晓斐;王骄;徐心和;;中国象棋机器博弈的时间自适应分配策略研究[J];智能系统学报;2006年02期

10 李学俊;王小龙;吴蕾;;机器博弈教学实验平台[J];计算机教育;2014年12期

中国重要会议论文全文数据库 前4条

1 朱峰;张雪峰;徐心和;;关于机器博弈中的逐步展开型对策的一点讨论[A];2007中国控制与决策学术年会论文集[C];2007年

2 徐心和;王浩;孔凡禹;;事件对策理论及在棋类游戏中的应用[A];2007年中国智能自动化会议论文集[C];2007年

3 李微波;傅调平;鄢力;;基于机器博弈的海战兵棋仿真系统设计与实现[A];Proceedings of 14th Chinese Conference on System Simulation Technology & Application(CCSSTA’2012)[C];2012年

4 王珏;程然;王骄;;人工神经元网络结合TD(λ)算法在中国象棋机器博弈中的应用[A];2009中国控制与决策会议论文集（2）[C];2009年

中国博士学位论文全文数据库 前2条

1 张加佳;非完备信息机器博弈中风险及对手模型的研究[D];哈尔滨工业大学;2015年

2 徐长明;基于连珠模式的六子棋机器博弈关键技术研究[D];东北大学;2010年

中国硕士学位论文全文数据库 前9条

1 张恩海;基于多自动机复合多子类机器博弈及其估值方法研究[D];沈阳大学;2011年

2 林靖;Q-学习在非完备信息机器博弈中的应用[D];哈尔滨工业大学;2009年

3 安涌;六子棋机器博弈研究与开发[D];沈阳航空工业学院;2008年

4 唐霜霜;点格棋机器博弈系统的研究与实现[D];安徽大学;2015年

5 唐艳;围棋博弈机器学习算法的研究及应用[D];重庆理工大学;2012年

6 连莲;基于Moore自动机的机器博弈系统建模与研究[D];东北大学;2009年

7 谢国;中国象棋机器博弈数据结构设计与搜索算法研究[D];西安理工大学;2008年

8 张柳;基于极大极小搜索算法的亚马逊棋博弈系统的研究[D];东北大学;2010年

9 王小龙;连珠模式棋类博弈的搜索优化[D];安徽大学;2014年

  本文关键词：非完备信息机器博弈中风险及对手模型的研究，由笔耕文化传播整理发布。

，

本文编号：317641