Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Alpha-beta pruning for Minimax

I have spent a whole day trying to implement minimax without really understanding it. Now, , I think I understand how minimax works, but not alpha-beta pruning.

This is my understanding of minimax:

  1. Generate a list of all possible moves, up until the depth limit.

  2. Evaluate how favorable a game field is for every node on the bottom.

  3. For every node, (starting from the bottom), the score of that node is the highest score of it's children if the layer is max. If the layer is min, the score of that node is the lowest score of it's children.

  4. Perform the move that has the highest score if you are trying to max it, or the lowest if you want the min score.

My understanding of alpha-beta pruning is that, if the parent layer is min and your node has a higher score than the minimum score, then you can prune it since it will not affect the result.

However, what I don't understand is, if you can work out the score of a node, you will need to know the score of all nodes on a layer lower than the node (in my understanding of minimax). Which means that you'llstill be using the same amount of CPU power.

Could anyone please point out what I am getting wrong? This answer ( Minimax explained for an idiot ) helped me understand minimax, but I don't get how alpha beta pruning would help.

Thank you.

like image 834
apscience Avatar asked Oct 25 '11 11:10

apscience


People also ask

How do you implement Alpha-Beta pruning in minimax?

How does alpha-beta pruning work? Initialize alpha = -infinity and beta = infinity as the worst possible cases. The condition to prune a node is when alpha becomes greater than or equal to beta. Start with assigning the initial values of alpha and beta to root and since alpha is less than beta we don't prune it.

What is Alpha-Beta in minimax?

Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization technique for the minimax algorithm. As we have seen in the minimax search algorithm that the number of game states it has to examine are exponential in depth of the tree.

Why Alpha-Beta pruning is better than minimax?

Both algorithms should give the same answer. However, their main difference is that alpha-beta does not explore all paths, like minimax does, but prunes those that are guaranteed not to be an optimal state for the current player, that is max or min. So, alpha-beta is a better implementation of minimax.

How does Alpha-Beta pruning change the result of the minimax tree search?

If we apply alpha-beta pruning to the standard minimax algorithm it gives the same decision as that of standard algorithm but it prunes or cuts down the nodes that are unusual in decision tree i.e. which are not affecting the final decision made by the algorithm.


2 Answers

To understand Alpha-Beta, consider the following situation. It's Whites turn, white is trying to maximize the score, black is trying to minimize the score.

White evaluates move A,B, and C and finds the best score is 20 with C. Now consider what happens when evaluating move D:

If white selects move D, we need to consider counter-moves by black. Early on, we find black can capture the white queen, and that subtree gets a MIN score of 5 due to the lost queen. However, we have not considered all of blacks counter-moves. Is it worth checking the rest? No.

We don't care if black can get a score lower than 5 because whites move "C" could keep the score to 20. Black will not choose a counter-move with a score higher than 5 because he is trying to MINimize the score and has already found move with a score of 5. For white, move C is preferred over move D as soon as the MIN for D (5 so far) goes below that of C (20 for sure). So we "prune" the rest of the tree there, pop back up a level and evaluate white moves E,F,G,H.... to the end.

Hope that helps.

like image 139
phkahler Avatar answered Sep 27 '22 20:09

phkahler


You don't need to evaluate the entire subtree of a node to decide its value. Alpha Beta Pruning uses two dynamically computed bounds alpha and beta to bound the values that nodes can take.

Alpha is the minimum value that the max player is guaranteed (regardless of what the min player does) through another path through the game tree. This value is used to perform cutoffs (pruning) at the minimizing levels. When the min player has discovered that the score of a min node would necessarily be less than alpha, it need not evaluate any more choices from that node because the max player already has a better move (the one which has value alpha).

Beta is the maximum value that the min player is guaranteed and is used to perform cutoffs at the maximizing levels. When the max player has discovered that the score of a max node would necessarily be greater than beta, it can stop evaluating any more choices from that node because the min player would not allow it to take this path since the min player already has a path that guarantees a value of beta.

I've written a detailed explanation of Alpha Beta Pruning, its pseudocode and several improvements: http://kartikkukreja.wordpress.com/2014/06/29/alphabetasearch/

like image 21
Kartik Kukreja Avatar answered Sep 27 '22 20:09

Kartik Kukreja