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
Figure ?? The alpha-beta search algorithm. Notice that these routines are the same as the MINIMAX functions in Figure ??, except for the two lines in each of MIN-VALUE and MAX-VALUE that maintain α and β (and the bookkeeping to pass these parameters along).