问题求解与博弈
主要内容
• 状态空间
• 搜索技术
• 机器博弈
一些例子
• 搭积木
• 智力游戏：
– 有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到
右岸，但受下列条件限制：
• 船太小，农夫每次只能带一样东西过河
• 没有农夫看管，则狼要吃羊，羊要吃菜
– 请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。
• 下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于
博弈）
状态空间表示法
• 人工智能的多个研究领域从求解现实问
题的过程来看，都可抽象为一个“问题求
解”过程
• 问题求解过程实际上就是一个搜索过程
• 为了进行搜索，首先必须用某种形式把
问题表示出来
• 状态空间表示法就是用来表示问题及其
搜索过程的一种方法
状态空间表示法
• 状态空间表示法是用“状态”和“算子”来表
示问题的一种方法
– 状态：用来描述问题求解过程中不同时刻的
状况
– 算子：表示对状态的操作，算子的每次使用
就使问题由一种状态变换为另一种状态
– 当达到目标状态时，由初始状态到目标状态
所用算子的序列就是问题的一个解
状态空间表示法
• 状态
– 状态是描述问题求解过程中任一时刻状况的数据结构，
一般用一组变量的有序组合表示
– SK(SK0,SK1,…)
– 当给每一分量以确定的值时，就得到一个具体的状态
• 算子
– 引起状态中某些分量发生变化，从而使问题由一个状
态变为另一个状态的操作称为算子。产生式系统中，
每一条产生式规则就是一个算子
• 状态空间
– 由问题的全部状态及一切可用算符所构成的集合称为
问题的状态空间，一般用三元组表示: (S,F,G)
• S: 所有初始状态构成的集合
• F: 算子的集合
• G: 目标状态的集合
例子:Hanoi Tower
• 二阶hanoi tower
– SK=(SK0,SK1)表示问题的状态，SK0 表示盘片A所在
的柱号，SK1 表示盘片B所在的柱号
– 全部可能的状态:
• S0=(1,1), S1=(1,2), S2=(1,3),
• S3=(2,1), S4=(2,2), S5=(2,3),
• S6=(3,1), S7=(3,2), S8=(3,3).
– 问题的初始状态集合S={S0},目标集合为
G={S4,S8}
– 算子分别用A(i,j), B(i,j)表示
• A(i,j):盘片A从柱i移到柱j
• B(i,j):盘片B从柱i移到柱j
– 全部可能的算子：
• A(1,2), A(1,3), A(2,1), A(2,3), A(3,1), A(3,2),
• B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)
状态空间表示法
• 首先必须定义状态的描述形式，通过使用这种描述可把问
题的一切状态都表示出来。其实还要定义一组算子，通过
使用算子可把问题由一种状态转变为另一种状态
• 问题的求解过程就是一个不断把算子作用于状态的过程
• 算子的一次使用，就使问题由一种状态转变为另一种状态。
可能有多个算子序列都可使问题从初始状态变到目标状态，
这就得到了多个解，我们把使用算子最少的解称为最优解
• 对于任何一种状态，可使用的算子可能不止一个，这样由
一个状态所生成的后继状态就可能有多个。当对这些后继
状态使用算子生成更进一步状态时，首先应对哪一状态进
行操作呢？这取决于搜索策略，不同搜索策略的操作顺序
是不相同的。
搜索技术
• 搜索技术是人工智能的基本技术之一, 在人工
智能各应用领域中被广泛地使用。
– 早期的人工智能程序与搜索技术联系就更为紧密，几乎所有
的早期的人工智能程序都是以搜索为基础的。例如，
(艾伦·纽厄尔)和H·A·Simon(西蒙)等人编写的
LT(Logic Theorist)程序, 写的符号积分程序SAINT,
A·Newell和H·A·Simon写的GPS(General Problem Solver)程
序, H·Gelernter(格伦特尔)写的Geometry theorem-proving
machine程序, (菲克斯)和(尼尔逊)写的
STRIPS(Stanford Research Institute Problem Solver)程
序以及(塞缪尔)写的Chechers程序等, 都使用了各种
搜索技术。
– 现在, 搜索技术渗透在各种人工智能系统中, 可以说没有哪一
种人工智能的应用不用搜索方法,在专家系统、自然语言理解、
自动程序设计、模式识别、机器人学、信息检索和博弈都广
泛使用搜技术。
搜索技术
• 搜索问题是AI核心理论问题之一
– 一般一个问题可以用好几种搜索技术解决,
选择一种好的搜索技术对解决问题的效率很
有关系, 甚至关系到求解问题有没有解。
– 搜索方法好的标准, 一般认为有两个：
• (1)搜索空间小;
• (2)解最佳。
搜索技术
• 搜索从问题性质上来看, 可分为一般搜
索和博奕搜索, 从处理方法上来看, 可分
为盲目搜索和启发式搜索。还可以分得
更细。
– 当所给定的问题用状态空间表示时, 则求解
过程可归结为对状态空间的搜索。
– 当问题有解时, 使用不同的搜索策略, 找到
解的搜索空间范围是有区别的。一般来说,
对大空间问题, 搜索策略是要解决组合爆炸
的问题
搜索策略
• 通常搜索策略的主要任务是确定如何选取规
则的方式。有两种基本方式:
– 一种是不考虑给定问题所具有的特定知识, 系统根
据事先确定好的某种固定排序, 依次调用规则或随
机调用规则,这实际上是盲目搜索的方法, 一般统称
为无信息引导的搜索策略。
– 另一种是考虑问题领域可应用的知识, 动态地确定
规则的排序, 优先调用较合适的规则使用, 这就是通
常称为启发式搜索策略或有信息引导的搜索策略。
AI领域的搜索方法
• (1)求任一解路的搜索策略
– 回溯法(Backtracking)
– 爬山法(Hill Climbing)
– 宽度优先法(Breadth-first)
– 深度优先法(Depth-first)
– 限定范围搜索法(Beam Search)
– 最佳优先法(Best-first)
• (2)求最佳解路的搜索策略
– 大英博物馆法(British Museum)
– 分枝界限法(Branch and Bound)
– 动态规划法(Dynamic Programming)
– 最佳图搜索法(A*)
AI领域的搜索方法
• (3)求与或关系解图的搜索法
– 一般与或图搜索法(AO*)
– 极小极大法(Minimax)
– 剪枝法(Alpha-beta Pruning)
– 启发式剪枝法(Heuristic Pruning)
搜索策略分类
盲目搜索方法
• 盲目搜索是不利用问题的有关信息, 而根
据事先确定好的某种固定的搜索方法进
行搜索。
– 典型的盲目搜索方法是深度优先搜索和宽度
优先搜索(亦称广度优先搜索), 这是两处基
本搜索方法
回溯策略
• 例：皇后问题
– 在一个4×4的国际象棋棋盘上,一次一个地
摆布四枚皇后棋子, 摆好后要满足每行、每
列和对象线上只允许出现一枚棋子, 即棋子
间不许相互俘获
( )
( )
Q
((1,1))
( )
Q
Q
((1,1))
((1,1) (2,3))
( )
Q
((1,1))
((1,1) (2,3))
( )
Q
Q
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
( )
Q
Q
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
Q
((1,1) (2,4) ())
( )
Q
Q
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
((1,1) (2,4) ())
( )
Q
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
((1,1) (2,4) ())
( )
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
((1,1) (2,4) ())
( )
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
((1,1) (2,4) ())
Q
((1,2))
( )
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
((1,1) (2,4) ())
Q
((1,2))
Q
((1,2) (2,4))
( )
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
((1,1) (2,4) ())
Q
((1,2))
Q
((1,2) (2,4))
Q
((1,2) (2,4) (3,1))
( )
((1,1))
((1,1) (2,3)) ((1,1) (2,4))
((1,1) (2,4) ())
Q
((1,2))
Q
((1,2) (2,4))
Q
((1,2) (2,4) (3,1))
Q
((1,2) (2,4) (3,1) (4,3))
递归的思想
从前有座山……
从前有座山……
从前有座山……
Fibonacci数列
• 1202年，意大利家斐波那契在提出了一
个关于兔子繁殖的问题：
如果一对兔子每月能生一对小兔（一雄
一雌），而每对小兔在它出生後的第三
个月里，又能开始生一对小兔，假定在
不发生死亡的情況下，由一对出生的小
兔开始，50個月后会有多少对兔子？
• 當n＞1時，Fn+2 = Fn+1 + Fn，而
F0=F1=1。
递归的思想（续）
当前状态
目标状态g
回溯搜索算法
BACKTRACK（DATA）
DATA：当前状态。
返回值：从当前状态到目标状态的路径
（以规则表的形式表示）
或FAIL。
回溯搜索算法
递归过程BACKTRACK(DATA)
1, IF TERM(DATA) RETURN NIL;
2, IF DEADEND(DATA) RETURN FAIL;
3, RULES:=APPRULES(DATA);
4, LOOP: IF NULL(RULES) RETURN FAIL;
5, R:=FIRST(RULES);
6, RULES:=TAIL(RULES);
7, RDATA:=GEN(R, DATA);
8, PATH:=BACKTRACK(RDATA);
9, IF PATH=FAIL GO LOOP;
10, RETURN CONS(R, PATH);
存在问题及解决办法
• 问题：
– 深度问题
– 死循环问题
• 解决办法：
– 对搜索深度加以限制
– 记录从初始状态到当前状态的路径
回溯搜索算法1
BACKTRACK1（DATALIST）
DATALIST：从初始到当前的状态表（逆向）
返回值：从当前状态到目标状态的路径
（以规则表的形式表示）
或FAIL。
回溯搜索算法1
1, DATA:=FIRST(DATALIST)
2, IF MENBER(DATA, TAIL(DATALIST))
RETURN FAIL;
3, IF TERM(DATA) RETURN NIL;
4, IF DEADEND(DATA) RETURN FAIL;
5, IF LENGTH(DATALIST)>BOUND
RETURN FAIL;
6, RULES:=APPRULES(DATA);
7, LOOP: IF NULL(RULES) RETURN FAIL;
8, R:=FIRST(RULES);
回溯搜索算法1（续）
9, RULES:=TAIL(RULES);
10, RDATA:=GEN(R, DATA);
11, RDATALIST:=CONS(RDATA,
DATALIST);
12, PATH:=BACKTRCK1(RDATALIST)
13, IF PATH=FAIL GO LOOP;
14, RETURN CONS(R, PATH);
一些深入的问题
• 失败原因分析、多步回溯
Q
Q
一些深入问题（续）
• 回溯搜索中知识的利用
基本思想：
尽可能选取划去对角线上位置数最少的。
Q Q Q Q
4 3 3 4
图搜索策略
• 问题的引出
– 回溯搜索：只保留从初始状态到当前状态的
一条路径。
– 图搜索：保留所有已经搜索过的路径。
一些基本概念
• 节点深度：
根节点深度=0
其它节点深度=父节点深度+1
0
1
2
3
一些基本概念（续1）
• 路径
设一节点序列为(n0, n1,…,nk)，对于i=1,…,k
，若节点ni-1具有一个后继节点ni，则该序
列称为从n0到nk的路径。
• 路径的耗散值
一条路径的耗散值等于连接这条路径各节
点间所有耗散值的总和。用C(ni, nj)表示从
ni到nj的路径的耗散值。
一些基本概念（续1）
• 扩展一个节点
生成出该节点的所有后继节点，并给出
它们之间的耗散值。这一过程称为“扩展
一个节点”。
图搜索的一般过程
• (1) 建立一个只含有起始节点S的搜索图G，把
S放到一个叫做OPEN的未扩展节点表中（简
称OPEN表）。
• (2) 建立一个叫做CLOSED的已扩展节点表
（简称CLOSED表），其初始为空表。
• (3) LOOP：若OPEN表是空表，则失败退出。
• (4) 选择OPEN表上的第一个节点，把它从
OPEN表移出并放进CLOSED表中。称此节点
为节点n，它是CLOSED表中节点的编号。
• (5) 若n为一目标节点，则有解并成功退出，此
解是追踪图G中沿着指针从n到S这条路径而得
到的(指针将在第7步中设置)。
• (6) 扩展节点n，同时生成不是n的祖先的那些后继
节点的集合M。把M的这些成员作为n的后继节点
添入图G中。
• (7) 对那些未曾在G中出现过的(既未曾在OPEN表
上或CLOSED表上出现过的)M成员设置一个通向n
的指针。把M的这些成员加进OPEN表。对已经在
OPEN或CLOSED表上的每一个M成员，确定是否
需要更改通到n的指针方向。对已在CLOSED表上
的每个M成员，确定是否需要更改图G中通向它的
每个后裔节点的指针方向。
• (8) 按某一任意方式或按某个探试值，重排OPEN
表。
• (9) GO LOOP。
• OPEN表
– 节点
– 父节点
• CLOSED表
– 标号
– 节点
– 父节点
例子
• 例子：从某王姓家族的四代中找王A的后代且
其寿命为X的人。
王A：寿命47，有儿子王B1、王B3、王B2
王B1：寿命77，有儿子王C1、王C2
王B3：寿命52，有儿子王D1
王B2：寿命65，有儿子王E1、王E2
王F1：寿命32
王G1：寿命96
王C2：寿命87，有儿子王F1
王D1：寿命77，没有儿子
王E1：寿命57，有儿子王G1
王E2：寿命92，有儿子王H1
王C1：寿命27，没有儿子
王H1：寿命51
• 若X=57，如何寻找？
无信息图搜索过程
• 深度优先搜索
– (1) 把起始节点S放到未扩展节点OPEN表中。如果
此节点为一目标节点，则得到一个解。
– (2) 如果OPEN为一空表，则失败退出。
– (3) 把第一个节点(节点n)从OPEN表移到CLOSED
表。
– (4) 如果节点n的深度等于最大深度，则转向(2)。
– (5) 扩展节点n，产生其全部后裔，并把它们放入
OPEN表的前头。如果没有后裔，则转向(2)。
– (6) 如果后继节点中有任一个为目标节点，则求得
一个解，成功退出；否则，转向(2)。
无信息图搜索过程
• 宽度优先搜索
– (1) 把起始节点放到OPEN表中(如果该起始节点为
一目标节点，则求得一个解答)。
– (2) 如果OPEN是个空表，则没有解，失败退出；
否则继续。
– (3) 把第一个节点(节点n)从OPEN表移出，并把它
放入CLOSED扩展节点表中。
– (4) 扩展节点n。如果没有后继节点，则转向上述第
(2)步。
– (5) 把n的所有后继节点放到OPEN表的末端，并提
供从这些后继节点回到n的指针。
– (6) 如果n的任一个后继节点是个目标节点，则找到
一个解答，成功退出；否则转向第(2)步
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
7 1 4
6 5
8 3
2 1 4
7 6 5
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
1 2 3
7 8 4
6 5
1 2 3
8 4
7 6 5
2 8 3
6 4
1 7 5
2 8 3
1 6
7 5 4
8 3
2 1 4
7 6 5
2 8 3
7 1 4
6 5
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
1
2
3
4 5
6
7 8
9
a b
c
d
1 2 3
8 4
7 6 5
目标
深度优先搜索的性质
• 一般不能保证找到最优解
• 当深度限制不合理时，可能找不到解，
可以将算法改为可变深度限制
• 最坏情况时，搜索空间等同于穷举
• 与回溯法的差别：图搜索
• 是一个通用的与问题无关的方法
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
7 1 4
6 5
8 3
2 1 4
7 6 5
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
1 2 3
7 8 4
6 5
1 2 3
8 4
7 6 5
1
2
5
6 7
3
1 2 3
8 4
7 6 5
目标
8
2 3 4
1 8
7 6 5
4
宽度优先搜索的性质
• 当问题有解时，一定能找到解
• 当问题为单位耗散值，且问题有解时，
一定能找到最优解
• 方法与问题无关，具有通用性
• 效率较低
• 属于图搜索方法
非启发式搜索
• 按照事先规定的路线进行搜索
– 广度优先搜索是按“层”进行搜索的，先进入
OPEN 表的节点先被考察
– 深度优先搜索是沿着纵深方向进行搜索的，
后进入OPEN表的节点先被考察
• 按已经付出的代价决定下一步要搜索的
节点
– 代价树的广度优先
– 代价树的深度优先
启发式图搜索
• 利用知识来引导搜索，达到减少搜索范围，降
低问题复杂度的目的。
• 启发性信息
– 用于指导搜索过程，且与具体问题求解有关的控制
性信息称为启发性信息
• 启发信息的强度
– 强：降低搜索工作量，但可能导致找不到最
优解
– 弱：一般导致工作量加大，极限情况下变为
盲目搜索，但可能可以找到最优解
希望：
• 引入启发知识，在保证找到最佳解的情
况下，尽可能减少搜索范围，提高搜索
效率。
基本思想
• 定义一个评价函数f，对当前的搜索状态
进行评估，找出一个最有希望的节点来
扩展。
1，启发式搜索算法A（A算法）
• 评价函数的格式：
f(n) = g(n) + h(n)
f(n)：评价函数
g(n): 实际已经付出的代价函数
h(n)：启发函数
符号的意义
• g*(n)：从s到n的最短路径的耗散值
• h*(n)：从n到g的最短路径的耗散值
• f*(n)=g*(n)+h*(n)：从s经过n到g的最短路
径的耗散值
• g(n)、h(n)、f(n)分别是g*(n)、h*(n)、
f*(n)的估计值
一个A算法的例子
定义评价函数：
f(n) = g(n) + h(n)
g(n)为从初始节点到当前节点的耗散值
h(n)为当前节点“不在位”的将牌数
2 8 3
1 6 4
7 5
1 2 3
8 4
7 6 5
h计算举例
h(n) =4
2 8 3
1 6 4
7 5
1 2 3
4
5
7 6
8
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
7 1 4
6 5
8 3
2 1 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
7 8 4
6 5
s(4)
A(6) B(4) C(6)
D(5) E(5) F(6)
G(6) H(7)
I(5) J(7)
K(5)
L(5) M(7)
目标
1
2
3 4
5
6
最佳图搜索算法A*（A*算法）
• 在A算法中，如果满足条件：
h(n)≤h*(n)
则A算法称为A*算法。
A*条件举例
• 8数码问题
– h(n) = “不在位”的将牌数
– h(n) = 将牌“不在位”的距离和
2 8 3
1 6 4
7 5
1 2 3
4
5
7 6
8
将牌1：1
将牌2：1
将牌6：1
将牌8：2
A*算法的性质
定理1：
对有限图，如果从初始节点s到目标节点
t有路径存在，则算法A一定成功结束。
问题
• 图搜索是针对什么知识表示方法的问题求解方
法？
• 什么是图搜索? 其中，重排OPEN表意味着什
么，重排的原则是什么?
• 宽度优先搜索方法中OPEN表需要按什么方式
进行操作
– A．先进后出 B．先进先出
• 有界深度优先搜索方法能够保证在搜索树中找
到一条通向目标节点的最短途径吗？
• 试比较各种盲目搜索搜索方法的效率，找出影
响算法效率的原因
• 试比较宽度优先搜索、有界深度优先搜索及有
序搜索的搜索效率，并以实例数据加以说明
启发式搜索的必要性
• 现实的困难迫使人们转而求援于启发式算法。
这种算法的本质是部分地放弃算法“一般化, 通
用化”的概念, 把所要解的问题的具体领域 的
知识加进算法中去, 以提高算法的效率。
– 如, 广度优先法几乎可以用于解一切搜索问题：九
宫图(八数码难题), hanoi塔(焚塔问题), 旅行推销员,
华容道, 以至魔方等等。但实际使用时, 效率也许低
得惊人, 甚至根本解不出来(例如魔方问题)。
– 如果我们为每类问题找出一些特殊规则, 和广度优
先法配合起来使用, 那结果就可能完全不一样了。
启发式搜索的必要性
• 根据启发信息, 在生成各种搜索树时可以考虑种
种可能的选择, 如:
– 1. 下一步展开哪个节点?
– 2. 是部分展开还是完全展开?
– 3. 使用哪个规则(或算子)?
– 4. 怎样决定舍弃还是保留新生成的节点?
– 5. 怎样决定舍弃还是保留一棵子树?
– 6. 怎样决定停止或继续搜索?
– 7. 如何定义启发函数(评价函数)?
– 8. 如何决定搜索方向?
– ……
由于这些选择的不同, 就得到了不同的启发式算
法
*解路径如粗线所标左、上、
右、下
**S、A、B、…、L、M等为
状态空间图中各个节点名,
其后的小括号中数字表示该
节点的评价函数f(n)的估计
值, 例如S(4)、L(5)等。
*** 图中标记"▲"节点为
被扩的节点, 标记"■"的节
点为生成的节点。
九宫重排问题
搜索效率比较
启发式搜索策略
• 人工智能问题求解者在两种基本情况下运用
启发式策略:
–一个问题由于在问题陈述和数据获取方面固有的模
糊性可能使它没有一个确定的解。医疗诊断即是一
例。所给出的一系列症状可能有多个原因, 医生运
用启发式搜索来选择最有可能的论断并依此产生治
疗计划。
–一个问题可能有确定解, 但是求解过程中的计算机
代价令人难以接受。在很多问题(如国际象棋)中,
状态空间的增长特别快, 可能的状态数随着搜索的
深度呈指数级增长、分解。在这种情况下, 穷尽式
搜索策略诸如深度优先或广度优先搜索, 在一个给
定的较实际的时空内很可能得不到最终的解
• 和发明创造的所有规则一样, 启发式策略也是
极易出错的
图搜索策略
• 图搜索策略的定义
– 图搜索策略可看作一种在图中寻找路径的方法。初
始节点和目标节点分别代表初始数据库和满足终止
条件的数据库。求得把一个数据库变换为另一数据
库的规则序列问题就等价于求得图中的一条路径问
题。研究图搜索的一般策略，能够给出图搜索过程
的一般步骤。
• 图搜索算法中的几个重要名词术语
– （1）OPEN表与CLOSE表
– （2）搜索图与搜索树
你可曾听说过“深蓝”？
1997年5月11日，IBM开发的“深蓝”
击败了国际象棋冠军卡斯帕罗夫。
•1980年他获得世界少年组冠军
•1982年他并列夺得苏联冠军
•1985年22岁的卡斯帕罗夫成为历史上最年轻的国
际象棋冠军
•积分是2849，这一分数是有史以来最高分。
远远领先于第二位的克拉姆尼克的2770
卡氏何许人也？
电脑棋手：永不停歇的挑战！
• 1988年“深思”击败了丹麦特级
大师拉森。
• 1993年“深思”第二代击败了丹
麦世界优秀女棋手小波尔加。
电脑棋手：永不停歇的挑战！
• 2001年“更弗里茨” 击败了除了
克拉姆尼克之外的所有排名世界前
十位的棋手。
• 2002年10月“更弗里茨”与世界棋
王克拉姆尼克在巴林交手，双方以
4比4战平。
• 2003年1至2月“更年少者”与卡斯
帕罗夫在纽约较量，3比3战平。
许多人在努力
机器博弈
• 20世纪50年代，有人设想利用机器智能来实现机器与
人的对弈。
• 1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕
罗夫，惊动了世界。
• 加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳
棋程序Chinook也相继成为确定的、二人、零和、完
备信息游戏世界冠军
• 西洋双陆棋这样的存在非确定因素的棋类也有了美国
卡内基梅隆大学的西洋双陆琪程序BKG这样的世界冠
军。
• 对围棋、中国象棋、桥牌、扑克等许多种其它种类游
戏博弈的研究也正在进行中。
机器博弈的基本思想
• 机器博弈的核心思想就是对博弈树节点
的估值过程和对博弈树搜索过程的结合
博弈树
• 在博弈的任何一个中间阶段，站在博弈
双方其中一方的立场上，可以构想一个
博弈树。这个博弈树的根节点是当前时
刻的棋局，它的儿子节点是假设再行棋
一步以后的各种棋局，孙子节点是从儿
子节点的棋局再行棋一步的各种棋局，
以此类推，构造整棵博弈树，直到可以
分出胜负的棋局。
机器博弈系统的构成
• 知识表示
• 规则集，产生机制，构建博弈树
• 搜索技术
• 估值技术
博弈搜索
• 博弈搜索的基本思想已经提出半个多世纪，目前广泛
研究的是确定的、二人、零和、完备信息的博弈搜索。
– 没有随机因素的博弈在两个人之间进行，在任何一个时刻，
一方失去的利益即为另一方得到的利益，不会出现“双赢”的
局面，而且在任何时刻，博弈的双方都明确的知道每一个棋
子是否存在和存在于哪里。
• 二人、零和、完备信息的博弈搜索理论已经很系统。
极大极小算法是所有搜索算法的基础。
– 一类是作为主流的深度优先的alpha-beta搜索及其系列增强
算法
– 另一类是最佳优先的系列算法。
解谜：电脑是怎样下棋的
——人机博弈程序的一般设计方法
以中国 棋为例
（1）第一步该做什么？
数据结构的选取——棋盘表示
占用空间-〉少
操作速度-〉快
是否方便-〉方便
在机器中表示棋局，让程序知道
博弈状态。
九
列
十
行
十
四
种
不
同
的
棋
子
三
十
二
个
棋
子
几种棋盘表示的方式
• 二维数组——直观
• 紧凑的数据结构——省空间，不直
观，速度?
• 比特棋盘——用于8*8棋盘（国际象
棋），64位主机
（2）接下来怎么办？
• 产生合法走步的规则，使博弈能公正
的进行，并且能够判断对手是否乱走。
依赖于具体棋类特征。
• 是一段将局面所有可能的正确走法罗
列出来的程序。称之为走法产生。
几种走法产生的实现方式
• 一般做法
• 建立小型数据库
• 位运算
位运算走法产生之例
寻
找
象
的
可
走
步
位运算走法产生之要求
• 一个基于比特棋盘的完善的数据库
• 该数据库应位于内存中
（3）终于到核心了
•从所有的走法中找出最佳的走法，
也就是——
搜索
博弈概述
• 诸如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。
博弈有很多种，我们讨论最简单的"二人零和、全信息、非偶然"
博弈，其特征如下：
(1) 对垒的MAX、MIN双方轮流采取行动，博弈的结果只有
三种情况：MAX方胜，MIN方败；MIN方胜，MAX方败；和局。
(2) 在对垒过程中，任何一方都了解当前的格局及过去的历
史。
(3) 任何一方在采取行动前都要根据当前的实际情况，进行
得失分析，选取对自已为最有利而对对方最为不利的对策，不存
在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的
行动。
博弈概述
• 在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方
当前有多个行动方案可供选择时，他总是挑选对自己最为有利而
对对方最为不利的那个行动方案。此时，如果我们站在MAX方
的立场上，则可供MAX方选择的若干行动方案之间是"或"关系，
因为主动权操在MAX方手里，他或者选择这个行动方案，或者
选择另一个行动方案，完全由MAX方自已决定。当MAX方选取
任一方案走了一步后，MIN方也有若干个可供选择的行动方案，
此时这些行动方案对MAX方来说它们之间则是"与"关系，因为这
时主动权操在MIN方手里，这些可供选择的行动方案中的任何一
个都可能被MIN方选中，MAX方必须应付每一种情况的发生。
博弈概述
• 这样，如果站在某一方(如MAX方，即MAX要取胜)，把上述博
弈过程用图表示出来，则得到的是一棵"与或树"。描述博弈过程
的与或树称为博弈树，它有如下特点：
(1) 博弈的初始格局是初始节点。
(2) 在博弈树中，"或"节点和"与"节点是逐层交替出现的。
自己一方扩展的节点之间是"或"关系，对方扩展的节点之间是"
与"关系。双方轮流地扩展节点。
(3) 所有自己一方获胜的终局都是本原问题，相应的节点是
可解节点；所有使对方获胜的终局都认为是不可解节点。
我们假定MAX先走，处于奇数深度级的节点都对应下一步
由MAX走，这些节点称为MAX节点，相应地偶数级为MIN节点。
搜索算法
• 极大极小值算法
• 负极大值搜索
• 深度优先的 alpha-beta搜索
– 渴望搜索（Aspiration Search）
– 极小窗口搜索（Minimal Window Search）
– 遍历深化（Iterative Deepening）
– 历史启发搜索（History Heuristic）
– 杀手启发搜索(Killer Heuristic)
– MTD(f)算法 （Memory –enhanced Test Driver with f and n ）
极大极小法
• 基本思想或算法是：
(1) 设博弈的双方中一方为MAX，另一方为MIN。
然后为其中的一方(例如MAX)寻找一个最优行动方案。
(2) 为了找到当前的最优行动方案，需要对各个
可能的方案所产生的后果进行比较,具体地说，就是要
考虑每一方案实施后对方可能采取的所有行动，并计
算可能的得分。
(3) 为计算得分，需要根据问题的特性信息定义
一个估价函数，用来估算当前博弈树端节点的得分。
此时估算出来的得分称为静态估值。
极大极小法（续）
• (4) 当端节点的估值计算出来后，再推算出父
节点的得分，推算的方法是：对“或”节点，选
其子节点中一个最大的得分作为父节点的得分，
这是为了使自己在可供选择的方案中选一个对
自己最有利的方案；对“与”节点，选其子节点
中一个最小的得分作为父节点的得分，这是为
了立足于最坏的情况。这样计算出的父节点的
得分称为倒推值。
• (5) 如果一个行动方案能获得较大的倒推值，
则它就是当前最好的行动方案。
一字棋游戏极小极大分析法
• 设有九个空格，由MAX，MIN二人对弈，
轮到谁走棋谁就往空格上放一只自己的
棋子，谁先使自己的棋子构成“三子成一
线”(同一行或列或对角线全是某人的棋
子)，谁就取得了胜利。
• 用叉号表示MAX，用圆圈代表MIN。
一字棋游戏极小极大分析法
• 为了不致于生成太大的博弈树，假设每次仅扩
展两层。估价函数定义如下
– 设棋局为P，估价函数为e(P)
– (1) 若P对任何一方来说都不是获胜的位置，则
e(P)=e(那些仍为MAX空着的完全的行、列或对角
线的总数)-e(那些仍为MIN空着的完全的行、列或
对角线的总数)
– (2) 若P是MAX必胜的棋局，则e(P)＝+∞。
– (3) 若P是B必胜的棋局，则e(P)＝-∞。
一字棋极大极小法的第一阶段
一字棋极大极小法的第二阶段
一字棋极大极小法的第三阶段
Alpha-Beta剪枝技术
• 基本思想或算法是，边生成博弈树边计
算评估各节点的倒推值，并且根据评估
出的倒推值范围，及时停止扩展那些已
无必要再扩展的子节点，即相当于剪去
了博弈树上的一些分枝，从而节约了机
器开销，提高了搜索效率。
Alpha-Beta剪枝技术
• (1) 对于一个与节点MIN，若能估计出其倒推值的上
确界β，并且这个β值不大于 MIN的父节点(一定是或
节点)的估计倒推值的下确界α，即α≥β，则就不必再扩
展该 MIN节点的其余子节点了(因为这些节点的估值
对MIN父节点的倒推值已无任何影响 了)。这一过程
称为α剪枝。
• (2) 对于一个或节点MAX，若能估计出其倒推值的下
确界α，并且这个α值不小于 MAX的父节点(一定是与
节点)的估计倒推值的上确界β，即α≥β，则就不必再扩
展该MAX节点的其余子节点了(因为这些节点的估值
对MAX父节点的倒推值已无任何影响 了)。这一过程
称为β剪枝。
搜索算法
• 最佳优先算法
– SSS*和DUAL*算法
– B*和PB*算法
Alpha-Beta剪枝
Alpha-Beta搜索
和极大极小搜索结合
在奇数层进行Alpha剪枝，偶数层
Beta剪枝。
和负极大值搜索结合
在每一层都进行Beta剪枝。
（4）最后
• 评估局面优劣，配合搜索技术做出
智能的选择——估值技术
棋子价值评估
SideValue=Sum(piecenumber*piecevalue)
棋子灵活性
Mobility=Sum(movenumber*movevalue)
棋盘控制
棋子关系的评估（威胁、保护、形、定势。
并且要考虑到谁走棋）
估值的几种形式
• 终点估值
思路清晰，容易设计，模块独立性高，
同搜索算法耦合程度低
速度慢
•棋子价值表
T[pieceType][boardWidth][boardHeight]
•二者结合
•动态棋子价值表
估值函数的内容及其调试
• Score=aX+bY+cZ+dK+……
• X=车+马+炮+……
参数确定的方法
• 手工调整
• 爬山法
• 蒙特卡罗
• 模拟退火
• 遗传算法
爬山法的缺陷——初值依赖
蒙特卡罗
• 使用多种初始参数，从不同的地方
开始多次爬山
• 有足够多次的爬山，出现频率最高
的结果是最优解的概率就会足够大
• 不同初值的大量采样，使运算效率
低
模拟退火
• MetroPolis重要性采样的基本思
想：在寻优的开始使用较高的概
率进行随机突跳，随着寻优过程
的深入逐步降低这一接受不佳参
数概率。并且随着搜索的深入，
可接受的参数的不佳程度也越来
越小。
模拟退火
• 一次对参数改变一点，测试。
• 提高，保留
• 不提高，在一定概率上继续
• 由粗到细，逼近最优参数
遗传算法
• 随机产生一组初始个体构成初始种群，并
评价每一个体的适配值。
• 判断算法收敛准则是否满足，若满足则输
出搜索结果，否则执行以下步骤。
• 根据适配值大小以一定方式执行复制操作。
• 按交叉概率pc之行交叉操作。
• 按变异概率pm执行变异操作。
• 返回上面第二步骤。
遗传算法
• 适配值：对个体进行评价的指标，算法优
化的主要信息，与个体的目标值对应
• 复制：复制概率正比于适配值
• 交叉：交换父代个体中的部分信息产生后
代，继承
• 变异：随机改变个体中的某些信息产生新
个体，增加种群多样性
标
准
遗
传
算
法
优
化
框
图
Genetic Algorithms 优越性
• 全空间并行搜索，重点集中在高
性能部分，防止陷入局部最优
孰优孰劣？
• 名局测试
• 和其他博弈程序对弈
• 选不同的参数，自相对弈
• 同向下几层的搜索结果比较
启发式搜索的一个例子
• 井字博弈中，博弈者在3X3数组中轮流
标记，一个标记X，一个标记O ,先用标
记填满一行、一列或一条对角线者便赢
得博弈。初始状态为空棋盘，从起点到
终点的路径表明了赢棋的走法。
启发式搜索的一个例子
• 一个简单的启发式策略几乎可以整个地
消除复杂的搜索过程。假设我方为“X”,
首先, 将棋子走到棋盘上×有最多的赢线
的点
启发式搜索的一个例子
• 启发信息：将棋子走到棋盘上×有最多的
赢线的点
衡量一个搜索策略性能的
准则
• 完备性
– 只要问题有解，在搜索策略的控制下就一定
能找到这个（些）解
• 尽量避免无用搜索
– 增强搜索的目的性，尽量避免产生及考察那
些无用的节点
• 控制开销小
– 要求搜索策略实现简单，选择及调度可用知
识的开销尽可能小
问题
• 什么是搜索？有哪两大类不同的搜索方法？两
者的区别是什么？
• 广度优先搜索和深度优先搜索有和区别？在何
种情况下广度优先搜索优于深度优先搜索？在
何种情况下深度优先搜索优于广度优先搜索？
• 试谈机器博弈的基本思想。
