First post (and FailHigh question!)

[xmas79]

Hi Chan,

Hello Natale,

Hi Chan,

There is something which I still cannot understand with Natale's output. From what I now understand, at depth 20, the +mate score that search may have is limited to infi - 19 - 19, or infi - 38; ie MATE19. So I don't understand why the output has scores like MATE76.

Chan, you're not thinking fourth dimensionally! It's easy to understand those mate scores as well: what if at next iteration (say depth 16) you hit the same position at a node C you already had at node B while searching ply 15? Since you got a cut-off early and stored a score of infi-17 now you will get that score-15, infi-17-15, infi-32! And you will store that score as well... And the more next iteration you'll get another cutoff getting a score of infi-32-ply_i_will_hit_this_position_again. In this way at ply 20 I can have a MATE76 score...

If at the next iteration at a node C which has the same position as B (which is also that of A), then again the node will not be searched as there will be an exact TT hit. It will still be probing the same TT entry which B got and it would be the same TT entry that was hashed when node A was search: infi - 5. So the retrieved TT exact best-score that C has will be infi - 5 - 15, or infi - 20; So search immediately returns the score infi - 20. This contradicts your score of infi - 32.

The contradiction arises from the contradiction of what you said earlier with what is stated in this quote. In an earlier reply, you mentioned that your search returns straight from any TT cutoff without rehashing the same position. But now, what you say is "you got a cut-off early and stored a score of infi-17". Storing infi - 17 in the TT for node B is wrong as it is mate-in-3 from node B; ie infi - 5.

My analysis here may also be wrong just as how I traveled to the moon and back

Best Regards,
Rasjid.

You get a hash hit when you are searching THAT position. And you get and backup the score of infi- 5. That's all. But in the parnet node, you will adjust the score to infi-5-12, infi-17, and that score is still above beta, so another cut-off occurs, and if a cut-off occurs you must store that position/score/move in the hash. In that way you will store a inf-17 score. And next time you will encounter this position again, a probe in THAT position will result in a hash hit of a score of infi-17 and you'll backup immediately that score as well, and the parent will adjust the score to infi-17-15,infi-32, and as it is still above beta, another cut-off will occurr, causing another store in the TT with a score of infi-32 and so on... Got it?

[xmas79]

Do you mean without hash probing in QS?

Yes, I don't use the hashtable in quiescence search.

And for your problem, do you have a different result if you enable or disable mate score adjustment ?

Another thing: have you implemented perft? Yes... Of course you did... Well, did you implemented perft when you added your staged move gen?

Of course I have a perft function and used it many times, but in perft I don't use the new staged move generation.

I think it is a problem with hash table but I don't know what is wrong.

Thanks.

I actually don't even use QS If I remove mate score adjustment everything doesn't work. It won't be able to mate etc... So I really never tried.

Perfting you staged move gen shuold be very easy. Do something like I suggested. In my opinion it's worth debugging, as movegen is the basis. Then you can move on debugging TT.

[Sven]

You get a hash hit when you are searching THAT position. And you get and backup the score of infi- 5. That's all. But in the parnet node, you will adjust the score to infi-5-12, infi-17, and that score is still above beta, so another cut-off occurs, and if a cut-off occurs you must store that position/score/move in the hash. In that way you will store a inf-17 score. And next time you will encounter this position again, a probe in THAT position will result in a hash hit of a score of infi-17 and you'll backup immediately that score as well, and the parent will adjust the score to infi-17-15,infi-32, and as it is still above beta, another cut-off will occurr, causing another store in the TT with a score of infi-32 and so on... Got it?

You are wrong, sorry. Maybe I have to explain it one more time.

1) You are at node A1 at ply=12 (i.e., distance to root = 12 plies) and get a hash hit with an exact mate score "+(infi-5)", i.e. "mate in 5 plies from here".

2) You adjust the retrieved score to the current ply by subtracting 12 to get a valid tree score, so you return "+(infi-17)".

3) Now the direct parent gets back "-(infi-17)" from that subtree. To be able to continue the discussion about your "cutoff" case let's assume the move was forced, or there are no better moves for the opponent, so it returns this "-(infi-17)" value to the grandparent of A1.

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". Why? Because he indirectly got back the "mate in 5 plies from A1" and A1 is two plies away, so the grandparent knows "I can mate in at most 7 plies from here".

5) Following the principle above, you will never be able, with correct hash table and search implementation, to get a mate distance of more than roughly twice the longest mate distance that you can find within the given iteration *without* using a hash table. It should be easy to figure out why. Especially there can't be an effect like the one you described where mate scores grow in an almost uncontrolled manner.

Regarding your original problem, I have not seen yet whether you have solved it or not, so assuming you haven't, have you already found an explanation for the fact that your iteration 14 failed high with a mate score (which may or may not result from a wrong mate score somewhere below) but the research does not confirm the mate?

Sven

[xmas79]

Regarding your original problem, I have not seen yet whether you have solved it or not, so assuming you haven't, have you already found an explanation for the fact that your iteration 14 failed high with a mate score (which may or may not result from a wrong mate score somewhere below) but the research does not confirm the mate?

Sven

Hi Sven,
I have not resolved yet. I'm still investigating... I have an idea, but still nothing certain...

Best regards,
Natale.

[Chan Rasjid]

Hello Sven,

You get a hash hit when you are searching THAT position. And you get and backup the score of infi- 5. That's all. But in the parnet node, you will adjust the score to infi-5-12, infi-17, and that score is still above beta, so another cut-off occurs, and if a cut-off occurs you must store that position/score/move in the hash. In that way you will store a inf-17 score. And next time you will encounter this position again, a probe in THAT position will result in a hash hit of a score of infi-17 and you'll backup immediately that score as well, and the parent will adjust the score to infi-17-15,infi-32, and as it is still above beta, another cut-off will occurr, causing another store in the TT with a score of infi-32 and so on... Got it?

You are wrong, sorry. Maybe I have to explain it one more time.

1) You are at node A1 at ply=12 (i.e., distance to root = 12 plies) and get a hash hit with an exact mate score "+(infi-5)", i.e. "mate in 5 plies from here".

2) You adjust the retrieved score to the current ply by subtracting 12 to get a valid tree score, so you return "+(infi-17)".

3) Now the direct parent gets back "-(infi-17)" from that subtree. To be able to continue the discussion about your "cutoff" case let's assume the move was forced, or there are no better moves for the opponent, so it returns this "-(infi-17)" value to the grandparent of A1.

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". Why? Because he indirectly got back the "mate in 5 plies from A1" and A1 is two plies away, so the grandparent knows "I can mate in at most 7 plies from here".

5) Following the principle above, you will never be able, with correct hash table and search implementation, to get a mate distance of more than roughly twice the longest mate distance that you can find within the given iteration *without* using a hash table. It should be easy to figure out why. Especially there can't be an effect like the one you described where mate scores grow in an almost uncontrolled manner.

Regarding your original problem, I have not seen yet whether you have solved it or not, so assuming you haven't, have you already found an explanation for the fact that your iteration 14 failed high with a mate score (which may or may not result from a wrong mate score somewhere below) but the research does not confirm the mate?

Sven

The unrestricted magnification of search mate scores happens and I think it is not a bug. I have confirmed it by printing out within the internal nodes all TT cutoff with +mate score where score <= inf - 3 * N where N is the root iteration depth. Many were found.

The reason for the magnification is that a chess tree of KBN-K have many nodes being transpositions - K/B/N all have most moves being reversible. When a +mate score gets returned as a fail high from a TT cutoff, it may be propagated towards the root and hashed as a fail high lower bound. There should be many such hashed positions at lower plies. These nodes have transpositions higher up the tree. When these higher nodes are reached, a TT cutoff again magnify the score and it gets passed down. These recursive sequences repeats with every root iteration and it is why Natale has scores like MATE76 for fail high at root.

So Natale's program behavior should not be a bug but rather is a case of search instability. The only difficulty is to explain when and why the mate score fail high stops as beta is progressively relaxed and researched at the root.

Best Regards,
Rasjid.

[xmas79]

Hi all
I'm under pressure at work, so I have to stop for a week. Yesterday night I begun to write a debug code to extract TT scores, when they are probed/stored. It's not finished yet, but I think it will help us to find out exactly what's wrong or not. Chan's reasoning is right for sure. The problem I described in the orignal post is amplified with small TT sizes, so I think it is more like an "overwrite feature" of the TT policy than a real TT bug. A search instability. But before I move on, as I always have done until now, I want to be sure I have no bugs in my code. If it's plain search instability, OK, move on. Else I don't want to add features like LMR, null-moves and so, which makes debugging more painful...

And the reason I fail high with such mate scores and then I do not fail high when beta is wide open must be searched in the fact that when I have beta less than say MATE100, a MATE76 score is propagated back to the root caused by a failhigh at ply 3. The research then WILL overwrite one or more cricical TT entries on ply 3 and I miss the mate. It' like having 6 mating sequences of say 9 plies each, and connecting the tail of one to the head of another. That way I have a longer "mate" than my search horizon. But if I overwrite an entry that is in the middle of one of those mating sequences I miss the final mate score from hash hits and I have to rely on search, which has no sufficient depth to see the mate in 11 (or 37 whatsoever). Another thing is happening for sure is that I hit a position A1 with a mate score like "mate in 7 plies", then the search connects this node to another node which has a score "mate in 5 plies" and a cut-off, and depending on which ply I get that hit, I store the adjusted score in fancy ways (ply=18 ---> mate in 23, ply=3 ---> mate in 8) overwriting (due to hash collisions) original slot which could contain a mate in 3 plies. Bigger hash table, in fact result in less overwriting, hence lesser big mate scores (MATE in 20 at most if I recall correctly).

That's all for now.

Best regards,
Natale.


EDIT: typo on ply=3 adjustment

[tpetzke]

So Natale's program behavior should not be a bug but rather is a case of search instability. The only difficulty is to explain when and why the mate score fail high stops as beta is progressively relaxed and researched at the root.

But if this would be the case then it should show up in other programs as well, shouldn't it ? But I think most engines will handle that correctly.

I handle the Mate scores in my TT rather straight forward. I dedicate a few bits in the hash entry to store the ply the score comes from. And if the score is probed from a different ply and it is a Mate score the difference between the plys is added or subtracted.

Code: Select all

/***********************************************************************************************
*   Adjust a possible mate score to the ply where it is probed from
*   e.g. in the hash a mate score 'mate in 3' resulting from ply 10 is stored = mate at ply 16
*   if the hash is hit at ply 12 then the store mate in 3 must be translated into mate at ply 18
************************************************************************************************/
int TMainTranspositionTable::adjustMateScore(int hashScore, int hashScoreFromPly, int hashProbeFromPly)
{
	int	plyDiff;

	if &#40;hashScore < -ICE_INFINITY + MAX_BOARD_HISTORY&#41;         // a mate score for the active side detected
	&#123;
		plyDiff = hashScoreFromPly - hashProbeFromPly;
		return &#40;hashScore - plyDiff&#41;;
	&#125; else if &#40;hashScore > ICE_INFINITY - MAX_BOARD_HISTORY&#41;   // a mate score for the passive side detected
	&#123;
		plyDiff = hashScoreFromPly - hashProbeFromPly;
		return &#40;hashScore + plyDiff&#41;;
	&#125; else return hashScore;
&#125;

Thomas...

[Chan Rasjid]

Hello Thomas,

So Natale's program behavior should not be a bug but rather is a case of search instability. The only difficulty is to explain when and why the mate score fail high stops as beta is progressively relaxed and researched at the root.

But if this would be the case then it should show up in other programs as well, shouldn't it ? But I think most engines will handle that correctly.

I handle the Mate scores in my TT rather straight forward. I dedicate a few bits in the hash entry to store the ply the score comes from. And if the score is probed from a different ply and it is a Mate score the difference between the plys is added or subtracted.

Code: Select all

/***********************************************************************************************
*   Adjust a possible mate score to the ply where it is probed from
*   e.g. in the hash a mate score 'mate in 3' resulting from ply 10 is stored = mate at ply 16
*   if the hash is hit at ply 12 then the store mate in 3 must be translated into mate at ply 18
************************************************************************************************/
int TMainTranspositionTable::adjustMateScore(int hashScore, int hashScoreFromPly, int hashProbeFromPly)
{
	int	plyDiff;

	if &#40;hashScore < -ICE_INFINITY + MAX_BOARD_HISTORY&#41;         // a mate score for the active side detected
	&#123;
		plyDiff = hashScoreFromPly - hashProbeFromPly;
		return &#40;hashScore - plyDiff&#41;;
	&#125; else if &#40;hashScore > ICE_INFINITY - MAX_BOARD_HISTORY&#41;   // a mate score for the passive side detected
	&#123;
		plyDiff = hashScoreFromPly - hashProbeFromPly;
		return &#40;hashScore + plyDiff&#41;;
	&#125; else return hashScore;
&#125;

Thomas...

I am not too sure what you mean by "it" should show up in other engines as well.

The following is an analysis from my engine:

info depth 16, score +780 cp, time 18471 ms, nodes 75641701 nps 4095160, pv d6e5 h1g2 e5f4 g2h3 f4g5 h3g3 d1g4 g3h2 g5h4 h2g2 g4d1 g2g1
depth 17, score +780 cp, d6e5
info depth 17, score +780 cp, time 28291 ms, nodes 115758899 nps 4091721, pv d6e5 h1g2 e5f4 g2h3 f4g5 h3g3 d1g4 g3h2 g5h4 h2g2 g4d1 g2g1 d1f3 g1f1
!!! History Max reached
rsc depth 18 score 7971
!!! Matesearch Reduce History 8863839
depth 18, score +7973 cp, d6e5
info depth 18, +mate 14, time 34403 ms, nodes 139625140 nps 4058516, pv d6e5 h1g2 e5f4 g2h3 d3e1
depth 20, score +7979 cp, d6e5
info depth 20, +mate 11, time 41164 ms, nodes 158816362 nps 3858137, pv d6e5 h1g2 e5f4 g2h3 d3e1 h3h4 e1g2 h4h3 f4f3 h3h2 f3f2 h2h3 d1e2 h3h2 g2f4 h2h1 f2g3
info depth 22, +mate 11, time 47157 ms, nodes 178028684 nps 3775233, pv d6e5 h1g2 e5f4 g2h3 d3e1 h3h4 e1g2 h4h3 f4f3 h3h2 f3f2 h2h3 d1e2 h3h2 g2f4 h2h1 f2g3 h1g1
Matesearch found no better mate 7979, depth 22, d6e5
info depth 24, +mate 11, time 53216 ms, nodes 197481701 nps 3710945, pv d6e5 h1g2 e5f4 g2h3 d3e1 h3h4 e1g2 h4h3 f4f3 h3h2 f3f2 h2h3 d1e2 h3h2 g2f4 h2h1 f2g3 h1g1

Within internal nodes, my engine did detect mate scores far from infi - N; some more than inf - 3 * N. But only mate scores within infi - 2 * N reached the root and failed high. At depth 18, there is a first fail high with a +mate score +7973, infi - 27 or mate14. This is beyond the horizon ply of 17 (mate9). But it is still within infi - 2 * 17. I think this is also true for my engine even for other positions (I checked one KQK position).

I have no idea as to how Natale's could fail high at root with scores much further from infi - 2 * N.

I am not too sure if your method of hashing mate scores is any different or simpler or more complex than the way most of us are using. Ours is the way how Crafty handles mate scores within TT. From what I know, it seems there is only another "acceptable" alternative - that of Gert Muller; and he should be the only one implementing it. Gert's method is the reverse of how most do it. His mate scores within TT are all mate from root. The scores within search is mate-in-N type. But he needs to dynamically shift alpha and beta by 1 on every call to search() and return from search(). I don't understand how it works, but he claimed "it works like a charm that never failed me!" .

Best Regards,
Rasjid.

[Chan Rasjid]

I handle the Mate scores in my TT rather straight forward. I dedicate a few bits in the hash entry to store the ply the score comes from. And if the score is probed from a different ply and it is a Mate score the difference between the plys is added or subtracted.

Code: Select all

/***********************************************************************************************
*   Adjust a possible mate score to the ply where it is probed from
*   e.g. in the hash a mate score 'mate in 3' resulting from ply 10 is stored = mate at ply 16
*   if the hash is hit at ply 12 then the store mate in 3 must be translated into mate at ply 18
************************************************************************************************/
int TMainTranspositionTable::adjustMateScore(int hashScore, int hashScoreFromPly, int hashProbeFromPly)
{
	int	plyDiff;

	if &#40;hashScore < -ICE_INFINITY + MAX_BOARD_HISTORY&#41;         // a mate score for the active side detected
	&#123;
		plyDiff = hashScoreFromPly - hashProbeFromPly;
		return &#40;hashScore - plyDiff&#41;;
	&#125; else if &#40;hashScore > ICE_INFINITY - MAX_BOARD_HISTORY&#41;   // a mate score for the passive side detected
	&#123;
		plyDiff = hashScoreFromPly - hashProbeFromPly;
		return &#40;hashScore + plyDiff&#41;;
	&#125; else return hashScore;
&#125;

Thomas...

I think your method of handling mates scores is just a slight variation of that of Crafty's - but with an additional cost of a few addition memory bits.

Mate scores within search would still be of type distance-to-mate-from root. If it is correct, than within internal nodes, large amplification of mate scores should also happen.

Best Regards,
Rasjid.

[tpetzke]

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