5

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.

derjack
  • 144
  • 1
  • 10

3 Answers3

4

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.

fgb
  • 18,439
  • 2
  • 38
  • 52
  • That what I was doing. First level were moves themselves and the rest is calculating just scores. It's just they didn't mention it in Wikipedia and thought that I was missing something. – derjack Jul 16 '15 at 06:11
  • Returning the first one found seems to be very important! Thank you so much for clarifying, I was shuffling the nodes with the same score to get some "random" play, but retrospectively, that's not very smart. It results in unideal moves being played that aren't fully evaluated. – Marv Mar 11 '19 at 18:42
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.

xXliolauXx
  • 1,273
  • 1
  • 11
  • 25
0

Original poster is correct. If you use the equals it will give you sub-optimal results in many cases (at least with the specific algorithm I am using, which requires proper move being returned as well). I have a game I'm programming and using the equals I was getting non-optimal results (actually terribly non-optimal). Without the equals the results were exactly equivalent to the minmax algorithm. I think there is a lot of bad information on the web about minmax alpha/beta. Garbage actually. Cost me 8 hours of debugging before I figured it out.

Joe Mama
  • 1
  • It took me a while to understand this. Nowadays, at root I have the moves, and for each of the moves I use alphabeta search, then I can use the >= equals, which reduce the number of moves. It's just that most of the tutorials ignore the fact, that the root (1st level), it searches "fully". – derjack Aug 06 '23 at 21:17