My program can't mate KQK or KRK!

[Sven]

Code: Select all

#define INFI 8000
#define MAX_PLY 127
#define M_MATE (-INFI + MAX_PLY)
#define P_MATE (INFI - MAX_PLY)

best means best score.

So (best > M_MATE && best < p_MATE)
are non-mate scores; 0 means material/rep3/fifty draw and it is not hashed.

best <= M_MATE are losing mate scores, best >= P_MATE are winning mate scores.

O.k., thanks. So probehash(ply) does the reverse, it changes any mate score from "distance to mate from node" into "distance to mate from root", correct? How does it do that? I'd assume something like this:

Code: Select all

// ... code to probe TT and fill struct to which ttdata points ...
// ...
if (ttdata->score <= M_MATE-ply) {
    ttdata->score += ply;
} else
if (ttdata->score >= P_MATE+ply) {
    ttdata->score -= ply;
}

Sven

[Sven]

If everything is fine with your "distance to mate" adjustment code then answering these questions might help:

- Is the problem restricted to KQK/KRK positions, or does the engine also refute to win from other (e.g. middlegame) mate-in-N positions? In the former case I would assume that the root cause is outside of your mate search function.

- Did mating in KQK/KRK positions ever work before? If so, what did you change in the meantime? Especially, what were your last changes prior to finding that KQK/KRK mating does not work?

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

Sven

[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

[Chan Rasjid]

Hello Sven,

Code: Select all

#define INFI 8000
#define MAX_PLY 127
#define M_MATE (-INFI + MAX_PLY)
#define P_MATE (INFI - MAX_PLY)

best means best score.

So (best > M_MATE && best < p_MATE)
are non-mate scores; 0 means material/rep3/fifty draw and it is not hashed.

best <= M_MATE are losing mate scores, best >= P_MATE are winning mate scores.

O.k., thanks. So probehash(ply) does the reverse, it changes any mate score from "distance to mate from node" into "distance to mate from root", correct? How does it do that? I'd assume something like this:

Code: Select all

// ... code to probe TT and fill struct to which ttdata points ...
// ...
if (ttdata->score <= M_MATE-ply) {
    ttdata->score += ply;
} else
if (ttdata->score >= P_MATE+ply) {
    ttdata->score -= ply;
}

Sven

In your code, I think there is no need of :-
if (ttdata->score <= M_MATE-ply)
just :
if (ttdata->score <= M_MATE)

Mine is :

Code: Select all

            ttdata->score = PROBE_SCORE(p);
            assert(ttdata->score ^ 0);
            if (ttdata->score > M_MATE) {
                if (ttdata->score < P_MATE);
                else {
                    ttdata->score -= ply;
                }
            } else {
                ttdata->score += ply;
            }

Best Regards,
Rasjid.

[Sven]

In your code, I think there is no need of :-
if (ttdata->score <= M_MATE-ply)
just :
if (ttdata->score <= M_MATE)

That would map TT scores in the range [M_MATE-ply+1 .. M_MATE] to tree scores in the range [M_MATE+1 .. M_MATE+ply] which are, by definition, no mate scores any longer. You can ignore that as long as you prove that such TT scores will "never" occur. Can you prove it?

Nevertheless, for all realistic cases you may be right, and I also have the feeling that this is not the reason for your problem (see my other posts for possible other reasons).

Sven

[Chan Rasjid]

Hello Sven,

If everything is fine with your "distance to mate" adjustment code then answering these questions might help:

- Is the problem restricted to KQK/KRK positions, or does the engine also refute to win from other (e.g. middlegame) mate-in-N positions? In the former case I would assume that the root cause is outside of your mate search function.

From the start position, my program would win and mate a weaker program normally; eg, with TSCP, Kurt, the only weaker programs I have. Also, not often to concede any rpt3 draws.

- Did mating in KQK/KRK positions ever work before? If so, what did you change in the meantime? Especially, what were your last changes prior to finding that KQK/KRK mating does not work?

With TT disabled, will always mate with any KQK/KRK positions.

With TT enabled, it may mate when xboard is just started. A repeat of the same game by rewinding to start of game will fail to mate (TT not cleared) - conceding a rpt3/fifty draw.

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

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

Best Regards,
Rasjid.

[Chan Rasjid]

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

Best Regards,
Rasjid.

[hgm]

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: delay bonus */
 // everything else
 ...
 return bestScore+=bestScore<eval;                               /* delayed-loss bonus       */
}

which never failed me.

[Desperado]

Hello,

My program has a hashing bug that I could not resolve after weeks of attempts. If anyone had come across a similar situation in the development of their engine, I would like to know the solution.

With TT hashing enabled, my program plays normally from the start position and does not do strange moves. But when given KQK or KRK positions, it fails to mate and will concede a repetition/fifty-moves draw.

But with TT disabled, it does successfully mate with KQK or KRK. With KRK, it will take some moves to force the lone king into the corner. When it detects mate, matesearch() will be called starting at root. The root search iterates through even depth 2/4/6/8.. to seek the best mate. It will take almost zero second for it to find the next better mate move: mate in 5/4/3/2/1 - checkmate.

...

Hi Chan,

well, first i am not sure if it is the best idea to go with that kind of
special search within gameplay, because imo it could ( should be ) handled
with the normal search. Even to detect a shortest mate might be flagged
in a research and mate bounds for example, if it is that important to you.
But that isnt the topic...

Second, i did not studdied your code snipped, but i want to give you some
general ideas what you can look for when having this kind of problem.
( i try to leave out the obvious things already mentioned, but that
doesnt mean to forget them, even if you think you prooved it 20 times
before )

* simply try to find and catch artificial mate values inside the search which
are outside the mate bounds. If there are some, locate them...
* make your test frame simple as possible like to disable aspiration
window, or mate detection in QS and things like that

uninitialized variables like bValue in a failSoft frame can cause stupid
things in an aspiration search with artificial windows ( not if done right ).

or simply try out to disable TT-pruning within PV for example.
* to prevent as good as possible search instabilities try out mateDistance
Pruning. This is a general good idea to have it in.

* check out the effect of repetion detection and TT

* combine all this stuff step by step, and you will get it to work

* if your move generator uses special evasion functions, check them
out again if they _really_ work propper. More General make sure
you legal move validation code works proper.

Well, after checking "mating" code sippets i would start looking for
invalid values outside the mate bounds...

Good Luck,

Michael

[Sven]

Hello Sven,

If everything is fine with your "distance to mate" adjustment code then answering these questions might help:

- Is the problem restricted to KQK/KRK positions, or does the engine also refute to win from other (e.g. middlegame) mate-in-N positions? In the former case I would assume that the root cause is outside of your mate search function.

From the start position, my program would win and mate a weaker program normally; eg, with TSCP, Kurt, the only weaker programs I have. Also, not often to concede any rpt3 draws.

Even though you did not answer my question directly, it seems you want to imply that the problem is restricted to KQK/KRK positions, don't you? If that is the case then why should your mate search function cause the problem? KQK/KRK looks more like an eval problem, in your case combined with some TT effect. To check whether normal mate search really works, take an arbitrary position which has a couple of pieces and is mate-in-N. Let your engine play against a "perfect" opponent (that can be yourself if you defend as good as possible) from that position, with TT enabled. Does it play the shortest path to mate in each single move until mate is on the board?

- Did mating in KQK/KRK positions ever work before? If so, what did you change in the meantime? Especially, what were your last changes prior to finding that KQK/KRK mating does not work?

With TT disabled, will always mate with any KQK/KRK positions.

With TT enabled, it may mate when xboard is just started. A repeat of the same game by rewinding to start of game will fail to mate (TT not cleared) - conceding a rpt3/fifty draw.

Again, my questions were a bit different. In a previous post you wrote that you are debugging this problem for a couple of weeks already. But I know that you have been developing your chess engine over several years, at least much longer than few weeks. So either you never tested mating with KQK/KRK and TT enabled before, or the problem has started to occur only recently. In the latter case there must have been some code change that caused the problem to pop up. Or did you implement the whole TT code only recently?

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

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?

Sven