Stockfish-1.5 Detects mate then changes mind?

[zamar]

I wonder if you tried instead of skipping the rest of the moves to make a research with bigger depth after fail high(like you do after fail high in case of late move reductions)

There is going to be no difference in the score of the move that fail high but the rest of the moves are going to be searched with smaller depth.

In the next iteration you can simply skip the first move.

I've consider sth like this, but never tested it. It should not be too hard to implement, we could save the search depth for each root move separately. One question remains open: how to handle multiple fail-highs in row?

Note that skipping the first move in case that the branching factor was high in the last iteration may be also an interesting idea to try.
Here is an example from analysis by rybka.
The branching factor was very high at depth 24 because rybka needed a long time to get a score for Bd1 and rybka immediately get a score at depth 25 with the same pv so it seems simply to skip Bd1 at depth 25(this is from analysis of one of my correspondence games and I do not give the position and the pv).

Possibly Rybka uses some system to divide search time/nodes between moves (at root and perhaps also elsewhere in search tree). Finding the right recipe is the difficulty.

[mcostalba]

I wonder if you tried instead of skipping the rest of the moves to make a research with bigger depth after fail high(like you do after fail high in case of late move reductions)

There is going to be no difference in the score of the move that fail high but the rest of the moves are going to be searched with smaller depth.

In the next iteration you can simply skip the first move.

I've consider sth like this, but never tested it. It should not be too hard to implement, we could save the search depth for each root move separately. One question remains open: how to handle multiple fail-highs in row?

Yes this is an interesting problem:

First move at depth 12 fails high, so research with a wider window at depth 13 and suppose move returns score v that becomes our new alpha.

Now we do a zero window search of all the other moves at depth12 and one of them fails high.

What to do ? we trust the search at depth 13 or a failh high but at depth 12 ?

If we adopt the same logic used for hash table we should discard the fail high at depth 12 and continue, but then, the next natural question is why do we search the remaining moves at depth 12 if in any case we don't trust a possible fail high ?

In this case we should better skip the remaining moves at depth 12 altoghter and jump directly at depth 13....in this case we end up exactly in how is now implemented the fail high policy.

So the bottom line is that further developinng the idea of Uri we end up rediscovering the idea of Joona.

[Uri Blass]

I wonder if you tried instead of skipping the rest of the moves to make a research with bigger depth after fail high(like you do after fail high in case of late move reductions)

There is going to be no difference in the score of the move that fail high but the rest of the moves are going to be searched with smaller depth.

In the next iteration you can simply skip the first move.

I've consider sth like this, but never tested it. It should not be too hard to implement, we could save the search depth for each root move separately. One question remains open: how to handle multiple fail-highs in row?

Yes this is an interesting problem:

First move at depth 12 fails high, so research with a wider window at depth 13 and suppose move returns score v that becomes our new alpha.

Now we do a zero window search of all the other moves at depth12 and one of them fails high.

What to do ? we trust the search at depth 13 or a failh high but at depth 12 ?

If we adopt the same logic used for hash table we should discard the fail high at depth 12 and continue, but then, the next natural question is why do we search the remaining moves at depth 12 if in any case we don't trust a possible fail high ?

In this case we should better skip the remaining moves at depth 12 altoghter and jump directly at depth 13....in this case we end up exactly in how is now implemented the fail high policy.

So the bottom line is that further developinng the idea of Uri we end up rediscovering the idea of Joona.

I think that if you have another fail high at depth 12 you can do again a research at depth 13 with a wider window only for the specific move that failed high.

Uri

[mcostalba]

I think that if you have another fail high at depth 12 you can do again a research at depth 13 with a wider window only for the specific move that failed high.

Uri

Yes, I understand, but the point IMHO is another one: why do search moves at depth 12 if we _already_ have a PV move at depth 13 ?

In case we don't fail high with any of the remaining moves what do we have reached ? We have only wasted time because we could have used that time to search at depth 13 instead perhaps....

....or, in the case we have a fail high at depth 12 and we need to research at depth 13 why not search directly at depth 13 ?

So it is not clear to me, once we have a PV at depth 13 why we should insist on the remaining moves at depth 12 ?


Form what I have understood once you have a PV at depth 13 you should try to confute that PV at the same depth, not at a lower depth, or am I missing something ?

[Uri Blass]

I think that if you have another fail high at depth 12 you can do again a research at depth 13 with a wider window only for the specific move that failed high.

Uri

Yes, I understand, but the point IMHO is another one: why do search moves at depth 12 if we _already_ have a PV move at depth 13 ?

In case we don't fail high with any of the remaining moves what do we have reached ? We have only wasted time because we could have used that time to search at depth 13 instead perhaps....

....or, in the case we have a fail high at depth 12 and we need to research at depth 13 why not search directly at depth 13 ?

So it is not clear to me, once we have a PV at depth 13 why we should insist on the remaining moves at depth 12 ?


Form what I have understood once you have a PV at depth 13 you should try to confute that PV at the same depth, not at a lower depth, or am I missing something ?

I think that you practically can save time and may get better order of moves for depth 13.

You can save time because you can fail high faster(by searching the previous bad moves at depth 12 and not at depth 13)

you can get better order of moves thanks to getting different hash moves to refute other root moves at depth 12 when you can use the new hash moves at depth 13.

Uri

[bob]

If I understand correctly
The situation today is that stockfish may miss some good winning move that is not mate at depth 21 because it found some wrong mate in 12 score and it may need depth 22 for it.

Actually, when a new best move is found and the score is above the aspiration window, Stockfish doesn't try to resolve the fail high, but skips all the remaining moves at the current iteration, and starts searching the new best move at the next iteration. This is very radical, and seems so crazy that it obviously can't work. One of Joona's unique skills is coming up with such outrageous ideas, being brave enough to actually spend time implementing and testing them, and proving that they are tremendously effective in practice.

What do you do in this case:

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. But you are not going to search it, instead you skip to the next iteration before you discover this. There is another move that loses nothing. But it might be very hard to find this move since we are now one ply deeper...

It would seem quite dangerous to terminate the current iteration on a fail high when the score might be way bad still... Do you handle that case differently?

The old Belle (PVS) idea was safe enough. This seems pretty risky.

[zamar]

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.

[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.

My code makes this easy to change, I will try to give it a go on the cluster when I get a chance to see what the effect is.

[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

[zamar]

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

It's difficult to use the correct terms here, because there are two different kind of fail-highs here (aspiration fail-high and null-window search fail high). I posted the code to avoid misunderstandings.