人工智能导论搜索求解.pdf

《人工智能导论搜索求解.pdf》由会员分享，可在线阅读，更多相关《人工智能导论搜索求解.pdf（87页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、搜索求解 人工智能：模型与算法人工智能：模型与算法 提纲提纲 1、 启发式搜索启发式搜索 2、 对抗搜索对抗搜索 3、 蒙特卡洛蒙特卡洛树搜索树搜索 人工智能中的搜索人工智能中的搜索 你见，或者不见我 我就在那里 不悲 不喜 -扎西拉姆多多 海量 信息源 问题求解器 问题所对应答案 人工智能中的搜索：以寻找最短路径问题为例人工智能中的搜索：以寻找最短路径问题为例 问题：寻找从Arad到Bucharest的一条最短路径 搜索算法的形式化描述：搜索算法的形式化描述： 状态、动作、状态转移、路径、测试目标状态、动作、状态转移、路径、测试目标 问题：寻找从Arad到Bucharest的一条路径，满 足

2、路径最短、时间最少、价钱最经济？ 状态 动作 搜索算法的形式化描述：搜索算法的形式化描述： ，因此右边节点及后续节点就被剪枝掉了 为可能解法的最大上界 为可能解法的最小下界 如果节点 是可能解法路径中的一个节点，则其产生的收益一定满足如下条件： () (其中()是节点产生的收益) 每个节点有两个值，分别是和。节点的和值在搜索过程中不断变化。其中，从负无穷大 ()逐渐增加、从正无穷大()逐渐减少。如果一个节点中 ，则该节点的后续节点可剪枝。 对抗对抗搜索：如何利用搜索：如何利用Alpha-Beta 剪枝剪枝 对抗对抗搜索：搜索：Alpha-Beta 剪枝搜索示意剪枝搜索示意 对抗对抗搜索：搜索：

3、Alpha-Beta 剪枝搜索示意剪枝搜索示意 对抗对抗搜索：搜索：Alpha-Beta 剪枝搜索剪枝搜索的算法描述的算法描述 剪枝本身不影响算法输出结果 节点先后次序会影响剪枝效率 如果节点次序“恰到好处”，Alpha-Beta剪枝的时间复杂度为 O( 2)，最小最大搜索的时间复杂度为O() 对抗对抗搜索：搜索：Alpha-Beta 剪枝搜索的性质剪枝搜索的性质 提纲提纲 1、 启发式搜索启发式搜索 2、 对抗搜索对抗搜索 3、蒙特卡洛树搜索蒙特卡洛树搜索 推荐阅读材料 David Silver, et.al., Mastering the game of Go with Deep Neur

4、al Networks and Tree Search, Nature, 529:484-490,2016 Cameron Browne, et.al., Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1-49,2012 Sylvain Gelly, Levente Kocsis, Marc Schoenauer, et al., The Grand Challenge of Computer Go: Monte C

5、arlo Tree Search and Extensions, Communications of the ACM, 55(3):106-113,2012 Levente KocsisCsaba Szepesvari, Bandit Based Monte-Carlo Planning, ECML 2006 Auer, P., Cesa-Bianchi, N., & Fischer, P. , Finite-time analysis of the multi-armed bandit problem, Machine learning, 47(2), 235-256, 2002 对抗搜索：

6、蒙特卡洛树搜索对抗搜索：蒙特卡洛树搜索 (exploitation)与探索(exploration)在游戏博弈树上的有机协调 蒙特卡洛规划 (Monte-Carlo Planning) 单一状态蒙特卡洛规划： 多臂赌博机 (multi-armed bandits) 上限置信区间策略 (Upper Confidence Bound Strategies, UCB) 蒙特卡洛树搜索 (Monte-Carlo Tree Search) UCT (Upper Confidence Bounds on Trees) 单一单一状态蒙特卡洛状态蒙特卡洛规划规划： 多多臂赌博机臂赌博机 (multi-arme

7、d bandits) 单一状态， 种行动（即有 个摇臂） 在摇臂赌博机问题中，每次以随机采样形式采取一种行动, 好比随机拉动第个赌博机的臂膀，得到(,) 的回报。 问题：下一次需要拉动那个赌博机的臂膀，才能获得最大回 报呢？ 多臂赌博机问题是一种序列决策问题，这种问题需要在利用 (exploitation)和探索(exploration) 之间保持平衡。 利用(exploitation) ：保证在过去决策中得到最佳回报 探索(exploration) ：寄希望在未来能够得到更大回报 多臂多臂赌博机赌博机 (multi-armed bandits) 多多臂赌博机臂赌博机 (multi-armed

8、 bandits) 如果有个赌博机，这个赌博机产生的操作序列为,1,2, (i = 1,K)。 在时刻 = 1,2，选择第个赌博机后，可得到奖赏,，则在次操作 1,后，可如下定义悔值函数： = max =1, , =1 , =1 悔值函数表示了如下意思：在第次对赌博机操作时，假设知道哪个赌博机 能够给出最大奖赏（虽然在现实生活中这是不存在的），则将得到的最大 奖赏减去实际操作第个赌博机所得到的奖赏。将次操作的差值累加起来， 就是悔值函数的结果。 很显然，一个良好的多臂赌博机操作的策略是在不同人进行了多次玩法后， 能够让悔值函数的方差最小。 上限置信区间 (Upper Confidence Bo

9、und, UCB) 在多臂赌博机的研究过程中，上限置信区间（Upper Confidence Bound, UCB） 成为一种较为成功的策略学习方法，因为其在探索-利用（exploration- exploitation）之间取得平衡。 在UCB方法中，使,(1)来记录第个赌博机在过去 1时刻内的平均奖赏， 则在第时刻，选择使如下具有最佳上限置区间的赌博机： =max 1, 1 + 1, 1 其中,取值定义如下： ,= 2 = (= ) =1 为在过去时刻（初始时刻到时刻）过程中选择第个赌 博机的次数总和。 上限置信区间 (Upper Confidence Bound, UCB) 也就是说，在

10、第时刻，UCB算法一般会选择具有如下最大值的第个赌博 机： = + 2 或者 = + 2 是第个赌博机在过去时间内所获得的平均奖赏值， 是在过去时间内 拉动第个赌博机臂膀的总次数，是过去时间内拉动所有赌博机臂膀的 总次数。 是一个平衡因子，其决定着在选择时偏重探索还是利用。 从这里可看出UCB算法如何在探索-利用（exploration-exploitation）之间 寻找平衡：既需要拉动在过去时间内获得最大平均奖赏的赌博机，又希 望去选择那些拉动臂膀次数最少的赌博机。 UCB算法描述 上限置信区间 (Upper Confidence Bound, UCB) 蒙特卡洛树搜索 将上限置信区间算法

11、UCB应用于游戏树的搜索方法，由Kocsis和Szepesvari在2006年提出 包括了四个步骤：选举(selection)，扩展(expansion)，模拟(simulation)，反向传播(Back- Propagation) L. Kocsis and C. Szepesvari, Bandit based Monte-Carlo Planning, ECML, 2006:282293 选择：选择： 从根节点 R 开始，向下递归选择 子节点，直至选择一个叶子节点L。 具体来说，通常用UCB1（Upper Confidence Bound，上限置信区间） 选择最具“潜力”的后续节点 蒙特

12、卡洛树搜索 = + 2 扩展扩展 ： 如果 L 不是一个终止节点（即 博弈游戏不），则随机创建其 后的一个未被访问节点，选择 该节点作为后续子节点C。 蒙特卡洛树搜索 模拟：模拟： 从节点 C出发，对游戏进行模拟， 直到博弈游戏结束。 反向传播反向传播 用模拟所得结果来回溯更新导致 这个结果的每个节点中获胜次数 和访问次数。 蒙特卡洛树搜索 两种策略学习机制： 搜索树策略: 从已有的搜索树中选择或创建 一个叶子结点（即蒙特卡洛中选择和拓展两 个步骤）.搜索树策略需要在利用和探索之 间保持平衡。 模拟策略：从非叶子结点出发模拟游戏，得 到游戏仿真结果。 蒙特卡洛树搜索 蒙特卡洛树搜索：例子 以围

13、棋为例，假设根节点是执 黑棋方。 图中每一个节点都代表一个局 面，每一个局面记录两个值 A/B： A：该局面被访问中黑棋胜利次 数。对于黑棋表示己方胜利次数， 对于白棋表示己方失败次数（对 方胜利次数）； B：该局面被访问的总次数。 蒙特卡洛树搜索：例子 该图刻画了蒙特卡洛树搜索四个步骤， 假设根结点由黑棋行棋，为了选择根节 点后续节点，需要由UCB1公式来计算根 节点后续节点如下值，取一个值最大的 节点作为后续节点： 左1：7/10对应的局面奖赏值为 7 10 + log (21) 10 = 1.252 左2，5/8对应的局面奖赏值为5 8 + log (21) 8 = 1.243 左3，0

14、/3对应的局面评估分数为 0 3 + log (21) 3 = 1.007 由此可见，黑棋会选择局面7/10进行行 棋。 蒙特卡洛树搜索：例子 在节点7/10，由白棋行棋，评估该节点 下面的两个局面，由UCB1公式可得（注 意：此时A记录的的是白棋失败的次数， 所以第一项为1-A/B）： 左1，2/4对应的局面奖赏为 1 2 4 + log (10) 4 = 1.26 左2，5/6对应的局面奖赏为 1 5 6 + log (10) 6 = 0.786 由此可见，白棋会选择局面2/4进行行棋。 蒙特卡洛树搜索：例子 在节点2/4，黑棋评估下面的两个局面， 由UCB1公式可得： 左1，1/3对应的

15、局面奖赏为1 3 + log(4) 3 = 1.01 左1，1/1对应的局面奖赏1 1 + log(4) 1 = 2.18 由此可见，黑棋会选择局面1/1进行行棋。 此时已经到达叶子结点，需要进行扩展。 蒙特卡洛树搜索：例子 随机扩展一个新节点。由于该新节 点未被访问，所以初始化为0/0，接 着在该节点下进行模拟。假设经过 一系列仿真行棋后，最终白棋获胜。 根据仿真结果来更新该仿真路径上 每个节点的A/B值，该新节点的A/B 值被更新为0/1，并向上回溯到该仿 真路径上新节点的所有父辈节点， 即所有父辈节点的A不变，B值加1。 使用蒙特卡洛树搜索的原因 Monte-Carlo Tree Sea

16、rch (MCTS)：蒙特卡洛树搜索基于采样来得到 结果、而非穷尽式枚举（虽然在枚举过程中也可剪掉若干不影响结果 的分支）。 蒙特卡洛树搜索算法 (Upper Confidence Bounds on Trees , UCT) 状态集 在状态s能够采取的有效行动的集合 () 节点所代表的状态 () 所采取的行动导致到达节点 : A 状态转移函数 () 节点被访问的次数 () 节点所获得的奖赏值 (,) 玩家选择节点所得到的奖赏值 v0 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 v 蒙特卡洛树搜索算法(UCT) v0 vl 蒙特卡

17、洛树搜索算法(UCT) v0 vl reward 蒙特卡洛树搜索算法(UCT) v0 vl reward 蒙特卡洛树搜索算法(UCT) v0 vl 蒙特卡洛树搜索算法(UCT) v0 vl 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 v 蒙特卡洛树搜索算法(UCT) v0 v 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 v 蒙特卡洛树搜索算法(UCT) v0 v 蒙特卡洛树搜索算法(UCT) v0 vl 蒙特卡洛树搜索算法(UCT)

18、 v0 vl 蒙特卡洛树搜索算法(UCT) v0 蒙特卡洛树搜索算法(UCT) v0 a 蒙特卡洛树搜索算法(UCT) 将每个状态（局面）均视 为一幅图像 训练策略（policy）网络和 价值（value）网络 ,(|)表示当前状态为 （局面）时，采取行动 后所得到的概率； () 表示当前状态为时，整 盘棋获胜的概率。 David Silver, et.al., Mastering the game of Go with Deep Neural Networks and Tree Search, Nature, 529:484-490,2016 AlphaGo算法解读 3000万人类万人类 选

19、手对决的选手对决的 局面（图像）局面（图像） 3000万自我万自我 博弈局面博弈局面 （图像）（图像） 基于监督学习来先训练策略网络 Idea: perform supervised learning (SL) to predict human moves Given state , predict probability distribution over moves , ,(|) Trained on 30M positions, 57% accuracy on predicting human moves Also train a smaller, faster rollout poli

20、cy network (24% accurate) 再基于强化学习来训练策略网络 Idea: fine-tune policy network using reinforcement learning (RL) Initialize RL network to SL network Play two snapshots of the network against each other, update parameters to maximize expected final outcome RL network wins against SL network 80% of the time,

21、 wins against open-source Pachi Go program 85% of the time AlphaGo算法解读：策略网络的训练 Value network Idea: train network for position evaluation Given state , estimate (), expected outcome of play starting with position s and following the learned policy for both players Train network by minimizing mean squ

22、ared error between actual and predicted outcome Trained on 30M positions sampled from different self-play games AlphaGo算法解读：价值网络的训练 在通过深度学习得到的策略网络和价值网络帮助之下，如下完成棋局局 面的选择和搜索。给定节点0，将具有如下最大值的节点选择作为0 的后续节点 () () + (|0) 1 + () 这里(|0) 的值由策略网络计算得到。 在模拟策略阶段(default policy)，AlphaGo不仅考虑仿真结果，而且考虑价值 网络计算结果。 策略网络

23、和价值网络是离线训练得到的。 AlphaGo算法解读：蒙特卡洛树搜索中融入了策略网络和价值网络 AlphaGo算法解读：蒙特卡洛树搜索中融入了策略网络和价值网络 策略网络计算策略网络计算 价值网络计算价值网络计算 AlphaGo算法解读 AlphaGo算法解读：AlphaGo Zero （一张白纸绘蓝图） 经过40天训练后，Zero总计运行约2900万次自 我对弈，得以击败AlphaGo Master，比分为89 比11 不需要人类选手对决的棋面进行训练 策略网络和价值网络合并 深度残差网络 Mastering the game of Go without human knowledge, Nature, volume 550, pages 354 359 (19 October 2017)