搜索
第五章对抗搜索内容提要博弈α-β剪枝不完美的实时决策随机博弈部分可观察的博弈发展现状竞争环境中多个agent之间的目标是有冲突的，称为对抗搜索问题，也称为博弈博弈有完整信息的，确定的，轮流行动的，两个游戏者的零和游戏,如国际象棋难于求解注重时间效率游戏表示成搜索问题S0初始状态Player(s)谁行动Action(s)状态下的合法移动集合Result(s,a)转移模型Terminal-test(s):终止测试Utility(s,p):效用函数零和游戏叶子结点表示结果赢:1输:-1和:0博弈树的最优策略通过检查每个结点的极大极小值来决定：minimax(n)Max喜欢移动到有极大值的状态，min喜欢移动到有极小值的状态3完备性？最优性？时间复杂度？空间复杂度？与两人博弈的不同用向量值取代单一值通常选择使自己效用值最大的行为联盟与破坏联盟游戏状态数目的增长是指数级的通过剪枝来消除对部分分支的搜索，且被剪掉的分支不影响最终的决策α-β剪枝的效率很大程度上依赖于检查后继状态的顺序最佳剪枝情况下可以将时间复杂度从极大极小算法的O(bm)减少到O(bm/2)，采用随机顺序检查的总结点数大约是O(b3m/4)当遇到大的问题的时候搜索空间是非常大的解决问题的方法：截断测试限制搜索深度或搜索时间评估函数评估当前位置的有效性值结点为结点为为真如果IN)1),,((min)1),,((max),()(),()()(MsdasRESULTMINIMAXHMAXsdasRESULTMINIMAXHdsTESTCUTOFFsEVALdsMINMAXHsActionsasActionsa评估函数的定义准则：对于终止状态的排序应该和效用函数一致计算时间不能太长对于非终止状态应该和取胜几率相关评估函数的效率值可能被映射到多个终止状态用终止状态的概率值来表示当前状态的期望值0.72*1+0.2*0+0.08*(-1)=0.76对于国际象棋问题，典型的评估函数是线性加权评估：Eval(s)=w1f1(s)+w2f2(s)+…+wnfn(s)Eg.w1=9,f1=(白棋皇后数量)-(黑棋皇后数量)线性评估假定特征之间是独立的，然而实际中特征之间具有关联性，比如国际象棋在残局中2个象比单个象的价值要高出2倍Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)在α-β剪枝算法中Terminal-test被替换程cutoff-test(state,depth)Utility被替换程eval(state)cutoff-test(state,depth)截断策略：当大于固定深度是返回True根据游戏允许的时间来决定深度评估函数的近似性会使截断搜索可能导致错误评估函数只适应于静态棋局，即不会很快出现大摇摆的棋局22对方招数导致我方严重损失并且理论上基本无法避免黑棋行棋后，黑象命运已定，但是黑方可以通过检查白王和兵，迫使王吃兵。这样就将象拉出了地平线，被牺牲掉的兵被搜索算法视为好棋招23无需考虑直接剪枝一些子结点柱搜索每一层只考虑最好的n步棋可能导致最佳的行棋被剪掉Probcut算法使用先验的统计信息在一定程度上保护最佳行棋不被剪枝掉首先浅层搜索计算结点的v值，再根据经验来估计深度d上的值是否在(α,β)范围外开局时的行棋大多依赖于人类的专业知识接近尾声的棋局可能性有限在开局和尾声阶段可以通过查表的方式来进行行棋25许多博弈存在不确定性的随机因素，如掷骰子，我们称为随机博弈如西洋双陆棋结合了运气和技巧通过掷骰子决定合法行动白方掷骰子(6-5)将有4中合法移动西洋双陆棋的博弈树除了max和min结点之外还必须包括随机结点没有明确的极大极小值，而是期望值27期望极大极小值rsActionsasActionsasrsRESULTIMAXEXPECTIMINrPMINsasRESULTIMAXEXPECTIMINMAXsasRESULTIMAXEXPECTIMINzssUTILITYsIMAXEXPECTIMIN为机会结点结点为结点为终止状态为)),(()()),((min)),((max)()()()(评估函数应该与棋局获胜的概率成线性变换时间复杂度(bmnm)军旗棋子可以移动但对方看不见棋子是什么使用信念状态牌类随机部分可观察需要概率推算来制定决策30国际象棋：深蓝打败世界冠军。深蓝在30个IBMRS/6000处理器并行计算机上运行α-β剪枝。西洋跳棋：Chinook程序1990年战胜了世界冠军奥赛罗：也叫翻转棋，1997年6比0击败人类世界冠军西洋双陆棋：1992年GerryTeasuro使用强化学习与神经网络训练的评估函数性能良好。博弈α-β剪枝不完美的实时决策随机博弈部分可观察的博弈发展现状QA？