(3.4)--PPT-蒙特卡洛树搜索机器学习模型与算法.ppt

蒙特卡洛树搜索问题与认知目标问题：请大家想想AlphaGo在跟李世石下围棋时，是如何选择落子的，或如何落子才能获胜？认知目标：掌握上限置信区间算法掌握蒙特卡洛树搜索算法对抗搜索：蒙特卡洛树搜索对抗搜索：蒙特卡洛树搜索对抗搜索：蒙特卡洛树搜索对抗搜索：蒙特卡洛树搜索对抗搜索：蒙特卡洛树搜索l不足：忽略了其他从未摇动或很少摇动的赌博机，而失去了可能的机会。智能体错误地认为5号赌博机不如4号赌博机，因而无法做出更好的选择l上述困境体现了探索探索（exploration）和利用利用（exploitation）之间存在对立关系。贪心算法基本上是利用利用从已有尝试结果中所得估计来指导后续动作，但问题是所得估计往往不能准确反映未被（大量）探索过的动作。因此，需要在贪心算法中增加一个能够改变其“惯性”的内在动力，以使得贪心算法能够访问那些尚未被（充分）访问过的空间。对抗搜索：蒙特卡洛树搜索对抗搜索：蒙特卡洛树搜索上限置信区间算法（上限置信区间算法（Upper Confidence Bounds,UCB1Upper Confidence Bounds,UCB1）：为每个动作的奖励期望计算一个估计范围，优先采用估计范围上限较高的动作。图图 3.23 UCB1算法的策算法的策略示意图略示意图动作1的奖励期望取值的不确定度（估计范围）虽然最大，但是因为其均值太小，因此UCB1算法不优先考虑探索动作1。动作2和3的奖励期望的均值相同，但是动作2的奖励期望取值的不确定度（估计范围）更大，于是因为置信上限更大，动作2会被UCB1算法优先考虑。对抗搜索：蒙特卡洛树搜索霍夫丁不等式（霍夫丁不等式（Hoeffdings inequalityHoeffdings inequality）对抗搜索：蒙特卡洛树搜索（3.5）对抗搜索：蒙特卡洛树搜索对搜索算法进行优化以提高搜索效率基本上是在解决如下两个问题：优先扩展哪优先扩展哪些节点以及放弃扩展哪些节点些节点以及放弃扩展哪些节点，综合来看也可以概括为如何高效地扩展搜索树。如果将目标稍微降低，改为求解一个近似最优解，则上述问题可以看成是如下探索性问题：算法从根节点开始，每一步动作为选择（在非叶子节点）或扩展（在叶子节点）一个孩子节点。可以用执行该动作后所收获奖励来判断该动作优劣。奖励可以根据从当前节点出发到达目标路径的代价或游戏终局分数来定义。算法会倾向于扩展获得奖励较高的节点。算法事先不知道每个节点将会得到怎样的代价（或终局分数）分布，只能通过采样式探索来得到计算奖励的样本。由于这个算法利用蒙特卡洛法通过采样来估计由于这个算法利用蒙特卡洛法通过采样来估计每个动作优劣，因此它被称为蒙特卡洛树搜索（每个动作优劣，因此它被称为蒙特卡洛树搜索（Monte-Carlo Tree Search）算法）算法Kocsis 2006。对抗搜索：蒙特卡洛树搜索l选择（选择（selectionselection）：）：选择指算法从搜索树的根节点开始，向下递归选择子节点，直至到达叶子节点或者到达具有还未被扩展过的子节点的节点L。这个向下递归选择过程可由UCB1算法来实现，在递归选择过程中记录下每个节点被选择次数和每个节点得到的奖励均值。l扩展（扩展（expansionexpansion）：）：如果节点 L 不是一个终止节点（或对抗搜索的终局节点），则随机扩展它的一个未被扩展过的后继边缘节点M。对抗搜索：蒙特卡洛树搜索l模拟（模拟（simulationsimulation）：）：从节点M出发，模拟扩展搜索树，直到找到一个终止节点。模拟过程使用的策略和采用UCB1算法实现的选择过程并不相同，前者通常会使用比较简单的策略，例如使用随机策略。l反向传播（反向传播（Back PropagationBack Propagation）：）：用模拟所得结果（终止节点的代价或游戏终局分数）回溯更新模拟路径中M以上（含M）节点的奖励均值和被访问次数。对抗搜索：蒙特卡洛树搜索图 3.25 蒙特卡洛树搜索算法。结点中数字代表总收益分数/被访问次数。对抗搜索：蒙特卡洛树搜索在图3.25(b)中，算法随机扩展了L的子结点C，将其总分数和被访问次数均初始化为0。注意，为了清晰地展示算法选择扩展的结点，图3.25(b)画出了L的其他未被扩展的子结点，并标记其UCB值为正无穷大，以表示算法下次访问到L时必然扩展这些未被扩展的结点。图3.4.6(c)中采用随机策略模拟游戏直至完成游戏。当游戏完成时，终局得分为3。图 3.25 蒙特卡洛树搜索算法。结点中数字代表总收益分数/被访问次数。对抗搜索：蒙特卡洛树搜索在图3.4.6(d)中C结点的总分被更新为-3，被访问次数被更新为1；L结点的总分被更新为13，被访问次数被更新为2；根结点的总分被更新为-18，被访问次数被更新为3。在更新时，会将MIN层结点现有总分加上终局得分分数，MAX层结点现有总分减去终局得分分数。这是因为在对抗搜索中，玩家MIN总是期望最小化终局得分，因此在MIN层选择其子结点时，其目标并非选取奖励最大化的子结点，而是选择奖励最小化的结点，为了统一使用UCB1算法求解，算法将MIN层的子结点（即MAX层结点）的总分记为其相反数。对抗搜索：蒙特卡洛树搜索课后题1.下列关于蒙特卡洛树搜索算法的说法中，不正确的是（）。A.选择过程体现了探索与利用的平衡。B.算法进入扩展步骤时，当前节点的所有子节点必然都未被扩展。C.模拟步骤采取的策略与选择步骤不一定要相同。D.反向传播只需要更新当前路径上已被扩展的节点。