糟糕的局面
甚至可能更糟......这样一来便可以在很大程度上减少搜索的工作量
提高搜索效率这称为"树的裁剪"。
下面用图来进一步说明"树的裁剪"。
为了简便起见,将博弈树进行了简化--每个结点只有三个分支,
实际情况中刚才讲过在盘中应有大约40个分支。
假定棋盘上的局面发展到了结点A(图3),
现在轮到你走棋了你是"最大的一方"--即你希望棋局的分值尽可能的高。
用搜索两层来看一看"树的裁剪"对提高搜索效率的帮助。
图中表示该结点要取子结点中的最大值;表示该结点要取子结点中的最小值。
图3 树的裁剪
首先,考察结点A的子结点B。
结点B所属的这一层是轮到你的对手--"最小者"来走棋了,
目的是使得棋局的分值尽可能的小。
依次考察结点B的各个子结点,查看它们的分值(因为事先约定好了搜索两层,
现在已达到搜索深度的要求了所以就停下来调用局面评估函数来给它打分)。
结点B的第一个子结点(从左到右算起)返回10,
第二个子结点返回了-5第三个子结点返回了2。
由于结点B这层是你的对手来做选择,假设他一定会做出明智的选择(你不能寄希望于你的对手会走出一步"昏招"),
那么他会选择返回值为-5的那个结点。
-5最终也就成了从结点B传递回的值,即倘若你(现在位于结点A)选择了产生结点B的走法,
使得局面发展到了结点B。
那么下一步,你的对手的选择就会使得棋局发展成为分值为-5的那个结点所表示的局面。
再来分析结点A的第二个子结点C,结点C与结点B同属一层,
它依然是轮到你的对手作选择。
依次查看结点C的各个子结点的分值,其第一个子结点返回了-8......
采用 "裁剪"方法。
不必再继续考察结点C的剩余子结点了,因为结点C已经够糟糕的了,
不管结点C的剩余子结点有怎样的分值它最多只能传回-8(有可能其剩余子结点中还有分值更小的结点
因而结点C还有可能传回更小的值)。
而与前面已经分析过的结点B所传回-5相比较,
作为"最大一方"的你显然更不愿意看到-8的局面。
所以,你当然不会选择相应的着法使得局面发展成为结点C。
因为那样的话,下一步你的对手就会带给你一个分值不高于-8的局面。
由此,在不影响搜索质量的前提下避免了搜索"无价值的"结点C的剩余子结点的大量工作,
从而节省了宝贵时间为在同样机器配置下搜索更多的层数提供了可能。
"最小-最大"的思想再加上"对树的裁剪",
这就是Alpha-Beta搜索算法的核心。
最基本的Alpha-Beta算法的代码如下:
int AlphaBeta(int depth, int alph
上一篇:
中国象棋打谱系统-Java语言毕业设计内附详细的Java程序
下一篇:
近三年来思想工作小结(德能勤绩廉)