人工智能：5.4    博弈树搜索

 

5.4.1        
博弈树搜索的概念

博弈一向被认为是富有智能行为的游戏 ， 因而很早就受到人工智能界的重视，早在 20
世纪 60 年代就已经出现若干 博弈 程序，并达到一定水平。博弈 问题的研究还不断提出一些新的研究课题，从而推动了人工智能研究的发展 。现代博弈理论由匈牙利数学家冯 ・诺伊曼于 20 世纪 20 年代开始创立， 1944 年他与经济学家奥斯卡・摩根斯特恩合作出版的巨著《博弈论与经济行为  》，标志着现代系统博弈理论的初步形成。对于非合作、纯竞争型博弈，冯 ・ 诺伊曼所解决的只有二人零和博弈 ―― 好比两个人下棋，或是打乒乓球，一个人赢一着则另一个人必输

 

・126 ・

第 5 章   搜索原理

一着，净获利为零。应用传统决定论中的 “最小最大”准则，即博弈的每一方都假设对方的所有攻略的根
本目的是使自己最大限度地失利，并据此最优化自己的对策，冯・诺伊曼从数学上证明，通过一定的线性运算，对于每一个二人零和博弈， 
都能够找到一个 “最小最大”解。通过一定的线性运算，竞争双方以概率分布的形式随机使用某套最优策略中的各个步骤，就可以最终达到彼此盈利最大且相当。
当然，其隐含的意义在于，这套最优策略并不依赖于对手在博弈中的操作。用通 俗的话说，这个著名的最小最大定理所体现的基本 “理性” 思想是“抱最好的希望， 做最坏的打算 ”。

诸如下棋、打牌、战争等一类竞争性智能活动称为博弈 。其中最简单的一种称为“二人零和、全 信息、非偶然”博弈 。所谓“二人零和、全信息、非偶然” 博弈

是指：

(1)      双垒的 A 、B 双方轮流采取行功， 博弈 的结果只有 A 方胜， B 方败 ； B

方胜， A 方败； 双方战成平局三种结果。

(2)      在对垒过程中，任何一方都了解当前的格局及过去的历史。
就是两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。

(3)      任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取

对自己最为有利而对对方最为不利的对策，不存在 “碰运气”的偶然因素 ， 即双方都很理智地决定自己的行动。对 于带机遇性的任何博弈，因不具有完备信息 及存在偶然因素 ， 所以 不属这里
讨论的 范围 。

在 博弈 过程中，任何一方都希望自己取得胜利。因此，在某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动 方案。此时，如果站在 A
方的立场上，则可供 A 方选择的若干行动方案之间是“或” 关系，因为主动权操在  A   方子里，他或者选择这个行动方案，或者选择另一个行动方案，完全由 A 方决定。但是，若 B 方也有若干个可供选择的行动方案，则对

A
方来说这些行动方案之间是“与”关系，因为这时主动权操在
B 方手里，这些可供选择的行
动方案中的任何一个都可能被 B 方选中，
A 方必须考虑到对自己最不利的情况。若把上述博弈过程用图表示出来，得到的是一棵“与或”树。这里要特别指  出，该“与或”树是始终站在某一方( 例如 A 方) 的立场上得出的，决不可一会儿站在这一方的立场上，一会儿又站在另一方的立场上。

・127 ・

人工智能技术与方法

如图 5.26 所示，设有甲、乙二人对 弈 ，甲方对当前棋局态势为
1 ，甲先行。

他有 2 种可能的走法，使棋局态势成为
2 或 3
； 乙方对态势 2 ，有 2 种可能的走

法，使棋局态势成为 4 或 5 ； 乙方对态势 3
，有 3 种可能的走法，使棋局态势成

为 6 、7 或 8 ；甲方对态势 4
，有 2 种可能的走法
，使棋局态势成为 9 或
10 ；

甲方对态势 8 ，有 2 种可能的走法，使棋局态势成为 17 或
18 。那么，甲应该如何走法呢？显然，若 甲往节点 2
走( 使棋局态势成为为 2) ， 则乙必然往节点 5 走。因为在再次轮到甲走时，甲或者走
11 ，或者走 12 ， 乙至少是一个 平 手，甲至多是一个 平 手 。如果乙往节点 4
走，则一旦甲在下一轮走出 10 ，结果即为甲赢而乙输。综上所述，
如果 甲往节点 2 走的最好后果( 对甲来说) 将是平手。另一种可能

 

 

图 5.26   博弈树

是甲往节点 3 走，此时不管乙选择
6 、7
还是 8 ，甲都有一步赢棋可 走(13 ， 16 或

18) 
，因此，走节点 3 对甲来说是保赢的。两相比较，甲应走
3 。称描述 博弈 过程的“与或”树为 博弈 树，它有如下特点 。

(1)      博弈 的初始格局是初始节点。

(2)     
在博弈 树中 ，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是 “与”关系。双方轮流地扩展节点。

(3)     
所有能使自己一方获胜的终局的相应的节点是可解节点 。 所有使对方获胜的终局都是不可解节点。

由于双人 博弈 可用“与或”树(“与或”图) 描述，因而搜索就是寻找最佳解树( “与或”图) 的问题。 至于 与或树(“与或”图) 的 搜索 算法，限于篇幅，此处不再讨论。

 

 

・128 ・

 

5.4.2        
Grundy 博弈(完全取胜策略)

第 5 章   搜索原理

 

Grundy 博弈是一个分钱币的游戏。有一堆数目为 N 的钱币 ， 由两位选手轮流进行分堆，要求每个选手每次把其中某一堆分成数目不等的两小堆。例如
， 选手甲把 N  分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去直到有一位选手无法把钱币再分成不相等的两堆时就得认输。
设初始时共有 7 个 钱币
，

MIN 方先走。MIN 有三种可选的方法，分别为( 6
，1 ，MAX ) ，(5 ，2 ，MAX) 和(4 ，

2 ， MAX) 。这 一 博弈 的完整 博弈 图如图 5.27 所示。

(6，1，MAX)

搜索策略要考虑的问题是对 MIN
走步后的每一个 MAX
节点 。必须证明 MAX
对 MIN 可能走的每一个棋局对弈后能获胜，即
MAX 必须考虑应付到
MIN 的所有招法，这是一个“与”的含意，因此含 MAX 的节点可看成“与”节点。比如 ，MAX
必须考虑应付到 MIN
的所有招法(6，1，MAX)，(5，2，MAX) 和 ( 4，3，MAX)都

 

 

(4，1，1，1，MAX)

MIN
胜利点

 

 

(3，1，1，1，1，MIN)

(2，1，1，1，1，1，MAX)

MAX
胜利点

MIN 胜利点

 

图 5.27 Grundy 博弈状态空间图

能获胜 。对 MAX 走步后的每一个 MIN 节点，只 需 要证明 MAX 有 一 步 能走赢就可以 了， 即 当轮到 MAX 走步 时， MAX 只要考虑能 从多种 走步 中，找到 一步棋使 MIN 无法招架就成，因此 ，
含有 MIN 符号的节点可看成“或”节点。这样一来对弈过程的搜索图就呈现出“与或”图表示的形式。

从搜索图中可以看出， MAX 存在完全取胜的策略，图中粗线所示部分就代

 

・129 ・

人工智能技术与方法

表了这种策略 ， 这时不论 MIN 怎么走， MAX 均可取胜。因而 ， 寻找 MAX 的取胜策略便和求“与 或”图的解图一致起来，即 MAX 要取胜，必须对所有“与”节点取胜，但只需对一个“或”节点取胜，这就是一个解图。因此， 实现一种取胜的策略就是搜索一个解图的问题 ，解图就代表一种完整的博弈策略。

对于 Grundy 这种较简单的博弈，或者复杂博弈的残局，可以用类似于“与或” 图的搜索技术求出解图，解图代表了从开局到终局任何阶段上的弈法。显然这对许多博弈问题是不可能实现的。

根据香农的估计，在国际象棋中，对于每一个棋局态势( 棋子分布现 状) ， 均有 30 种不同的 走 法。在每一局棋中，平均双方各走
40 步。因此，总的可能性是

(30² )⁴⁰» 10¹²⁰

这是博弈树中最后一排节
点( 叶节点) 的个数，因此，总节点数应是 10¹²¹左右。这是世界上任何 一台 计算机 都 放不下的。即使生成每个节点只要一个 纳 秒，则为生成这些节点所需的时间就是 10¹¹²
秒或 10¹⁰⁴
年。另有人估计，对中国象棋来说，

每个棋局的走法约有 20~ 60 种，平均双方要各走 50 余步，即以平均数 40 种走法为下限 ， 双方各走 50 步来说，也要生成

(40² ) ⁵⁰» 10¹⁶⁰

个节点，超过了国际象棋的节点数。围棋就更复杂了。因此要考虑完整的搜索策略，就是用亿次机来处理，也得 花费 以天文数字计的时间。即使用 了有力的启发式搜索技术，也不可能使分枝 修剪 得很少。因此 ， 这种完全取胜策略( 或和局) 必须丢弃，而应当把目标确定为寻找一步好棋这种实际可行的实用策略。这种情况下每一步结束条件可根据时间限制、存储空间限制或深度限制等因素加以确 定。在给定的 限制 条件下， 要从 局部 搜索 中 提取一个 相对的“ 最好的” 走步，这就是实用策略的基本点。基于这种机理的博弈搜索策略叫极小极大过程。

 

5.4.3        
极小极大分析法

前面已说过，对 于 大多数博弈问题 ， 必须放弃完全取胜的策略，而采用一个实用的叫极小极大搜索过程的搜索策略。在二人 博弈 问题中， 在一定 深度 的条件

・130 ・

第 5 章   搜索原理

下(
而不是整个 搜索 树的 深度)
，为了从众多可供选择的行动方案中选出一个对自己有利的行动方案，就需要对当前情况以及将要发生的情况进行分析，从中选出最优者。

最常使用的分析方法是 极小极大分析法。 其基本思想如下。

(1)      设博弈 的双方中一方为 A ，另一方为 B 。极大极小分析法是为其中的一方( 例如 A) 寻找一个最优行动方案的方法。

(2)      为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比

较。具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。

(3)      为计算得分，需要根据问题  的特性信息定义一个估价函数，用来估算当前 博弈 树端节点的得分。此时估算出来的得分称为静态估值。在讨论关于 博弈
问题是 ，通常习惯于约定 MAX 代表程序方( 己方) ，MAX 方先走 ，MIN 代表对手方， 有利于 MAX 的态势 p ，棋局的评价函数 f ( p ) 取正值，有利于 MIN 的态势 p ，棋局的评价函数 f ( p ) 取负值，势均力敌的态势 p ，棋局的评价函数 f ( p ) 取 0 值，

若 f ( p ) = +¥ ，则表示 MAX
赢，若 f ( p )
= -¥ ，则表示 MIN
赢。

(4)     
当端节点的估值计算出来后，再推算出父节点的得分。推算的方法是 ： 对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使

自己在可供选择的方案中选一个对自己最有利的方案
； 对于“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值， 如图 5.28 所示。

 

MAX                                        2

MIN

9