Cropping Alphabeta, alpha is equal to or greater than beta. Why is it equal?

Question

While I understand the concept of a miniature tree and alpha beta, I don’t understand why in many (for example, wikipedia) resources about trimming alpha beta there is a condition like α> = β. In particular, equals are confusing. As far as I understand, alpha beta returns a movement that minmax will return, but basically makes it faster. But this example contradicts this:

. / | \ 1 3* 2 / | / \ | \ \ 1 1 5 3 4 3 2 

Above is the original min-max tree. As we can see, he will choose one step with a score of 3. Now let's do an alpha beta:

  . / | \ 1 3* 3* / | / \ | \ 1 1 5 3 4 3 

It cuts off the right move, because 3> = 3. But then the algorithm can choose between two moves, because they have the same score, but, as we saw in min-max, the correct choice is a little worse. This will not happen if the algorithm specifies simply α> β, so it will also need to look for 2.

So was there a typo in the pseudocode wikipedia (and many other resources)? Or I misunderstood something really big here.

Answer 1

The algorithm on Wikipedia does not return a move; it returns a node root score of 3. This is a score that matches the minimax result. You will need to slightly modify the algorithm to make the game play instead of rating.

One way to do this is to run the alphabeta function on every possible move from the current state and reproduce the highest score. After referencing wikipedia, it produces an implementation that does this.

I think you can also track the best move found in the alphabeta function, but if several nodes have the same score at the same level, return the first one found. This might be better because fewer nodes need to be evaluated.

Answer 2

The equals value is usually used because it provides a recognizable performance increase, and since your return value will not change from equal branches.

The only point at which it, at least, can be useful in the first search, but the performance loss here is worse.

Minimax relies on the opponent, who always plays on the best moves, and not on the thought that he makes mistakes. If you include some kind of special rating to choose the best of two equal branches, you would spend ressources on speculation (which you don't do in minimax because of this definition).

So, in general, it makes no sense not to use equals.