Alphabeta pruning, alpha equals or greater than beta. Why equals?

Question

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 condition like α >= β. Specifically, the 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 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 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.

Answer 1

The algorithm on Wikipedia doesn't return a move, it returns the score of the root node which is 3. It's this score that's the same as the minimax result. You would need to modify the algorithm slightly to get the move to play instead of the score.

One way of doing that is to run the alphabeta function on each possible move from the current state and play the highest scoring one. Following the links on wikipedia gives an implementation that does this.

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

Answer 2

Usually, equals is used, since it makes a recognizable performance gain, and since your returned value won't change from equal branches.

The only point where it at least could be usefull ist in the first ply searchdepth, but the performance loss is the worst here.

Minimax relies on the opponent always playing best moves, and not on speculating wether he makes mistakes. If you include some special evaluation for choosing the better of two equal branches, you would spend ressources on speculating (which you don't do in minimax due to it's definition).

So all in all, there is no point in not using equals.