Alpha beta剪枝伪代码理解

Question

我无法理解教科书中的以下伪代码。特别是，我不明白第一个功能。在我们计算 v ← MAX-VALUE(state, −∞, +∞) 之后，我们如何继续计算值为 v 的动作？值 v 的动作到底是什么意思？是不是每个动作都要计算MAX-VALUE(Result(state, a) , −∞, +∞)，return和v ← MAX-VALUE(state, −∞, +∞)一样的动作。通常，我可以毫不费力地实现这本书中的伪代码，但这次我被严重卡住了。有人可以帮我解释一下吗？

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) the 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) the 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

Answer 1

我相信如果你看了这个解释，你会明白v和action的意思，并且能够实现这个伪代码。

我们来分解一下。

state - 一个问题实例 alpha - 可能解的最大下界 beta - 可能解的最小上界

当一个新状态被认为是通往解决方案的可能路径时，它必须具有：

alpha <= price(state) <= beta

现在让我们了解一下方法：

1. MAX-VALUE(state, α, β)

Returns 子树的最大可能值，根植于 state，a 和 b 作为 alpha 和 beta（分别）。

它是怎么做到的？那么，对于从 state 一步可达的每个状态，我们要考虑将我们移动到该状态的操作的价值（或“价格”）。这背后的直觉是，如果你坚持下去，你就会知道最终状态的价格，对所有（仅相关的）最终状态执行此操作，并且你知道最佳的“最小-最大”解决方案。

在您的伪代码中，它是在以下行中完成的：

for each a in ACTIONS(state) do

此操作是应用于当前 state、return 下一个 state 的操作。例如，您可以将其想象为 move player left，因此 returning 状态是原始的 state，只是玩家现在向左一步（愚蠢的例子，但它可能会有所帮助).请注意，它在您的代码中称为 RESULT(state, a) - 为简单起见，我将使用 next_state。

现在让我们检查以下行：

v ← MAX(v, MIN-VALUE(RESULT(state, a), α, β))

首先，让我们看看 MIN-VALUE(RESULT(state, a), α, β)，或者更好的是：MIN-VALUE(next_state, α, β)。因为您现在正在“探索”一条新路径（到达 next_state 的路径，您想要从该状态的所有可能性中获取 最小值（仅用于下一个level). 那是因为接下来轮到对手了，我们假设他打得尽可能聪明（所以我们知道我们有最佳路径）。直觉上，这可以看作是“如果我选择 next_state，最坏情况的价值是多少？”。

好的，那么现在，我们为什么要有这个 MAX(v, ...)？这个很简单，如果你已经通过不同的路径找到了一个更好的值v，那就去吧，没有理由去next_state。

2。 MIN-VALUE(state, α, β)

这与 MAX-VALUE 非常相似。你可以把这看成是“对手的回合”，因为他很“聪明”，他会选择给你最小值的下一步（因此MIN-VALUE）。

3。寻找解决方案：

function ALPHA-BETA-SEARCH(state) returns an action
 v ← MAX-VALUE(state, −∞, +∞)

现在，要利用MAX-VALUE和MIN-VALUE，你只需要找到最优解，从根state开始，没有具体的alpha或beta 限制（这些将在 MAX-VALUE 和 MIN-VALUE 中更新），因此您为它们分配 −∞ 和 +∞ 值。

那么实现这个需要什么

ACTIONS(state)

每个状态都需要有一个集合或运算符，每个return一个新状态，这是应用运算符逻辑后的原始状态。

RESULT(state, action)

按照上面的解释，这个可以简单的看成state.action()或者action(state)。只需对状态应用操作并 returning 新状态。

TERMINAL-TEST(state)

回答“这是一个终结状态吗？”问题的谓词。您需要能够在某处结束当前的分支搜索 - 此谓词是每个分支的中断条件。

我希望这有助于解决一些问题。

Alpha beta剪枝伪代码理解

Alpha beta pruning pseudo code understanding

algorithm

game-theory

graph-algorithm

alpha-beta-pruning

我们来分解一下。

那么实现这个需要什么