Current Step:

Ready to start

Game Tree with Alpha-Beta Pruning

Algorithm Execution

ALPHA-BETA-SEARCH(state):
v ← MAX-VALUE(state, -∞, +∞)
return the action in ACTIONS(state) with value v
MAX-VALUE(state, α, β):
if TERMINAL-TEST(state) then return UTILITY(state)
v ← -∞
for each a in ACTIONS(state) do
v ← MAX(v, MIN-VALUE(RESULT(s,a), α, β))
if v ≥ β then return v
α ← MAX(α, v)
return v
MIN-VALUE(state, α, β):
if TERMINAL-TEST(state) then return UTILITY(state)
v ← +∞
for each a in ACTIONS(state) do
v ← MIN(v, MAX-VALUE(RESULT(s,a), α, β))
if v ≤ α then return v
β ← MIN(β, v)
return v