CODEWITHSUNDEEP
minimax
YellowPillow
YellowPillow

Reputation: 4270

How does alpha-beta pruning reduce run-time complexity?

I'm a bit confused about how alpha-beta pruning helps with run-time reduction for the minimax algorithm. Maybe my understanding of the minimax algorithm is wrong but I know that the naive version runs in O(b^d) where b is the branching factor and d is the search depth. Now with alpha-beta pruning we would reduce it to O(b^(3/4)d) on average. But doesn't the time taken to generate the game states still take O(b^d) time? Is the generation of all states not factored into the run-time of minimax, or is my understanding of the minimax algorithm wrong?

Upvotes: 2

Views: 2265

Answers (1)

xXliolauXx
xXliolauXx

Reputation: 1313

You are right, Alpha-Beta does not reduce the speed at which the moves are being generated.

What does do however is reducing the amount of game branches to be searched through Alpha-Beta-Cutoffs. Since moves should be generated only after a branch is sure to be searched, the moves for the alpha-beta subbranches will not have to be calculated, thus reducing the time complexity.

AB-Tree source:google

In the above picture I marked the moves that do not have to be generated. As you can see, although the rightmost branch is cut off at layer 2, the moves leading to layer too are still generated. But the moves following after the cutoff are saved. This is where the complexity is reduced.

Upvotes: 3

Related Questions