Stockfish-1.5 Detects mate then changes mind?

[Uri Blass]

The code in stockfish means that the problem that Bob described does not happen but you did not mention it so I thought maybe I do not understand the code.

Uri

[mcostalba]

There is something more in root_search(), I repost the code with the missing piece.

Code: Select all

root_search(alpha, beta)
{
  for (int i = 0; i < RootMoveCount && alpha < beta; i++)
  {
    if (alpha >= beta)
    {
        // We failed high, invalidate and skip next moves, leave node-counters
        // and beta-counters as they are and quickly return, we will try to do
        // a research at the next iteration with a bigger aspiration window.
        rml.set_move_score(i, -VALUE_INFINITE);
        continue;
    }

    if (i == 0)
      value = -search_pv(-beta, -alpha)
    else 
    {
      value = -search(-alpha-1,-alpha)
      if (value > alpha)
        value = -search_pv(-beta,-alpha)
    }

    if (i == 0 || value > alpha)
      best_i = i

    if (value > alpha)
      alpha = value
  }
  return alpha;
}

[zamar]

Marco,

please note that I wrote everything in short form. There is an extra
"alpha < beta" condition compared to Stockfish code.

Code: Select all

for (int i = 0; i < RootMoveCount && alpha < beta; i++) 

[Sven]

There is something more in root_search(), I repost the code with the missing piece.

Code: Select all

root_search(alpha, beta)
{
  for (int i = 0; i < RootMoveCount && alpha < beta; i++)
  {
    if (alpha >= beta)
    {
        // Note that this condition is always false !!!
    }
    // ...
}

I don't believe this is close to the real code since the "if (alpha >= beta)" condition would never be true due to the loop condition.

Sven

[Sven]

I don't believe this is close to the real code since the "if (alpha >= beta)" condition would never be true due to the loop condition.

Actually the current Stockfish 1.5 source code from the JA site looks a bit different, more like this, so that it makes more sense:

Code: Select all

root_search(alpha, beta)
{
  for (int i = 0; i < RootMoveCount && !AbortSearch; i++)
  {
    if (alpha >= beta)
    {
        // We failed high ...
    }
    // ...
}

Sven

[Sven]

Code: Select all

    if (alpha >= beta)
    {
        // We failed high, invalidate and skip next moves, leave node-counters
        // and beta-counters as they are and quickly return, we will try to do
        // a research at the next iteration with a bigger aspiration window.
        rml.set_move_score(i, -VALUE_INFINITE);
        continue;
    }

Within this piece of code, which is from the currently published Stockfish 1.5 source, I wonder what the real intention is: either "quickly return", as stated in the comment, or "continue" (with the remaining moves). Only one of both can be meant, but which one?

Sven

[Sven]

Code: Select all

    if (alpha >= beta)
    {
        // We failed high, invalidate and skip next moves, leave node-counters
        // and beta-counters as they are and quickly return, we will try to do
        // a research at the next iteration with a bigger aspiration window.
        rml.set_move_score(i, -VALUE_INFINITE);
        continue;
    }

Within this piece of code, which is from the currently published Stockfish 1.5 source, I wonder what the real intention is: either "quickly return", as stated in the comment, or "continue" (with the remaining moves). Only one of both can be meant, but which one?

Sven

Found my fault. After detecting a fail high ("aspiration fail high"), all remaining moves are assigned -VALUE_INFINITE as move score in the root move list but not searched. So this is the "quick return", although it is not done with a "break" or "return" since some code has to be executed for the remaining root moves.

Sorry for making noise but it was not immediately obvious for me.

Sven

[bob]

Currently we stay with the original aspiration window no matter what happens. We don't ever research fail-high/low with bigger window, just allocate much extra time to (hopefully) be able to complete the next iteration. It works surpisingly often, but sometimes when facing a big fail low (like +4 -> +1), it really sucks.

Simplified code for root_search() goes like this:

Code: Select all

root_search(alpha, beta)
{
  for (int i = 0; i < RootMoveCount && alpha < beta; i++)
  {
    if (i == 0)
      value = -search_pv(-beta, -alpha)
    else 
    {
      value = -search(-alpha-1,-alpha)
      if (value > alpha)
        value = -search_pv(-beta,-alpha)
    }

    if (i == 0 || value > alpha)
      best_i = i

    if (value > alpha)
      alpha = value
  }
  return alpha;
}

root_search is called by standard iterative deepening routine which calculates the window [alpha, beta] based on previous iterations.

Maybe I do not understand this code but based on my understanding
the problem that bob discribed should not happen because you do not skip the rest of the moves in every fail high but only in fail high that is above beta

Bob's words are:

"You fail low at the root as the "best" moves loses a rook. You search and the next move fails high. Once you resolve it you realize it just loses a knight."

I think that in this case you continue to search at the same depth because assuming that
beta=0 before the fail low it continue to be 0 until the end of the iteration.

The only fail high that cause skipping the rest of the moves is fail high that cause you to get a positive score.

Uri

The above is not limited to one search depth. At depth=16 you fail low and decide you are losing a rook. At depth=17 you fail high on a move after the first move. Now you abort, and start depth=18. There may well be a much better move at depth=17 if you had just taken the time to find it. By skipping it, you start a search that is hard enough to complete that you might not see this.

I'm not a fan of the idea of pruning at the root like this, and that is exactly what is happening with this approach. We throw the rest of the moves out the window, and start the next iteration.

[Uri Blass]

Currently we stay with the original aspiration window no matter what happens. We don't ever research fail-high/low with bigger window, just allocate much extra time to (hopefully) be able to complete the next iteration. It works surpisingly often, but sometimes when facing a big fail low (like +4 -> +1), it really sucks.

Simplified code for root_search() goes like this:

Code: Select all

root_search(alpha, beta)
{
  for (int i = 0; i < RootMoveCount && alpha < beta; i++)
  {
    if (i == 0)
      value = -search_pv(-beta, -alpha)
    else 
    {
      value = -search(-alpha-1,-alpha)
      if (value > alpha)
        value = -search_pv(-beta,-alpha)
    }

    if (i == 0 || value > alpha)
      best_i = i

    if (value > alpha)
      alpha = value
  }
  return alpha;
}

root_search is called by standard iterative deepening routine which calculates the window [alpha, beta] based on previous iterations.

Maybe I do not understand this code but based on my understanding
the problem that bob discribed should not happen because you do not skip the rest of the moves in every fail high but only in fail high that is above beta

Bob's words are:

"You fail low at the root as the "best" moves loses a rook. You search and the next move fails high. Once you resolve it you realize it just loses a knight."

I think that in this case you continue to search at the same depth because assuming that
beta=0 before the fail low it continue to be 0 until the end of the iteration.

The only fail high that cause skipping the rest of the moves is fail high that cause you to get a positive score.

Uri

The above is not limited to one search depth. At depth=16 you fail low and decide you are losing a rook. At depth=17 you fail high on a move after the first move. Now you abort, and start depth=18. There may well be a much better move at depth=17 if you had just taken the time to find it. By skipping it, you start a search that is hard enough to complete that you might not see this.

I'm not a fan of the idea of pruning at the root like this, and that is exactly what is happening with this approach. We throw the rest of the moves out the window, and start the next iteration.

If you fail low at depth 16 and do not find a better move than losing a rook at that depth then you probably cannot find a saving move at depth 17.

The situation that you describe can happen but I guess that it is relatively rare and I guess that in near 99% of the cases the fail high that cause skipping the rest of the moves comes from non losing positions.

Uri

[bob]

Currently we stay with the original aspiration window no matter what happens. We don't ever research fail-high/low with bigger window, just allocate much extra time to (hopefully) be able to complete the next iteration. It works surpisingly often, but sometimes when facing a big fail low (like +4 -> +1), it really sucks.

Simplified code for root_search() goes like this:

Code: Select all

root_search(alpha, beta)
{
  for (int i = 0; i < RootMoveCount && alpha < beta; i++)
  {
    if (i == 0)
      value = -search_pv(-beta, -alpha)
    else 
    {
      value = -search(-alpha-1,-alpha)
      if (value > alpha)
        value = -search_pv(-beta,-alpha)
    }

    if (i == 0 || value > alpha)
      best_i = i

    if (value > alpha)
      alpha = value
  }
  return alpha;
}

root_search is called by standard iterative deepening routine which calculates the window [alpha, beta] based on previous iterations.

Maybe I do not understand this code but based on my understanding
the problem that bob discribed should not happen because you do not skip the rest of the moves in every fail high but only in fail high that is above beta

Bob's words are:

"You fail low at the root as the "best" moves loses a rook. You search and the next move fails high. Once you resolve it you realize it just loses a knight."

I think that in this case you continue to search at the same depth because assuming that
beta=0 before the fail low it continue to be 0 until the end of the iteration.

The only fail high that cause skipping the rest of the moves is fail high that cause you to get a positive score.

Uri

The above is not limited to one search depth. At depth=16 you fail low and decide you are losing a rook. At depth=17 you fail high on a move after the first move. Now you abort, and start depth=18. There may well be a much better move at depth=17 if you had just taken the time to find it. By skipping it, you start a search that is hard enough to complete that you might not see this.

I'm not a fan of the idea of pruning at the root like this, and that is exactly what is happening with this approach. We throw the rest of the moves out the window, and start the next iteration.

If you fail low at depth 16 and do not find a better move than losing a rook at that depth then you probably cannot find a saving move at depth 17.

The situation that you describe can happen but I guess that it is relatively rare and I guess that in near 99% of the cases the fail high that cause skipping the rest of the moves comes from non losing positions.

Uri

While it is not common, I do see it regularly. Score suddenly drops, then starts to climb over the next few iterations. Either way, this appears to be a problem. I did not look at their code, but assume they use aspiration search (can't think of a single reason why one would not). With aspiration search, score > beta is still not enough justification, in my mind, to skip the rest of the moves and start a new search. You can still fail low on the first move, reset the search window, and now start failing high on beta, for multiple moves. Except that if you give up after the first fail high and go to the next iteration, it is more than a little likely that you will be deep enough that you will never find the true best move, because the fail-high move will take so long to search.