
180
|
第
7
章
图 7-11:两步之后的井字棋棋局
不过,要实现如此大幅削减,唯一的途径是可行走法有序,而且最优走法排在最前面。
但是,我们的解并不会这样对井字棋的走法排序,所以可能会得到一些异常结果。例如,
将上面的棋局旋转
180
°
(见图
7-12
),那么
AlphaBeta
需要探测
960
个棋局状态(节
省了
88.3%
)。这是由于它在扩展博弈树使用了另外一种排序算法。因此,有些算法会
在静态评估函数重新排序以减少博弈树的规模。
图 7-12:两步之后的井字棋棋局,它是图 7-11 的旋转版本
7.6 搜索树
有些游戏只需要一个玩家参与,目标是为了从初始状态(搜索树的顶端结点)开始,经
过一系列的走法达到目标状态。
搜索树
就适用于这种情况。构建一棵树的原因就是为了
防止重复访问同一状态。算法在这里负责决定访问状态的顺序,以达到目标。
八数码游戏是在一个
3
×
3
的网格上,放着
8
个小方块,分别标上
1~8
,有一个空的格子
没有方块。空格周围(水平的或者垂直的)方块可以移动到这里,方块原有位置便是一
个新的空格。这个游戏的目标就是从一个初始状态开始,移动空格周围的方块,达到目
标状态。我们可以看到图
7-13
的解路径便是用粗体标识出来的从初始结点到目标结点的
路径,一共用了
8
步。
搜索树通常会快速增长到数百万亿个状态,本章的算法将会告诉我们如何在搜索树中高
效快速地搜索。为了了解问题本身的复杂度,我们首先使用采用
深度优先搜索
和
广度优
先搜索
的寻路算法,然后使用强有力的
A*
搜索
算法,找到一个最小耗费的解(在特定
的条件下)。我们在这里简单地描述一些核心类,如图 ...