问题求解基本原理 搜 索 技 术 ( 三 ) 博 弈 搜 索 博 弈：被认为高智能行为游戏; 不断为AI研究提出新课题，推动AI研究的发展。

Presentation on theme: "问题求解基本原理 搜 索 技 术 ( 三 ) 博 弈 搜 索 博 弈：被认为高智能行为游戏; 不断为AI研究提出新课题，推动AI研究的发展。"— Presentation transcript:

1 问题求解基本原理 搜 索 技 术 ( 三 ) 博 弈 搜 索 博 弈：被认为高智能行为游戏; 不断为AI研究提出新课题，推动AI研究的发展。

2 基于博弈搜索的搜索策略 博弈问题及博弈树概念 博弈搜索控制策略 博弈搜索算法及其应用实例 博弈树的 α - β 剪枝

3 博弈问题及博弈树概念 博弈问题： 双人完备信息：
对抗的双方参加博弈，取胜的因素不仅取决于一方的如意算盘，还需充分考虑对方的应付策略，（一字棋、国际象棋、打扑克、中国象棋、围棋）。 双人完备信息： 对垒的双方轮流走步，对弈的条件和走步规则完全相同。每一方不仅知道对方已走过的所有棋步，而且还能估计出对方未来可能走的棋步。

4 博弈问题及博弈树概念 博弈问题求解： 博弈问题描述： 棋局描述； 棋局走步规则。 博弈搜索过程： 搜索棋局走步规则，隐含生成一棵特殊的与或树

5 博弈问题及博弈树概念 或节点 与节点 完全取胜解 图 甲走步 或节点 从甲的立场出发 与或节点分层交替出现的与或树

6 博弈问题及博弈树概念 判断走步的极小-极大原则：
考虑对方走步时（与节点）：假定对手不会犯错误，他总是选择对自己最有利，对我方最不利的棋步走。因此，我方不能采取任何冒险行动,视对手将走出的棋局为极小值； 　考虑我方走步时（或节点）：应在对方造成的最坏的局势中尽可能地选择最好的棋着走，视自己可能走出的棋局为极大值。

7 基于博弈搜索的搜索策略 博弈问题及博弈树 博弈搜索控制策略 博弈搜索算法及其应用实例 博弈树的 α - β 剪枝
完整的博弈搜索策略（盲目搜索策略） 有界深度博弈搜索策略

8 完整的博弈搜索策略 核心思想： 从博弈的初始格局开始，轮番考虑自己与对方可能的所有走步，生成出棋局的各个格局，直到达到分出胜负输赢的终止格局为止，此搜索过程产生的一棵完整的博弈树。

9 完整的博弈搜索策略 走步规则： 分堆格局(状态): (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)

10 完整的博弈搜索策略 与节点 完全取胜的完备策略 或节点 与节点 站在MAX立场

11 完整的博弈搜索策略 特点： 例，中国象棋： 有必要引入有界深度博弈搜索策略。 搜索策略简单，易于控制，可用于简单的博弈或一个复杂博弈的残局；
不适合复杂的博弈问题搜索 - 指数爆炸。 例，中国象棋： 设每种格局有40种走法，一盘棋双方平均走50步， 完整的博弈搜索 - 搜索节点数（402）50 ≈ 10160，搜索深度达100层。 有必要引入有界深度博弈搜索策略。

12 基于博弈搜索的搜索策略 博弈问题及博弈树 博弈搜索控制策略 完整的博弈搜索策略（盲目搜索策略） 有界深度博弈搜索策略（启发式搜索策略）

13 有界深度搜索策略 核心思想： 需解决的关键问题： 根据对方已走出的棋步，构造出具有一定深度的博弈树，并从此局部博弈树中选择相对好的棋着走。
定义估计终结棋局优劣的评价函数； 给出棋局优劣性传递的计算方法。

14 定义棋局的评价函数 设 P 为有界博弈树中棋局；ｈ(P): 棋局Ｐ优劣的评价函数。 ｈ(P)MAX赢 = ｈ(P)MIN输 = +∞
例1：从当前棋局到离我方最后取胜的差距： 胜利在望 – ｈ(P)值较大，败局显露 – ｈ(P)值较小； 例2：从当前棋局到到某个明显有利于我方棋局的差距： 吃掉对方一子, 或者 “叫吃”。

15 计算棋局的评价函数 有界博弈树中任一棋局（节点Ｐ）评价函数值的计算： 对于终叶节点Ｐ：赋静态评价函数值ｈ(P);

16 基于极小-极大原则的评价函数计算实例 站在MAX立场 动态评价函数值 静态启发式评价函数值

17 基于博弈搜索的搜索策略 博弈问题及博弈树 博弈搜索控制策略 有界深度搜索算法及其应用实例 博弈树的 α - β 剪枝

18 有界深度搜索算法及其应用实例 针对当前对方给出的棋局 s ： 1、按宽度优先法自上而下地生成规定深度的博弈树；
2、为有界深度博弈树的所有叶节点赋静态评价函数估计值 3、根据极小-极大走步原则自下而上地逐级计算各非终叶节点的动态评价函数估计值，直至求到起始节点的评价函数值 ｈ(s)为止。 比较我方可走的各棋局的评价函数估计值，从中选择最好的棋步走。 再根据对方走出的棋局 s，重复上述过程。

19 有界深度搜索算法及其应用实例 一字棋（站在MAX的立场） 定义特殊棋局估计函数h1(P) h1(P)MAX赢 = +∞

20 有界深度搜索算法及其应用实例 一字棋（站在MAX的立场） 定义棋局评价函数： 将整行、整列或整条对角线称为赢线。如果一条赢线上只有ＭＡＸ（ＭＩＮ）方的棋子或为空，而没有ＭＩＮ（ＭＡＸ）方的棋子，则称此赢线称为ＭＡＸ（ＭＩＮ）方的赢线。　 设ＭＡＸ方任意棋局的静态评价函数 h1(P) ： ｈ１(P) = ＭＡＸ的赢线数　–　ＭＩＮ的赢线数 h(p)MAX = 6 – 4 = 2 h(p)MＩＮ = 4 – 6 = - 2

21 有界深度搜索算法及其应用实例 MAX走棋第一步( 深度为2 )： MAX走步

22 有界深度搜索算法及其应用实例 MAX走棋第二步： MAX走棋第三步： MAX走步 MAX走步

23 基于博弈搜索的搜索策略 问题： 启发式博弈搜索策略 - 将扩展生成博弈树的过程与计算、评价及确定最优走步的过程完全分开进行，导致了搜索效率的低下。 对策： α - β剪枝技术 - 在生成博弈树同时计算和评价棋局节点，对不必要展开的节点进行剪枝，可减少许多不必要节点的生成和计算工作量，提高搜索效率。

24 基于博弈搜索的搜索策略 博弈问题及博弈树 博弈搜索控制策略 有界深度搜索算法及其应用实例 博弈树的 α - β 剪枝

25 博弈树的 α - β 剪枝 h(3) ≤ 17 h(3)  25

26 博弈树的α - β 剪枝 n n1 α 值： 设博弈树中某节点 n 属于极大层。它左边第一个子节点 n1的评价函数值 h(n1)可视为节点 n 的下界值，或称为 α 值，节点 n 的评价函数值 h(n)决不会小于此 α 值。 n 的α值

27 博弈树的α - β 剪枝 n n1 β 值： 设博弈树中某节点 n 属于极小层。它左边第一个子节点 n1的评价函数值 h(n1)可视为节点 n 的上界值，或称为 β 值，节点 n 的 h(n)决不会大于此 β 值。 n 的β值

28 博弈树的α - β 剪枝 α剪枝： 若任一极小层节点 m 的 β 值小于或等于其位于极大层的父节点的 α 值，即 α  β，则可终止该极小层中节点 m 以下的搜索过程。 m α值 β值

29 博弈树的 α - β 剪枝 m β 剪枝： 若任一极大层节点 m 的 α 值大于或等于其位于极小层的父节点的 β 值，即 α  β，则可终止该极大层中节点 m 以下的搜索过程。 β值 α值

30 进一步研究技术： 博弈子树改变排列顺序时，α - β 剪枝可能无计可施。 对弈双方不大可能使用同一个棋局估计函数。
静态评价函数并非绝对可靠。一旦某个节点发生误差，由于无法动态调整误差，则此误差将会通过极大-极小计算原则向上传播，导致决策的失误。 在有界深度搜索的全过程中，将深度固定不尽合理。有时暂时的局部的放弃可能导致全面的重大胜利。 呆板的自下而上的计算估计值方法，难于体现对弈弈手的灵活的作战意图，如声东击西、诱敌深入等。

31 作 业

32 博弈搜索作业： 设局部博弈树如图所示，其中，方格表示‘或’节点属极大层，圆圈表示‘与’节点属极小层，叶节点下面的数字为静态评价函数值 h，请在图上标出： １. 对博弈树进行的必要的α或β剪枝（要求标出剪去的分枝以及剪枝采用的技术类型）； ２. 按极小极大原则计算的非叶节点的函数估计值； 3. 确定1最终走出的棋步。 1 2 3 4 5 6 7 10 11 8 9 30 21 73 91 43