infinite score & tt

[flok]

Hi,

Sanity check:
Some old code in my program checks when storing an entry in the transposition table, that the score is checkmate_score or less. So infinite would trigger an assert.
My question now is: is this check correct? I think it is but I'm not sure.
For example at the leaves the evaluate is called. This score can be outside alpha...beta range but then the final alpha of that position would be <= the starting alpha and thus no tt update would be performed.

Hmmm. So I think my question boils down to: can a search() return -/+ infinite?

[Robert Pope]

Hi,

Sanity check:
Some old code in my program checks when storing an entry in the transposition table, that the score is checkmate_score or less. So infinite would trigger an assert.
My question now is: is this check correct? I think it is but I'm not sure.
For example at the leaves the evaluate is called. This score can be outside alpha...beta range but then the final alpha of that position would be <= the starting alpha and thus no tt update would be performed.

Hmmm. So I think my question boils down to: can a search() return -/+ infinite?

When you record a score in the TT, it will always be the value of a search, either a current search, or a prior search that caused an adjustment in your alpha or beta bounds. So, can your evaluation return -/+ infinite? The highest mine can return is mate in 0, which has a value smaller than infinite.

[flok]

While tracking that infinite-value score I looked at the delta pruning code:
http://chessprogramming.wikispaces.com/ ... ample Code

Code: Select all

if ( val < alpha - BIG_DELTA ) &#123;
   return alpha;
&#125;

Am I right that this could return in theory +/- infinite? Or shouldn't it happen that qs is called with +/- infinite for either alpha or beta?

[Joost Buijs]

While tracking that infinite-value score I looked at the delta pruning code:
http://chessprogramming.wikispaces.com/ ... ample Code

Code: Select all

if ( val < alpha - BIG_DELTA ) &#123;
   return alpha;
&#125;

Am I right that this could return in theory +/- infinite? Or shouldn't it happen that qs is called with +/- infinite for either alpha or beta?

In theory it could happen when value < (-infinite - delta), but in practice it will never happen because value will never get that small.
If value gets <= -infinite or >= +infinite there must be a bug in your code somewhere.

There is nothing wrong with calling qs(-infinite, +infinite), but returning +/-infinite is definitely an error.

[hgm]

'Infinite' is the score I award in my engines to capturing a King, and it is chosen large enough so that the heuristic evaluation can never top it. (So that you don't walk into the trap of not wanting to checkmate when you have 5 Queens.) For determining the best move I initialize bestScore to -INF, and after that it can only increase. So it is also not possible for bestScore to ever get below -INF. It would only stay at -INF if none of the moves were legal (i.e. when they were all refuted by King capture).

Scores near -INF tend to increase towards zero because of the delayed-loss bonus. Alpha and beta can sometimes go outside the [-INF, INF] range because of their pre-adjustment for this bonus. But these cannot find their way into the score. Even with fail hard you only return alpha or beta when the bestScore was already outside that range, and when alpha or beta are already outside that range, it is not possible for the score to beat them.

[flok]

Thanks!

Found that it only happens with null-move enabled.

This is the call done for null-move:

Code: Select all

val = -search(sd, NULL, depthLeft - nmDepth, co, -beta, -(beta - 1), newHash, stopFlag, invalidBestSibblings, true, pv, false);

My NM never directly jumps into QS.
If beta is 32767 here, then it calls search() with -32767,-32766. Search() then goes through the movelist and may invoke qs with -beta,-alpha and thus 32766,32767.

So I wonder if the null-move needs special handling for this? Or qs?

[Sven]

Hi,

Sanity check:
Some old code in my program checks when storing an entry in the transposition table, that the score is checkmate_score or less. So infinite would trigger an assert.
My question now is: is this check correct? I think it is but I'm not sure.
For example at the leaves the evaluate is called. This score can be outside alpha...beta range but then the final alpha of that position would be <= the starting alpha and thus no tt update would be performed.

Hmmm. So I think my question boils down to: can a search() return -/+ infinite?

It depends on the type of score. An exact score will be in the range [score_for_being_checkmated_now .. score_for_mating_in_one_ply]. An upper or lower bound score can be outside of that range, so it could as well be -INF or +INF, depending on your search algorithms of course (not necessarily restricted to a null-move search). So you might want to modify your sanity check according to the type of score you want to store in TT.

[flok]

Hmmm. So I think my question boils down to: can a search() return -/+ infinite?

It depends on the type of score. An exact score will be in the range [score_for_being_checkmated_now .. score_for_mating_in_one_ply]. An upper or lower bound score can be outside of that range, so it could as well be -INF or +INF, depending on your search algorithms of course (not necessarily restricted to a null-move search). So you might want to modify your sanity check according to the type of score you want to store in TT.[/quote]

Yeah at this point I know that it has to do with the null-move code. Simple: disabling takes away the problem.
Mysterious.

[flok]

While tracking that infinite-value score I looked at the delta pruning code:
http://chessprogramming.wikispaces.com/ ... ample Code

Code: Select all

if ( val < alpha - BIG_DELTA ) &#123;
   return alpha;
&#125;

Am I right that this could return in theory +/- infinite? Or shouldn't it happen that qs is called with +/- infinite for either alpha or beta?

In theory it could happen when value < (-infinite - delta), but in practice it will never happen because value will never get that small.
If value gets <= -infinite or >= +infinite there must be a bug in your code somewhere.

There is nothing wrong with calling qs(-infinite, +infinite), but returning +/-infinite is definitely an error.

Did some debugging and found this:

Code: Select all

root: s(a, b) -32767, 79
1: s(-b, -a) -79, 32767
2: s(-b, -(b - 1)) -32767, -32766 NM
3: s(-b, -a) 32766, 32767
4: s(-b, -(b - 1)) -32767, -32766 NM
5: qs(-b, -a)) 32766, 32767
6qs: (assert)

infinite is 32767 in my code
At the root search() is called with -32767 for alpha and 79 for beta and so on. NM means that a null-move is executed.
So this null move makes a/b go to -32767,-32766. By this alpha ends up being 32766 and thus the assert triggers (

Code: Select all

        if &#40;bestVal < alpha - big_delta&#41; &#123;
                assert&#40;abs&#40;alpha&#41; <= 10000&#41;;
                return alpha;
        &#125;

[flok]

It depends on the type of score. An exact score will be in the range [score_for_being_checkmated_now .. score_for_mating_in_one_ply]. An upper or lower bound score can be outside of that range, so it could as well be -INF or +INF, depending on your search algorithms of course (not necessarily restricted to a null-move search). So you might want to modify your sanity check according to the type of score you want to store in TT.

Storing +/- infinite don't make sense to be put in tt I think. They tell you nothing, only that a search was not performed. Right?