My program can't mate KQK or KRK!

[Sven]

Hello Sven,

Another thought: could your problem be caused by this "hack"?

Code: Select all

    switch (ttdata->type) {
        case EX:
            assert(ttdata->score ^ -INFI);
            ttmove = ttdata->move;/* return if not rpt3; a temp bad hack  */
            break;
        // ...
    }
    // ...
    for (move = list; *move; ++move) { 
        // ...
        makemove(*move, side);
        // ... check for repetition ...
        // ... check for 50 moves rule ...
        // ...
        if (ttmove){
            /* !!! TEMP; return TT exact hit  */
            unmake(*move, side);
            pv[ply][0] = ttmove;
            pv[ply][1] = 0;
            return ttdata->score;
        }

When detecting an exact TT hit at ply N, you obviously check whether any legal move leads to a repetition or 50-moves-draw at ply N+1. Why do you go one ply deeper in this case? Aren't you interested in excluding that the CURRENT position at ply N, i.e. the one you found in the TT, is not a repetition?

Furthermore, in case of a lower-bound or upper-bound TT hit you don't care about repetition or 50-moves draw but simply return the TT score.

Sven

There is indeed a bug in these lines:-

Code: Select all

        /* error */
        if (ttmove){
            unmake(*move, side);
            /* return TT exact hit  */
            pv[ply][0] = ttmove;
            pv[ply][1] = 0;
            return ttdata->score;
        }
        /* should be this  */
        if (ttmove == *move){
            unmake(*move, side);
            /* return TT exact hit  */
            pv[ply][0] = ttmove;
            pv[ply][1] = 0;
            return ttdata->score;
        }

I don't think that omitting the "== *move" in the "if" condition is a bug, since the action you take is fully unrelated to the current move in the move loop (apart from unmaking it which is necessary). So by applying this change you would even delay the TT cutoff a bit more. What you should do is to always return when detecting an "acceptable" TT hit, only the way how you return may differ. In the given case of an exact hit you can immediately check (not within the move loop but above it!) whether the position is a rep draw or 50 moves draw, and if it is, return a draw score instead of the TT score. That would be a clear program structure. What you do instead creates a lot of sources for irritation.

I am not too sure about the hack to check for rpt3 with a TT exact hit. If we cutoff with a TT exact hit, the tt-move and line may be the PV and we have a repeat move in our PV. It may be a possible way to eliminate the possibility of conceding a repeat draw. We could restrict this test only when the score is in our favour say score > contempt factor, etc... I am not too sure as I was just attempting to trace my bug.

Repetition is a concern only for the case of returning on an EXACT TT hit. LB/UB would never be the PV as the scores are outside of [alpha, beta].

So you say that you introduced this "hack" only for debugging? In that case I would comment it out for now since it may interfere with other behaviour of the search that you want to observe.

Sven

[Chan Rasjid]

Hello Herr,

I guess this is what you get when you bother with all this awfully complex stuff. I am still happy with the two lines

Code: Select all

Search(alpha,beta)
{
 alpha-=alpha<eval;beta-=beta<=eval;                             /* adj. window&#58; delay bonus */
 // everything else
 ...
 return bestScore+=bestScore<eval;                               /* delayed-loss bonus       */
&#125;

which never failed me.

I don't understand that two lines of codes. What's all that about

OK. I remember there are two ways to deal with mating - the way of Crafty or the way of Bruce Moreland (Ferret). I've completely forgotten how the other way works (I think Alvaro is using this other method). I only remember I concluded that Crafty's method is more intuitive and should be the way. But why do not all use it?

If you want to know what is real complexity, I'll send you my source code

I still don't trust your two lines; you didn't mention the other blocks that will be needed later to make them work.

Rasjid.

[hgm]

Between the lines is everything that is in a normal search of whatever type you like. (Except there is no messing with mate scores; they are stored and loaded from the hash table just like any other score, and have no special status in any place in the code. The code even does not know what a mate score is.)

The lines just add 1 point to and score that is below the node's evaluation, just before it is returned. As a mated-in-N score is always below the evaluation, it means that the losing side earns 1 point for every node where it has the move between the root. So it tries to survive as long as it can. While the opponent will try to make him survive as short as possible.

The first line adapts alpha and beta in a way to make sure that the 1-point bonus will not push you on the wrong side of the window (so that upper bounds in the parent would be interpreted as lower bounds, etc.

That is really all.

[Chan Rasjid]

Hello Sven,

Yes, I miss some of your questions.

When this bug occurred could not be traced. I wanted to check if my older sources also have this bug. For a very long time, I have been using this method of having mate_search(). I lost my really old codes, threw away the CD's when I change to usb pen-drive. So the older versions now available too had this bug.

I did a match cowrie-stockfish and extracted a clearly winning position. Then I let my program play the winning side with TT enabled. I replayed the same position 6/7 times and each time, my program would win and mate. Because both programs did not clear the TT, the games are all clearly different; stockfish gets smarter with each game and I show the log for the last game. Notice that from move 36, it detected mate score 7981; after that, mate_search() takes over
and the mate-distance decreased exactly by one after every move - 7991/7993/7995/7997/7999, checkmate.

So it shows that under 'usual circumstances', my program played the position in 6/7 ways and did not concede a draw by mistake. Actually I trust my engine is generally very well debugged through many, many asserts.

"r6r/Pp1b2q1/2pk1p2/R5p1/P2P4/1QPB1NPp/5P1P/4R1K1 w - - 8 34"

35 f3e5 score( 2052) depth( 7) pvL(11) ply(18) nps( 1747626) pc(11) cttime(10) ctpoll(0)
sec(0.48, used 0.38) nodes(q 2.7%, h 62.2%, f 35.1%) FH(53.5%) evasion(25.4%) invalid(10.6%)
Root-red(30.12%, rsc 0.00%) Root-research(1.20%) BranchF(1.10%)
Hash-hit(full 55.8%, qs 6.3%, p( 100.0%, cover 0.0%), ev (29.3%) matOWrite( 73.71) draw(0)
ext(8.94%) see(qs 2.45%, delay 45.45%) zero-wnd(29.95%, rsc 0.60%)
null(0.0% hit -nan% verify -nan% ok -nan% ) lmr(0.00%, rsc -nan%) ply1_rsc(0) fut(0.00%) killer(8.06%)
EV call(59.53%) lazy(0.00%) cut(0.00%) fl(0.00%)
35 d7c8
node-mask, timeout 0x1ffff, poll 0x1fffff
Number valid moves 29
!!! Opponent followPV, score(725) bestmove(a2c4)
depth start 1
36 a2c4 score( 7981) depth( 8) pvL( 1) ply(16) nps( 2127792) pc(11) cttime(18) ctpoll(0)
sec(0.41, used 0.31) nodes(q 1.4%, h 33.0%, f 65.6%) FH(14.9%) evasion(14.8%) invalid(3.3%)
Root-red(8.46%, rsc 0.00%) Root-research(1.54%) BranchF(1.09%)
Hash-hit(full 50.1%, qs 6.5%, p( 100.0%, cover 0.0%), ev (29.7%) matOWrite( 76.77) draw(0)
ext(4.89%) see(qs 1.90%, delay 13.81%) zero-wnd(15.26%, rsc 0.47%)
null(0.0% hit -nan% verify -nan% ok -nan% ) lmr(0.00%, rsc -nan%) ply1_rsc(0) fut(0.00%) killer(3.65%)
EV call(31.04%) lazy(0.00%) cut(0.00%) fl(0.00%)
36 c8f5
node-mask, timeout 0x1ffff, poll 0x3fffff
Number valid moves 30
depth start 5
Matesearch found best mate 7991, depth 10
37 c4c6 score( 7991) depth( 8) pvL( 9) ply(11) nps( 2777083) pc(12) cttime(9) ctpoll(0)
sec(0.57, used 0.12) nodes(q 0.0%, h 2.3%, f 97.7%) FH(0.4%) evasion(19.4%) invalid(0.1%)
Root-red(0.00%, rsc -nan%) Root-research(1.65%) BranchF(0.89%)
Hash-hit(full 51.5%, qs 2.9%, p( 100.0%, cover 0.0%), ev (93.0%) matOWrite( 82.85) draw(0)
ext(0.17%) see(qs 3.33%, delay 0.71%) zero-wnd(0.50%, rsc 0.49%)
null(0.0% hit -nan% verify -nan% ok -nan% ) lmr(0.00%, rsc -nan%) ply1_rsc(0) fut(0.00%) killer(0.12%)
EV call(0.16%) lazy(0.00%) cut(0.00%) fl(0.00%)
37 f5e6
node-mask, timeout 0x3ffff, poll 0x3fffff
!!! Root start with TT matesearch score 7993 d4d5
Number valid moves 33
depth start 2
Matesearch found no better mate 7993, depth 6, d4d5
38 d4d5 score( 7993) depth( 6) pvL( 1) ply( 5) nps( 2777083) pc(12) cttime(3) ctpoll(0)
sec(0.56, used 0.00) nodes(q 0.0%, h 0.0%, f 100.0%) FH(0.0%) evasion(14.1%) invalid(0.0%)
Root-red(0.00%, rsc -nan%) Root-research(0.00%) BranchF(-nan%)
Hash-hit(full 78.2%, qs -nan%, p( 100.0%, cover 0.0%), ev (-nan%) matOWrite( 5.48) draw(0)
ext(0.00%) see(qs -nan%, delay 0.00%) zero-wnd(0.00%, rsc -nan%)
null(0.0% hit -nan% verify -nan% ok -nan% ) lmr(0.00%, rsc -nan%) ply1_rsc(0) fut(0.00%) killer(0.00%)
EV call(6.50%) lazy(0.00%) cut(0.00%) fl(0.00%)
38 e6g4
node-mask, timeout 0x3ffff, poll 0x3fffff
!!! Root start with TT matesearch score 7995 c6b6
Number valid moves 30
depth start 2
Matesearch found no better mate 7995, depth 4, c6b6
39 c6b6 score( 7995) depth( 4) pvL( 1) ply( 3) nps( 2777083) pc(12) cttime(2) ctpoll(0)
sec(0.57, used 0.00) nodes(q 0.0%, h 0.0%, f 100.0%) FH(0.0%) evasion(43.1%) invalid(0.0%)
Root-red(0.00%, rsc -nan%) Root-research(0.00%) BranchF(-nan%)
Hash-hit(full 68.2%, qs -nan%, p( 100.0%, cover 0.0%), ev (-nan%) matOWrite( 42.31) draw(0)
ext(0.00%) see(qs -nan%, delay 0.00%) zero-wnd(0.00%, rsc -nan%)
null(0.0% hit -nan% verify -nan% ok -nan% ) lmr(0.00%, rsc -nan%) ply1_rsc(0) fut(0.00%) killer(0.00%)
EV call(11.05%) lazy(0.00%) cut(0.00%) fl(0.00%)
39 b8a8
node-mask, timeout 0x3ffff, poll 0x3fffff
!!! Root start with TT matesearch score 7997 e5c6
Number valid moves 36
depth start 2
Matesearch found no better mate 7997, depth 2, e5c6
40 e5c6 score( 7997) depth( 2) pvL( 1) ply( 1) nps( 2777083) pc(12) cttime(1) ctpoll(0)
sec(0.59, used 0.00) nodes(q 0.0%, h 0.0%, f 100.0%) FH(0.0%) evasion(50.0%) invalid(0.0%)
Root-red(0.00%, rsc -nan%) Root-research(0.00%) BranchF(-nan%)
Hash-hit(full 85.7%, qs -nan%, p( 100.0%, cover 0.0%), ev (-nan%) matOWrite( 50.00) draw(0)
ext(0.00%) see(qs -nan%, delay 0.00%) zero-wnd(0.00%, rsc -nan%)
null(0.0% hit -nan% verify -nan% ok -nan% ) lmr(0.00%, rsc -nan%) ply1_rsc(0) fut(0.00%) killer(0.00%)
EV call(207.14%) lazy(0.00%) cut(0.00%) fl(0.00%)
40 g4d1
node-mask, timeout 0x3ffff, poll 0x3fffff
!!! Root returns immediate - Checkmate 7999 b6a7
41 b6a7 score( 7999) depth( 0) pvL( 1) ply( 0) nps( 2777083) pc(12) cttime(1) ctpoll(0)
sec(0.61, used 0.00) nodes(q -nan%, h -nan%, f -nan%) FH(-nan%) evasion(0.0%) invalid(-nan%)
Root-red(-nan%, rsc -nan%) Root-research(-nan%) BranchF(-nan%)
Hash-hit(full -nan%, qs -nan%, p( -nan%, cover -nan%), ev (-nan%) matOWrite( -nan) draw(0)
ext(-nan%) see(qs -nan%, delay -nan%) zero-wnd(-nan%, rsc -nan%)
null(-nan% hit -nan% verify -nan% ok -nan% ) lmr(-nan%, rsc -nan%) ply1_rsc(0) fut(-nan%) killer(-nan%)
EV call(-nan%) lazy(-nan%) cut(-nan%) fl(-nan%)

Probing at the root is good for nothing IMO, and I firmly believe you should change that. But it can only be related to your current problem as far as the mate search is concerned. What does your engine do if the mate search function, when called at the root node, returns a score (and possibly a best move) that it took directly from the TT without searching?

I don't exactly understand the above.

!!! Root start with TT matesearch score 7993 d4d5
Number valid moves 33
depth start 2
Matesearch found no better mate 7993, depth 6, d4d5
38 d4d5 score( 7993) depth( 6) pvL( 1) ...

From the log above for move (38), TT probe at root had a mate score of 7993. Then mate_search() was called with:
best = alpha = 7993;
beta = INFI;
with a best move.

mate_search(), after search, confirmed it is the best mate and returns.

Best Regards,
Rasjid.

[Sven]

Notice that from move 36, it detected mate score 7981; after that, mate_search() takes over
and the mate-distance decreased exactly by one after every move - 7991/7993/7995/7997/7999, checkmate.

So it shows that under 'usual circumstances', my program played the position in 6/7 ways and did not concede a draw by mistake. Actually I trust my engine is generally very well debugged through many, many asserts.

O.k., so then what are the "unusual circumstances"? It seems to be "KQK/KRK" according to all you have written. Which part of your engine has any kind of specific handling of KQK/KRK positions (presumably eval?), and how does that interact with your TT implementation? I would investigate into that direction.

Probing at the root is good for nothing IMO, and I firmly believe you should change that. But it can only be related to your current problem as far as the mate search is concerned. What does your engine do if the mate search function, when called at the root node, returns a score (and possibly a best move) that it took directly from the TT without searching?

I don't exactly understand the above.

I mean, at the root you NEED a best move while everywhere else you only need a score (or a bound). Therefore you can probe the TT everywhere else, and possibly cut off by returning the TT score if appropriate. But you simply can't do that at the root, you must expand all root moves, and only within their subtrees you can probe the TT. Probing at root itself is not "illegal" but must not lead to a TT cutoff. As far as I can judge, your mate search function does a TT cutoff also at the root node, and I regard this as a bug. No search function that you call at the root may terminate without expanding at least one root move, unless either the root position is a terminal position or some external condition (e.g. timeout) indicates a premature end of search.

Code: Select all

!!! Root start with TT matesearch score  7993 d4d5
Number valid  moves 33
depth start  2
Matesearch found no better mate  7993, depth 6, d4d5
 38 d4d5 score( 7993) depth( 6) pvL( 1) ...

From the log above for move (38), TT probe at root had a mate score of 7993. Then mate_search() was called with:
best = alpha = 7993;
beta = INFI;
with a best move.

mate_search(), after search, confirmed it is the best mate and returns.

Fine, but what would you do without that confirmation? Would you continue to search, exit with an error message, or do some other magic stuff?
No: you would simply play the move that your (mate) search has found. The score found for the root node by probing the TT has not much value in reality since you need to search anyway and knowing that score in advance can't change your move decision. It can only make things more complex to know that score.

Sven

[Chan Rasjid]

Hello Michael,

check out the effect of repetion detection and TT

I was thinking if there is some failure in my repetition detection lines; but it is not easy to debug. But, in my last reply to Sven, I showed my program did not concede any draws by mistake.

I will think about the other matters you posted.

Best Regards,
Rasjid.

[Chan Rasjid]

Hello Sven,

Notice that from move 36, it detected mate score 7981; after that, mate_search() takes over
and the mate-distance decreased exactly by one after every move - 7991/7993/7995/7997/7999, checkmate.

So it shows that under 'usual circumstances', my program played the position in 6/7 ways and did not concede a draw by mistake. Actually I trust my engine is generally very well debugged through many, many asserts.

O.k., so then what are the "unusual circumstances"? It seems to be "KQK/KRK" according to all you have written. Which part of your engine has any kind of specific handling of KQK/KRK positions (presumably eval?), and how does that interact with your TT implementation? I would investigate into that direction.

Probing at the root is good for nothing IMO, and I firmly believe you should change that. But it can only be related to your current problem as far as the mate search is concerned. What does your engine do if the mate search function, when called at the root node, returns a score (and possibly a best move) that it took directly from the TT without searching?

I don't exactly understand the above.

I mean, at the root you NEED a best move while everywhere else you only need a score (or a bound). Therefore you can probe the TT everywhere else, and possibly cut off by returning the TT score if appropriate. But you simply can't do that at the root, you must expand all root moves, and only within their subtrees you can probe the TT. Probing at root itself is not "illegal" but must not lead to a TT cutoff. As far as I can judge, your mate search function does a TT cutoff also at the root node, and I regard this as a bug. No search function that you call at the root may terminate without expanding at least one root move, unless either the root position is a terminal position or some external condition (e.g. timeout) indicates a premature end of search.

Code: Select all

!!! Root start with TT matesearch score  7993 d4d5
Number valid  moves 33
depth start  2
Matesearch found no better mate  7993, depth 6, d4d5
 38 d4d5 score( 7993) depth( 6) pvL( 1) ...

From the log above for move (38), TT probe at root had a mate score of 7993. Then mate_search() was called with:
best = alpha = 7993;
beta = INFI;
with a best move.

mate_search(), after search, confirmed it is the best mate and returns.

Fine, but what would you do without that confirmation? Would you continue to search, exit with an error message, or do some other magic stuff?
No: you would simply play the move that your (mate) search has found. The score found for the root node by probing the TT has not much value in reality since you need to search anyway and knowing that score in advance can't change your move decision. It can only make things more complex to know that score.

Sven

I think there is some misunderstanding.

My search for a move to play at the root is think():

Code: Select all

 
    int think(int followPV){

    probehash();/*this may show that there is a +mate score with best move.
    By right, if it is EXACT, we can just play the move immediately if there is no 
    bug here. The distance-to-mate would reduce by 1 after every move if the opponent       
    knows how to play the best reply. If the opponent does not play the best reply, 
    a mate-in 5 may jump straight to mate-in-2 bypassing mate-in-4.  
          */
    gen-full().
    
    //iterative deepening.
    for &#40;depth = 1; depth < 64; ++depth&#41;
    ...
    
    for &#40;move, ...)&#123;
        makemove&#40;);
        .....
        if &#40;matesearch == 1&#41;&#123;
            x = mate_search&#40;);
        &#125;else&#123;
            x = searchPVS&#40;);
       &#125;
    &#125;

    etc, ...
    

I think the only use of probehash() at root is as the comments above.

Currently, many of the things done are also for debugging. When things are clean,
some features could be removed.

Best Regards,
Rasjid.

[Sven]

My search for a move to play at the root is think():
...
I think the only use of probehash() at root is as the comments above.

I misunderstood your reply on my following question:

- Do you call search_mate() from the root node? This would imply that you also probe at root, and return in case of a hit, which is not what you would intend normally.

I do probe hash at the start of root search and may just return if TT hit with a losing mate score.

and now I see that actually you don't call mate_search() at the root node itself.

You call probehash() at root, and in your comment you mention that you might return the best move from TT. I would not do so. You need to consider the depth to which that move was searched at the time where it was stored in the TT. How do you know that depth will be sufficient this time? Imagine you find a best move from a depth=3 search. Would you play that move in the game? If not, what is your depth threshold, and how do you estimate it before even starting your iterative deepening loop? Playing a move from TT without any search at all is a no-go. You can use the TT move for move ordering but never to play it immediately.

Sven

[Chan Rasjid]

Hello Sven,

Hello Sven,

Another thought: could your problem be caused by this "hack"?

Code: Select all

    switch (ttdata->type) {
        case EX:
            assert(ttdata->score ^ -INFI);
            ttmove = ttdata->move;/* return if not rpt3; a temp bad hack  */
            break;
        // ...
    }
    // ...
    for (move = list; *move; ++move) { 
        // ...
        makemove(*move, side);
        // ... check for repetition ...
        // ... check for 50 moves rule ...
        // ...
        if (ttmove){
            /* !!! TEMP; return TT exact hit  */
            unmake(*move, side);
            pv[ply][0] = ttmove;
            pv[ply][1] = 0;
            return ttdata->score;
        }

When detecting an exact TT hit at ply N, you obviously check whether any legal move leads to a repetition or 50-moves-draw at ply N+1. Why do you go one ply deeper in this case? Aren't you interested in excluding that the CURRENT position at ply N, i.e. the one you found in the TT, is not a repetition?

Furthermore, in case of a lower-bound or upper-bound TT hit you don't care about repetition or 50-moves draw but simply return the TT score.

Sven

There is indeed a bug in these lines:-

Code: Select all

        /* error */
        if (ttmove){
            unmake(*move, side);
            /* return TT exact hit  */
            pv[ply][0] = ttmove;
            pv[ply][1] = 0;
            return ttdata->score;
        }
        /* should be this  */
        if (ttmove == *move){
            unmake(*move, side);
            /* return TT exact hit  */
            pv[ply][0] = ttmove;
            pv[ply][1] = 0;
            return ttdata->score;
        }

I don't think that omitting the "== *move" in the "if" condition is a bug, since the action you take is fully unrelated to the current move in the move loop (apart from unmaking it which is necessary). So by applying this change you would even delay the TT cutoff a bit more. What you should do is to always return when detecting an "acceptable" TT hit, only the way how you return may differ. In the given case of an exact hit you can immediately check (not within the move loop but above it!) whether the position is a rep draw or 50 moves draw, and if it is, return a draw score instead of the TT score. That would be a clear program structure. What you do instead creates a lot of sources for irritation.

I am not too sure about the hack to check for rpt3 with a TT exact hit. If we cutoff with a TT exact hit, the tt-move and line may be the PV and we have a repeat move in our PV. It may be a possible way to eliminate the possibility of conceding a repeat draw. We could restrict this test only when the score is in our favour say score > contempt factor, etc... I am not too sure as I was just attempting to trace my bug.

Repetition is a concern only for the case of returning on an EXACT TT hit. LB/UB would never be the PV as the scores are outside of [alpha, beta].

So you say that you introduced this "hack" only for debugging? In that case I would comment it out for now since it may interfere with other behaviour of the search that you want to observe.

Sven

Hello Sven,

I am not too sure here if I am wrong. I have not implemented this in my program. I will elaborate.

At the start of search() within internal nodes, we do a probehash(). If there is an exact TT hit, we return the tt-score, and etc...

But this line with the tt-move may finally end as the new PV. Also it is not tested that this tt-move is not a repeat move. So we can delay the exact TT-hit cutoff. We generate the move list and do as per normal - generate the full move list, list through every move with the purpose of searching every move; makemove(), searchPVS(),...

But we could just sort the tt-move front(I think there is a misunderstanding here; the tt-move is one of the move in the list). If this tt-move pass the repetition test, then we could immediately return the tt-score (exact hit), etc otherwise, the search of every move proceeds as usual.

I will ponder a little more to see if I miss the point you make.

Best Regards,
Rasjid.

[Chan Rasjid]

Hello Sven,

My search for a move to play at the root is think():
...
I think the only use of probehash() at root is as the comments above.

I misunderstood your reply on my following question:

- Do you call search_mate() from the root node? This would imply that you also probe at root, and return in case of a hit, which is not what you would intend normally.

I do probe hash at the start of root search and may just return if TT hit with a losing mate score.

and now I see that actually you don't call mate_search() at the root node itself.

You call probehash() at root, and in your comment you mention that you might return the best move from TT. I would not do so. You need to consider the depth to which that move was searched at the time where it was stored in the TT. How do you know that depth will be sufficient this time? Imagine you find a best move from a depth=3 search. Would you play that move in the game? If not, what is your depth threshold, and how do you estimate it before even starting your iterative deepening loop? Playing a move from TT without any search at all is a no-go. You can use the TT move for move ordering but never to play it immediately.

Sven

We could safely return the move from a root probehash() exact hit only for +mate scores.

Also ok for -mate scores if we are surely losing.

Best Regards,
Rasjid.