时序差分学习算法介绍.PPT

时序差分学习在非完备信息机器博弈中的应用 王轩 许朝阳 哈尔滨工业大学深圳研究生院 智能计算中心 2007.10.3 主要内容 非完备信息博弈简介 1 2 时序差分在四国军旗中的应用 3 时序差分学习算法介绍 非完备信息博弈 完备信息博弈（Perfect Information Game ）: 中国象棋； 围棋； … 非完备信息博弈（Imperfect Information Game ）: 四国军棋； 牌类游戏：红心大战，拱猪…. …. 非完备信息博弈树 菱形表示随机节点 四国军旗游戏 蒙特卡罗抽样 根据前面的走步来更新棋子的概率表； 根据更新后的棋子概率表，为棋盘上的 每个棋子随机选择棋子的种类，得到一个 完备信息棋局； 对该完备信息棋局进行MaxMin博弈树有哪些信誉好的足球投注网站， 找到一个最佳走步； 多次重复上述过程，选择选中次数最多的走步 作为最终的最佳走步； 概率表的建立 根据112个经典布局来设定各个棋子的概率表； 根据走步结果来修改棋子的概率表； 为棋盘上的每个棋子都建立各自的概率表； 主要内容 非完备信息博弈简介 1 2 时序差分在四国军旗中的应用 3 时序差分学习算法介绍 时序差分学习 最早由Sutton提出 ； 他证明时序差分学习可以和有监督学习 获得同样的结果而且占用更少的内存， 收敛更快； TD最成功的应用是Tesauro 根据时序差分编制的西洋双陆棋 程序TDGammon，棋力可以和最好的人类棋手相媲美； TD Gammon 时序差分学习场景 时序差分学习基本概念 智能体（Agent）从外部环境（Environment）中读取输入（State），根据State来选择采取哪个行动（Action）； 外部环境根据action的结果提供给智能体一个回报值（reward）； 在一个阶段结束之后，智能体根据回报值，采用某个学习算法（例如时序差分学习算法）来调整自己的行为； 时序差分调整算法基本概念 步数 t = 1，2，3，……表示到了第几步； St 表示第t步时的棋盘状态 ； w是描述棋局状态的一个向量，里面是描述棋局的各种参数（如各种棋子的基本值等）； rst表示在状态St时采取某个走步所获得的回报值； 在游戏结束时的 回报值rsn是确定的，比如1表示赢了，－1表示输了 ，0表示和局； 定义估值函数J（ St ，w）来模拟逼近第t步时采取某个走步时的回报值rst； 假设从游戏开始到结束经历了n步，则估值函数序列为： J（ S1 ，w ）, J（ S2 ，w ） ….J（ Sn-1 ，w ）, rsn ; 时序差分调整算法 期望找到一个最佳向量w，使得估值函数 J（S ，w）在棋局状态S下能够和真实回报值J*（ S, w ）之间的error最小 ： 定义在第t步的时序差分dt如下： 最后的dN-1是实际的最终结果rsn和第n-1步预测之间的差值。 在一轮游戏结束时，TD (λ)利用下面的公式来更新和调整参数向量w: 时序差分公式 其中 是估值函数 J在状态St时关于参数向量w的偏导数， α是一个0到1之间的一个正常数，控制了学习的速率； λ也是一个0到1之间的正常数，控制着时序差分更新时向前传播的 百分比； 主要内容 非完备信息博弈简介 1 2 时序差分在四国军旗中的应用 3 时序差分学习算法介绍 系统运行界面 系统基本架构 四国军旗系统特点 有哪些信誉好的足球投注网站空间巨大； 非完备信息博弈，这里采用了蒙特卡罗抽样技术来解决； 有哪些信誉好的足球投注网站算法根据军棋游戏的特点，使用了历史启发有哪些信誉好的足球投注网站算法，History Heuristics； 估值函数采用时序差分学习技术进行优化 估值函数的优化-时序差分 估值函数是博弈程序的核心； 原来的估值函数结构简单，难以有效的描述棋局； 时序差分定义了一系列的描述棋盘的参数，并通过不断调整这些参数来逼近棋局的真实状况； 四国军旗系统场景设计 Agent是人工智能玩家； Environment外部环境是所有可能的棋局构成的集合； State是当前棋局； Action集合是在当前棋局下所有合法的走步； 回报值r在游戏结束时，有3个可能的值：1，－1，0。1表示赢了，－1表示输了，0表示和局；游戏中间使用估值函数J来模拟逼近回报值r； 四国军旗中的时序差分 在一局游戏结束时根据时序差分学习算法进行调整； 希望对从游戏开