{ }
Initializing AlgoBuddy...
Optimizing your workspace
Optimizing your workspace
Enter 8 comma-separated numbers for leaf nodes.
Alpha-beta pruning is an optimization technique for the minimax algorithm that reduces the number of nodes evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Connect 4, etc.).
The algorithm maintains two values, Alpha and Beta, which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of, respectively.
Minimax explores all possible states in the game tree. For games like Chess, the number of states is astronomical. Alpha-beta pruning allows us to search much deeper in the same amount of time by cutting off branches that won't affect the final decision.
Worst Case: O(bd) (Same as minimax if search order is poor)
Best Case: O(bd/2) (With perfect move ordering, it effectively doubles search depth)
Space: O(d) where d is the maximum depth of the tree (due to recursion stack).
algorithm alphaBeta(node, depth, alpha, beta, isMaximizingPlayer)
if depth = 0 OR node.isTerminal( then)
return node.value
if isMaximizingPlayer then
bestVal ← -Infinity
for each child in node.children do
bestVal = Math.max(bestVal, alphaBeta(child, depth - 1, alpha, beta, false))
alpha = Math.max(alpha, bestVal)
if beta <= alpha then
break; // Beta cut-off
return bestVal
else
bestVal ← +Infinity
for each child in node.children do
bestVal = Math.min(bestVal, alphaBeta(child, depth - 1, alpha, beta, true))
beta = Math.min(beta, bestVal)
if beta <= alpha then
break; // Alpha cut-off
return bestVal