基于Moore自动机的机器博弈系统建模与研究

论文摘要

机器博弈源自于二十世纪五十年代,是一门新兴的研究领域。作为飞速发展的新学科,它的竞技水平不断攀升,但是其理论成果还相对匮乏。为了能够使机器博弈更均衡的发展,亟需为其理建立适于理论研究的模型。机器博弈的理论研究主要分为两个方向：博弈论和离散事件动态系统。博弈论主要指导机器博弈的着法选择,本文简要的阐述了机器博弈中的均衡情况。离散事件动态系统主要用于研究其本质,有限自动机是对离散事件动态系统建模的常用工具之一,也是本文研究的主要内容。本文首先研究了确定型有限自动机的极小化问题。有限自动机的化简是一个十分重要的问题,在等价的前提下,自动机的状态越少,意味着越节省软件和硬件资源。状态的最小化过程是指将自动机的状态集划分成一些不相交的子集,使得任何两个不同的子集中的状态都是可区分的,而同一子集中的任何两个状态都是等价的,我们可以将子集用其中一个元素代表。本文基于自动机等价性定义提出了状态转移反函数和状态差别表的概念以及一个新的状态等价性判定定理,基于三者构造了一类针对不带输出的确定型有限状态自动机的极小化方法,该方法可以弥补以前方法的不足,并用例子证明了方法的正确性。随后,研究了机器博弈系统的建模问题。提出了一个机器博弈系统的自动机模型,该模型以Moore自动机为核心。但是面对复杂的机器博弈系统,本文对Moore自动机的内部结构做了改动,引入了受控子自动机来完成搜索部分的建模。受控子自动机选择的是变形的图灵机-含有两条堆栈的多栈机（又称为双栈机）,监控器作为控制器与双栈机形成闭环反馈控制系统,从而对多栈机的输入进行监控。将模型应用于走法规则相对简单的井字棋机器博弈系统,验证了该模型的可行性。最后,对国际计算机博弈锦标赛参赛项目之一的点点连格棋的相关背景作了介绍,给出了常常出现在棋局中的几个棋型的定义,分析了主要对弈策略。并对6×6的点点连格棋机器博弈系统进行了分析与建模。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究的背景及意义
• 1.2 国内外研究的现状
• 1.3 本文的主要内容及创新点
• 1.3.1 本文的主要内容
• 1.3.2 本文的创新点
• 第2章 机器博弈系统介绍
• 2.1 离散事件动态系统
• 2.2 博弈论
• 2.2.1 博弈的分类
• 2.2.2 博弈论的基本概念
• 2.3 机器博弈系统基础
• 2.3.1 机器博弈系统概念与要素
• 2.3.2 开局与残局
• 2.3.3 机器博弈系统中的均衡分析
• 2.4 小结
• 第3章 有限自动机理论
• 3.1 有限自动机基本概念及分类
• 3.2 确定型有限自动机基本概念
• 3.2.1 确定型有限自动机的定义
• 3.2.2 确定型有限自动机的极小化
• 3.3 基于状态差别表的确定型有限自动机的极小化方法
• 3.3.1 状态差别表基本概念
• 3.3.2 状态等价性的判定
• 3.3.3 极小化的步骤
• 3.4 小结
• 第4章 机器博弈系统的自动机模型
• 4.1 α-β搜索算法的自动机实现
• 4.1.1 α-β搜索算法
• 4.1.2 图灵机的基本概念
• 4.1.3 监控器自动机
• 4.1.4 基于图灵机的α-β搜索算法
• 4.2 模型建立与分析
• 4.2.1 模型建立
• 4.2.2 井字棋的自动机实现
• 4.3 小结
• 第5章 点点连格棋系统设计
• 5.1 点点连格棋
• 5.1.1 点点连格棋简介
• 5.1.2 点点连格棋的基本概念
• 5.2 点点连格棋机器博弈系统策略分析
• 5.2.1 相关定理
• 5.2.2 残局的处理
• 5.3 点点连格棋机器博弈系统自动机模型
• 5.3.1 棋局的矩阵表述
• 5.3.2 点点连格棋的系统模型
• 5.4 小结
• 第6章 总结和展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间的研究成果