博弈树的搜索课件.ppt

1、博弈树搜索博弈树搜索l所谓双人完备信息，就是两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。对弈的结果是一方赢（另一方则输），或者双方和局。这类博弈的实例有：一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。对于带机遇性的任何博弈，因不具有完备信息，不属这里讨论范围，但有些论述可推广到某些机遇博弈中应用。 l博弈问题可以用产生式系统的形式来描述，例如中国象棋，综合数据库可规定为棋盘上棋子各种位置布局的一种描述，产生式规则是各类棋子合法走步的描述，目标则可规定为将（帅）被吃掉，规则作用于数据库的结果便生成出博弈图或博弈树。下面举一个简单的

2、例子说明博弈问题可用与或图表示，并讨论搜索策略应考虑的实际问题。 中国象棋中国象棋l一盘棋平均走50步，总状态数约为10的161次方。l假设1毫微秒走一步，约需10的145次方年。l结论：不可能穷举。博弈树是与博弈树是与/ /或树或树l双方都希望自己能够获胜。因此，当任何一方走步时，双方都希望自己能够获胜。因此，当任何一方走步时，都是试图选择都是试图选择对自己最为有利，而对另一方最为不利对自己最为有利，而对另一方最为不利的的行动方案。行动方案。l从从MAXMAX方的观点看方的观点看，在博弈过程的每一步，可供自己选择，在博弈过程的每一步，可供自己选择的行动方案之间是的行动方案之间是“或或”的关系

3、，原因在于选择哪个方案完的关系，原因在于选择哪个方案完全是由自己决定的；而可供全是由自己决定的；而可供MINMIN选择的行动方案之间则是选择的行动方案之间则是“与与”的关系，原因是主动权掌握在的关系，原因是主动权掌握在MIN手里，任何一个方手里，任何一个方案都有可能被案都有可能被MIN选中，选中，MAX必须防止那种对自己最为不利必须防止那种对自己最为不利的情况的发生。的情况的发生。l这样，这样，从选手的角度看从选手的角度看，博弈树就是一棵与或树，博弈树就是一棵与或树， 其特点是：其特点是： （l）博弈的初始状态是初始节点；）博弈的初始状态是初始节点； （2）博弈树中的）博弈树中的“或或”节点和

4、节点和“与与”节点节点逐层交替出现逐层交替出现 （3）整个博弈过程始终站在某一方的立场上，所有能使自己）整个博弈过程始终站在某一方的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。有使对方获胜的终局都是不可解节点。极小极大搜索过程极小极大搜索过程极小极大搜索策略是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的走法来走，即在有限的搜索深度范围内进行求解。为此要定义一个静态估计函数定义一个静态估计函数f f，以便，以便对棋局的势态（节点）作出优劣估值，对棋局的势态（节点）作出优劣估

5、值，这个函数可根据势态优劣特征来定义（主要用于对端节点的“价值”进行度量）。一般规定有利于MAX的势态，f（p）取正值，有利于MIN的势态，f（p）取负值，势均力敌的势态，f（p）取0值。若f（p），则表示MAX赢，若f（p），则表示MIN赢。下面的讨论规定：顶节点深度顶节点深度d d0 0，MAXMAX代代表程序方，表程序方，MINMIN代表对手方，代表对手方，MAXMAX先走。先走。极小极大搜索过程极小极大搜索过程极大极小过程步骤：极大极小过程步骤： （1）以当前考察的态势）以当前考察的态势P为根节点，生成指定深度为根节点，生成指定深度的博弈树。的博弈树。 （2）根据静态估计函数）根据静态

6、估计函数f计算各叶节点的估计值。计算各叶节点的估计值。 （3）自底向上计算各个非叶节点的估计值，计算的）自底向上计算各个非叶节点的估计值，计算的方法是方法是MAX节点节点取其子节点的取其子节点的最大值最大值，MIN节点节点取取其子节点的其子节点的最小值最小值。 （4）将根节点的倒推值对应的策略作为当前的最佳）将根节点的倒推值对应的策略作为当前的最佳策略。策略。极小极大过程极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小一字棋游戏一字棋游戏设有一个三行三列的棋盘，两个棋手轮流走步，每个棋手走时往空格上摆一个自己的棋子，谁先

7、使自己的棋子成三子一线为赢。设程序方MAX的棋子用（）表示，对手MIN的棋子用（）表示，MAX先走。静态估计函数f（p）规定如下：1. 若若 P是是 MAXMAX的必胜局的必胜局， 则则 e(P) = + ；2. 若若 P是是 MINMIN的必胜局的必胜局， 则则 e(P) = - ；3. 若若P对对MAX、MIN都是都是胜负未定局胜负未定局，则，则 e(P) = e(+P)e(-P)其中，e(+P)表示棋局 P上有可能使 成三子一线的数目；e(-P)表示棋局 P上有可能使 成三子一线的数目。一字棋游戏一字棋游戏f(+P)=6f(P) = f(+P) - f(P) =2f(-P)=4例例l在搜

8、索过程中，具有对称性的棋局认为是同一在搜索过程中，具有对称性的棋局认为是同一棋局，以大大减少搜索空间。棋局，以大大减少搜索空间。 对称棋局的例子对称棋局的例子用极大极小搜索方法为用极大极小搜索方法为MAXMAX寻找第一步棋的走法。寻找第一步棋的走法。 （搜索深度为（搜索深度为2 2）-剪枝剪枝l极大极小过程是先生成与极大极小过程是先生成与/或树，然后再计算各节点的估或树，然后再计算各节点的估值，即值，即生成节点生成节点和和计算估值计算估值这两个过程是这两个过程是分离分离的。在搜索的。在搜索时，时，需要生成规定深度内的所有节点需要生成规定深度内的所有节点，因此搜索效率较低。，因此搜索效率较低。以

9、棋盘为1515大小的五子棋为例，人机对弈，用极大极小搜索算法，搜索深度为3时，计算机（配 置：CUP赛场1.7 G，内存DDR266 256 M）每走1步要用10 min，搜索的节点数超过了107个；而搜索深度为4时，每走1步要用10个多小时，搜索节点数超过了2109个。l如果能如果能边生成节点边对节点估值边生成节点边对节点估值，并根据一定的条件，并根据一定的条件，提提前前剪去剪去一些没用的分枝，那么就可以有效提高搜索效率。一些没用的分枝，那么就可以有效提高搜索效率。在这种思想的基础上，人们提出了在这种思想的基础上，人们提出了-剪枝技术剪枝技术。-剪枝技术剪枝技术l采用采用有界深度优先策略有界

10、深度优先策略，当生成规定深度的节点，当生成规定深度的节点时，计算叶节点的静态估值，并时，计算叶节点的静态估值，并倒推倒推非端节点的非端节点的估值。根据倒推结果，在非端节点的向下分枝中，估值。根据倒推结果，在非端节点的向下分枝中，剪掉那些目前未知，但无论如何都不会改变非端剪掉那些目前未知，但无论如何都不会改变非端节点倒推值的未扩展分枝节点倒推值的未扩展分枝。用剪枝技术，搜索深度为3时，每走1步不到2 min，搜索的节点数小于1.5106个；而搜索深度为4时，每走1步要用160 min，搜索的节点数小于2108个。 l- 值值为为MAXMAX节点（节点（“或或”节点）节点）倒推值的倒推值的下确界下

11、确界 当前子节点中的最小倒推值当前子节点中的最小倒推值 值值为为MINMIN节点（节点（“与与”节点）节点）倒推值的倒推值的上确界上确界 当前子节点中的最大倒推值当前子节点中的最大倒推值l剪枝：剪枝：若任一若任一MIN节点（节点（“与与”节点）的节点）的值小值小于或等于其父节点（于或等于其父节点（MAX节点（节点（“或或”节点）节点）的的值（即不能升高其父节点的值（即不能升高其父节点的值），则可中止值），则可中止该该MIN节点以下的搜索过程。这个节点以下的搜索过程。这个MIN节点最终的节点最终的倒推值就设定为这个倒推值就设定为这个值值l剪枝：剪枝：若任一若任一MAX节点（节点（“或或”节点）的节点）的值值大于或等于其父节点（大于或等于其父节点（ MIN节点（节点（“与与”节点）节点）的的值（即不能降低其父节点的值（即不能降低其父节点的值），则可以中值），则可以中止该止该MAX节点以下的搜索过程。这个节点以下的搜索过程。这个MAX节点最节点最终的倒推值就设定为这个终的倒推值就设定为这个值。值。S0ABCDFGHEIJKLMNPQRT4861580-644144554400-6=004 -剪枝例剪枝例S1