First post (and FailHigh question!)

[Chan Rasjid]

Hello Natale,

I see Sven too had just replied, but I only briefly browse through his post without raking my brain too much.

Let me explain it more precisely... We already know that original position is mate in 11, and there's no doubt about it. So suppose a ply 22 search returned already that mate score (32000-21 = 31979). Let's suppose I do not stop iterating at ply 22 (as I found the minimal mate and I could stop searching), and keep iterating. Let's suppose we are starting iteration at depth 26. Is it possible to reach the original position at ply different than 0 and get a hash hit? Well, yes, by a long sequence of moves that leads to the same position after exactly 26 plies. We can suppose it can happen because TT entries can be overwritten, PV sometimes is truncated, move order at this point can be completely random and I have no evaluation that drives search towards best moves (and that's another story...)
In this case we are at ply=26 and can get a hash hit (draft condition is OK and hash signature is OK) returning a score back that is 31979. At this point, we will adjust the score by subtracting 26 plies from 31979 ---> 31953 ---> which is a mate in 47 plies even if horizon is at ply 26. So I have just replaced my "mate in 21 plies" TT entry with one that says "mate in 47 plies"... And this entry can be in turn be hit and get replaced by another "mate in 85 plies" and so on...

My intuition says this is happening here, but I can't explain better than this, and I have no other means to explain this behaviour... Maybe what I wrote is completely wrong, but I need something that points my eyes on the (very subdole) bug (if any), because if this is not a "standard" behaviour, well I really don't have idea of what's happening here and of what I'm really doing....

I think I now understand what's happening.

Believe me! Read my lips! There is nothing wrong with your search. Everything's fine and your
search is behaving "normally". Your description is also all correct.

My guess (hopefully correct) is that you did not implement what most of us do - returning a draw score of zero on the first repetition.

1) There is the draw rule for a three-fold repetition. Most program don't wait till three repetition. After a move is executed, there is a loop to detect a first repetition; mine is like this :

Code: Select all

        makemove(*move, side);

        if &#40;currstack->fifty < 100&#41; &#123;
            /* a rep move is valid as it repeats a valid move.
             * 1st possible repetition is each side 2 moves/fifty >= 4 */
            for &#40;i = 4; i <= currstack->fifty; i += 2&#41; &#123;
                if &#40;currstack->hash ^ &#40;currstack - i&#41;->hash&#41;;
                else &#123;
                    x = DRAW0;/* 1st repetiton scored as a draw == 0 */
                    pv&#91;ply + 1&#93;&#91;0&#93; = 0;
                    goto SET_BEST;
                &#125;
            &#125;
        &#125; else &#123;
            x = DRAW0;/* fifty draw */
            pv&#91;ply + 1&#93;&#91;0&#93; = 0;
            goto SET_BEST;
        &#125;

2) Your post exposed the fact that I don't really understand alpha-beta and the chess tree too well despite many years working on my engine. What the +mate score inf - N (in your case 32000 - N) mean is not really "mate in N plies from the root" - a misconception that somehow sticks with me. It is more correctly "mate in N half-moves from the root position". The graph tree seem to convey the picture that a leave node is very high up the tree and, therefore, "very far" from the root - wrong!

When your search at root did the depth 26 iteration, and at ply 26 at a leaf node, repeats the same position as that at the root. TT probe gives mate-in-26. Before returning with a fail high, your "always overwrite" TT scheme would rehashed that position as mate-in-47 - it is all proper. What it means is that from the leaf node at ply 26, you could checkmate by (traveling to the moon and back!) by taking a path that repeats (do many backmoves, ...) many of the positions earlier along the line playing until you reach the root-position - that's 26 half-moves! Now you go for the kill- take another 22 half-moves and announce - Checkmate. That's a mate-in-47.

Sorry that I did not read your earlier posts very carefully and miss the point.

Best Regards,
Rasjid.

[Sven]

I think I now understand what's happening.

Well, I am not so sure ...

My guess (hopefully correct) is that you did not implement what most of us do - returning a draw score of zero on the first repetition.

Returning a draw score on the first repetition of a position that belongs to the search tree (instead of the second repetition) is an optimization. It is not unimportant but not doing so should not lead to incorrect results as long as you detect the second repetition, it would just waste some time.

2) Your post exposed the fact that I don't really understand alpha-beta and the chess tree too well despite many years working on my engine.

What the +mate score inf - N (in your case 32000 - N) mean is not really "mate in N plies from the root" - a misconception that somehow sticks with me. It is more correctly "mate in N half-moves from the root position".

So what is your explanation of the difference between "plies" and "half-moves"? I don't see any "misconception" ...

When your search at root did the depth 26 iteration, and at ply 26 at a leaf node, repeats the same position as that at the root. TT probe gives mate-in-26. Before returning with a fail high, your "always overwrite" TT scheme would rehashed that position as mate-in-47 - it is all proper. What it means is that from the leaf node at ply 26, you could checkmate by (traveling to the moon and back!) by taking a path that repeats (do many backmoves, ...) many of the positions earlier along the line playing until you reach the root-position - that's 26 half-moves! Now you go for the kill- take another 22 half-moves and announce - Checkmate. That's a mate-in-47.

This is a wrong approach. If you get a hash hit you return from the node without storing anything again in the TT. You only store a value in the TT that results from actually having done a search, not from only reading the TT itself. Everything else is nonsense in my eyes. And even if you would do so then a move path that returns "mate in 21 plies" is still better than another move path returning "mate in 47 plies" so the latter must be rejected and must not pop up at the root.

Sven

[xmas79]

Guys, guys,
let's all take a breath... I'm gonna start a veeeery looong debugging session until I find this bug....

Back to the thread:
I *do* check for 50 moves rule and 3 repetition *before* probing hashtable. If code detects a draw by one of those two rules I simpy return zero. Then I probe hash and in case of hit I return the value.
Then I'm storing values into hashtables in all nodes types with the following priority:
- Cut node ---> score > beta ---> store hash, killer, best move
- PV node --> alpha improved ---> store hash, killer, pv, best move
- all node --> when score < alpha ---> store hash (for scoring), no killer, no best move
I think that's plain simple and logical. In code this would translate to:

Code: Select all

if (50moves or 3foldrep) return draw;
if (hash_hit) return hash_score (with bound checking etc..etc..)
for each move
  score = -search(....); // search and research stuff, pv, non pv etc...
  if (score > beta)
   ...cut node... store a SCORE_IS_AT_LEAST bound

  if(score> alpha)
    ... pv node... store pv and keep best move
end for

if (alpha not improved)
   ... all node....  store a SCORE_IS_AT_MOST bound
else
   ... pv node... store an EXACT alpha bound in hash with best move 

Then... The example at ply 26, was only an example... I simply thought that starting with a known position would allow you to understand better my thinking. What I really meant is that all this stuff happens at depths < 21. E.g. instead of being at depth 26, let's be at depth 16 and do all this stuff. If black does very dumb moves it will be mated in far less than 21 plies, so at ply 15 the program CAN see a mate in 14 plies. And at depth 16, an hash hit can cause a mate score to be "adjusted" to a value like "mate in 18 plies", and at aply 16 that mate score can be "adjusted" one more time to a "mate in 26 plies" and so on...
By the way, I just let my program iterate beyond iteration 22... From depth 22 onward (actually I let it arrive at depth 31) it annouces mate in 11 moves (21 plies), no more, no less, and keep telling the correct PV.

Code: Select all

--------------------------------------------------------------------------------
 00:07:31.876   31     Kd6-e5!!     8.2M  +MATE11        1. Kd6-e5    Kh1-g2
                                                         2. Ke5-f4    Kg2-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#

I'm really struggling to find the key, but my implementation seems very linear, and I cannot find the way.... And of coure I forgot to say I obviously do not allow duplicate entries in TT & killers....

buG I still haven't found what I'm looking for...


Natl.

[syzygy]

Then I'm storing values into hashtables in all nodes types with the following priority:
- Cut node ---> score > beta ---> store hash, killer, best move
- PV node --> alpha improved ---> store hash, killer, pv, best move
- all node --> when score < alpha ---> store hash (for scoring), no killer, no best move
I think that's plain simple and logical.

Make it:
- Cut node ---> score >= beta ---> store hash, killer, best move
- PV node --> alpha improved ---> store hash, killer, pv, best move
- all node --> when score <= alpha ---> store hash (for scoring), no killer, no best move

Your code:

Code: Select all

if (hash_hit) return hash_score (with bound checking etc..etc..) 

The "bound checking" implementation may of course contain errors.

Code: Select all

 if (score > beta)

>=

Code: Select all

if (alpha not improved)

How do you test this? Hopefully not with "score < alpha" or "score <= alpha" but with "best_score <= original_alpha" where you initialise best_score to -INF, original_alpha to alpha and update both best_score and alpha each time the returned score for a particular searched move is greater.

So:

Code: Select all

best_score = -INF
original_alpha = alpha

for each move
  score = -search(-beta, -alpha)
  if (score >= beta)
    .. cut ..
  if (score > alpha) {
    .. pv..
    alpha = score
  }
  if (score > best_score)
    best_score = score
end for

if &#40;best_score <= original_alpha&#41;
  .. all node ... store best_score
else
  .. pv node..

This is fail-soft. A bit simpler is fail-hard:

Code: Select all

original_alpha = alpha

for each move
  score = -search(-beta, -alpha)
  if (score >= beta)
    .. cut ..
  if (score > alpha) {
    .. pv..
    alpha = score
  }
end for

if (alpha == original_alpha)
  .. all node ... store alpha
else
  .. pv node..

[xmas79]

Hi Ronald,

Then I'm storing values into hashtables in all nodes types with the following priority:
- Cut node ---> score > beta ---> store hash, killer, best move
- PV node --> alpha improved ---> store hash, killer, pv, best move
- all node --> when score < alpha ---> store hash (for scoring), no killer, no best move
I think that's plain simple and logical.

Make it:
- Cut node ---> score >= beta ---> store hash, killer, best move
- PV node --> alpha improved ---> store hash, killer, pv, best move
- all node --> when score <= alpha ---> store hash (for scoring), no killer, no best move

Your code:

Code: Select all

if (hash_hit) return hash_score (with bound checking etc..etc..) 

The "bound checking" implementation may of course contain errors.

Code: Select all

 if (score > beta)

>=

Code: Select all

if (alpha not improved)

How do you test this? Hopefully not with "score < alpha" or "score <= alpha" but with "best_score <= original_alpha" where you initialise best_score to -INF, original_alpha to alpha and update both best_score and alpha each time the returned score for a particular searched move is greater.

So:

Code: Select all

best_score = -INF
original_alpha = alpha

for each move
  score = -search(-beta, -alpha)
  if (score >= beta)
    .. cut ..
  if (score > alpha) {
    .. pv..
    alpha = score
  }
  if (score > best_score)
    best_score = score
end for

if &#40;best_score <= original_alpha&#41;
  .. all node ... store best_score
else
  .. pv node..

This is fail-soft. A bit simpler is fail-hard:

Code: Select all

original_alpha = alpha

for each move
  score = -search(-beta, -alpha)
  if (score >= beta)
    .. cut ..
  if (score > alpha) {
    .. pv..
    alpha = score
  }
end for

if (alpha == original_alpha)
  .. all node ... store alpha
else
  .. pv node..

Sorry, typos. Yes beta cut-off condition is >=, improving alpha check at the end of the function is done by "originalAlpha != alpha" where original_alpha is initialized to alpha and bestScore is initialized to -INF and I update both of course. "alpha != original_alpha" vs "best_score <= original_alpha" is the same I suppose, since improving alpha once leads to make both tests to fail.

Bound checking in HT probing is:
if (exact_score && score_is_strictly_within_alpha_beta) return value; // pv node
if (score_is_at_least && value >= beta) return value; // beta cut-off
if (score_is_at_most && value <= alpha) return value; // alpha cut-off

Best regards,
Natale.

[syzygy]

"alpha != original_alpha" vs "best_score <= original_alpha" is the same I suppose, since improving alpha once leads to make both tests to fail.

They are exactly opposite, so probably this is another typo and you mean alpha == original_alpha

Code: Select all

Bound checking in HT probing is:
if (exact_score && score_is_strictly_within_alpha_beta) return value; // pv node

If the score is exact you can and should always return that value directly. The score is exact, so you can't go wrong.

if (score_is_at_least && value >= beta) return value; // beta cut-off
if (score_is_at_most && value <= alpha) return value; // alpha cut-off

This seems correct.

As has already been stated, you should correct the tt score in case of a mate value. Say you score a mate as -10000 and mate in 1 as 9999, then:

Code: Select all

/* retrieve score from tt */
value = ttentry->value;
if (value > 9900)
  value -= plies_from_root;
else if &#40;value < -9900&#41;
  value += plies_from_root

and

Code: Select all

/* store score in tt */
if (value > 9900)
  ttentry->value = value + plies_from_root;
else if &#40;value < -9900&#41;
  ttentry->value = value - plies_from_root;
else ttentry->value = value;

and of course when you detect that the position is a mate:

Code: Select all

if (in_check and no_legal_moves)
  return -10000 + plies_from_root;

[Chan Rasjid]

Hello Natale,

In this case we are at ply=26 and can get a hash hit (draft condition is OK and hash signature is OK) returning a score back that is 31979. At this point, we will adjust the score by subtracting 26 plies from 31979 ---> 31953 ---> which is a mate in 47 plies even if horizon is at ply 26. So I have just replaced my "mate in 21 plies" TT entry with one that says "mate in 47 plies".

If you really do as you described above, then it means your search have a bug in hashing and retrieving mate scores.

Although the codes you posted earlier was correct (Sven asked if it really was done that way) there is a bug in the storing part. For hashing +mate scores, you failed to do the adding adjustment by ply :
When retrieving you get 31979 ---> 31953 or mate in 47.
Before you fail high, you rehash and "overwrite" the TT score; you also need to adjust thus:
31979 ---> 31953 ---> 31979 again back to mate-in 21; which means the TT score remained unchanged in spite of being "overwritten".

The fact that you have ballooning mate scores on every TT hit and rehash shows that this is what was happening.

IMNSHO, this is your bug.

To Sven,
Yes, you're right. I think I have a minor bug just like Natale - there is (generally ?) no need to rehash when there is a TT cutoff - just return from search.

Best Regards,
Rasjid.

[xmas79]

They are exactly opposite, so probably this is another typo and you mean alpha == original_alpha

Yes another typo... It was late night... I meant I check if alpha is improved with "alpha != original_alpha", which is the same as "best_score > original_alpha", and the negate are obviuosly "alpha==orig_alpha" and best_score <= orig_alpha"...

If the score is exact you can and should always return that value directly. The score is exact, so you can't go wrong.

I have to think a bit more on this.... I suppose is safe because we are talking about a FailSoft framework. In a FailHard case I think I have to check... I checked bounds since I had a "semi-Fail-soft". I changed it too, the effect were a lot more of exact hash hits, with very turncated PV, but less high mate scores: only a mate in 17 at ply 15, then a mate in 25 at ply 16 (with a PV of onyl 3 plies), then again a mate in 25 suddenly changed to a mate in 12 at ply 17, then mate in 11 at play 18 onward with truncated PV (only 10 plies).

As has already been stated, you should correct the tt score in case of a mate value ....

I already posted the code and I do exacty what you suggested. I add "plies count from root" when storing mate scores, I subtract "plies count from root" when storing mated scores, and the opposite when retriving from hash (AKA transforming the mate in N plies from root to mate in N plies from here and viceversa). And of couse returning a "-MATE+current_plies_from_root" when detecting mate, so that the very first parent node of the mated node stores a score of (-returned_score + current_plies_from_root), which is always 31999 and so on....

If you really do as you described above, then it means your search have a bug in hashing and retrieving mate scores.

What I wrote (the one at ply 26) was only an example. It doens't happen, I wrote it only to allow you understand better what's happening because starting from a knonw position instead of telling "suppose at ply 8" or "suppose at ply 15" I thought it was better...

Although the codes you posted earlier was correct (Sven asked if it really was done that way) there is a bug in the storing part.

Negative... I know mate score adjustment works fine because I walked hashtable hits manually, and the scores I get are that:
ply 0: mate in 21 plies (39179)
ply 1: mated in 20 plies (-39180)
ply 2: mate in 19 plies (39181)
ply 3: mated in 18 plies (-39182)
ply 4: mate in 17 plies (39183)
ply 5: mated in 16 plies (-39184)
.
.
.
ply 20: mated in 2 ply (-31998)
ply 21: mate in 1 ply (31999)

And I already said that from ply 22 onward my program finds only mate in 21 plies.

To Sven,
Yes, you're right. I think I have a minor bug just like Natale - there is (generally ?) no need to rehash when there is a TT cutoff - just return from search.

I'm sorry but this is NOT a bug I have. I already posted what I do and I'm reposting it below again so you can clearly see when I do hash probe and hash store:

Code: Select all

if (50moves or 3foldrep) return draw; 
if (hash_hit) return hash_score (with bound checking etc..etc..) 
for each move 
  score = -search(....); // search and research stuff, pv, non pv etc... 
  if &#40;score >= beta&#41;    // <--- Note the = sign, in the first post it was missing &#40;the famous typo&#41;
   ...cut node... store a SCORE_IS_AT_LEAST bound 

  if&#40;score> alpha&#41; 
    ... pv node... store pv and keep best move 
end for 

if &#40;alpha not improved&#41; 
   ... all node....  store a SCORE_IS_AT_MOST bound 
else 
   ... pv node... store an EXACT alpha bound in hash with best move 

Best regards,
Natale.

[syzygy]

If the score is exact you can and should always return that value directly. The score is exact, so you can't go wrong.

I have to think a bit more on this.... I suppose is safe because we are talking about a FailSoft framework. In a FailHard case I think I have to check...

Yes, with fail-hard you would have to check, but you still return immediately in all cases. The score returned would be alpha if value <= lpha, beta if value >= beta, and value otherwise.

[xmas79]

What about this?

http://www.talkchess.com/forum/viewtopi ... 19&t=30333

Maybe it's a similar situation... It's like also failing high and then failing low... But in my case I just not fail low on research because when I fail high I just relax beta and not set alpha to the failed value... So I get a score back in the window...