My program can't mate KQK or KRK!

[Ferdy]

Finally, the only way I know how to debug my program is:
1) many many asserts.
2) play fast games to look for strange behaviour.

For me I can add, analyze games with long time control or even watch it play in on line games (HGM monthly for example).
This is where I found that the passer in the program is actually not a passer .

[Chan Rasjid]

Hello,

Finally, the only way I know how to debug my program is:
1) many many asserts.
2) play fast games to look for strange behaviour.

For me I can add, analyze games with long time control or even watch it play in on line games (HGM monthly for example).
This is where I found that the passer in the program is actually not a passer .

There could be many other useful techniques to fine tune and debug our chess program - but resources and IQ and time and life-span is limitied

We have to learn and learn or WORK!

But I did do some work. There is one evaluation debug method that may be very important - color assymetry test. But it is a little tricky to implement.

Best regards,
Rasjid.

[Chan Rasjid]

Hello,

I have finally traced the bug in my program that caused it to not able to mate endings of KQK and KRK when a position is replayed without the transposition table cleared. The content of the table stored mate scores that were incorrect.

First about aspiration windows for root search. The usual practice is to set [alpha, beta] to cover the expected best score of every iteration, say about 100cp about the expected value. But if an iteration returns a winning +mate score, the iteration may be reset to seek the shortest mate, iterating through even depth 2/4/6/8 until the best possible mate is reached when root search returns. For this, the setting may be:
alpha = bestscore = winning_mate_score.
beta = INFI;
There is a corresponding best move.

This is perfectly safe and probably the correct way. My program earlier found that it had to set alpha = -INFI and the reason was due to a bug elsewhere.

The bug was in the way I hashed mate scores. It had nothing to do with the +/- ply adjustment needed to the scores for hashing. It was done accordingly. The bug was in the bound type hashed - exact, upper or lower.

I don't know how other program hash mate scores. The way in my program was all the while :
storehash(score, MAX_DEPTH, EX/UB/LB, bestmove, ...);
It was always with max depth.

For non-mate scores, the bound type of the score to hash changes with the search depth. With max depth for mate scores, the way to determine bound type to hash would be different. 'exact' for +mate means the best possible mate; eg. INF - 1 is always 'exact'. In the hashing of interior nodes, there are some subtleties if root search is seeking a better mate. Some +mate and -mate scores may not be hashed as the bound type is indeterminate corresponding to MAX_DEPTH. It is clearer that I show the hashing code at the end of my pvs search with comments. Only the mate scores are of interest to this topic:

Code: Select all

HASH_AND_RETURN:
;
/* M_MATE is minus-mate, P_MATE is  plus-mate.   */
if (bestmove) {
CUT:
    if (best > M_MATE) {
        if (best < P_MATE) {
            if (best ^ 0) {
                if (depth <= 0) {
                    /* QS */
                    storehash(best, incheck || (genChecks && best > alpha0) ? 1 : 0,
                            best <= alpha0 ? UB : (best >= beta || genChecks ? LB : EX),
                            bestmove, currstack->xeval);
                } else {
                    storehash(best, depth, best <= alpha0 ? UB : (best >= beta ? LB : EX),
                            bestmove, currstack->xeval);
                }
            }
        } else {
            /* winning mate scores */
            assert(ply & 1 ? !(best & 1) : best & 1);
            if (best == INFI - ply - 1) {
             /* mate-in-1 */
                storehash(best + ply, MAX_DEPTH, EX, bestmove, -INFI);
            } else if (best > alpha0) {
                storehash(best + ply, MAX_DEPTH, LB, bestmove, -INFI);
            }
            /* otherwise indeterminate bound type  */
        }
    } else {
     /* losing mate score  */
        assert(ply & 1 ? (best & 1) : !(best & 1));
        if (best == -INFI + ply + 2) {
            /* this is an exact score !!! */
            storehash(best - ply, MAX_DEPTH, EX, bestmove, -INFI);
        } else if (best <= alpha0) {
            storehash(best - ply, MAX_DEPTH, UB, bestmove, -INFI);
        }
        /* otherwise indeterminate bound type  */
    }
    return best;
} else {
    if (incheck) {
        /* losing mate, exact  */
        storehash(-INFI, MAX_DEPTH, EX, 0, -INFI);
        return -INFI + ply;
    }

    if (depth > 0) {
        /* stalemate*/
        storehash(1, MAX_DEPTH, EX, 0, -INFI);
        return 1;
    }

    /* QS - without a bestmove ==> best is eval; hash EX only if best == xeval.
     */
    assert(best ^ -INFI);
    if (best ^ 0 && best == currstack->xeval) {
        storehash(best, 0, EX, 0, currstack->xeval);
    }
    return best;
}

Best Regards,
Rasjid.

[Chan Rasjid]

Hello,

While googling for 'search instability', I found an old thread 'Transposition table pruning'.

from Joona Kiiski of Stockfish:

Values from TT are not used in PV, because:

* Extra cost is small (TT values can be used for non-PV child nodes).
* rep. draws are problematic (as hgm, pointed out)
* fifty move rule detection is problematic
* delivering mate is problematic when TT shows matescores everywhere and would need special handling.

'TT shows matescores everywhere' - this was the problem I faced when games replayed without clearing the hash tables.

Best Regards,
Rasjid.

[Evert]

'TT shows matescores everywhere' - this was the problem I faced when games replayed without clearing the hash tables.

Sounds like a bug to me.

I have no problems with spurious mate scores, but I had in the past. I don't remember exactly what the bug was, but it certainly was one.

Note that issues with 50-move and repetition draws are not exclusive to the PV either...

[hgm]

The hash-store code looks a bit messy. And why don't you store upper-bound mate scores and lower-bound to-be-mated scores? In Fairy-Max I have none of that; all bound types are stored (because mate scores are not treated special in any way).

Storing the mate scores with MAX_DEPTH seems in general completely wrong for any bound type. You can only do that if the search depth is larger than the distance to mate (and then only if you are sure that reduction cannot make you miss a mate of the nominal depth). If your replacement algorithm uses the draft in its decision for what to replace it would probably be very detrimental, as it would cling on to hash entries which represent very little search effort. Much better to upgrade the depth in the probing code, so that it does not interfere with the replacement.

Upgrading mate-in-1 to an exact score and increase its depth is not really necessary; if it is a lower bound the probing code would take a cuttoff on it any way if it was stored as a lower bound. Mate-distance pruning takes care of that.

[Chan Rasjid]

The hash-store code looks a bit messy. And why don't you store upper-bound mate scores and lower-bound to-be-mated scores? In Fairy-Max I have none of that; all bound types are stored (because mate scores are not treated special in any way).

Storing the mate scores with MAX_DEPTH seems in general completely wrong for any bound type. You can only do that if the search depth is larger than the distance to mate (and then only if you are sure that reduction cannot make you miss a mate of the nominal depth). If your replacement algorithm uses the draft in its decision for what to replace it would probably be very detrimental, as it would cling on to hash entries which represent very little search effort. Much better to upgrade the depth in the probing code, so that it does not interfere with the replacement.

Upgrading mate-in-1 to an exact score and increase its depth is not really necessary; if it is a lower bound the probing code would take a cuttoff on it any way if it was stored as a lower bound. Mate-distance pruning takes care of that.

Currently, the bug is nominally cleared. It could be as you suggest - not to hash mate score with maximum depth unless it really helps. I'll think about it.

Best Regards,
Rasjid.

[hgm]

In Fairy-Max I had a similar problem with King captures. As soon as it generates a capture of the King it ups the score to +INF and the depth to MAX_PLY, to be sure it will break out of the IID loop. But that depth then also ends up in the hash table. In Fairy-Max' always-replace table that is no problem, but as soon as I try to implement a better replacement scheme it immediately kills it. Any form of depth preference will see the entire depth-preferred part of the table poisioned by K-capt positions, which can never be replaced by anything, and never save you more work than a single node. So basically any attempt to improve on always-replace degenerates into halving (or quartering) your always-replace table.

That can be solved by storing the King-capture positions with the true search depth (= 0-ply), so they can get easily replaced by anything more valuable (like a 1-ply search), and do the depth correction on probing: every time you probe an entry with LB score +INF, in stead of taking the depth stored with it, you can assume it is valid to depth MAX_PLY.

A generalization of this would be to up the (probed) score to MAX_PLY whenever the stored draft exceeds, or is equal to the DTM.

[Chan Rasjid]

In Fairy-Max I had a similar problem with King captures. As soon as it generates a capture of the King it ups the score to +INF and the depth to MAX_PLY, to be sure it will break out of the IID loop. But that depth then also ends up in the hash table. In Fairy-Max' always-replace table that is no problem, but as soon as I try to implement a better replacement scheme it immediately kills it. Any form of depth preference will see the entire depth-preferred part of the table poisioned by K-capt positions, which can never be replaced by anything, and never save you more work than a single node. So basically any attempt to improve on always-replace degenerates into halving (or quartering) your always-replace table.

That can be solved by storing the King-capture positions with the true search depth (= 0-ply), so they can get easily replaced by anything more valuable (like a 1-ply search), and do the depth correction on probing: every time you probe an entry with LB score +INF, in stead of taking the depth stored with it, you can assume it is valid to depth MAX_PLY.

A generalization of this would be to up the (probed) score to MAX_PLY whenever the stored draft exceeds, or is equal to the DTM.

I have not seriously thought about whether hashing mate scores with max-depth is wrong - it did allow my program to deliver the best mate normally. But it is likely not a good alternative.

I have now changed my codes for hashing of mate scores to the way hashing is usually done, basically without mate scores being treated in any special manner - hashed draft is the search depth of max(1, depth) and the bound types would be the usual exact, lower(fail high) and upper (fail low). Hash draft would only be max-depth when a +mate score is the best possible mate.

Only in probe hash is there some minor exceptions to the need for sufficient hash draft for cutoff. For example, if the hashed score is a +mate and beta below +mate(non-mate bound), then we can fail high even though the hash draft is 'insufficient'. We return tt-score (fail high) if the bound type is exact or lower. If the bound type is upper, we still can fail high by returning the least +mate score(upper +mate score is at least a +mate score). Similarly for -ve mate scores.

I was aware of the problem of having max-depth in the TT and, unless always replace, could persist in the TT and those entries may be completely outdated and useless. I had some fix for it but I think it is still bad. Hashing now with just the normal search depth clears the problem.

It is now working very well. I tested it with various opponents for KQK/KRK and by replaying the same game a multiple times. Though the TT has 'matescores everywhere', it is ok as long as those entries are valid.

BTW, thanks for the 'very good' public domain KPK bitbase generators. I'll be looking into using it later.

Best Regards,
Rasjid.

[DrRibosome]

Had the exact same problem. Couldnt do simple mating, but clearing hash fixed things, etc. Problem for me was zobrist hash keys didnt account for positions repeating (ie, for 3-fold repitiion). As a result, engine would do strange things and weird moves, not realizing that these things would lead to draws. Fixing this fixed the problem entirely.