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.
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.