1.-博弈搜索

曲阜师范大学计算机科学学院Slide1高级人工智能雷玉霞[e-mail]曲阜师范大学计算机科学学院Slide2至2050年信息科学各层次的重要研究方向曲阜师范大学计算机科学学院Slide3本课程的要求需要的基础：离散数学，数据结构，算法设计与分析等考试成绩:平时成绩30分+期末成绩70曲阜师范大学计算机科学学院Slide4博弈搜索算法决策树学习算法贝叶斯学习算法局部搜索方法模拟退火算法遗传算法蚁群算法免疫克隆算法鱼群算法主要内容：曲阜师范大学计算机科学学院Slide5参考文献ArtificialIntelligence:ANewSynthesis--(美国)NilssonArtificialIntelligence:StructureandStrategiesforComplexProblemSolving--(美国)Luger机器学习理论与算法科学出版社（2012）遗传算法的基本理论与应用科学出版社（2004）智能科学网站曲阜师范大学计算机科学学院Slide6AI的重要国际会议IJCAI:AI最好的综合性会议AAAI:美国人工智能学会AAAI的年会COLT:计算学习理论最好的会议,ACM主办CVPR:计算机视觉和模式识别方面最好的会议之一,IEEE主办ICML:机器学习方面最好的会议之一ACL:计算语言学/自然语言处理方面最好的会议KR:知识表示和推理方面最好的会议之一SIGIR:信息检索方面最好的会议,ACM主办SIGKDD:数据挖掘方面最好的会议,ACM主办曲阜师范大学计算机科学学院Slide7一、状态空间搜索和回溯技术的例子二、博弈搜索搜索技术（博弈搜索）曲阜师范大学计算机科学学院Slide8状态空间表示法的构成状态空间方法:是用来表示问题及其搜索的一种方法，以状态和算符为基础来表示和求解问题，其四要素如下：1.状态2.算符3.状态空间4.问题的解曲阜师范大学计算机科学学院Slide9例子1.回溯策略(皇后问题)在一个4×4的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获QQQQ曲阜师范大学计算机科学学院Slide10()曲阜师范大学计算机科学学院Slide11()Q((1,1))曲阜师范大学计算机科学学院Slide12()QQ((1,1))((1,1)(2,3))曲阜师范大学计算机科学学院Slide13()Q((1,1))((1,1)(2,3))曲阜师范大学计算机科学学院Slide14()QQ((1,1))((1,1)(2,3))((1,1)(2,4))曲阜师范大学计算机科学学院Slide15()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))曲阜师范大学计算机科学学院Slide16()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))曲阜师范大学计算机科学学院Slide17()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))曲阜师范大学计算机科学学院Slide18()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))曲阜师范大学计算机科学学院Slide19()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))曲阜师范大学计算机科学学院Slide20()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))曲阜师范大学计算机科学学院Slide21()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))曲阜师范大学计算机科学学院Slide22()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))曲阜师范大学计算机科学学院Slide23例2：修道士和野人过河问题问题描述：有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到和的右岸。约束条件：但该船每次只能装载2个人，在任何岸边野人的数目都不能超过修道士的人数，否则修道士就会被野人吃掉。假设野人服从从任何一种过河安排，请问如何规划过河计划才能让所有人都安全地渡到河的右岸。曲阜师范大学计算机科学学院Slide24第一步：定义问题状态的描述形式。S=(Nx,Ny,C)，其中Nx表示修道士在左岸的实际人数；Ny表示野人在左岸的实际人数，C来指示船是否在左岸。C=1表示在左岸，C=0表示不在左岸。第二步：把所有的状态描述出来（32个状态）S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(3,0,1)S4=(3,3,0)S5=(3,2,0)S6=(3,1,0)S7=(3,0,0)S8=(2,3,1)S9=(2,2,1)S10=(2,1,1)S11=(2,0,1)S12=(2,3,0)S13=(2,2,0)S14=(2,1,0)S15=(2,0,0)S16=(1,3,1)S17=(1,2,1)S18=(1,1,1)S19=(1,0,1)S20=(1,3,0)S21=(1,2,0)S22=(1,1,0)S23=(1,0,0)S24=(0,3,1)S25=(0,2,1)S26=(0,1,1)S27=(0,0,1)S28=(0,3,0)S29=(0,2,0)S30=(0,1,0)S31=(0,0,0)曲阜师范大学计算机科学学院Slide25第三步：定义算符L(i,j)和R(i,j)从左到右：L(1,0),L(2,0),L(1,1),L(0,1),L(0,2)从右到做：R(1,0),R(2,0),R(1,1),R(0,1),R(0,2)曲阜师范大学计算机科学学院Slide26第四步：状态空间搜索图曲阜师范大学计算机科学学院Slide27二、博弈搜索博弈：被认为高智能行为游戏;不断为AI研究提出新课题，推动AI研究的发展。曲阜师范大学计算机科学学院Slide28基于博弈搜索的搜索策略博弈问题及博弈树概念博弈搜索控制策略博弈搜索算法及其应用实例博弈搜索优化-α-β剪枝曲阜师范大学计算机科学学院Slide29博弈问题及博弈树概念博弈问题：对抗的双方参加博弈，取胜的因素不仅取决于一方的如意算盘，还需充分考虑对方的应付策略，（一字棋、国际象棋、打扑克、中国象棋、围棋）。双人完备信息：对垒的双方轮流走步，对弈的条件和走步规则完全相同。每一方不仅知道对方已走过的所有棋步，而且还能估计出对方未来可能走的棋步。曲阜师范大学计算机科学学院Slide30博弈问题及博弈树概念博弈问题描述：棋局描述；棋局走步规则。博弈搜索过程：搜索棋局走步规则，隐含生成一棵特殊的与或树博弈问题求解：曲阜师范大学计算机科学学院Slide31博弈问题及博弈树概念与或节点分层交替出现的与或树从甲的立场出发或节点与节点或节点完全取胜解图甲走步曲阜师范大学计算机科学学院Slide32博弈问题及博弈树概念判断走步的极小-极大原则：考虑对方走步时（与节点）：假定对手不会犯错误，他总是选择对自己最有利，对我方最不利的棋步走。因此，我方不能采取任何冒险行动,视对手将走出的棋局为极小值；考虑我方走步时（或节点）：应在对方造成的最坏的局势中尽可能地选择最好的棋着走，视自己可能走出的棋局为极大值。曲阜师范大学计算机科学学院Slide33基于博弈搜索的搜索策略博弈问题及博弈树博弈搜索控制策略博弈搜索算法及其应用实例博弈树的α-β剪枝完整的博弈搜索策略（盲目搜索策略）有界深度博弈搜索策略曲阜师范大学计算机科学学院Slide34完整的博弈搜索策略核心思想：从博弈的初始格局开始，轮番考虑自己与对方可能的所有走步，生成出棋局的各个格局，直到达到分出胜负输赢的终止格局为止，此搜索过程产生的一棵完整的博弈树。曲阜师范大学计算机科学学院Slide35完整的博弈搜索策略博弈问题实例：有一堆数目为N的钱币，甲、乙二人轮流分堆。要求每人每次挑选其中某一堆钱币，将其分成数目不等的两小堆。分堆过程持续，直至其中一人无法再将任一堆钱币分成数目不等的两堆时，则认输。博弈问题描述：分堆格局(状态):(x1,x2,…,xn,M),其中，xi:第i堆钱币的个数；M:当前走步人编号-（MAX,MIN）走步规则：IF(x1,x2,…,xn,M)∧(xi=Y+Z)∧(Y≠Z)THEN(x1,x2,…,xi-1,Y,Z,xi+1,…,xn,M)曲阜师范大学计算机科学学院Slide36完整的博弈搜索策略站在MAX立场与节点或节点与节点完全取胜的完备策略曲阜师范大学计算机科学学院Slide37特点：搜索策略简单，易于控制，可用于简单的博弈或一个复杂博弈的残局；完整的博弈搜索策略不适合复杂的博弈问题搜索-指数爆炸。例，中国象棋：设每种格局有40种走法，一盘棋双方平均走50步，完整的博弈搜索-搜索节点数（402）50≈10160，搜索深度达100层。有必要引入有界深度博弈搜索策略。曲阜师范大学计算机科学学院Slide38基于博弈搜索的搜索策略博弈问题及博弈树博弈搜索控制策略完整的博弈搜索策略（盲目搜索策略）有界深度博弈搜索策略（启发式搜索策略）曲阜师范大学计算机科学学院Slide39有界深度搜索策略核心思想：根据对方已走出的棋步，构造出具有一定深度的博弈树，并从此局部博弈树中选择相对好的棋着走。需解决的关键问题：定义估计终结棋局优劣的评价函数；给出棋局优劣性传递的计算方法。曲阜师范大学计算机科学学院Slide40定义棋局的评价函数设P为有界博弈树中棋局；ｈ(P):棋局Ｐ优劣的评价函数。•例1：从当前棋局到离我方最后取胜的差距：胜利在望–ｈ(P)值较大，败局显露–ｈ(P)值较小；•例2：从当前棋局到到某个明显有利于我方棋局的差距：吃掉对方一子,或者“叫吃”。ｈ(P)MAX赢=ｈ(P)MIN输=+∞ｈ(P)MAX输=ｈ(P)MIN赢=-∞ｈ(P)平=0ｈ(P)–任一终叶棋局Ｐ优劣的评价函数的定义原则：曲阜师范大学计算机科学学院Slide41计算棋局的评价函数有界博弈树中任一棋局（节点Ｐ）评价函数值的计算：对于终叶节点Ｐ：赋静态评价函数值ｈ(P);对于非终叶节点Ｐ：按极小-极大走步原则，采用倒推的方法，自下而上地由子节点计算父节点的动态评价函数值ｈ(P)。曲阜师范大学计算机科学学院Slide42站在MAX立场基于极小-极大原则的评价函数计算实例静态启发式评价函数值动态评价函数值曲阜师范大学计算机科学学院Slide43基于博弈搜索的搜索策略博弈问题及博弈树博弈搜索控制策略有界深度搜索算法及其应用实例博弈树的α-β剪枝曲阜师范大学计算机科学学院Slide44有界深度搜索算法及其应用实例针对当前对方给出的棋局s：1、按宽度优先法自上而下地生成规定深度的博弈树；2、为有界深度博弈树的所有叶节点赋静态评价函数估计值3、根据极小-极大走步原则自下而上地逐级计算各非终叶节点的动态评价函数估计值，直至求到起始节点的评价函数值ｈ(s)为止。比较我方可走的各棋局的评价函数估计值，从中选择最好的棋步走。再根据对方走出的棋局s，重复上述过程。曲阜师范大学计算机科学学院Slide45有界深度搜索算法及其应用实例一字棋（站在MAX的立场）定义特殊棋局估计函数h1(P)h1(P)MAX赢=+∞h1(P)MAX输=-∞h1(P)平=０h1(P)MAX赢=+∞h1(P)MAX输=-∞h1(P)平=０曲阜师范大学计算机科学学院Slide46有界深度搜索算法