Alpha-Beta is a MinMax optimization.
MinMaxAB(Player, Depth, Alpha, Beta) { if ( Depth == 0 ) return Evaluation(Position) Generate_Moves(Player) Sort_Moves() Best_Score = -INFINITE
while ( Get_Next_Move(Move) ) { Make_Move(Move) Score = -MinMaxAB(-Player, Depth - 1, -Beta, -Alpha); UnMake_Move(Move) if ( Score > Best_Score ) { Best_Score = Score if ( Best_Score > Alpha ) { Alpha = Best_Score if ( Best_Score >= Beta ) return Best_Score } } } return Best_Score } |
B = Branching Factor = Average Moves by Position
D = Depth
T = Total Searched Positions
T(Best Case) = B ^ (D/2)
T(Worst Case) = B ^ D
MinMax = MinMaxAB (Worst Case)
Alpha-Beta efficiency is dependent on Move Sorting Function.
In this Tree, MinMax searches and evaluates all nodes (15 Nodes).
With AlphaBeta, MinMax does not search all nodes because the score of the upper node is transmitted to the lower node.
The lower node compare its Score with the upper node Score then return immediately if its Score is worst for upper player.
In this Tree, MinMax, with Alpha-Beta, searches only 11 Nodes instead of 15 Nodes without Alpha-Beta (Grayed Nodes are skipped).
