Alpha-beta fail soft cut-off issue

[ydebilloez]

Dear all,
I discovered following issue. I have to add 1 to beta on return, otherwise if 2 positions get equal evaluation, the wrong one might be considered.
Nowhere I could find any reference to this.

Code: Select all

    score = -ABFailSoft(brd, nDepth + 1, -beta, -alpha);
    if (brd.getSearchCompleted()) { // if aborting during search, scores might be irrelevant
      if (score >= beta) {
        return beta+1;
      }

Any thoughts on it?
Regards,

[derjack]

Are you calling alphabeta on all moves on the root level or just alphabeta? Alphabeta returns score that would return minimax, not the move (not always). Years ago I asked similar question on stack overflow.

Imagine minimax tree like this:

Code: Select all

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

And alphabeta:

Code: Select all

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

The alphabeta returns score 3, which would minimax return. But seemingly only one move has the exact 3, and the other move has at most 3. Your returning beta+1 works because then this second move has at most score-1 so it won't be chosen. But the issue with that is because if those 2 moves were really equal, only the first could be chosen.

[hgm]

The whole idea of alpha-beta pruning is that when two positions get equal score, only the one you encountered first will be considered. So it is always safe to return beta. (And hence you take a beta cutoff when score >= beta, rather than when score > beta.)

[ydebilloez]

Are you calling alphabeta on all moves on the root level or just alphabeta? Alphabeta returns score that would return minimax, not the move (not always). Years ago I asked similar question on stack overflow.
...
The alphabeta returns score 3, which would minimax return. But seemingly only one move has the exact 3, and the other move has at most 3. Your returning beta+1 works because then this second move has at most score-1 so it won't be chosen. But the issue with that is because if those 2 moves were really equal, only the first could be chosen.

I am calling AB on all moves on root level. I store the score of each move in the movelist and sort accordingly to find the best move. (Other implementations store the move at root level, so they do not suffer from this.)
If there are other moves at root level that return the same score, a wrong move can be selected. So hence the +1.
I want to use basic piece points (100,300,450,900=Q) to evaluate exchange variations, hence scores are equal all the time.

I will be trying with both >= and +1....

[Sven]

Dear all,
I discovered following issue. I have to add 1 to beta on return, otherwise if 2 positions get equal evaluation, the wrong one might be considered.
Nowhere I could find any reference to this.

Code: Select all

    score = -ABFailSoft(brd, nDepth + 1, -beta, -alpha);
    if (brd.getSearchCompleted()) { // if aborting during search, scores might be irrelevant
      if (score >= beta) {
        return beta+1;
      }

Any thoughts on it?
Regards,

Returning beta belongs into the fail-hard world. With fail-soft you should return score.

[hgm]

I am calling AB on all moves on root level. I store the score of each move in the movelist and sort accordingly to find the best move.

That is a flawed implementation. For one, scores from moves that failed low are upper limits, and might be arbitrarily poor. They should never be allowed to 'overtake' any move with an exact score during sorting; they should not be eligible for playing at all. The soring should preserve the order of moves with equal score, as only the first of those can have an exact score.

I am also not sure why you would want to do this. You can play only one move, so you can extract the best from the list. No reason to sort the others in whatever order.

[jwilson82]

I store the score of each move in the movelist and sort accordingly to find the best move.
If there are other moves at root level that return the same score, a wrong move can be selected. So hence the +1.

While I agree with HGM that sorting the entire list is overkill because...

• You only need the best move

• Bounded scores and exact scores aren't really the same, so you're sorting apples with oranges

...it sounds like your problem could be that your sort is unstable. A stable sort guarantees that elements with the same sort key maintain their relative order in the sorted list. That is, whichever move gave the best score first (ie earliest in the unsorted list) would be the first move in the sorted list

[ydebilloez]

I store the score of each move in the movelist and sort accordingly to find the best move.
If there are other moves at root level that return the same score, a wrong move can be selected. So hence the +1.

While I agree with HGM that sorting the entire list is overkill because...

• You only need the best move

• Bounded scores and exact scores aren't really the same, so you're sorting apples with oranges

...it sounds like your problem could be that your sort is unstable. A stable sort guarantees that elements with the same sort key maintain their relative order in the sorted list. That is, whichever move gave the best score first (ie earliest in the unsorted list) would be the first move in the sorted list

Sort algorithm: c++11 std::algorithm. But a lot of positions have the same score because I am only counting material.

I do not agree that you only need the best move. A move down 0.x pawns compared to another might be played.

• because this is how I play as a human player

• position evaluation might not be accurate

• we introduce some randomness in the move selection

• fewer variations in a tree lead to worse position

Some elaboration on point 1. How many times as a human player haven't you thought of a move for 30 minutes and finally reverting to the safer move because: it is more like likely played in this opening, just developing a piece, consolidating a defence, just because in the last minute you saw a possible refutation to your best move that you don't want to evaluate, you try to trick your opponent in playing in zeitnot....
A program could use parallel algorithms and select the move that comes out more frequently with different algorithms in the top list...

The idea is to count everything up to ply x, and then research with only the best x moves to ply y. So therefore, an algorithm that only returns the best move without caring for the others might not be filling its refutation tables right.

[ydebilloez]

I am also not sure why you would want to do this. You can play only one move, so you can extract the best from the list. No reason to sort the others in whatever order.

I was thinking of a sorting algorithm that sorts the best x moves, and leaves all the other scores as soon as there is a score gap unsorted, and the deeper we go in the variations, the fewer moves we want to maintain. (Thinking like a human, not like an algorithm)

[Sven]

Regarding the alpha-beta algorithm, the root node is not different from other nodes down the tree, except for the minor fact that you need score and move there while everywhere else you are only interested in the score. So you should use basically the same alpha-beta code at the root, like in:

Code: Select all

bestScore = -INF
bestMove = MOVE_NONE
for (m in "all legal moves") {
    makeMove(m)
    score = -alphaBeta(pos, -beta, -max(alpha, bestScore), depth - 1)
    unmakeMove(m)
    if (score >= beta) {
        // won't happen at root when using (alpha = -INF, beta = +INF)
        // but may happen when using aspiration windows
        return score
    }
    if (score > bestScore) {
        bestScore = score
        bestMove = m
        if (score > alpha) {
            printPV(...)
        }
    }
}
return (bestMove, bestScore)

So no additional sorting is needed and no "beta + 1". Also it is very important for alpha-beta to work that you take the first of possibly several moves with equal score, since all subsequent moves are not guaranteed to actually have that same score but only "equal or lower" (since the alpha-beta principle takes the first refutation, not necessarily the best one!).