人工智能导论第二章对抗搜索PPT讲稿.ppt

《人工智能导论第二章对抗搜索PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《人工智能导论第二章对抗搜索PPT讲稿.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能导论第二章对抗搜索1第1页，共28页，编辑于2022年，星期四2.1 博弈问题l博弈问题双人一人一步双方信息完备零和2第2页，共28页，编辑于2022年，星期四分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走我方必胜3第3页，共28页，编辑于2022年，星期四中国象棋l一盘棋平均走50步，总状态数约为10的161次方。l假设1毫微秒走一步，约需10的145次方年。l结论：不可能穷举。4第4页，共28页，

2、编辑于2022年，星期四02.2 极小极大过程5-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab025第5页，共28页，编辑于2022年，星期四2.3-剪枝l极大节点的下界为。l极小节点的上界为。l剪枝的条件：后辈节点的值祖先节点的值时，剪枝后辈节点的 值祖先节点的值时，剪枝l简记为：极小极大，剪枝极大极小，剪枝6第6页，共28页，编辑于2022年，星期四486-315035-剪枝（续）-33-3022-30-2309-300-303305411-31661abcdefghijkmn7第7页，共28页，编辑于2022年，星期四2.4

3、 蒙特卡洛博弈方法l为什么-剪枝方法在围棋上失效？-剪枝方法存在的问题l依赖于局面评估的准确性局面评估问题l大量专家知识l知识的统一性问题l人工整理8第8页，共28页，编辑于2022年，星期四围棋落子模型l围棋对弈过程可以看做一个马尔科夫过程：l五元组：T，S，A(i)，P(|i,a)，r(i,a)T：决策时刻S：状态空间，S=iA(i)：可行动集合（可落子点）P(|i,a)：状态i下选择行动a的概率r(i,a)：状态i下选择行动a后课获得的收益9第9页，共28页，编辑于2022年，星期四蒙特卡洛方法l二十世纪40年代中期S.M.乌拉姆和J.冯诺伊曼提出的一种随机模拟方法多重积分矩阵求逆线性方

4、程组求解积分方程求解偏微分方程求解随机性问题模拟10第10页，共28页，编辑于2022年，星期四蒲丰投针问题l1777年法国科学家蒲丰提出一种计算的方法：l取一张白纸，在上面画上许多条间距为d的等距平行线，另取一根长度为l（ld）的针，随机地向该纸上投掷针，并记录投掷次数n以及针与直线相交的次数m，据此计算值。11第11页，共28页，编辑于2022年，星期四dlxl(x,)决定了针的位置l针与直线的相交条件：x (l/2)sinl其中：x0,d/2,0,12第12页，共28页，编辑于2022年，星期四l黄颜色部分与长方形面积之比即为针与直线相交的概率d/2013第13页，共28页，编辑于202

5、2年，星期四14第14页，共28页，编辑于2022年，星期四蒙特卡洛评估l从当前局面的所有可落子点中随机选择一个点落子l重复以上过程l直到胜负可判断为止l经多次模拟后，选择胜率最大的点落子15第15页，共28页，编辑于2022年，星期四蒙特卡洛规划l解决马尔科夫决策问题的有效方法之一l基本思想与特点：将可能出现的状态转移过程用状态树表示从初始状态开始重复抽样，逐步扩展树中的节点某个状态再次被访问时，可以利用已有的结果，提高了效率在抽样过程中可以随时得到行为的评价16第16页，共28页，编辑于2022年，星期四蒙特卡洛规划的步骤l选择从根节点出发自上而下地选择一个落子点l扩展向选定的点添加一个或

6、多个子节点l模拟对扩展出的节点用蒙特卡洛方法进行模拟l回溯根据模拟结果依次向上更新祖先节点估计值17第17页，共28页，编辑于2022年，星期四更新过程l设ni为当前要模拟的节点，为模拟获得的收益l对ni及其祖先的模拟次数加1lni的收益加l更新ni的祖先的收益，同类节点加，非同类节点减（这里节点的类型按照极大极小节点划分）18第18页，共28页，编辑于2022年，星期四蒙特卡洛规划算法流程19第19页，共28页，编辑于2022年，星期四选择落子点的策略l两方面的因素：对尚未充分了解的节点的探索对当前具有较大希望节点的利用20第20页，共28页，编辑于2022年，星期四多臂老虎机模型21第21

7、页，共28页，编辑于2022年，星期四多臂老虎机模型l1952年Robbins提出的一个统计决策模型l多臂老虎机多臂老虎机拥有k个手臂，拉动每个手臂所获得的收益遵循一定的概率且互不相关，如何找到一个策略，使得拉动手臂获得的收益最大化l用于解决蒙特卡洛规划中选择落子点的问题22第22页，共28页，编辑于2022年，星期四信心上限算法UCB1lfunction UCB1l for each 手臂j:l 访问该手臂并记录收益l end forl while 尚未达到访问次数限制 do:l 计算每个手臂的UCB1信心上界Ijl 访问信心上界最大的手臂l end while23第23页，共28页，编辑于

8、2022年，星期四l其中：l 是手臂j所获得回报的均值ln是到当前这一时刻为止所访问的总次数l 是手臂j到目前为止所访问的次数l上式考虑了“利用”和“探索”间的平衡24第24页，共28页，编辑于2022年，星期四信心上限树算法UCTl将UCB1算法应用于蒙特卡洛规划算法中，用于选择可落子点可落子点不是随机选择，而是根据UCB1选择信心上限值最大的节点实际计算UCB1时，加一个参数c进行调节：25第25页，共28页，编辑于2022年，星期四l引入符号:lv:节点，包含以下信息：s(v):v对应的状态a(v):来自父节点的行为Q(v):随机模拟获得的收益N(v):v的总访问次数26第26页，共28页，编辑于2022年，星期四l信心上限树算法（UCT）l function UCTSEARCH(S0)l 以状态S0创建根节点v0;l while 尚未用完计算时长 do:l vl=TREEPOLICY(v0);l =DEFAULTPOLICY(s(vl);l BACKUP(vl，);l end whilel return a(BESTCHILD(v0，0);27第27页，共28页，编辑于2022年，星期四l全部算法的伪代码，请见课程资料28第28页，共28页，编辑于2022年，星期四