第Ⅱ部分 问题求解 第5章 对抗搜索 中国科大 计算机学院.

Presentation on theme: "第Ⅱ部分 问题求解 第5章 对抗搜索 中国科大 计算机学院."— Presentation transcript:

1 第Ⅱ部分 问题求解 第5章 对抗搜索 中国科大 计算机学院

2 本章内容 5.1 博弈 5.2 博弈中的优化决策 5.3 -剪枝 5.4 不完美的实时决策 5.5 随机博弈 5.6 部分可观察的博弈
5.7 博弈程序发展现状 5.8 其他途径

3 5.1 博弈 概述 Grundy博弈

4 概述 在博弈问题中——比如说象棋——搜索是在博弈者双方之间进行的。 任何一方在搜索时，都必须要考虑对方可能要采用的走步。
对于一个优秀的博弈者来说，应考虑的不只是对方一步的走法，而是若干步的走法。 这一过程一般来说是动态进行的。在考虑若干步走法以后，下了一步棋；而在对方走棋之后，还要再次考虑若干步走法，决定下一步的走法，而不是一劳永逸，搜索一次就决定了所有的走法。

5 概述 本章所讲的博弈：主要指的是类似于象棋这样的游戏问题。 这类问题有以下一些特点： 双人对弈，对垒的双方轮流走步。
信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。 零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。

6 概述 双人完备信息博弈： 指两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。
对弈的结果是一方赢（另一方则输），或者双方和局。 这类博弈的实例有：一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。 机遇性博弈：存在不可预测性的博弈，例如掷币等。 例如：西洋双陆棋。

7 Grundy博弈 Grundy博弈是一个分钱币的游戏。
如此进行下去，直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。 对于这样的简单博弈问题，可以生成出它的状态空间图。这样就有可能从状态空间图中找出取胜的策略。

8 Grundy博弈 当初始钱币数为7时的状态空间图 MIN代表对方走 MAX代表我方走 MAX存在完全取胜的策略

9 Grundy博弈 搜索策略要考虑的问题： 对MIN走步后的每一个MAX节点，必须证明MAX对MIN可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付MIN的所有招法，这是一个与的含意。 因此含有MAX符号的节点可看成与节点。 对MAX走步后的每一个MIN节点，只须证明MAX有一步能走赢就可以，即MAX只要考虑能走出一步棋使MIN无法招架就成。 因此含有MIN符号的节点可看成或节点。 因此，对弈过程的搜索图就呈现出与或图表示的形式。

10 Grundy博弈 寻找MAX的取胜策略和求与或图的解图相对应。 MAX要取胜，必须对所有与节点取胜，但只需对一个或节点取胜，这就是一个解图。
因此，寻找一种取胜的策略就是搜索一个解图的问题，解图就代表一种完整的博弈策略。 对于Grundy这种较简单的博弈，或者复杂博弈的残局，可以用类似于与或图的搜索技术求出解图，解图代表了从开局到终局任何阶段上的弈法。 显然这对许多博弈问题是不可能实现的。例如，中国象棋，国际象棋和围棋等。

11 Grundy博弈 对于复杂的博弈问题，因此即使用了强有力的启发式搜索技术，也不可能使分枝压到很少。
因此，这种完全取胜策略（或和局）必须丢弃。 应当把目标确定为寻找一步好棋，等对手回敬后再考虑寻找另一步好棋这种实际可行的实用策略。 这种情况下每一步的结束条件可根据时间限制、存储空间限制或深度限制等因素加以确定。 搜索策略可采用宽度、深度或启发式方法。一个阶段搜索结束后，要从搜索树中提取一个优先考虑的"最好的"走步，这就是实用策略的基本点。

12 本章内容 5.1 博弈 5.2 博弈中的优化决策 5.3 -剪枝 5.4 不完美的实时决策 5.5 随机博弈 5.6 部分可观察的博弈
5.7 博弈程序发展现状 5.8 其他途径

13 5.2 博弈中的优化决策 极小极大值法 多人游戏中的最优决策

14 极小极大搜索过程 人类下棋的方法：实际上采用的是一种试探性的方法。
首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的回应...... 这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。 初学者可能只能看一、两个回合，而高手则可以看几个，甚至十几个回合。 极小极大搜索方法：模拟的就是人的这样一种思维过程。 极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的α-β剪枝搜索方法，就是从这一方法发展而来的。

15 极小极大搜索过程 极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在有限的搜索深度范围内进行求解。
定义一个静态估计函数f，以便对棋局的势态（节点）作出优劣估值。 这个函数可根据势态优劣特征来定义（主要用于对端节点的“价值”进行度量）。 一般规定：有利于MAX的势态，f（p）取正值；有利于MIN的势态，f（p）取负值；势均力敌的势态，f（p）取0值。 若f（p）＝＋∞，则表示MAX赢，若f（p）＝－∞，则表示MIN赢。

16 极小极大搜索过程 注意：不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。
等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。 极小极大过程是一种假定对手每次回应都正确的情况下，如何从中找出对我方最有利的走步的搜索方法。

17 极小极大搜索过程 规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方。MAX先走。 例：一个考虑2步棋的例子。
图中端节点给出的数字是用静态函数f（p）计算得到，其他节点不用f（p）估计，因为不够精确，而应用倒推的办法取值。例如A、B、C是MIN走步的节点，MAX应考虑最坏的情况，故其估值应分别取其子节点f（p）估值中最小者，而s是MAX走步的节点，可考虑最好的情况，故估值应取A、B、C值中的最大者。这样求得f（s）＝－2，依此确定了相对较优的走步应是走向B，因为从B出发，对手不可能产生比f（s）＝－2更差的效果。实际上可根据资源条件，考虑更多层次的搜索过程，从而可得到更准确的倒推值，供MAX选取更正确的走步。当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。

18 极小极大搜索过程 规定：顶节点深度d＝0，MAX代表程序方，MIN代表对手方。MAX先走。 例：一个考虑2步棋的例子。
图中端节点给出的数字是用静态函数f（p）计算得到，其他节点不用f（p）估计，因为不够精确，而应用倒推的办法取值。例如A、B、C是MIN走步的节点，MAX应考虑最坏的情况，故其估值应分别取其子节点f（p）估值中最小者，而s是MAX走步的节点，可考虑最好的情况，故估值应取A、B、C值中的最大者。这样求得f（s）＝－2，依此确定了相对较优的走步应是走向B，因为从B出发，对手不可能产生比f（s）＝－2更差的效果。实际上可根据资源条件，考虑更多层次的搜索过程，从而可得到更准确的倒推值，供MAX选取更正确的走步。当用端节点的静态估计函数f（p）求倒推值时，两位选手应采取不同的策略，从下往上逐层交替使用极小和极大的选值方法，故称极小极大过程。 端节点给出的数字是用静态估计函数f（p）计算得到。

19 过程MINIMAX ① T:＝（s，MAX），OPEN:＝（s），CLOSED:＝（ ）；开始时树由初始节点构成，OPEN表只含有s。
② LOOP1: IF OPEN＝（ ）THEN GO LOOP2； ③ n:＝FIRST(OPEN)，REMOVE(n，OPEN)，ADD(n，CLOSED)； ④ IF n可直接判定为赢、输或平局 THEN f（n）:＝∞∨－∞∨0，GO LOOP1 ELSE EXPAND（n）→{ni}，ADD（{ni}，T） IF d（ni）＜k THEN ADD（{ni}，OPEN），GO LOOP1 ELSE 计算f（ni ），GO LOOP1；ni达到深度k，计算各端节点f值。 ⑤ LOOP2：IF CLOSED＝NIL THEN GO LOOP3 ELSE np:＝FIRST（CLOSED）； ⑥ IF（np∈MAX）∧（f（nci∈MIN）有值） THEN f（ np ）:＝max{f（nci）}，REMOVE(np，CLOSED)；若MAX所有子节点均有值，则该MAX取其极大值。 IF （ np ∈MIN）∧（f（ nci ∈MAX）有值） THEN f（ np ）:＝min{f（nci）}，REMOVE(np ，CLOSED)；若MIN所有子节点均有值，则该MIN取其极小值。 ⑦ GO LOOP2； ⑧ LOOP3：IF f（s）≠NIL THEN EXIT( END∨M(Move，T) )；s有值，则结束或标记走步。

20 过程MINIMAX 该算法分两个阶段进行: 第一阶段②～④：用宽度优先法生成规定深度的全部博弈树，然后对其所有端节点计算其静态估计函数值。
第二阶段⑥～⑧：从底向上逐级求非端节点的倒推估计值，直到求出初始节点s的倒推值f（s）为止，此时 等对手响应走步后，再以当前的状态作为起始状态s，重复调用该过程。

21 例：3×3棋盘的一字棋 3×3棋盘的一字棋：九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。
假设： 程序方MAX的棋子用（×）表示； 对手MIN的棋子用（○）表示； MAX先走。

22 例：3×3棋盘的一字棋 静态估计函数f（p）规定如下： 若p是MAX获胜的格局，则f（p）＝∞； 若p是MIN获胜的格局，则f（p）＝－∞；
若p对任何一方来说都不是获胜的格局，则f（p）＝（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总数－（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数）。 例、当p的格局如下时，则可得f（p）＝6－4＝2。

23 例：3×3棋盘的一字棋 在搜索过程中，具有对称性的棋局认为是同一棋局，可以大大减少搜索空间。 对称棋局的例子

24 例：3×3棋盘的一字棋 假定考虑走两步的搜索过程，利用棋盘对称性的条件，则第一次调用算法产生的搜索树为：

25 例：3×3棋盘的一字棋 假设MAX走完第一步后，MAX的对手是在×之上的格子下棋子，这时MAX在新格局下调用算法，第二次产生的搜索树为：

26 例：3×3棋盘的一字棋 类似地，第三次的搜索树为： 至此MAX走完最好的走步后，不论MIN怎么走，都无法挽回败局，因此只好认输了。

27 博弈中的优化决策 极小极大值法 多人游戏中的最优决策

28 多人游戏中的最优决策 许多流行的游戏允许多于两个的参加者。 如何把极小极大思想推广到多人游戏中？
在两人的零和游戏中，由于效用值正好相反，所以二维向量可以简化为一个单一值。 每个节点上的单一评估值要替换成一个向量。 例、一个有三个人A, B和C的游戏中，每个节点都与一个向量<vA, vB, vC>相关联。 对于终止状态，该向量给出了从每个人的角度出发得到的状态效用值。

29 多人游戏中的最优决策 一般来讲，节点n的回传值是该游戏者在节点n选择的效用值最高的后继者的效用值向量。

30 多人游戏中的最优决策 多人游戏通常会涉及在游戏者之间出现正式或者非正式联盟的情况。 随着游戏的进行，联盟会建立或解散。
在多人游戏中，对每个游戏者来说，联盟是否是最优策略的一个自然结果？ 违反盟约会损害社会声誉。 游戏者要在毁约得到的直接利益和被认为不可信任带来的长期弊端之间寻求平衡。

31 本章内容 5.1 博弈 5.2 博弈中的优化决策 5.3 -剪枝 5.4 不完美的实时决策 5.5 随机博弈 5.6 部分可观察的博弈
5.7 博弈程序发展现状 5.8 其他途径

32 -剪枝的基本思想 在极小极大搜索方法中，由于要生成指定深度以内的所有节点，其节点数将随着搜索深度的增加成指数增长。
这极大地限制了极小极大搜索方法的使用。 能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？

33 -剪枝的基本思想 设某博弈问题如下图所示： 设某博弈问题如下图所示，应用极小极大方法进行搜索。 假设搜索的顺序为从下到上，从左到右。
当计算完a的值为0后，由于b是极大节点，马上就可以知道b的值大于等于0。接下来求c的值。由于c是极小节点，由d的值为-3，知道c的值小于等于-3。而a和c都是b的子节点，所以即便不扩展节点e，也可以知道b的值一定为0了。所以在这种情况下，没有生成节点e的必要。同样，在知道b的值为0后，由于k是极小节点，所以立即知道k的值要小于等于0。而通过节点f、g，知道h的值至少为3。这样即便不扩展A所包围的那些节点，也能知道k的值一定为0。所以A包围的那些节点也没有生成的必要，不管这些节点取值如何，都不影响k的值。如果在搜索的过程中，充分利用这些信息，不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程正是这样一种搜索方法。

34 -剪枝的基本思想 α-β搜索过程的基本思想：把博弈树生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早修剪掉一些无用的分枝。
为了使生成和估值过程紧密结合，采用有界深度优先策略进行搜索。 当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值。

35 -剪枝的基本思想 极大值层的下界值称为α 极小值层的上界值称为β

36 α-β搜索过程的剪枝规则 α剪枝：若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值，即α（先辈层）≥β（后继层），则可中止该极小值层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值。 β剪枝：若任一极大值层节点的α值大于或等于它任一先辈极小值层节点的β值，即α（后继层）≥β（先辈层），则可以中止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的最终倒推值就确定为这个α值。 根据这些剪枝规则，很容易给出α-β算法描述，显然剪枝后选得的最好优先走步，其结果与不剪枝的MINIMAX方法所得完全相同，因而α-β过程具有较高的效率。

37 α-β搜索过程的博弈树 α-β剪枝举例 约定： 在搜索过程中，节点的生成次序是从上到下，从左到右进行的。
图中带圈的数字，表示节点的计算次序。在叙述时，为了表达上的方便，该序号也同时表示节点。 当一个节点有两个以上的序号时，不同的序号，表示的是同一个节点在不同次序下计算的结果。

38 α-β搜索过程的博弈树 α-β剪枝举例

39 -搜索过程 在进行α-β剪枝时，应注意以下几个问题：
比较都是在极小节点和极大节点间进行的；极大节点和极大节点的比较，或者极小节点和极小节点间的比较是无意义的。 在比较时注意是与“先辈层”节点比较，不只是与父辈节点比较。当然，这里的“先辈层”节点，指的是那些已经有了值的节点。 只有一个节点的值“固定”以后，其值才能够向其父节点传递。

40 -搜索过程 在进行α-β剪枝时，应注意以下几个问题：
α-β剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是一致的，α-β剪枝并没有因为提高效率，而降低得到最佳走步的可能性。 在实际搜索时，并不是先生成指定深度的搜索图，再在搜索图上进行剪枝。 如果这样，就失去了α-β剪枝方法的意义。 在实际程序实现时，首先规定一个搜索深度，然后按照类似于深度优先搜索的方式，生成节点。在节点的生成过程中，如果在某一个节点处发生了剪枝，则该节点其余未生成的节点就不再生成了。

41 剪枝的效率问题 若以最理想的情况进行搜索，即对MIN节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），MAX先扩展最高估值的节点（设估计值从左向右递减排序），则当搜索树深度为D，分枝因数为B时， 若不使用α-β剪枝技术，搜索树的端节点数为： 若使用α-β剪枝技术，可以证明理想条件下生成的端节点数最少，有

42 剪枝的效率问题 比较后得出最佳α-β搜索技术所生成深度为D处的端节点数约等于不用α-β搜索技术所生成深度为D／2处的端节点数。
这就是说，在一般条件下使用α-β搜索技术，在同样的资源限制下，可以向前考虑更多的走步数，这样选取当前的最好优先走步，将带来更大的取胜优势。

43 其他改进方法 使用α-β剪枝技术，当不满足剪枝条件（即α不大于等于β ）时，若β值比α值大不了多少或极相近，这时也可以进行剪枝。
以便有条件把搜索集中到会带来更大效果的其他路径上，这就是中止对效益不大的一些子树的搜索，以提高搜索效率。 不严格限制搜索的深度，当到达深度限制时，如出现博弈格局有可能发生较大变化时（如出现兑子格局），则应多搜索几层，使格局进入较稳定状态后再中止，这样可使倒推值计算的结果比较合理，避免考虑不充分产生的影响，这是等候状态平稳后中止搜索的方法。

44 其他改进方法 当算法给出所选的走步后，不马上停止搜索，而是在原先估计可能的路径上再往前搜索几步，再次检验会不会出现意外，这是一种增添辅助搜索的方法。 对某些博弈的开局阶段和残局阶段，往往总结有一些固定的对弈模式。 因此，可以利用这些知识编好走步表，以便在开局和结局时使用查表法。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。

45 其他改进方法 以上这些方法还不能全面反映人们弈棋过程实际所使用的一切推理技术，也未涉及棋局的表示和启发函数问题。
高明的棋手对棋局的表示有独特的模式。 博弈过程中，若在一个短时期内短兵相接，进攻和防御的战术变化剧烈，这些情况如何在搜索策略中加以考虑？ 基于极小极大过程的一些方法都设想对手走的总是最优走步，即我方总应考虑最坏的情况。实际上，再好的选手也会有失误，如何利用失误加强攻势，也值得考虑。 总之要真正解决具体的博弈搜索技术，有许多更深入的问题需要作进一步的研究和探讨。

46 本章内容 5.1 博弈 5.2 博弈中的优化决策 5.3 -剪枝 5.4 不完美的实时决策 5.5 随机博弈 5.6 部分可观察的博弈
5.7 博弈程序发展现状 5.8 其他途径

47 不完整的实时决策 MINIMAX或–剪枝算法 理想情况：算法一直搜索，直到至少一部分空间到达终止状态，从而对端节点做出准确评价。
这样的搜索不现实。 实用方法： 用可以估计棋局效用的启发式评价函数评价非终止节点。 用可以决策什么时候运用评价函数的截断测试取代终止测试。 实用方法：Shannon于1950年提出。

48 评价函数 评价函数的设计： 应该以和真正的效用函数同样的方式对终止状态进行排序。 评价函数的计算不能花费太多的时间！
效用函数（又称目标函数或者收益函数）：对终止状态给出一个数值。例如，在国际象棋中，结果是赢、输或平局，分别赋予＋1，－1或0。 评价函数的计算不能花费太多的时间！ 对于非终止状态，评价函数应该和取胜的实际机会密切相关。

49 评价函数 在计算能力有限情况下，评价函数能做到最好的就是猜测最后的结果。
例如，国际象棋并不是几率游戏，而且也确切知道当前状态；但计算能力有限，从而导致结果必然是不确定的。 大多数评价函数的工作方式是计算状态的不同特征。 例如，国际象棋中兵的数目、象的数目、马的数目等等。 这些特征一起定义了状态的各种类别或者等价类。 但因类别太多而几乎不可能去估计取胜概率。

50 评价函数 大多数评价函数计算每个特征单独的数值贡献，然后把它们结合起来找到一个总值。 加权线性评价函数
每个wi是一个权值，fi是棋局的某个特征。

51 评价函数 例如，国际象棋的入门书中给出各个棋子的估计子力价值。 兵值1分； 马、象值3分； 车值5分； 后值9分。
其它特征。例如，“好的兵阵”和“王的安全性”可能值半个兵。 把这项特征值简单相加就得到了一个对棋局的估计。 经验表明，如果其它都一样，则 在领先超过1分的可靠子力优势下很可能取得胜利； 3分的优势几乎足以肯定取胜。

52 评价函数 （a）黑棋有1个马、2个兵的优势，能够取胜。 （b）黑棋会被白棋吃掉皇后，从而失败。
马：走法有点特别，先横走或直走1格，再沿离开原在格子的方向斜走1格，合起来为一步棋。可以越子，可进可退，也没有“中国象棋”中“蹩马腿”的限制。

53 评价函数 加权线性评价函数的假设：每个特征的贡献独立于其它特征的值。 假设太强！ 例如，象赋予3分忽略了象在残局中能够发挥更大作用的事实。
当前国际象棋和其它游戏的程序也采用非线性的特征组合。

54 评价函数 注意：特征和权值并不是国际象棋规则的一部分。 它们只是人类下棋的经验总结。 在很难归纳这样的经验规律的游戏中，怎么办？
评价函数的权值可以通过机器学习来估计。

55 截断搜索 最直接的控制搜索次数的方法：设置一个固定的深度限制。 更鲁棒的方法：使用迭代深入搜索。
具体实现：不断加大深度优先限制。首先为0，接着为1，然后为2，依此类推。 当时间用完时，程序就返回目前已完成的最深的搜索所选择的招数。

56 截断搜索 由于评价函数的近似性，这些方法可能导致错误。 需要更为复杂的截断测试。 评价函数应该只用于那些静止的棋局。
静止的棋局：评价值在很近的未来不会出现大的摇摆变化棋局。 例如，在国际象棋中，有很好的吃招的棋局对于只统计子力的评价函数来说就不能算时静止的。 非静止的棋局可以进一步扩展直到静止的棋局，这种额外的搜索称为静止搜索。 有时候只考虑某些类型的招数，诸如吃子，能够快速地解决棋局的不确定性。

57 单一扩展和前向剪枝 单一扩展：搜索在给定的棋局中一步明显好于其它招数的行棋。 对“一步明显好于其它招数的行棋”进行超过一般深度限制的搜索。
目的：避免地平线效应且不增加太多搜索代价。 前向剪枝：在某个结点上不需要进一步搜索而直接剪枝。 有危险！只在某些特殊的情况下使用才是安全的。

58 不完整的实时决策 假设已经实现： 国际象棋的评价函数 使用静止搜索的合理截断测试
一个很大的调换表（存储以前见过的棋局的哈希表一般被称做调换表） 若在“最新的PC”上可每秒生成和评价约一百万个节点，则允许我们在标准的时间控制下（每步棋3分钟）对每步棋可搜索约2亿个节点。 国际象棋的分支因子平均为35，355约为5亿。 如果使用极大极小搜索，只能向前预测5层，很容易被平均水平的人类棋手欺骗。 如果使用alpha-beta搜索，可以预测大约10层，接近专业棋手水平。