In this week’s post, I am going to explain how Pruning works in Minimax and Negamax algorithm.

Consider the algorithm starts its way by checking the foremost left side of the game tree. By seeing the current player (minimizing), you will know the value will be 3. Checking the middle branch of the tree, there will be other branches inside it, but do we have to check all of them? Since the algorithm has already gotten the value of 2, the best value will be less than or equal to 2. But, the algorithm knows that it already has the best value of 3 coming from the foremost left side, hence it doesn’t need to check the other branches. The same goes for the most right side of the branch.

Pruning in our algorithm is presented by using alpha and beta variables. Alpha will be used for maximizing player and Beta for minimizing player. Both of them start by using the worst possible value, hence -infinity for the alpha and infinity for the beta.

If the pruning is set to on, all the called Minimax functions will contain the value of alpha and beta from their respective parent condition.

If the algorithm meets the condition where the current node has more than 1 possible child condition, it will initiate a for loop to check each of them one by one. With that in mind, if the above condition is met where ALPHA >= BETA, it will break the for loop. Why? Because the algorithm has already gotten the best value from the other branch(es) that it has previously detected.

Different method applies when there is no possible child within the sight. It will still call the alpha and beta variables, but there won’t be a comparison between them. The algorithm no need to compare if there is nothing to compare (another possible child) beside the current child.