博弈理论极大极小算法和Alpha-Beta搜索技术

论文帮手 3本页 3674字

4 搜索技术

  4.1 基本搜索技术

  假定你的房间里铺有 100 块地板,其中一块底下有一块金砖,而另一块底下有一颗地雷。如果你翻开有金砖的那块地板,你就可以成为百万富翁;如果你翻开有地雷的那块地板,你就可以到地狱旅行。在经历了长期煎熬之后,你决定将这些地板逐一翻开,以找寻百万富翁的生活。这个寻找命运答案的过程,就是搜索(Search)。而将地板逐一翻开的搜索方法,叫作盲目搜索( Blind Search)。在这个盲目搜索的过程中,随着未翻开地板数目的减少,终将会找到一个答案。又假定你还有一位朝夕相伴的室友,同你一样起了这个念头。于是,你们商定每人每天可以交替翻开一块地板。这样当一个人碰到地雷时,他最亲密的朋友就可以得到剩下的金砖。所以你们各自在心中祝愿对方黄泉路上一帆风顺。最多 50 天,命运的答案就会完全揭晓。你们翻开了 98 块地板后仍一无所获,在最后的时刻,你犹豫了,到底要不要翻开这一块决定命运的地板?你感到同你竞争的并非你的室友,而是魔鬼的化身。这个同魔鬼的化身交战的过程就叫作博弈。而敌对双方交替动作的搜索叫作对抗性搜索(AdversarialSearch)。

博弈理论

  4.2 博弈树

  设想下象棋的情形,两人对弈,我们将其中一位叫做甲,另一位叫做乙。假定现在该甲走棋,甲可以有 40 种走法(不论好坏);而对甲的任一走法,乙也可以有与之相对的若干种走法。然后又轮到甲走棋,对乙的走法甲又有若干种方法应对……如此往复。显然,我们可以依此构建一棵博弈树,将所有的走法罗列出来。在这棵树的根部是棋局的初始局面。根的若干子节点则是由甲的每一种可能走法所生成的局面,而这些节点的子节点则是由与之相对的乙的每一种可能走法所生成的局面……在这棵树的末梢,是结束的棋局,甲胜或者乙胜或者是双方都无法取胜的平局。图 4.1 极为简化地示意了博弈树的概要。图中省略号的地方指未能列出的大量分枝。如果我们令甲胜的局面值为 W IN,乙胜的局面值为 LOST,而和局的值为 DRAW 。当轮到甲走时,甲定会选择子节点值为 W IN 或 DRAW(如果没有值为 W IN 的子节点的话)的走法;而轮到乙时,乙则会选择子节点值为 LOST 或 DRAW(如果没有值为 LOST 的子节点的话)的走法。对于中间节点的值可以有如下计算方法:如果该节点所对应的局面轮到甲走棋,则该节点的值是其所有子节点中值最佳( 对甲而言)的一个的值;如果该节点所对应的局面轮到乙走棋,则该节点的值是其所有子节点中值最差(对甲而言)的一个的值。这样看来从这棵树的叶子节点倒推向根部,就可以得出所有节点的值。双方就可以从其所面临的棋局中选择一步好棋。然后一步步走向胜利。博弈树是从根部向下递归产生的一棵包含所有可能的对弈过程的搜索树,这里称为完全搜索树。NeillGraham 形容此过程类似于在一个状态图中寻求从初始状态通向终了状态的过程。只是状态图搜索仅有一个主体参加,仅是单方面做出的路径选择。而博弈树的搜索则有对立的双方参加,一方只能做出一半选择,而这一半选择的目的是使对方远离其竭力靠近的目标。也就是说状态图搜索是纯粹的或树(OR tree),而博弈树搜索是与或树(AND /OR tree)。

博弈树

图 4.1 博弈树

  象棋博弈树示意让我们面对一下不幸的实际,那就是,除了极少数非常简单的棋类游戏,大多数棋类游戏,如象棋,我们都没有建立完全搜索树的可能。一方面是因为很多情形根本就到达不了叶子节点,如将一个棋子反复来回走动就可永远循环下去。另一方面,即使我们将循环的情形排除,这棵树上的节点数量也已多到了无法处理的程度。以中国象棋为例,其每一局面可有约20 至 60 种走法。以平均 40 种走法计,建立一棵(双方各走 50 步)搜索树就需生成约 10160个节点。这远远超出了当今计算机的处理能力。即使生成一个节点仅需 10^-8秒,生成这棵树也要10140年以上。显然这是不切实际的;也就是说,必须得有其他切合实际的方法。

  4.3 极大极小值算法

  在上面的博弈树中,如果我们令甲胜的局面值为 1,乙胜的局面值为 -1,而和局的值为 0。当轮到甲走时,甲定会选择子节点值最大的走法;而轮到乙时,乙则会选择子节点值最小的走法。所以,对于中间节点的值可以有如下计算方法:如果该节点所对应的局面轮到甲走棋,则该节点的值是其所有子节点中值最大的一个的值。而如果该节点所对应的局面轮到乙走棋,则该节点的值是其所有子节点中值最小的一个的值。对博弈树的这个变化仅仅是形式上的,本质上丝毫未变,但是这个形式更容易推广以运用到一般实际的情形。既然建立整棵的搜索树不可能,那么,为当前所面临的局面找出一步好棋如何?也就是通过少量的搜索,为当前局面选择一步较好的走法。在通常的棋局当中,一个局面的评估往往并不像输、赢、平 3 种状态这么简单,在分不出输赢的局面中棋局也有优劣之分。也就是说,要用更细致的方法来刻画局面的优劣,而不是仅仅使用 1、-1、0 三个数字刻画 3 种终了局面。假定我们有一个函数可以为每一局面的优劣评分。例如甲胜为 +∞ ;乙胜为 -∞ ;和局为 0;其他的情形依据双方剩余棋子的数量及位置评定 -∞ 至 +∞ 之间的具体分数。这样我们可以建立一棵固定深度的搜索树,其叶子节点不必是终了状态,而只是固定深度的最深一层的节点,其值由上述函数评出;对于中间节点,如同前面提到的那样,甲方取子节点的最大值,乙方取子节点的最小值。这个评分的函数称作静态估值函数(Static Evaluation Function)。用以取代超出固定深度的搜索。显然,我们无法拥有绝对精确的静态估值函数。否则,只要这个静态估值函数就可以解决所有的棋局了。估值函数给出的只是一个较粗略的评分,在此基础上进行的少量搜索的可靠性,理论上是不如前述的W IN,LOST,DRAW 三种状态的博弈树的,但这个方法却是可实现的。利用具体的知识构成评估函数的搜索叫做启发式搜索( Heuristic Search)。估值函数在有些文献中也称为启发函数(Heuristic Function)。在博弈树搜索的文献当中,极大极小方法往往指的是基于静态估值函数的有限深度的极大极小搜索。

  4.4 深度优先搜索

  在生成极大极小树并对其进行搜索的方法上,我们面临着多种选择:是先在内存中生成整棵树然后进行搜索,还是在搜索的过程中仅仅产生将要搜索的节点?

  对于树的搜索以什么顺序进行,是广度优先(Breadth FirstSearch)深度优先,还是其他顺序?有必要生成整棵树吗?在搜索过程中将搜索过的节点删去行吗?几乎所有的人在使用基本的极大极小算法时都选择了深度优先搜索方法。这样可以在搜索过程中的任何时候仅仅生成整棵树的一小部分,搜索过的部分被立即删去。显然,这个算法对内存的要求极低,往往在内存只有几千字节的机器上也可以实现。并且同其他的选择相比,速度上也并不逊色。深度优先搜索极大极小树的过程,可以表示为一个递归的形式。如下图所示的一棵树,共有 3 层。根节点为 A,其子节点有 B、C、D 三个,而 B、C、D 也各有子节点若干。以深度优先算法搜索此树时,先进入根节点 A,生成其第 1 个子节点 B;然后遍历 B,生成 B 的第 1 个子节点 E;E 将其估值返回给父节点B,删掉 E,B 生成第 2 个子节点 F;F 将其估值返回给父节点 B,删掉 F,B 生成第 3 个子节点 G;G 将其估值返回给父节点 B,删掉 G,B 在 3 个叶节点的返回值中取极小值并将此值返回给 A,A 生成其第 2 个子节点 C;同样遍历 C 及其子节点,得到 C 的返回值后再生成 D 并向下遍历之;最后,A 在 B、C、D 的返回值中取极大值,拥有该极大值的子节点就是下一步要走的方向。从上述过程可以看出,深度优先搜索极大极小树的过程中,任何时候只要保存与其层数相同个数的节点。在些过程中,任何时刻仅需保存 3 个节点,仅生成将要搜索的节点,搜索完成的节点可以立即删去以节省空间。

深度优先搜索

图 4.2 深度优先搜索

  4.5 负极大值算法

  普通的极大极小值算法看起来有一点笨,既然一方试图取极大值而另一方试图取极小值———也就是说———我们总要检查哪一方要取极大值而哪一方又要取极小值,以执行不同的动作。Knuth 和 Moore在 1975 年提出了负极大值(Negamax)方法,消除了两方的差别,而且简洁优雅。使用负极大值方法,博弈双方都取极大值。负极大值算法比极大极小值算法短小并且简单。负极大值算法的核心在于:父节点的值是各子节点的值的负数的极大值。如要这个算法正确运作,还要注意一点额外的东西。例如象棋,估值函数必须对谁走棋敏感,也就是说对于一个该红方走棋的局面返回正的估值的话,则对于一个该黑方走棋的局面返回负的估值。初看上去,负极大值算法比极大极小值算法稍难理解,但事实上负极大值算法更容易被使用。在算法的原理上,这两种算法完全等效。负极大值算法仅仅是一种更好的表达形式。今天的博弈程序大多采用的也都是基于负极大值形式的搜索算法。

  4.6 Alpha-Beta 搜索

  前面已经介绍了博弈程序工作的基本原理——基础而重要的极大极小算法。通过前面的分析,我们实现一个基于极大极小搜索算法的中国象棋是如何工作的,我们也会发现由于搜索的时间耗费随着搜索层数的增加而急剧升高。这个程序实际上不可能进行较深的搜索,因为它会导致博弈性能的降低。20 世纪 60 年代至今,博弈树搜索算法的大多数重要改进。包括基本的 Alpha-Beta搜索、Transpositon Table、迭代深化、空窗搜索、历史 /杀手启发等一系列方法。把这些方法单独或者结合使用,将在很大程度上提高博弈树的搜索效率。

  由于本程序设计采用Alpha-Beta搜索技术,在这里主要介绍Alpha-Beta搜索。在极大极小搜索的过程中,存在着一定程度的数据冗余。举一个最简单的例子:在象棋博弈的过程中,如果某一个节点轮到甲走棋,而甲向下搜索节点时发现第一个子节点就可以将死乙(节点值为最大值),则剩下的节点就无需再搜索了,甲的值就是第一个子节点的值。这个过程,就可以将大量冗余的(不影响结果的)节点抛弃。

Alpha-Beta 搜索

图 4.3  Alpha-Beta 搜索

  将上述这个情形推广一下,设想有如图上左半部所示的一棵极大极小树的片断,节点下面数字为该节点的值,节点 B 的值为 18,节点 D 的值为 16,由此我们可以判断节点 C 的值将小于等于 16(取极小值);而节点 A 的值为节点 Max(B,C),为 18,也就是说不再需要估节点 C的其他子节点如 E、F 的值就可以得出父节点 A 的值了。这样将节点 D 的后继兄弟节点减去称为 Alpha剪枝(alpha cutoff)。设想有如图上右半部所示的一棵极大极小树的片断,节点 B 的估值为 8,节点 D 的估值为18,由此我们可以判断节点 C 的值将大于等于 18(取极大值);而节点 A 的值为节点 Min(B,C),为 8。也就是说不再需要求节点 C 的其他子节点如 E、F 的值就可以得出父节点 A 的值了。这样将节点 D 的后继兄弟节点减去称为 Beta剪枝(beta cutoff)。

  Alpha-Beta搜索能够让我们忽略许多节点的搜索。对于每一个被忽略的非叶子节点来说,这都意味着不仅节点本身,而且节点下面的子树也被忽略掉了。这就导致了 Alpha-Beta搜索需要遍历的节点远远少于极大极小算法所遍历的节点。这也同时意味着对搜索同一棵树来说,Alpha-Beta搜索所花费的时间远远少于极大极小算法所花费的时间。同极大极小搜索算法一样,Alpha-Beta搜索算法也有点繁琐,我们不仅要在奇数层进行 al-pha剪枝,而且还要在偶数层进行 beta剪枝。不过只要将负极大值的形式套用上去,这样在任何一层都只进行 beta剪枝,它就会同负极大值算法一样简洁。

  自 1928 年极大极小方法诞生以来,其间出现了多种改进搜索效率的方法,但 Alpha-Beta搜索算法到目前为止仍是使用最为广泛的搜索算法。也可以说,Alpha-Beta搜索是博弈树搜索的基础技术。由前面的介绍我们可以了解,当节点以特定的顺序排列时,就可以进行 Alpha剪枝或 Beta剪枝。那么,当节点的排列顺序不是像上图所示的时候,Alpha剪枝和 Beta剪枝就不能有效的进行了。那么,Alpha-Beta搜索最多可以比极大极小算法少搜索多少节点呢?Knuth和 Moore所作的研究表明,在节点排列最理想的情形之下,使用 Alpha-Beta搜索建立的博弈树的节点个数为:W(d+1)/2+ Wd/2+ 1其中 W 是博弈树的分支因子,d是最大搜索深度。这个数字大约是极大极小搜索建立的节点数的平方根的 2 倍左右。我们也将这棵理想的博弈树称作极小树(MinimalTree)。在最差的情况下,Alpha-Beta搜索建立的节点同极大极小搜索一样,也就是全部可能的节点。对于博弈树来说,节点的排列顺序是杂乱无章的。也就是说,Alpha-Beta搜索建立的博弈树的节点数目在极小树和全部节点之间。由于 Alpha-Beta剪枝与节点的排列顺序高度相关,使用其他手段将节点排列调整为剪枝效率更高的顺序就显得尤为重要了 。

(未完,请点击下面的其他章节)

相关文章

上一篇:象棋游戏系统流程图,接口及数据库概要设计

下一篇:象棋棋子的价值,灵活性及其关系评估

点击按钮复制手机号

18930620780

将微信二维码保存到相册

打开微信扫一扫从相册识别

1.点击按钮复制QQ号

3008635932

2.打开QQ→添加好友/群

粘贴QQ号,加我为好友