搜索(博弈树的启发式搜索)-课件·PPT

正在与深蓝下棋的卡斯帕罗夫
1.概述
博弈问题特点： 双人对弈，轮流走步。 信息完备，双方所得到的信息是一样的。 零和，即对一方有利的棋，对另一方肯定 是不利的，不存在对双方均有利或无利的 棋。
1.概述
博弈的特性 ① 两个棋手交替地走棋 ； ② 比赛的最终结果，是赢、输和平局中的
一种； ③ 可用图搜索技术进行，但效率很低； ④ 博弈的过程，是寻找置对手于必败态的
若P是MAX获胜的格局，则f(p)=+∞ ； 若P是MIN获胜的格局，则f(p)＝-∞ 。
3.极小极大搜索过程
当前棋局f(p)=2
估计函数 f(p)=(所有空格都放上MAX的棋子之后，MAX的三子 成线(行、列、对角)数)－(所有空格都放上MIN的棋子之后， MIN的三子成线(行、列、对角)的总数)
MAX节点和MIN节点
命名博弈的双方，一方为“正方”，对每 个状态的评估都是对应于该方的输赢的。 例如，赢2个，输1个等，都是指正方的。 正方每走一步，都在选择使自己赢得更多 的节点，因此这类节点称为“MAX”节点；
3Байду номын сангаас极小极大搜索过程
另一方为“反方”，对每个状态的评估 都是对应于对手的输赢的。例如，赢2个， 输一个，其实是指自己输2个，赢1个的。 反方每走一步，都在选择使对手输得更 多的节点，因此这类节点称为“MIN”节 点。
对各个局面进行评估
评估的目的：对后面的状态提前进行考虑，并 且以各种状态的评估值为基础作出最好的走棋 选择。
评估的方法：用评价函数对棋局进行评估。赢 的评估值设为+∞，输的评估值设为-∞，平局 的评估值设为0。
评估的标准：由于下棋的双方是对立的，只能 选择其中一方为评估的标准方。

f(x)=g(x)+h(x)
其中：g(x)——从初始节点S0到节点x的实际代价； h(x)——从x到目标节点Sg的最优路径的评估代价，它体现了问
题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式 函数。
2022/10/14
6
评估函数
启发式方法把问题状态的描述转换 成了对问题解决程度的描述。
这一程度用评估函数的值来表示。
2022/10/14
7
评估函数
S
搜索图G
2022/10/14
n ng
初始状态节点S
f(n):s-n-ng的估计最小路径代价
g(n):s-n的实际路径代价 h(n): n-ng的估计最小路径代价
节点n
目标状态节点ng
8
启发式搜索A算法
A算法的设计与一般图搜索相同，划分为二个阶段：
IF f(ni)>f(n,ni) THEN 令f(ni)=f(n,ni)
修改指针指向新父结点n
排序OPEN表（f(n)值从小到大排序）
2022/10/14
10
2022/10/14
4功指1搜 未做.若.退针建扩C索nL出从立为展图O，n一S一节到GE个此,目的把点S只这解标已S表放条包是扩节中路到含追展点；径一节起踪，建而个点始图则立得叫表节G有一到中O，点解P个的沿其ES成N叫；的初着的
始为空表；
5.扩展节点n，同时生成不是n的 祖 M2出的.先若；这的OP些那EN成些表员子是作节空为点表n，的的则集后失合继败节M,退点把 添入搜索图G中；对于M中每个 子3把 表.节选中它点f择(，从nnO,称nOi,P计iP)E此EN=算N表节g表:(n上点移,n为的出i) +节并第h放点一(n进in)个；C节LO点SE，

(5) If 栈为空并且 c, Then cc , 并返回2
End
.
25
迭代加深A*算法
上述算法涉及了两个深度限制:
(1)如果栈中所含节点的所有子节点的f值小于 限制值c,则把这些子节点压如栈中以满足迭代 加深算法的深度优先准则.
(2)如果不这样,即节点n的一个或多个子节点 n 的f值大于限制值c,则节点n的 c 值设置为 micn,f((n))
节点的最佳路径的总代价的估值。
.
16
A*算法
把估价函数f (n)和 f *(n)相比较：
g (n)是对 g*(n)的估计。 h (n)是对h* (n)的估计。
在这两个估计中，尽管g (n)容易计算，但它不 一定就是从起始节点S0到节点n 的真正的最短 路径的代价，很可能从初始节点S0到节点n 的 真正最短路径还没有找到，所以一般都有：
该算法终止的条件为:
(1)找到目标节点(成功结束); (2)栈为空并且限制值 c 。
.
26
迭代加深A*算法
IDA*算法和A*算法相比，主要优点是对于内存 的需求。A*算法需要指数级数量的存储空间，因 为没有深度方面的限制。而IDA*算法只有当节点 n的所有子节点 的 n 小f (于n)限制值c时才扩展 它,这样就可以节省大量的内存。
点 x 是从初始节点经过m步得到，则g (x) 应该和 m 成正比（或者就是m）。 如何计算h(x)呢? h (x) 只是一个预测值。
.
3
图搜索算法（A算法）(P78:算法3.8)
Procedure Graph-Search
Begin 建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表；计算f(S0)=g(S0)+h(S0); 假定初始时CLOSED表为空。 While OPEN 表不空 do Begin 从OPEN表中取出f值最小的节点(第一节点),并放入CLOSED表中.假设该节点 的编号为n。 If n是目标,则停止;返回n,并根据n的反向指针指出的从初始节点到n的路径。 Else do

s k0 = 2 s k0 = 3 s k0 = 1 s k0 = 3 s k0 = 1 s k0 = 2 s k1 = 2 s k1 = 3 s k1 = 1 s k1 = 3 s k1 = 1 s k1 = 2
17
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
➢ 7.1.2 状态图表示法
P
P1
P2
P3
27
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
3) “与/或〞树：
上述两种方法也可结合起来使用,此时的图称为“与/或 〞树。其中既有“与〞节点,又有“或〞节点。
注意：状态图是与/或图的特殊形式,即与/或图中既有与关系 又有或关系,而状态图只有或关系。
描述； 2) 叶节点：无子节点的节点,亦称端节点； 3) 终止节点：有解的叶节点,对应本原问题。即终止节点一定
是端节点,但端节点不一定是终止节点。
29
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
4) 可解节点：满足以下条件之一者： 它是一个终止节点。 它是一个“或〞节点,且其子节点中至少有一个是可解节点。 ③它是一个“与〞节点,且其子节点全部是可解节点。 5) 不可解节点：关于可解节点的三个条件全部不满足的节点
其中：a表示q1的变化, b表示q2的变化, c表示q3的变化。
9
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
➢ 7.1.2 状态图表示法
把这种描述得到的有向图称为状态〔空间〕图。
其中的节点代表一种格局〔或称为状态〕,而两节 点之间的连线表示两节点之间的联系,它可视为某种操 作、规则、变换等。

2， 1， 0
[S3，S2，S1，S0]
。。 。。 。。。 。。。
5.3.3 深度优先搜索策略
深度优先搜索：首先扩展最新产生的节点，深度相等的节 点可以任意排列的搜索方法。（用堆栈的数据结构）
特点：搜索沿着状态空间的某单一路径沿着起始点向下进
行下去，仅当搜索到达一个没有后裔的状态时，才选择另 S0 一条替代路径。 1 10
5.3
盲目的图搜索策略
5.4 启发式图搜索策略 5.5 与/或图搜索策略
5.3 盲目的图搜索策略
5.3.1 回溯策略
5.3.2 宽度优先搜索策略
5.3.3 深度优先搜索策略
5.3.1 回溯策略
带回溯策略的搜索：（走不通就回头） 从初始状态出发，不停地、试探性地寻找路径， 直到它到达目的或“不可解结点”，即“死胡同” 为止。 若它遇到不可解结点就回溯到路径中最近的父结 点上，查看该结点是否还有其他的子结点未被扩展 。 若有，则沿这些子结点继续搜索；如果找到目标，
(3) NSS（no solvable states）表：不可解状态集，列出 了找不到解题路径的状态。如果在搜索中扩展出的 状态是它的元素，则可立即将之排除，不必沿该状 态继续搜索。
1 A B 2 5.3.1 回溯策略
8 C 11 D
E 3 回溯搜索示意图的回溯轨迹： 10 H 6 F 9 G 初值：PS=[A]； NPS=[A]； NSS=[ ]； CS=A。 J 5 7 K
5.1.2 搜索策略
3.人工智能的主要搜索策略： 求最佳解的搜索策略： 大英博物馆法（British museum）； 宽度优先法（Breadth-first search）； 分支界定法（Branch and Bound）； 最佳图搜索法（A*）； 动态规划法（Dynamic Programing）；

4
fn
n
…
hn
…
11
gn
33
定义一个评价函数 f
3.4.2 局部择优搜索
• 基本思想 ： 当一个节点扩展后, 在它的所有子
节点中，选估价函数f(n)最优者作为下一 个考察的节点 。
• 例1 ：用局部择优搜索策略求解八数码问题。
估价函数定义为f(n)= g（n）+h(n) 。 其中， g（n）=d(n)表示搜索depth,等代价时, g（n）对局
在OPEN表中保留所有已生成而未扩展的节点，并 用估价函数f(n)对它们全部进行估计，and sort!
❖ 得到的不一定是实际上的最佳解。
Answer: Design proper f(n). otherwise
QuestionS：
① how many h(w) of the states are ？
3.4 启发式搜索策略
➢ 启发信息和估价函数
➢ A*算法
Background
and Questions:
1. 宽度优先、深度优先搜 索属于盲目搜索（按规 定的路线搜索）。盲目 搜索效率低，耗费过多 的计算空间与时间。
2. 2. 若选择最有希望的节
点加以扩展(NOT按规定
的路线盲目搜索) ，则搜
索效率将会大为提高。
28 3
16 4
7
5
c)
W(n)=4 steps=5
2
3
18 4
76 5
b)
W(n)=3 steps=3
1 23 84
76 5
a)
31
W(n)=1 steps=1
Compare global and local
h(n)＝W(n)

❖ 为了保证找到解，应选择合适的深度限制值，或采取不断加 大深度限制值的办法，反复搜索，直到找到解。
❖ 与宽度优先搜索根本的不同点：将扩展的后继节点放在 OPEN表的最前端。
5.3.3 深度优先搜索策略
▪ 例3 卒子穿阵问题，要求一卒子从顶部通过下图所
示的阵列到达底部。卒子行进中不可进入到代表敌
兵驻守的区域（标注1），并不准后退。假定深度
（状态）
（操作算子）
状态空间的有向图描述
第5章 搜索求解策略 ▪ 5.1 搜索的概念 ▪ 5.2 状态空间知识表示方法
✓5.3 盲目的图搜索策略
▪ 5.4 启发式图搜索策略 ▪ 5.5 与/或图搜索策略
5.3 盲目的图搜索策略 5.3.1 回溯策略 5.3.2 宽度优先搜索策略 5.3.3 深度优先搜索策略
特点：逐层搜索；高价搜索：若解存在，必能找到。
5.3.2 宽度优先搜索策略
▪ 例2 通过搬动积木块，希望从初始状态达到一个目 的状态，即三块积木堆叠在一起。
A BC
(a) 初始状态
积木问题
A B C
(b) 目的状态
5.3.2 宽度优先搜索策略
▪ 操作算子为MOVE（X，Y）：把积木X搬到Y（积 木或桌面）上面。MOVE（A，Table）：“搬动积木A到桌
G ：若干具体状态或满足某些性质的路径信息描述。
5.2.1 状态空间表示法 ▪ 求解路径：从S0结点到G结点的路径。
状态空间的一个解：一个有限的操作算子序列。
S0 O1S1 O2 S2 O3Ok G
O1,,Ok ：状态空间的一个解。
❖ 例如下棋、迷宫及各种游戏。
5.2.1 状态空间表示法 ▪ 例1 三数码问题（3 puzzle problem）。

在路径规划中，博弈与搜索的结合应用可以帮助机器人或自动驾驶车辆在复杂的环境中寻找最优路径。通过使用博弈论和搜索 算法，机器人或车辆可以评估不同路径的优劣，并根据实际情况选择最佳路径。这有助于提高机器人或车辆的导航精度和效率 。
机器学习中的博弈与搜索
在机器学习中，博弈与搜索的结合应用可以帮助算法在处理大 规模数据时更加高效。通过使用博弈论和搜索算法，机器学习 模型可以快速地找到最优解或近似最优解。这有助于提高机器 学习模型的性能和效率，使其在处理大规模数据时更加可靠和 高效。
广度优先搜索
按照广度优先的顺序搜索 状态空间，先搜索离起始 状态近的状态，再逐步向 外扩展，直到达到目标状 态或无法再扩展为止。
启发式搜索
使用启发式函数指导搜索 ，通过评估状态的好坏来 决定搜索的方向，常见的 启发式搜索包括A*搜索和 Dijkstra算法。
混合搜索
结合深度优先搜索和广度 优先搜索的优点，根据问 题的特性和具体情况选择 合适的搜索策略，以提高 搜索效率。
03
搜索算法概述
搜索算法的基本概念
搜索算法是解决优化问题的基本方法，通过搜索算法可以找到问题的最优解或近似 最优解。
搜索算法的基本概念包括问题表示、状态空间、搜索空间、目标状态和最优解等。
搜索算法的分类包括深度优先搜索、广度优先搜索、启发式搜索和混合搜索等。
搜索算法的分类
深度优先搜索
按照深度优先的顺序搜索 状态空间，尽可能深地搜 索，直到达到目标状态或 无法再深入为止。
详细描述
广度优先搜索从起始节点开始，先搜索离起始节点最近的节点，再逐步向外扩展，直到找到目标节点 或搜索完所有可达节点。该算法按照层次顺序访问节点，先访问离起始节点最近的节点，再逐步向外 扩展。

若P对MAX、MIN都是胜负未定局， 则 e（P）= e（+P）－e（-P） 其中，e（+P）表示棋局 P上有可能使 × 成三子一线的数目；e（-P）表示棋 局 P上有可能使 ○成三子一线的数目。
14
一字棋棋盘
例如，对图1所示的棋局有估价函数值 e（P）＝6-4＝2 在搜索过程中，具有对称性的棋局认为是同一棋 局。例如，图2所示的棋局可以认为是同一个棋局， 这样可以大大减少搜索空间。图3给出了第一着走棋 以后生成的博弈树。图中叶节点下面的数字是该节点 的静态估值，非叶节点旁边的数字是计算出的倒推值。 从图中可以看出，对MAX来说S2是一着最好的走棋， 它具有较大的倒推值。
人下棋的思考方式
人下棋实际上采用一种试探性的方法: 假定走了一步棋,看对方会有哪些应法; 再根据对方的每一种应法,看我方是否有好的回应; 这一过程一直进行下去,直到若干步后,找到一个满意的走法 为止. 极大极小搜索方法模拟的就是人的这样一种思维过程.
节点A,轮到MAX下棋….
MAX
2.非叶子节点的估值由倒推取值的方法取得


博弈是一类富有智能行为的竞争活动，如下棋
、打牌、战争等。博弈可分为双人完备信息博 弈和机遇性博弈。所谓双人完备信息博弈，就 是两位选手对垒，轮流走步，每一方不仅知道 对方已经走过的棋步，而且还能估计出对方未 来的走步。对弈的结果是一方赢，另一方输； 或者双方和局。这类博弈的实例有象棋、围棋 等。所谓机遇性博弈，是指存在不可预测性的 博弈，例如掷币等。对机遇性博弈，由于不具 备完备信息，因此我们不作讨论。
算法框架 整个算法分为四个步骤： 1、以当前状态为根结点产生一个博弈树。 2、对博弈树的每一个叶结点，利用判定函数给出它的判定值。 3、从叶结点开始，一层一层地回溯。在回溯过程中，利用最大/最小判定为每一个结 点给出其判定值。 4、MAX方选择下一层中判定值最大的结点，作为它的下一状态。

极小极大过程
0
1 1
极大
极小
6
0
3
1
0
-3
3
-3
-3
-2
1
-3
6
-3
0
5
-3
3
3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
一字棋游戏
设有一个三行三列的棋盘，两个棋手轮流走步，每 个棋手走时往空格上摆一个自己的棋子，谁先使自己 的棋子成三子一线为赢。设程序方MAX的棋子用（×） 表示，对手MIN的棋子用（○）表示，MAX先走。静态 估计函数f（p）规定如下： 1. 若 P是 MAX的必胜局， 则 e(P) = +∞ ； 2. 若 P是 MIN的必胜局， 则 e(P) = -∞ ； 3. 若P对MAX、MIN都是胜负未定局，则 e(P) = e(+P)－e(-P) 其中，e(+P)表示棋局 P上有可能使× 成三子一线的 数目；e(-P)表示棋局 P上有可能使 ○成三子一线的 数目。
中国象棋

一盘棋平均走50步，总状态数约为10的161次方。 假设1毫微秒走一步，约需10的145次方年。 结论：不可能穷举。
博弈树是与/或树

双方都希望自己能够获胜。因此，当任何一方走步时， 都是试图选择对自己最为有利，而对另一方最为不利的 每一步，可供自己选择 的行动方案之间是“或”的关系，原因在于选择哪个方案完 全是由自己决定的；而可供MIN选择的行动方案之间则是 “与”的关系，原因是主动权掌握在MIN手里，任何一个方

α-β
α值为MAX节点（“或”节点）倒推值的下确界