Hash Collision?

[Fguy64]

...
The reason is that you get an inexact-depth hash hit after Bd6-d8 on the position that was already searched after 1.a8=Q Bxd8 2.Qxd8#, which was the PV at 3 ply, (although it could not see it ws a checkmate there), and was thus searched as the first branch at 4 ply. There it was discovered that black was in fact checkmated, so it started to look for black alternatives. It then found a better black defense (presumably 1.... Bb7+), which pushed the mate again over the horizon, and then it tried a white alternative 1.Bd6+, which ended up in the graft.

The fact that you don't see a 5-ply PV at 5 ply is further evidence of the hash hit; this position was searched at d=1 in the 4-ply search, so the hit would still be valid for the 5-ply search. The hash cutoffs then cuts the PV (obtained through the triangular method) short.

But I'm not searching PV first, I'm just using my hash table for transpositions only. PV is for display purposes only. In fact I got rid of my PV array altogther. AM I missing something there?

p.s. I'm not using iterative deepening either. Just a fixed depth, 6-ply search perhaps that points to the problem. Anyways, I'll be working on it.

[hgm]

What you are missing is that I was describing how my new engine is doing it, not yours. And there I know that the explanation is correct, because it does search the hash moves first, and gives me feedback so I know what that gash move was. (And thus it searches the PV first, as there are no replacements in the hash table for such a small tree.) Also note that it does get the correct distance-to-mate; the only thing that begs for explanation is why it already finds that score at 4 ply (where it is an over-the-horizon score), rather than at 6.

If your engine would find the mate-in-3 at 4 ply, it still could be due to the same graft, because it _accidentally_ searched the 1.a8=q Bxb8 2.Qxb8# before searchng 1.Bd6+. (E.g. because you search promotions before you search non-capture checks in your static ordering.) But then it would get a mate-in-3 score, not an erroneous mate-in-2.

[Fguy64]

What you are missing is that I was describing how my new engine is doing it, not yours. And there I know that the explanation is correct, because it does search the hash moves first, and gives me feedback so I know what that gash move was. (And thus it searches the PV first, as there are no replacements in the hash table for such a small tree.) Also note that it does get the correct distance-to-mate; the only thing that begs for explanation is why it already finds that score at 4 ply (where it is an over-the-horizon score), rather than at 6.

If your engine would find the mate-in-3 at 4 ply, it still could be due to the same graft, because it _accidentally_ searched the 1.a8=q Bxb8 2.Qxb8# before searchng 1.Bd6+. (E.g. because you search promotions before you search non-capture checks in your static ordering.) But then it would get a mate-in-3 score, not an erroneous mate-in-2.

I'm sorry if I am belaboring the point, but your last paragraph suggests that my problem is a design flaw rather than a bug. It's sounds like If my engine is such that a 2*N ply search is required to find a mate in N, then I better not use inexact hash matches.

[hgm]

No, that is not what I am suggesting. For one, i m not suggesting, but concluding: it is a 100% certainty that your engine has a bug, because it produces a result (namely mate in 2) that within the limitations of all its design flaws should not be possible to occur.

For a mate in 3 you need 6 ply in stead of 5 because of design flaw #1: not recognizing checkmate when it occurs. To see a mate in 3 at 4 ply you need to be lucky, because of design flaw #2 and 3: not searching the hash move first, and not having one because you have no ID. To see a mate in 3 in t 6 ply you will need to search very many nodes because of those same design flaws.

But mate in 2 when you search all branches 6 ply and the closest mate is 5 ply away? Sure bug!

[Fguy64]

OK noted.

As a starting point then, if you have time would you be so kind as to post some perf stats for the position in question?

Thanks much.

[hgm]

Code: Select all

$ ./qperft 6 "1B3k2/P2Q4/7p/8/P1N1B1p1/7b/7b/7K w - -"
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - . B . . . k . . - -
 - - P . . Q . . . . - -
 - - . . . . . . . p - -
 - - . . . . . . . . - -
 - - P . N . B . p . - -
 - - . . . . . . . b - -
 - - . . . . . . . b - -
 - - . . . . . . . K - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft(1)=52 ( 0.000 sec)

perft(2)=530 ( 0.000 sec)

perft(3)=22749 ( 0.000 sec)

perft(4)=263591 ( 0.050 sec)

perft(5)=10871062 ( 0.981 sec)

perft(6)=137871803 (22.532 sec)

Note that qperft can be downloaded from my website, so you could generate these data easily yourself.

Note that your move generator (i.e. perft counts) are unlikely to be the problem, as you do find the correct solution whent you search without hash. Even if the counts would be totaly off, e.g. because your Queens did not have any backward moves, you should still find the same mate in 3 with and without hashing.

[Fguy64]

Code: Select all

$ ./qperft 6 "1B3k2/P2Q4/7p/8/P1N1B1p1/7b/7b/7K w - -"
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - . B . . . k . . - -
 - - P . . Q . . . . - -
 - - . . . . . . . p - -
 - - . . . . . . . . - -
 - - P . N . B . p . - -
 - - . . . . . . . b - -
 - - . . . . . . . b - -
 - - . . . . . . . K - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft(1)=52 ( 0.000 sec)

perft(2)=530 ( 0.000 sec)

perft(3)=22749 ( 0.000 sec)

perft(4)=263591 ( 0.050 sec)

perft(5)=10871062 ( 0.981 sec)

perft(6)=137871803 (22.532 sec)

Note that qperft can be downloaded from my website, so you could generate these data easily yourself.

Note that your move generator (i.e. perft counts) are unlikely to be the problem, as you do find the correct solution whent you search without hash. Even if the counts would be totaly off, e.g. because your Queens did not have any backward moves, you should still find the same mate in 3 with and without hashing.

Let's be clear on one thing. Not only do I find the correct answer without hash, I find the correct answer with hash, when I use exact matches on the depth. The problem manifests itself in small percentage of case only when I use inexact ( depth <= stored depth ).

I change == to <= and there is this problem in maybe one or two positions out of 5000

I should point out that my perft routine also includes hash key verification as follows

the very first entries in my perft method are as follows...

Code: Select all

if( gs.zKey != Utils.calcZ( getFen() ) ) {
    System.out.println("Houston we have a problem at depth = " +depth);
    System.exit(0);
}

This routine constructs a fen string from the position array and game state variables, then builds a zKey (hash key actually) from that, then compares the zKey with that which is maintained incrementally during search. This is done for every node. the position in question passed the test for si6 independent searches, from 1 through 6.

So I am not sure what else to do. I intend to use the same z Key verification in my alphaBeta, If that works, and I expect it will, then I guess it is time to take a dump , It's not clear if that will show me why there is a problem, but I guess I will see.

p.s. the position passes the hash key verification test for search depth = 6

[hgm]

Well, the most likely explanation then is that you do not properly correct the hash mate scores during storing and probing. I don't suppose you use a delayed-loss bonus, so to get any measurement of the mate distance, you would have to use this silly method of fudging the mate scores with the current depth, which again requires you tocorrect them if probing takes place at a different depth than storing. This is notoriously error prone, and probably also the problem here.

[Fguy64]

Well, the most likely explanation then is that you do not properly correct the hash mate scores during storing and probing. I don't suppose you use a delayed-loss bonus, so to get any measurement of the mate distance, you would have to use this silly method of fudging the mate scores with the current depth, which again requires you tocorrect them if probing takes place at a different depth than storing. This is notoriously error prone, and probably also the problem here.

hmm, I make no special consideration for mate scores.

The hash type is initialized to typeAlpha at the beginning of the search function, then change to typeExact when there is an alpha update. At the end of the search function hval=alpha is written along with the type. Beta writes store hval = beta.

My hash probe is the first thing that happens at each node, before the termination condition (depth==0).

I'll have a look around for information on hashing and mate scores. Usually I use Moreland's pages, I'll try there first.

p.s. oooh, mate scores aren't being stored...

[Fguy64]

well, I tried changing the end of my search function from ...

Code: Select all

if( count == 0 ) {
	
    if( (gs.white && isSquareAttackedW(gs.wkp)) ||
        (!gs.white && isSquareAttackedB(gs.bkp)) ) return -(10000-ply);
		
		return 0;
}
	
hKey[hI] = gs.zKey; hType[hI] = hashType; hDepth[hI] = (byte) depth; hVal[hI] = (short) alpha;
return alpha;

to ...

Code: Select all

int score;
		
if( count == 0 ) {
	
    if( (gs.white && isSquareAttackedW(gs.wkp)) ||
        (!gs.white && isSquareAttackedB(gs.bkp)) ) score = -(10000-ply);
		
    else score = 0;
		
    hashType = exact;
}
else score = alpha;
	
hKey[hI] = gs.zKey; hType[hI] = hashType; hDepth[hI] = (byte) depth; hVal[hI] = (short) score;
return score;

but it made no difference.