(3.2)--PPT-对抗搜索机器学习模型与算法.ppt

对抗搜索问题与认知目标问题：能否使用搜索算法来帮助我们下井字棋或者围棋（如AlphaGo）?认知目标：了解对抗搜索算法概念框架掌握最小最大搜索算法掌握Alpha-Beta 剪枝搜索图图 3.9 井字棋的盘面，此时执井字棋的盘面，此时执“”棋子的玩家获胜棋子的玩家获胜对抗搜索l本本书书主主要要讨讨论论在在确确定定的的、全全局局可可观观察察的的、竞竞争争对对手手轮轮流流行行动动、零零和和游游戏戏（zero-sumzero-sum）下下的的对对抗搜索抗搜索l两人对决游戏两人对决游戏(MAX and MIN,MAX(MAX and MIN,MAX先走先走)可如下形式化描述，从而将其转换为对抗搜索问题可如下形式化描述，从而将其转换为对抗搜索问题状态状态动作动作状态转移状态转移终局状态检测终局状态检测终局得分终局得分注：所谓零和博弈是博弈论的一个概念，属非合作博弈。指参与博弈的各方，在严格竞争下，一注：所谓零和博弈是博弈论的一个概念，属非合作博弈。指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为“零零”，双方不存在，双方不存在合作的可能。与合作的可能。与“零和零和”对应，对应，“双赢博弈双赢博弈”的基本理论就是的基本理论就是“利己利己”不不“损人损人”，通过谈判、，通过谈判、合作达到皆大欢喜的结果。合作达到皆大欢喜的结果。对抗搜索：最小最大搜索最小最大搜索图图 3.9 井字棋的盘面，此时执井字棋的盘面，此时执“”棋子的玩家获胜棋子的玩家获胜对抗搜索：最小最大搜索最小最大搜索对抗搜索：Alpha-Beta 剪枝搜索剪枝搜索Alpha-Beta 剪枝搜索算法在剪枝搜索算法在Minimax算法中可减少被搜索的算法中可减少被搜索的结点结点数，即在保证得到与原数，即在保证得到与原Minimax算法同样的搜索结果时，剪去了不影响最终结果的搜索分枝。算法同样的搜索结果时，剪去了不影响最终结果的搜索分枝。图图中中MIN选选手手所所在在的的结结点点C下下属属分分支支4和和6与与根根结结点点最最终终优优化化决决策策的的取取值值无无关关，可不被访问。可不被访问。对抗搜索：Alpha-Beta 剪枝搜索剪枝搜索图图 3.12 存在剪枝的搜索树部分扩展过程存在剪枝的搜索树部分扩展过程对抗搜索：Alpha-Beta 剪枝搜索剪枝搜索图3.14 基于MIN结点反馈收益进行剪枝(alpha剪枝)MAXMINMAXMIN已被访问后继分支节点未被访问后继分支节点被剪枝对抗搜索：Alpha-Beta 剪枝搜索剪枝搜索图3.15基于MAX结点反馈收益进行剪枝(beta剪枝)对抗搜索：Alpha-Beta 剪枝搜索剪枝搜索算法流程对抗搜索：Alpha-Beta 剪枝搜索剪枝搜索课后题1.图中展示了一棵Minimax搜索树，可采用alpha-beta剪枝算法进行对抗搜索。假设对于每个节点的后继节点，算法按照从左向右的方向扩展。同时假设当alpha值等于beta值时，算法不进行剪枝。请对图中所示搜索树进行搜索，并画出alpha-beta剪枝算法结束时搜索树的状态，用“”符号标出被剪枝的子树，并计算该算法扩展的节点数量。