时序差分学习算法介绍课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,时序差分学习在非完备信息,机器博弈中的应用,王轩 许朝阳,哈尔滨工业大学深圳研究生院,智能计算中心,2007.10.3,时序差分学习在非完备信息机器博弈中的应用王轩 许朝阳,主要内容,非完备信息博弈简介,1,2,时序差分在四国军旗中的应用,3,时序差分学习算法介绍,主要内容 非完备信息博弈简介12,非完备信息博弈,完备信息博弈（,Perfect Information Game,）,:,中国象棋；,围棋；,非完备信息博弈（,Imperfect Information,Game,）,:,四国军棋；,牌类游戏：红心大战，拱猪,.,.,非完备信息博弈完备信息博弈（Perfect Informat,非完备信息博弈树,菱形表示随机节点,非完备信息博弈树菱形表示随机节点,四国军旗游戏,四国军旗游戏,蒙特卡罗抽样,根据前面的走步来更新棋子的概率表；,根据更新后的棋子概率表，为棋盘上的,每个棋子随机选择棋子的种类，得到一个,完备信息棋局；,对该完备信息棋局进行,MaxMin,博弈树搜索，,找到一个最佳走步；,多次重复上述过程，选择选中次数最多的走步,作为最终的最佳走步；,蒙特卡罗抽样根据前面的走步来更新棋子的概率表；,概率表的建立,根据,112,个经典布局来设定各个棋子的概率表；,根据走步结果来修改棋子的概率表；,为棋盘上的每个棋子都建立各自的概率表；,概率表的建立根据112个经典布局来设定各个棋子的概率表；,主要内容,非完备信息博弈简介,1,2,时序差分在四国军旗中的应用,3,时序差分学习算法介绍,主要内容 非完备信息博弈简介12,时序差分学习,最早由,Sutton,提出；,他证明时序差分学习可以和有监督学习,获得同样的结果而且占用更少的内存，,收敛更快；,TD,最成功的应用是,Tesauro,根据时序差分编制的西洋双陆棋,程序,TDGammon,，棋力可以和最好的人类棋手相媲美；,时序差分学习最早由Sutton提出；,TD Gammon,TD Gammon,时序差分学习场景,时序差分学习场景,时序差分学习基本概念,智能体（,Agent,）从外部环境（,Environment,）中读取输入（,State,），根据,State,来选择采取哪个行动（,Action,）；,外部环境根据,action,的结果提供给智能体一个回报值（,reward,）；,在一个阶段结束之后，智能体根据回报值，采用某个学习算法（例如时序差分学习算法）来调整自己的行为；,时序差分学习基本概念智能体（Agent）从外部环境（Envi,时序差分调整算法基本概念,步数,t,=,1,，,2,，,3,，,表示到了第几步；,S,t,表示第,t,步时的棋盘状态,；,w,是描述棋局状态的一个向量，里面是描述棋局的各种参数（如各种棋子的基本值等）；,r,st,表示在状态,S,t,时采取某个走步所获得的回报值；,在游戏结束时的 回报值,r,sn,是确定的，比如,1,表示赢了，,1,表示输了，,0,表示和局；,定义估值函数,J,（,S,t,，,w,）来模拟逼近第,t,步时采取某个走步时的回报值,r,st,；,假设从游戏开始到结束经历了,n,步，则估值函数序列为：,J,（,S,1,，,w,）,J,（,S,2,，,w,）,.J,（,S,n-1,，,w,）,r,sn,;,时序差分调整算法基本概念步数 t=1，2，3，表示到,时序差分调整算法,期望找到一个最佳向量,w,，使得估值函数,J,（,S,，,w,）在棋局状态,S,下能够和真实回报值,J*,（,S,w,）之间的,error,最小：,定义在第,t步的时序差分d,t,如下：,最后的,d,N-1,是实际的最终结果,r,sn,和第,n-1步预测之间的差值。,在一轮游戏结束时，,TD()利用下面的公式来更新和调整参数向量w:,时序差分调整算法期望找到一个最佳向量w，使得估值函数 J（S,时序差分公式,其中 是估值函数,J,在状态,S,t,时关于参数向量,w,的偏导数，,是一个,0,到,1,之间的一个正常数，控制了学习的速率；,也是一个,0,到,1,之间的正常数，控制着时序差分更新时向前传播的,百分比；,时序差分公式,主要内容,非完备信息博弈简介,1,2,时序差分在四国军旗中的应用,3,时序差分学习算法介绍,主要内容 非完备信息博弈简介12,系统运行界面,系统运行界面,系统基本架构,系统基本架构,四国军旗系统特点,搜索空间巨大；,非完备信息博弈，这里采用了蒙特卡罗抽样技术来解决；,搜索算法根据军棋游戏的特点，使用了历史启发搜索算法，,History,Heuristics,；,估值函数采用时序差分学习技术进行优化,四国军旗系统特点搜索空间巨大；,估值函数的优化,-,时序差分,估值函数是博弈程序的核心；,原来的估值函数结构简单，难以有效的描述棋局；,时序差分定义了一系列的描述棋盘的参数，并通过不断调整这些参数来逼近棋局的真实状况；,估值函数的优化-时序差分估值函数是博弈程序的核心；,四国军旗系统场景设计,Agent,是人工智能玩家；,Environment,外部环境是所有可能的棋局构成的集合；,State,是当前棋局；,Action,集合是在当前棋局下所有合法的走步；,回报值,r,在游戏结束时，有,3,个可能的值：,1,，,1,，,0,。,1,表示赢了，,1,表示输了，,0,表示和局；游戏中间使用估值函数,J,来模拟逼近回报值,r,；,四国军旗系统场景设计Agent是人工智能玩家；,四国军旗中的时序差分,在一局游戏结束时根据时序差分学习算法进行调整；,希望对从游戏开始到游戏结束所经历的每个棋局,S,，由估值函数,J,（,S,，,w,）所算出来的回报值和真实值,J*,之间的 差值最小；,例如，理想的回报值可能是这样的：,S,1,S,2,S,N-1,S,N,0.90 0.92 0.98 1,估值函数,J,（,S,，,w,）得到的结果可能是：,S,1,S,2,S,N-1,0.3 0.5 0.8,这里期望通过调整,w,，可是使得在每个棋局状态,S,，估值函数得到的结果都能够非常接近理想回报值。,四国军旗中的时序差分在一局游戏结束时根据时序差分学习算法进行,时序差分调整过程,对游戏过程中经历的每个状态,S,i,，,计算出,J,（,S,i,，,w,），利用,J,来作为估值函数计算博弈树搜索时博弈树的各个叶节点的估值；,对游戏所经历的各步，,t,1,，,2,，,3,，,N-1,计算出时序差分：,根据时序差分公式来更新参数向量,w,：,时序差分调整过程对游戏过程中经历的每个状态Si，计算出 J,参数向量,w,为了更准确有效的描述棋盘状态,S,，定义了下面几组参数来构成参数向量,w,：,棋子基本值数组：如司令的基本值为,500,，炸弹为,300,，军旗为,1000,等；,棋子灵活性数组：如司令的灵活性为,2.0,，工兵的灵活性为,0.8,等；,进攻位置加分数组：如在敌方军旗附近的位置加分，行营位置加分等；,特殊组合得分：如炸弹师长对得分，三角雷得分等；,威胁保护比例：棋子受到威胁（或受到保护）时的减分（或加分）比例等；,参数向量w为了更准确有效的描述棋盘状态S，定义了下面几组参数,估值函数,J,可以看作是一个,1n,的向量,v,和,n1,的参数向量,w,的内积；,例如：,N,是（基本值数组的各个参数所对应的系数，灵活性数组的各个参数所对应的系数，,）,w,是（基本值数组的各个参数，灵活性数组的各个参数，,），则,J,基本值数组的各个参数,基本值数组系数所对应的系数,灵活性数组的各个参数,灵活性数组参数所对应的系数,.,J,对,w,是处处可导的，满足时序差分的条件；,估值函数J可以看作是一个1n的向量v和n1的参数向量w的,有待改进的地方,学习过程较为缓慢；,能够精确有效描述棋局的各种参数需要进一步的增加和完善；,误差对于参数调整的影响；,研究学习参数,和参数,对于学习过程的影响；,有待改进的地方学习过程较为缓慢；,估值函数举例,估值函数举例,谢谢大家！,时序差分学习算法介绍课件,