Alpha-beta fail soft cut-off issue

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
ydebilloez
Posts: 70
Joined: Tue Jun 27, 2017 9:01 pm
Location: Lubumbashi
Full name: Yves De Billoëz
Contact:

Alpha-beta fail soft cut-off issue

Post by ydebilloez » Sat Jan 16, 2021 11:50 am

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
Posts: 11
Joined: Fri Dec 27, 2019 7:47 pm
Full name: Jacek Dermont

Re: Alpha-beta fail soft cut-off issue

Post by derjack » Sat Jan 16, 2021 12:17 pm

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.

User avatar
hgm
Posts: 25860
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Alpha-beta fail soft cut-off issue

Post by hgm » Sat Jan 16, 2021 12:24 pm

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
Posts: 70
Joined: Tue Jun 27, 2017 9:01 pm
Location: Lubumbashi
Full name: Yves De Billoëz
Contact:

Re: Alpha-beta fail soft cut-off issue

Post by ydebilloez » Sun Jan 17, 2021 11:30 am

derjack wrote:
Sat Jan 16, 2021 12:17 pm
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
Posts: 3951
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Alpha-beta fail soft cut-off issue

Post by Sven » Sun Jan 17, 2021 2:42 pm

ydebilloez wrote:
Sat Jan 16, 2021 11:50 am
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
hgm
Posts: 25860
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Alpha-beta fail soft cut-off issue

Post by hgm » Sun Jan 17, 2021 2:56 pm

ydebilloez wrote:
Sun Jan 17, 2021 11:30 am
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
Posts: 9
Joined: Tue Oct 06, 2015 3:00 pm

Re: Alpha-beta fail soft cut-off issue

Post by jwilson82 » Sun Jan 17, 2021 8:04 pm

ydebilloez wrote:
Sun Jan 17, 2021 11:30 am
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
Posts: 70
Joined: Tue Jun 27, 2017 9:01 pm
Location: Lubumbashi
Full name: Yves De Billoëz
Contact:

Re: Alpha-beta fail soft cut-off issue

Post by ydebilloez » Wed Jan 20, 2021 12:43 pm

jwilson82 wrote:
Sun Jan 17, 2021 8:04 pm
ydebilloez wrote:
Sun Jan 17, 2021 11:30 am
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
Posts: 70
Joined: Tue Jun 27, 2017 9:01 pm
Location: Lubumbashi
Full name: Yves De Billoëz
Contact:

Re: Alpha-beta fail soft cut-off issue

Post by ydebilloez » Wed Jan 20, 2021 12:47 pm

hgm wrote:
Sun Jan 17, 2021 2:56 pm
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
Posts: 3951
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Alpha-beta fail soft cut-off issue

Post by Sven » Wed Jan 20, 2021 12:56 pm

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!).
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Post Reply