基于Alpha-Beta剪枝与启发式演算的简单吃墩博弈方法

论文摘要

吃墩类博弈是一类零和动态博弈,以桥牌为代表,是人类长期从事的智力活动。不仅能提高人类的智力水平,对工业生产、经济行为以及其他科学技术的研究都具有很高的指导价值。吃墩类博弈的求解是机器博弈领域的一项重要任务,其面临的主要问题有:博弈的规则往往是信息不完备的,不完备信息的预测依赖于完备信息的高效求解,而博弈的朴素复杂度往往是O（P（n!m））甚至更高,计算的复杂性是博弈求解的巨大障碍。针对上述问题,本文将研究目标确定为吃墩博弈的简化形式,通过形式推演和统计分析来研究简单吃墩博弈的内在规律与求解方法,最终用计算机实验来验证其有效性。主要研究工作有:1.通过分析吃墩类博弈的最核心特点,从形式上定义了简单吃墩博弈（Simple Trick-Taking Game,STTG）及其顺序图结构;根据极大极小值原理定义了STTG的最优解、最优策略以及它们之间的等价关系。2.通过形式推演,发现并证明了STTG邻接结构的均匀性、饱和性等性质;通过统计分析,发现并验证了STTG最优解的邻接平衡性、进攻平衡性、防守平衡性、对称平衡性等性质;根据这些性质,提出了防守决策树与精确剪枝算法（Precise Pruning,PP）,将精确求解的计算复杂度从O（n!2）降至O（n!）。3.提出了近似求解的调和评估模型（Mediation Evaluation,ME）,包括特征调和模型与随机调和模型;对邻接图（Adjacent Graph,AG）以及最优解分布（Optimal Solution Distribution,OSD）进行统计分析。本文应用自主编写的STTG调试框架完成了三组主要实验,分别用于测试PP和ME以及对AG与OSD进行统计分析。结果显示在统计范围内PP的绝对准确率为100%,计算复杂度符合预期;ME的相对重合度达到了92.56%;AG成中心对称的生长形态;OSD服从类似中轴偏移的正态分布。实验表明了PP和ME的有效性,为STTG的后续研究打下基础。

论文目录

• 摘要
• abstract
• 第1章 绪论
•   1.1 研究背景及意义
•   1.2 机器博弈研究现状及难点
•     1.2.1 机器博弈的发展状况
•     1.2.2 机器博弈复杂度的难点及典型技术
•     1.2.3 博弈信息完备性的难点及专项技术
•   1.3 吃墩类博弈模型简化的必要性
•   1.4 本文研究内容及章节安排
• 第2章 吃墩类博弈研究综述
•   2.1 吃墩类博弈规则及分类
•   2.2 博弈求解方法概述
•     2.2.1 机器博弈的求解方法
•     2.2.2 计算机桥牌的求解方法
•   2.3 求解评价指标
•   2.4 本章小结
• 第3章 简单吃墩博弈模型
•   3.1 模型的引入
•   3.2 简单吃墩博弈STTG的定义
•     3.2.1 简单吃墩博弈的原始模型
•     3.2.2 简单吃墩博弈的顺序图
•   3.3 STTG的求解目标
•     3.3.1 最优解的定义
•     3.3.2 策略与赢墩的关系
•   3.4 STTG的极大极小搜索
•   3.5 本章小结
• 第4章 STTG的精确求解方法
•   4.1 STTG的数学性质
•     4.1.1 局部有序性
•     4.1.2 最优解的平衡性
•   4.2 STTG的精确防守决策
•   4.3 实验及结果分析
•     4.3.1 最优解平衡性的验证
•     4.3.2 精确剪枝搜索的测试
•     4.3.3 邻接图的统计分析
•   4.4 本章小结
• 第5章 STTG的近似求解方法
•   5.1 STTG的调和评估模型
•     5.1.1 一般的调和模型
•     5.1.2 典型的特化模型
•   5.2 STTG的最优解分布
•   5.3 实验及结果分析
•     5.3.1 调和评估模型的测试
•     5.3.2 最优解分布的统计分析
•   5.4 本章小结
• 第6章 结束语
•   6.1 主要工作与创新点
•   6.2 后续研究工作
• 参考文献
• 致谢
• 攻读硕士学位期间从事的科研工作及取得的成果

文章来源

类型: 硕士论文

作者: 罗俊逸

导师: 王进

关键词: 博弈论,机器博弈,吃墩类博弈,剪枝,启发式演算

来源: 重庆邮电大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 重庆邮电大学

分类号: O225

DOI: 10.27675/d.cnki.gcydx.2019.000475

总页数: 66

文件大小: 2288K

下载量: 32