0

alpha-beta剪枝算法如下：

function ALPHA-BETA-SEARCH(state) returns an action
      v <- MAX-VALUE(state, -∞, +∞)
      return the action in ACTIONS(state) with value v

function MAX-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then 
        return UTILITY(state)
    v <- -∞
    for each a in ACTIONS(state) do
        v <- MAX(v, MIN-VALUE(RESULT(state, a), α, β))
        if v ≥ β then
            return v
        α <- MAX(α, v)
    return v

function MIN-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then 
        return UTILITY(state)
    v <- +∞
    for each a in ACTIONS(state) do
        v <- MIN(v, MAX-VALUE(RESULT(state, a), α, β))
        if v ≤ α then 
            return v
        β <- MIN(β, v)
    return v

该算法声明该ACTIONS函数将给出给定 中所有可用操作的列表state。

让我们以跳棋游戏为例。假设一个棋子，比如说A，与另一个棋子，比如说 ，在对角线上B。如果Acan take B，那么这是一个（不可避免的，因为如果可以的话，我们必须采取另一个检查器）动作。或者，如果有多个镜头，这些都是动作。这种情况实际上可以用铅笔和纸画出来。更具体地说，可以使用树来表示情况，其中每个节点代表一个状态，到其子节点的边代表来自该状态的可能动作。

我认为您不需要显式存储树数据结构。但是，上面的算法包含以下语句：return the action in ACTIONS(state) with value v. 现在，ACTIONS(state)将返回某个状态（例如A需要播放的位置）的可能动作。

如果我们计算出所有算法，我们将得到一个 value v，我们将使用v从终端节点传递的值跟随节点。

现在，假设我没有存储来自每个状态的所有可能移动或动作的完整树。当return the action ACTIONS(state) with the value v被执行时，我只会得到引导我进入下一个状态的动作，并且我知道其中一个动作会引导我走向最佳路径。但是，如果我没有额外的簿记，例如完整的树，我是否能够将操作与价值相匹配v？

4

2 回答 2

4
于 2012-04-17T09:56:23.747 回答
1

我认为有两个问题很重要，可以回答你：

  1. 无论如何都会构建树 - 隐含地，每个ACTIONS(vertex)操作都可以简单地连接vertex到他的每个儿子 - 所以无论如何都没有真正需要额外的树构建。v而且，当然，您可以向该树的每个节点添加诸如此类的属性。

  2. 不过，如果您不需要也不关心实际的树，一种可能的解决方案是返回(v, state)[a tuple] 而不是v. 返回值上的所有操作 - 将在 上完成v，和现在一样，唯一实际使用state的 - 是顶层ALPHA-BETA-SEARCH()。当然，它需要较少的优雅MIN和MAX功能，因为您不仅需要找到值v- 还要找到给出该值的顶点。

于 2012-04-17T09:39:29.603 回答