First post (and FailHigh question!)

[Chan Rasjid]

About two months back, I started a thread "My program cannot mate KRK/KQK". The bug was finally traced to the way I stored mate scores wrongly in the TT. Very likely, your bug could also be the same as you mentioned the peculiarity disappeared when TT is disabled.

I need to clarify certain things. I assume you use an aspiration window of 50cp as you mention so you do root search with [alpha, beta] where beta-alpha = 50 cp. Fail high with score 6.00 means your root search returned 6.00 >= beta and you did a research; but the score returned is again 6.0 as you mentioned.

Q: What aspiration window [alpha, beta] did you use for the research? You should try research with an infinite window to see what's happening; ie [-infi, +infi].

The way to hash +mate scores is by a ply adjustment:
storehash(depth, mate_score + ply, ...)
when we retrieve a +mate score, we reversed the ply adjustment by subtracting the ply.
For -mate scores, all the adjustments are sign reversed.


I believe your program can play a match with xboard or winboard. Then try a KQK position. Even with material only, your engine should be able to find mate if there is no major bug in your program.

Best Regards,
Rasjid.

[xmas79]

Hi Chan,
thank you for your reply. Your thread was the first I read about this problem, I had it too but "unfortunately" it's already fixed... So the problem I don't think is there... I tested by playing manually every move and have a look in TT entries, and the score stored/retrieved (and mate annoucement) is correct. I actually don't have interfaces to xboard/winboard and no "play mode", only "analysis mode" where the engine keeps iterating until mate is found...

Best regards,
Natl.

[xmas79]

...
I need to clarify certain things. I assume you use an aspiration window of 50cp as you mention so you do root search with [alpha, beta] where beta-alpha = 50 cp. Fail high with score 6.00 means your root search returned 6.00 >= beta and you did a research; but the score returned is again 6.0 as you mentioned.

Q: What aspiration window [alpha, beta] did you use for the research? You should try research with an infinite window to see what's happening; ie [-infi, +infi].

Sorry, I should have been more precise. Beta-Alpha=100cp, so "aperture" is 50cp, window is 100cp. Material evaluation is 6.00, so since iteration 1 search window is [5.50 6.50], and every search fails-high with score >= 6.50 (I already know it is a "mate in N" score, since score can be higher than 6.00 only if a mate is found). Then I open beta to +INF so that research is [5.50 +INF] and it returns a score of 6.00, AKA the material value again.

Best regards,
Natl.

[Chan Rasjid]

...
I need to clarify certain things. I assume you use an aspiration window of 50cp as you mention so you do root search with [alpha, beta] where beta-alpha = 50 cp. Fail high with score 6.00 means your root search returned 6.00 >= beta and you did a research; but the score returned is again 6.0 as you mentioned.

Q: What aspiration window [alpha, beta] did you use for the research? You should try research with an infinite window to see what's happening; ie [-infi, +infi].

Sorry, I should have been more precise. Beta-Alpha=100cp, so "aperture" is 50cp, window is 100cp. Material evaluation is 6.00, so since iteration 1 search window is [5.50 6.50], and every search fails-high with score >= 6.50 (I already know it is a "mate in N" score, since score can be higher than 6.00 only if a mate is found). Then I open beta to +INF so that research is [5.50 +INF] and it returns a score of 6.00, AKA the material value again.

Best regards,
Natl.

The only thing I can see is what you already know.

As your evaluation is only material and the game position is KNB-K, it means all scores returned from search, even those from TT cutoff, can only be:
0 (draw), +- 300.00, +-600.00 or +- mate_score.

I think you are using fail-hard and so you could not catch the actual score that search() returned that was >= 650.00.

Almost all decent chess programs use fail-soft; ie search() always returns the exact score:
1) on fail low, do not return alpha, but the score (<= alpha).
2) on fail high, return score (>= beta), not beta.

If it is easy to change to fail soft, then you may catch what is the real score returned by search(). In this way, you may have hints to your bug.

You'll have to wait and see if others can help to trace you bug.

Best Regards,
Rasjid.

[Chan Rasjid]

One more thing.

The rule of thumb in debugging is "homing in" exactly what we are certain of. In your case, scores >= 650.00 can only be +mate scores. But in a research, it failed to find the mate, but found only a score of 600.00. So the bug is likely related to TT; error with storing hash scores or error when you retrieve hash scores, more likely with mate type scores.

Go over those lines N times!

Best Regards,
Rasjid.

[Sven]

...
I need to clarify certain things. I assume you use an aspiration window of 50cp as you mention so you do root search with [alpha, beta] where beta-alpha = 50 cp. Fail high with score 6.00 means your root search returned 6.00 >= beta and you did a research; but the score returned is again 6.0 as you mentioned.

Q: What aspiration window [alpha, beta] did you use for the research? You should try research with an infinite window to see what's happening; ie [-infi, +infi].

Sorry, I should have been more precise. Beta-Alpha=100cp, so "aperture" is 50cp, window is 100cp. Material evaluation is 6.00, so since iteration 1 search window is [5.50 6.50], and every search fails-high with score >= 6.50 (I already know it is a "mate in N" score, since score can be higher than 6.00 only if a mate is found). Then I open beta to +INF so that research is [5.50 +INF] and it returns a score of 6.00, AKA the material value again.

Best regards,
Natl.

Hi Natale,

I can imagine that the fail-high in iteration 14 is already wrong and you must find the reason for it. Since you don't have any evaluation apart from material and you don't find the mate in 21 plies already in iteration 14 there must be some error that causes the fail-high. Maybe there is some condition that lets your program pass a wrong value from the TT to the search, e.g. related to bounds? I think the research behaviour looks correct: when not seeing the mate, returning 6.00 when searching with [5.50 + INF] looks o.k. in your case.

Sven

[Sven]

Almost all decent chess programs use fail-soft; ie search() always returns the exact score:
1) on fail low, do not return alpha, but the score (<= alpha).
2) on fail high, return score (>= beta), not beta.

I agree that using fail-soft may give a hint in this case. I'm not so sure whether so many programs actually use fail-soft. But I disagree on your description of fail-soft: it does not "always return the exact score", at least this can be misunderstood. On failing low or high it returns bounds the same way as fail-hard does, the only difference is that these bounds can be < alpha or > beta.

You can rewrite fail-hard and fail-soft alphabeta to fully equivalent code such that there is only one line of difference between both, and that is the initialization of the best score (initialized to alpha vs. -INF) prior to the move loop. This is done by always passing [-beta, -Max(alpha, bestScore)] to the next level, and by always returning bestScore.

Sven

[hgm]

I'm not so sure whether so many programs actually use fail-soft.

Because in combination with hashing it is an improvement without any trade-offs. You will see hash hits causing a cutoff that otherwise would not have been possible because the score bound was too high (or low), just because when storing it you carelessly rounded the bound to alpha or beta. And there is no downside.

[tpetzke]

You will see hash hits causing a cutoff that otherwise would not have been possible because the score bound was too high (or low), just because when storing it you carelessly rounded the bound to alpha or beta.

I thought a score outside the alpha - beta window can't be trusted. Bob once stated that in an all node the move with the highest score is not necessarily the best, the scores have no meaning. I agree you get more cutoffs but does it at the end really improve the quality of the search?

Have you tested it? How much was it worth using fail soft over fail hard ?

Thomas...

[xmas79]

Almost all decent chess programs use fail-soft; ie search() always returns the exact score:
1) on fail low, do not return alpha, but the score (<= alpha).
2) on fail high, return score (>= beta), not beta.

I agree that using fail-soft may give a hint in this case. I'm not so sure whether so many programs actually use fail-soft. But I disagree on your description of fail-soft: it does not "always return the exact score", at least this can be misunderstood. On failing low or high it returns bounds the same way as fail-hard does, the only difference is that these bounds can be < alpha or > beta.

You can rewrite fail-hard and fail-soft alphabeta to fully equivalent code such that there is only one line of difference between both, and that is the initialization of the best score (initialized to alpha vs. -INF) prior to the move loop. This is done by always passing [-beta, -Max(alpha, bestScore)] to the next level, and by always returning bestScore.

Sven

Hi all,
I think I have a fail-soft framework already:

Code: Select all

search(alpha,beta)
  gen_moves();
  for each move
    make
    if (first_move)
      score = -search(-beta, -alpha);
    else
    {
        score = -search(-alpha - 1, -alpha);
        if (score > alpha && score < beta) // research only if non pv nodes
          score = -search(-beta, -alpha);
    }
    unmake
    if (score >= beta)
        return score;
    if (score > alpha)
        alpha = score;
  end for

  // mate or stalemale?
  if (moves_tried == 0)
  {
     if (in check) return LOST+ply; else return DRAW;
  }

  return alpha;
end search

I'm still debugging this problem, but as far as I can see, I can tell the research code works as expected, as tracing to the mate position at ply 14 it backup to ply 13 a -mate_score_in_x, so ply 13 fails-high with score +mate_score_in_x to ply 12, but then ply 12 tries next move and improves alpha from -mate to -6.00, so score backed-up to ply 11 is not -matescore_in_x but is -6.00, which will be flip-flopped by negasearch until root is reached with positive sign, hence the score of +6.00. Still investigating why it fails-high at ply 14. A lot of nodes to look through... Maybe the problem is here and not in the research. Problem is that research is fair easy to trace because I already know the search will follow PV... the search before, instead, have a complete different move ordering....... I'm trying also to investigate this problem on other positions where depths are less than 14...