First post (and FailHigh question!)

[xmas79]

Hello everyone,
my name is Natale and (after a lot of years, again) I decided it was time to try develop a new engine from scratch.

After reading suggestions on this forum and wikis on internet, I actually created the (not so) basic structure:
- PVS
- Q-search
- ID
- IID
- TT
- Killers
- Basic Move Order
- Eval with material only

All the stuff (after fixing A LOT of bugs) seems to work properly, actually tested with mate positions only (as I don't have evaluation at all), but I have a question I cannot find an answer to:

In mate tests it often fails high at root (when can it fail high? it should have seen a mate already, right?), but the research gives back the original score. As an example I post some iteration of this basic KNB-K endgame:

Code: Select all

FEN: 8/8/3K4/8/8/3N4/8/3B3k w - -
--------------------------------------------------------------------------------
     time      depth    move        nps     score        line
--------------------------------------------------------------------------------
...
previous iterations omitted...
...
--------------------------------------------------------------------------------
 00:00:01.431   14     Bd1-c2       7.4M    +6.00        1. Bd1-c2    Kh1-g1
                                                         2. Bc2-b1    Kg1-f1
                                                         3. Bb1-a2    Kf1-g1
                                                         4. Ba2-b3    Kg1-f1
                                                         5. Bb3-d1    Kf1-g1
                                                         6. Bd1-c2    Kg1-f1
                                                         7. Bc2-b1    Kf1-g1
 00:00:01.524   14     Kd6-e5       6.9M    +6.50 >
 00:00:01.720   14     Kd6-e5       7.6M    +6.00        1. Kd6-e5    Kh1-g2
                                                         2. Ke5-f4    Kg2-h2
                                                         3. Kf4-g5    Kh2-g1
                                                         4. Bd1-f3    Kg1-h2
                                                         5. Bf3-e2    Kh2-g1
                                                         6. Be2-d1    Kg1-f1
                                                         7. Bd1-c2    Kf1-g1
...
iterations 15-16-17-18 omitted...
...
--------------------------------------------------------------------------------
 00:02:47.444   19     Kd6-e5       8.8M    +6.50 >
 00:03:24.178   19     Kd6-e5!!     9.5M  +MATE11        1. Kd6-e5    Kh1-h2
                                                         2. Ke5-f4    Kh2-h3
                                                         3. Bd1-e2    Kh3-h4
                                                         4. Nd3-e1    Kh4-h3
                                                         5. Be2-g4+   Kh3-h2
                                                         6. Kf4-f3    Kh2-g1
                                                         7. Bg4-h3    Kg1-h2
                                                         8. Kf3-g4    Kh2-g1
                                                         9. Kg4-g3    Kg1-h1
                                                        10. Bh3-g2+   Kh1-g1
                                                        11. Ne1-f3#

As shown above, at iteration 14 it fails high (search window is 50cp, n=b=300cp) but the score returned back by a research is still 6.00! It keeps failing high at iterations 15-16-17-18 but score is still 6.00 in research, then at ply 19 it finally sees a mate in 11 and report it correctly. Is this a search instability introduced by TT & co.? I tried to disable Killers,Q-search,IID, TT completely or TT-cutoffs only (so I can keep PV), and the problem seems to disappear only when disabling TT stuff (completely or cut-offs only, no difference) as it doesn't fail high anymore (and takes ages to mate...). Tried to debug this thing and it was hard, I saw a TT cut in the research returning the score 6.00. Now I'm not sure if it's a real TT bug or simply "search instability" I have live with... Switching side to move or colors behaves similar to this, except it's failing low (score is -6.00, fail-low with score less than -6.50, but score is back to -6.00 after research).


Best regards,
Natl.

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