Explore Courses Blog Tutorials Interview Questions
0 votes
in AI and Deep Learning by (50.2k points)

While I understand the MiniMax tree and alpha-beta pruning concept, I don't understand why in many (for example Wikipedia) resources about alpha-beta pruning there is a condition like α >= β. Specifically, equals is confusing. As I understand, the alpha-beta returns move that minmax would return, but mostly does it faster. But this example contradicts it:


      / |  \

    1   3* 2

  / |  / \ | \ \

  1 1 5   3 4 3 2

Above is the original min-max tree. As we can see it would choose the one move with score 3. Now let's do the alpha-beta:


      / |  \

    1   3* 3*

  / |  / \ | \

  1 1 5   3 4 3

It cuts off the right-most move because of 3 >= 3. But then the algorithm can choose between 2 moves because they have the same score, but as we saw in min-max the right choice is slightly worse. That wouldn't happen if algorithm specified simply α > β, so it would need to search 2 as well.

So was that a typo in Wikipedia's pseudocode (and many other resources)? Or I misunderstood something really big here.

1 Answer

0 votes
by (108k points)

The algorithm on Wikipedia returns the score of the root node which is 3. This score is the same as the minimax result. You would need to change the algorithm slightly to get the move to playing rather than the score.

One way of doing that is to run the alpha-beta function on each possible move from the current state and play the highest-scoring one. Refer the link which gives an implementation that performs this.

I think you could also keep track of the best move found within the alpha-beta function, but if multiple nodes have the same score at the same level, then return the first one found. This could be more beneficial because fewer nodes need to be evaluated.

Browse Categories