First post (and FailHigh question!)

[Sven]

The unrestricted magnification of search mate scores happens and I think it is not a bug.

I'm tired to repeat the same over and over again. If you like you may choose to reread what I wrote, or to ignore it. I think I explained well what can happen via transpositions and what can't. I have nothing more to add here.

Sven

[Chan Rasjid]

Hello Sven,

The unrestricted magnification of search mate scores happens and I think it is not a bug.

I'm tired to repeat the same over and over again. If you like you may choose to reread what I wrote, or to ignore it. I think I explained well what can happen via transpositions and what can't. I have nothing more to add here.

Sven

It was you who explained how a TT entry of infi -5 may cause its grandparent node to fail high and hash an amplified score of infi - 7. This first amplification is the key. (Natale confused me a little by immediately stating how an infi - 5 - 12 got hashed into the TT).

The point is that the position of the grandparent node is not identical (a transposition) to that of its grandchild - two different positions. But this grandparent position may be reached via many different paths (transposition). When they are reached, further amplification occurs. If reached at ply 14, it would fail high with infi - 7 - 14; and this further amplified score gets propagated down towards the root again. And such processes keeps repeating.

Best Regards,
Rasjid.

[Chan Rasjid]

Hello Thomas,

I've read Bob's description in crafty how he does it (If I remember right it was storing the distance to the start of the current search).

At the time I did not understand how this will work if 2 moves are actually played on the board, a new search starts and now older entries are retrieved from the table. Even today I think this might be problematic.

Anyway my approach works quiet well (so it seems there is a 3rd one) and I'll keep it.

Here is my output. I don't see any strange mate scores. The first time the mate is spotted at ply 18 (where the selected depth due to extensions reached ply 24) and a Mate in 12 is announced. I know it is a Mate in 11 so probably LMR has pruned a shortcut away.

info depth 14 seldepth 22 time 484 nodes 1099363 pv d6e5 h1g2 e5f4 score cp 958 hashfull 31 tbhits 0
info depth 15 seldepth 24 time 797 nodes 1846451 pv d6e5 h1g2 score cp 958 hashfull 48 tbhits 0
info depth 16 seldepth 24 time 984 nodes 2273760 pv d6e5 h1g2 score cp 958 hashfull 67 tbhits 0
info depth 17 seldepth 26 time 1531 nodes 3414704 pv d6e5 h1g2 score cp 958 hashfull 91 tbhits 0
info depth 18 seldepth 24 time 2766 nodes 6700059 pv d6e5 h1g2 score mate 12 hashfull 125 tbhits 0
info depth 19 seldepth 24 time 3985 nodes 9632151 pv d6e5 h1g2 score mate 12 hashfull 162 tbhits 0
info depth 20 seldepth 25 time 6734 nodes 16106975 pv d6e5 h1g2 score mate 12 hashfull 198 tbhits 0
info depth 21 seldepth 24 time 8265 nodes 19686350 pv d6e5 h1g2 score mate 12 hashfull 243 tbhits 0
info depth 22 seldepth 26 time 10047 nodes 23116233 pv d6e5 h1g2 score mate 12 hashfull 283 tbhits 0
info depth 23 seldepth 24 time 13844 nodes 31754430 pv d6e5 h1g2 score mate 12 hashfull 324 tbhits 0
bestmove d6e5 ponder h1g2
info time 50265 nodes 116982045 nps 2327306

Thomas...

I am almost sure there is no "problematic" issue with the way Crafty hashes mate scores; otherwise it will get reported. In fact most first timer would find Crafty's the method more intuitive than the way you are doing it. When a +mate score of infi - x is hashed in the TT, we only need to do a ply adjustment to "mate ply distance from current node to mate node". Retrieving from another search reaching this same position will again need a ply adjustment to search score of type "distance of mate node from the root node".
(EDIT : root node)

The reason for ballooning of mate search scores is due not to the fault of the hashing method, but to using the "always" replacement scheme. We may be able to do away with ballooned mate scores if we select when to replace TT mate scores. I don't think it matters much if our search is not tripped by it.

Your output is basically the same as that from my engine. Your engine first detected mate at depth 18 with mate12 (there is a slight bug, should be mate11); it is the same with my engine. but a mate node at ply 17 would mean mate9. So your engine too could "see beyond its horizon" due to transposition. As to why you did not see longer mates like mate14 or mate16 earlier could be your particular aspiration search implementation or TT replacement scheme.

Best Regards,
Rasjid.

[Sven]

It was you who explained how a TT entry of infi -5 may cause its grandparent node to fail high and hash an amplified score of infi - 7. This first amplification is the key.

No! This is no "amplification", it is standard backing up of tree values. A score "mate in 5 plies from here" at node A1 is backed up as "mate in 7 plies from grandparent of A1" to the grandparent (if the line is forced).

The point is that the position of the grandparent node is not identical (a transposition) to that of its grandchild - two different positions. But this grandparent position may be reached via many different paths (transposition). When they are reached, further amplification occurs. If reached at ply 14, it would fail high with infi - 7 - 14; and this further amplified score gets propagated down towards the root again. And such processes keeps repeating.

Alpha-Beta with mate-distance pruning prevents going deeper than the shortest mate you already found from a given node, so you never really get there. But in my opinion even normal alpha-beta without mate-distance pruning will prevent the case you mentioned.

Sven

[Chan Rasjid]

Hello Sven,

Besides any misundertanding on our "disputes", only one of us is right; but it is not really important as we are not vying for the Nobel award! Or to head ICGA!

We all learn otherwise how are we going to keep up with Robert Houdini who has the advantage of magic tricks! Through this thread, I now learned that leave nodes are not that "far away" from the root. And people apply the term 'ply' as in plywood as well to half-moves. And amplification ... OPPS...

It was you who explained how a TT entry of infi -5 may cause its grandparent node to fail high and hash an amplified score of infi - 7. This first amplification is the key.

No! This is no "amplification", it is standard backing up of tree values. A score "mate in 5 plies from here" at node A1 is backed up as "mate in 7 plies from grandparent of A1" to the grandparent (if the line is forced).

The point is that the position of the grandparent node is not identical (a transposition) to that of its grandchild - two different positions. But this grandparent position may be reached via many different paths (transposition). When they are reached, further amplification occurs. If reached at ply 14, it would fail high with infi - 7 - 14; and this further amplified score gets propagated down towards the root again. And such processes keeps repeating.

Alpha-Beta with mate-distance pruning prevents going deeper than the shortest mate you already found from a given node, so you never really get there. But in my opinion even normal alpha-beta without mate-distance pruning will prevent the case you mentioned.

Sven

This was what you wrote earlier :

4) The grandparent of A1, which is at ply=10, gets back "+(infi-17)", fails high, and stores "+(infi-7)" as lower bound in the TT, i.e. "mate in at most 7 plies from here".

You said "stores" which means (infi - 7), an amplification, was hashed in the TT. The originating node hashed only "infi - 5". In Natale's case, the fail high reached the root node and what was hashed was (infi - 5 - 12 + 0)!

I have not examined about the part how alpha-beta would prevent any longer mates being propagated down. Off the hat now, the forced lines may stop after a few plies down and the black king may have a score within bounds and fail high stops. So as alpha-beta rewinds further down, the best score may again be a non-mate value. But the problem again is with the nodes higher up from this node - there are so many transpositions(KNB-K) and many have amplified TT scores hashed. So longer mates starts propagating down and search may start to fail high again with amplified mate scores. The processes repeats with each root iteration.

The thing is not many others join in this thread to express their humble opinion except the ICGA accredited experts Sven and Rasjid - and they are in disagreement!

Best Regards,
Rasjid.

[Sven]

This was what you wrote earlier :

4) The grandparent of A1, which is at ply=10, gets back "+(infi-17)", fails high, and stores "+(infi-7)" as lower bound in the TT, i.e. "mate in at most 7 plies from here".

You said "stores" which means (infi - 7), an amplification, was hashed in the TT. The originating node hashed only "infi - 5". In Natale's case, the fail high reached the root node and what was hashed was (infi - 5 - 12 + 0)!

You are talking about three different positions here: one is 12 plies away from root and shows "mate in 5 plies" from there, one is 10 plies away from root (the grandparent of the first) and shows "mate in 7 plies" from there, and one is the root showing "mate in 17 plies" from there. No "amplification", just three different nodes.

Sven

[Chan Rasjid]

Hello Sven.

This was what you wrote earlier :

4) The grandparent of A1, which is at ply=10, gets back "+(infi-17)", fails high, and stores "+(infi-7)" as lower bound in the TT, i.e. "mate in at most 7 plies from here".

You said "stores" which means (infi - 7), an amplification, was hashed in the TT. The originating node hashed only "infi - 5". In Natale's case, the fail high reached the root node and what was hashed was (infi - 5 - 12 + 0)!

You are talking about three different positions here: one is 12 plies away from root and shows "mate in 5 plies" from there, one is 10 plies away from root (the grandparent of the first) and shows "mate in 7 plies" from there, and one is the root showing "mate in 17 plies" from there. No "amplification", just three different nodes.

Sven

Of course they have to be different positions otherwise there could not be any "amplification". We could substitute 'OM' whenever we want to say 'amplification' if we like.

We are try to explain how a root search to depth of 16 can produce fail high +mate score of MATE76 which Natale found in his output. The amplification is 76/8.

It may be me now who may have to say "I have nothing more to add".

Best Regards,
Rasjid.

[Sven]

Of course they have to be different positions otherwise there could not be any "amplification". We could substitute 'OM' whenever we want to say 'amplification' if we like.

The term "amplification" seems to be misplaced here. Those three positions refer to exactly the same mating sequence of moves, seen from three different points on that sequence (ply=12, 10, 0). The tree score is the same for all (infi - 17). "Amplification" would be the effect caused by transposition, where a position close to the root with a "long" mate score is also encountered a second time but closer to the leaves, and then its parent, grandparent or any other node on the backup path to the root would store a "longer" mate score. But I think those "extra long" mate scores (if you ever manage to get them at some interior node) don't make it to the root since you already know a better (shorter) mate score at some point.

We are try to explain how a root search to depth of 16 can produce fail high +mate score of MATE76 which Natale found in his output. The amplification is 76/8.

I think that a mate in 76 plies should never show up in an iteration with a nominal depth of 16, unless there is some bug in the program. It should be prevented by alpha-beta.

Sven

[Chan Rasjid]

Hello Sven,

Of course they have to be different positions otherwise there could not be any "amplification". We could substitute 'OM' whenever we want to say 'amplification' if we like.

The term "amplification" seems to be misplaced here. Those three positions refer to exactly the same mating sequence of moves, seen from three different points on that sequence (ply=12, 10, 0). The tree score is the same for all (infi - 17). "Amplification" would be the effect caused by transposition, where a position close to the root with a "long" mate score is also encountered a second time but closer to the leaves, and then its parent, grandparent or any other node on the backup path to the root would store a "longer" mate score. But I think those "extra long" mate scores (if you ever manage to get them at some interior node) don't make it to the root since you already know a better (shorter) mate score at some point.

We are try to explain how a root search to depth of 16 can produce fail high +mate score of MATE76 which Natale found in his output. The amplification is 76/8.

I think that a mate in 76 plies should never show up in an iteration with a nominal depth of 16, unless there is some bug in the program. It should be prevented by alpha-beta.

Sven

I think we can ignore terminology for those hypermate scores. I have printed them and they are unlikely to be the result of bugs.

I am now almost sure that the depth 16 MATE76 fail high of Natales's output is not because of a bug, but a feature from his search. I have tweaked my engine to reproduce it and succeeded in getting greater amplification then his. The conditions :
1) fail soft.
2) TT always replace if signature matches.
3) Before researching fail high at root, do a hashstore() - maybe be unnecessary.
4) small TT size - 32 MB.
5) reverse move ordering.
6) start of new iteration with best = -infi, alpha = 500 cp, beta = 700 cp
7) anything else I forgot.

Mate fail high was first detected at about depth 12/14. My program was made to do some researches with progressively increased beta. One fail high score at root was 7895 (infi 8000); ie infi - 105 or MATE53 at depth 12. This was a much greater inflated score than what Natale got with his first fail high - something like only MATE25. But to explain how it happens could be a little tricky.

Best Regards,
Rasjid.

[Patrice Duhamel]

Hello,

Don't know if it helps, but for me one part of the problem with wrong mate scores was in null moves pruning.
In my condition to prevent zugzwang positions, I used the total number of non pawn pieces instead of the value for the current player.

Now there are other variations with mate scores in few endgames, and it's visible with all search options disabled (using only PVS + Quiescence), but I don't think it's a problem.