Alpha-Beta剪枝用于裁剪搜索树中不需要搜索的树枝,以提高运算速度。它基本的原理是:
- 当一个 Min 节点的 β值≤任何一个父节点的α值时 ,剪掉该节点的所有子节点
- 当一个 Max 节点的 α值≥任何一个父节点的β值时 ,剪掉该节点的所有子节点
下面为只使用 MiniMax 和使用 Alpha-Beta 剪枝的简单对比。
需要注意的是,剪枝的效果与树节点的访问顺序有关。
Alpha-Beta剪枝的伪代码如下:
Initialize MAX_VALUE(node,game,-∞,∞)
function MAX_VALUE(state,game,α,β) returns the minimax value of state
inputs: state, current state in game
game, game description
α, the best score for MAX along the path to state
β, the best score for MIN along the path to state
if CUTOFF_TEST(state) then return EVAL(state)
for each s in SUCCESSORS(state) do
α = MAX(α, MIN_VALUE(s,game,α,β))
if α ≥ β then return β
end
return α
function MIN_VALUE(state,game,α,β) returns the minimax value of state
if CUTOFF-TEST(state) then return EVAL(state)
for each s in SUCCESSORS(state) do
β = MIN(β, MAX_VALUE(s,game,α,β))
if α ≥ β then return α
end
return β
下面用一个例子说明。规定从左节点开始展开。原搜索树为:
阅读更多…