alpha-beta剪枝算法如下所示：
function ALPHA-BETA-SEARCH(state) returns an action v <- MAX-VALUE(state, -∞, +∞) return the action in ACTIONS(state) with value vfunction 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 vfunction 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在对角线上。如果A可以吃掉B，那么这是一个（不可避免的，因为如果可以，我们必须吃掉对方的棋子）动作。或者，如果有多个可吃的动作，这些都是可行的动作。这种情况实际上可以用铅笔和纸来画出来。更具体地说，这种情况可以用一棵树来表示，其中每个节点代表一个状态，通向其子节点的边代表从该状态可能采取的动作。
我认为你不需要显式地存储树数据结构。然而，上述算法包含以下语句：return the action in ACTIONS(state) with value v。现在，ACTIONS(state)将返回从某个状态（例如，A需要行动的状态）可能采取的动作。
如果我们完整地执行这个算法，我们将得到一个值v，我们将跟随从终端节点传递过来的具有值v的节点。
现在，假设我不存储所有可能移动或动作的完整树。当执行return the action ACTIONS(state) with the value v时，我只会得到引导我到下一个状态的动作，并且我知道其中一个动作会引导我到最佳路径。但是，如果我没有额外的记录，例如完整的树，我能将动作与值v匹配吗？
回答：
在极小化极大算法中，你不应该构建显式的树结构，在实际情况中，你不能这样做。一个具有深度限制d和分支因子b的极小化极大算法会遍历一个大小为O(dᵇ)节点的树，这很快就会变得太大而无法存储。（在你发布的版本中，甚至没有深度限制，这意味着你将生成整个游戏树。）
跟踪状态的方法是重写顶级的ALPHA-BETA-SEARCH函数，如下所示：
function ALPHA-BETA-SEARCH(state) returns an action best_a <- nil max_v <- -∞ for each a in actions(state) v <- MIN-VALUE(RESULT(state, a), +∞, max_v) if v > max_v then max_v <- v best_a <- a return best_a也就是说，你在主函数中“展开”了对MAX-VALUE的顶级调用。
请注意，在上面的函数中，你正在循环遍历每个动作a，计算它们的v。当某个v是你迄今为止找到的最大值时，你知道从中计算出这个值的动作目前是best_a。
