First post (and FailHigh question!)

[xmas79]

This is almost pure fail-hard The only deviation was already mentioned by Michael: you return "score" instead of "beta" in case of a beta cutoff (and additionally you possibly return a mate or draw score even if it is outside the alpha-beta window). But this won't make any difference in my opinion since the parent will simply not improve his "alpha" anyway, so the return value goes fully unnoticed. Even if you use the same algorithm at root I think it should not matter. But you can try whether I am right or wrong by replacing the "return score" by "return beta", of course

Sven

Well, let's say is something in between... First time I implemented this, I overlooked the wiki page, and I wrongly updated bestScore only when score was already above alpha, and that produced a very bad effect of backing up inconsistent mates to upper plies. Then I found a post that said that in FS bestscore could not be initialized to -INF, but already alpha, since returning values > beta you could propagate scores outside bounds and changed implementation... Thinking about it, it's true, parent will never improve alpha, so score will go unnoticed.

Now I did a true FS, QS and IID disabled, active only "hash, killers, search, evaluate" and I can see (at least I think I can see) what is happening there (the number aside ">" sign is the number of FH, window is opened with powers of two, starting with 1cp):

Code: Select all

--------------------------------------------------------------------------------
 00:00:01.302   15     Bd1-c2      16.5M    +6.00        1. Bd1-c2    Kh1-g1
                                                         2. Bc2-b1    Kg1-f1
                                                         3. Bb1-a2    Kf1-g1
                                                         4. Ba2-b1    Kg1-f1
                                                         5. Bb1-a2    Kf1-g1
                                                         6. Ba2-b3    Kg1-f1
                                                         7. Bb3-d1    Kf1-g1
                                                         8. Bd1-c2
 00:00:02.119   15     Bd1-e2      16.3M  +MATE25 > 1
 00:00:02.120   15     Bd1-e2       4.6M  +MATE24 > 2
 00:00:02.121   15     Bd1-e2       7.9M  +MATE23 > 3
 00:00:02.130   15     Bd1-e2      13.0M  +MATE21 > 4
 00:00:02.131   15     Bd1-e2      14.0M  +MATE17 > 5
 00:00:02.136   15     Bd1-e2      11.2M    +6.00        1. Bd1-e2    Kh1-g1
                                                         2. Be2-d1    Kg1-f1
                                                         3. Bd1-c2    Kf1-g1
                                                         4. Bc2-b1    Kg1-f1
                                                         5. Bb1-a2    Kf1-g1
                                                         6. Ba2-b1    Kg1-f1
                                                         7. Bb1-a2    Kf1-g1
                                                         8. Ba2-b1
--------------------------------------------------------------------------------
 00:00:02.996   16     Bd1-e2      10.8M  +MATE40 > 1
 00:00:03.016   16     Bd1-e2       9.6M  +MATE39 > 2
 00:00:03.017   16     Bd1-e2             +MATE38 > 3
 00:00:03.022   16     Bd1-e2       6.3M  +MATE36 > 4
 00:00:03.035   16     Bd1-e2       9.2M  +MATE32 > 5
 00:00:03.235   16     Bd1-e2      10.5M  +MATE24 > 6
 00:00:03.249   16     Bd1-e2       9.4M    +6.00        1. Bd1-e2    Kh1-g1
                                                         2. Be2-d1    Kg1-f1
                                                         3. Bd1-c2    Kf1-g1
                                                         4. Bc2-b1    Kg1-f1
                                                         5. Bb1-a2    Kf1-g1
                                                         6. Ba2-b1    Kg1-f1
                                                         7. Bb1-a2    Kf1-g1
                                                         8. Ba2-b3    Kg1-f1
--------------------------------------------------------------------------------
 00:00:08.211   17     Bd1-e2      16.4M  +MATE69 > 1
 00:00:08.212   17     Bd1-e2     319.0K  +MATE68 > 2
 00:00:08.213   17     Bd1-e2     351.0K  +MATE67 > 3
 00:00:08.215   17     Bd1-e2     351.0K  +MATE65 > 4
 00:00:08.220   17     Bd1-e2      13.0M  +MATE61 > 5
 00:00:08.292   17     Bd1-e2      16.4M  +MATE53 > 6
 00:00:08.312   17     Bd1-e2      16.2M  +MATE37 > 7
 00:00:08.438   17     Bd1-e2      16.8M    +6.00        1. Bd1-e2    Kh1-g1
                                                         2. Be2-d1
--------------------------------------------------------------------------------
 00:00:20.114   18     Bd1-e2       9.9M +MATE156 > 1
 00:00:20.203   18     Bd1-e2       9.2M +MATE155 > 2
 00:00:20.206   18     Bd1-e2       4.2M +MATE154 > 3
 00:00:20.207   18     Bd1-e2            +MATE152 > 4
 00:00:20.227   18     Bd1-e2       8.3M +MATE148 > 5
 00:00:20.235   18     Bd1-e2       8.3M +MATE140 > 6
 00:00:20.913   18     Bd1-e2       9.8M +MATE124 > 7
 00:00:25.632   18     Bd1-e2       9.8M  +MATE92 > 8
 00:00:26.515   18     Bd1-e2       9.4M  +MATE28 > 9
 00:00:27.029   18     Bd1-e2       9.7M    +6.00        1. Bd1-e2    Kh1-g1
                                                         2. Be2-d1    Kg1-f1
                                                         3. Bd1-c2    Kf1-g1
                                                         4. Bc2-b1    Kg1-f1
                                                         5. Bb1-a2    Kf1-g1
                                                         6. Ba2-b1    Kg1-f1
                                                         7. Bb1-a2    Kf1-g1
                                                         8. Ba2-b3    Kg1-f1
                                                         9. Bb3-d1    Kf1-g1
--------------------------------------------------------------------------------
 00:00:57.302   19     Bd1-e2      15.3M +MATE264 > 1
 00:00:57.315   19     Bd1-e2      13.5M +MATE263 > 2
 00:00:57.321   19     Bd1-e2      15.3M +MATE262 > 3
 00:00:57.322   19     Bd1-e2       3.4M +MATE260 > 4
 00:00:57.323   19     Bd1-e2       6.3M +MATE256 > 5
 00:00:57.350   19     Bd1-e2      15.4M +MATE248 > 6
 00:00:57.377   19     Bd1-e2      14.9M +MATE232 > 7
 00:01:25.478   19     Bd1-e2      15.7M +MATE200 > 8
 00:01:28.720   19     Bd1-e2      16.1M +MATE136 > 9
 00:01:35.279   19     Bd1-e2      15.8M    +6.00        1. Bd1-e2    Kh1-g1
                                                         2. Be2-d1    Kg1-f1
                                                         3. Bd1-c2    Kf1-g1
                                                         4. Bc2-b1    Kg1-f1
                                                         5. Bb1-a2    Kf1-g1
                                                         6. Ba2-b1    Kg1-f1
                                                         7. Bb1-a2    Kf1-g1
                                                         8. Ba2-b3    Kg1-f1
                                                         9. Bb3-d1    Kf1-g1
                                                        10. Bd1-c2
--------------------------------------------------------------------------------
 00:15:06.642   20     Bd1-e2       8.9M  +299.93 > 1
 00:15:28.677   20     Bd1-e2       9.2M  +MATE76 > 2
 00:15:30.529   20     Bd1-e2       9.3M  +MATE75 > 3
 00:15:30.565   20     Bd1-e2       9.1M  +MATE73 > 4
 00:15:30.569   20     Bd1-e2       7.5M  +MATE69 > 5
 00:15:30.688   20     Bd1-e2       8.9M  +MATE61 > 6
 00:15:30.791   20     Bd1-e2       9.2M  +MATE45 > 7
 00:17:51.152   20     Bd1-e2       9.3M    +6.00        1. Bd1-e2    Kh1-g2
                                                         2. Be2-d1    Kg2-f1
                                                         3. Bd1-c2    Kf1-g1
                                                         4. Bc2-b1    Kg1-f1
                                                         5. Bb1-a2    Kf1-g1
                                                         6. Ba2-b1    Kg1-f1
                                                         7. Bb1-a2    Kf1-g1
                                                         8. Ba2-b3    Kg1-f1
                                                         9. Bb3-d1    Kf1-g1
                                                        10. Bd1-c2    Kg1-f1
 00:20:31.284   20     Kd6-e5       9.2M  +MATE13 > 1
 00:21:40.464   20     Kd6-e5       9.2M  +MATE12 > 2
 00:21:57.154   20     Kd6-e5       9.3M  +MATE11 > 3
 00:23:11.766   20     Kd6-e5       9.2M    +6.00        1. Kd6-e5    Kh1-g2
                                                         2. Bd1-c2    Kg2-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1    Kg1-f1
                                                         9. Bd1-c2    Kf1-g1
                                                        10. Bc2-b1    Kg1-f1

With QS disabled, program is of course slower. And of course it cannot find mate at ply 14. It sees a mate at ply 15.

Q1) How a program can fail-high with a score like "mate in 25", that is _50_ plies, if it's "still" at ply 15?
A1) Hashtable hits! Debugging my code I saw HT is filled initially with few mate scores (something like mate in 3, because black doesn't move out of the corner, doesn't take a piece etc..., all these positions are analyzed and eventually stored in hashtable). Something like recursion, at some point, the program will enter a position say at ply 12, query the hashtable that is returning a score of mate in 3 and make the correction, that means mate in 9. That position can be hit on another part of the tree at ply 12 too, so it keep correcting the score until it reaches that mate in 25... These are NOT forced mates, are like "artificial" mates... And black can escape those artificial mates so root gets a score of 6.00.

Q2) Is that 6.00 score an exact score after 5 FH with scores like MATE17?
A2) Yes! _WE_ know this score is really a MATE11!!, the program still has not the depth to see it clearly. That score simply means black CAN be mated in at most 17 moves, but at ply 15 it cannot see a way to force a mate in less moves. In other means, the program is saying "if black is smart, he is safe for at most 17 moves..."

Q3) Other iterations?
A3) Well, I think hasthtable becomes full of mate scores eveywhere...And the positions stored gets stored with scores biggers and biggers... It's like a dog chasing its tail...

Q4) Iteration 20 finds a mate in 11, but then still scores 6.00.
A4) Read A2! It still misses one ply to mate (well, two plies effectively since _my_ evaluate has no idea of what mate is, and QS is disabled so mate is returned by the black site to move at ply 22).

Q5) Mate in 264??? That's funny!
A5) Yes it is... But looking at first FH of iteration 20 the score is 299.93, outside my mate scores (30000, where mate is 32000), that means a mate in 1000+ moves )) Quite easy to understand.... My program annouced mate in 1000 moves... oh yeah... It could be a fright for every top program!!!


I think that's all... If what I wrote is true (please someone confirm that!) I know there's no bug and the search works properly. It could be useful if someone else could disable extensions blah blah blah and test if his/her program behaves the same way.


Program is still running, after 50 mins still didn't go to ply 21...

Let me know....
Natl.

[Sven]

Hi Natale,

according to your report I am fully convinced that you have a very common bug which you need to fix as follows:

Whenever you store a mate score "mated in M plies from root" or "mate in M plies from root" at ply N you need to store a value that specifies "mated (mate)" in M-N plies relative from here". Whenever you retrieve a mate score "mated (mate) in K plies relative to the node where it was found" at ply L you need to convert the value into "mated (mate) in K+L plies from root".

This should help in your case.

Sven

[Henk]

Hi Natale,

according to your report I am fully convinced that you have a very common bug which you need to fix as follows:

Whenever you store a mate score "mated in M plies from root" or "mate in M plies from root" at ply N you need to store a value that specifies "mated (mate)" in M-N plies relative from here". Whenever you retrieve a mate score "mated (mate) in K plies relative to the node where it was found" at ply L you need to convert the value into "mated (mate) in K+L plies from root".

This should help in your case.

Sven

I do not trust transposition table, so I removed it from my chess program.
But I'm just a new bee.

[Chan Rasjid]

Hi Natale,

according to your report I am fully convinced that you have a very common bug which you need to fix as follows:

Whenever you store a mate score "mated in M plies from root" or "mate in M plies from root" at ply N you need to store a value that specifies "mated (mate)" in M-N plies relative from here". Whenever you retrieve a mate score "mated (mate) in K plies relative to the node where it was found" at ply L you need to convert the value into "mated (mate) in K+L plies from root".

This should help in your case.

Sven

I was also pondering what he was doing wrong, whether he treats mate scores as most of us do.

Code: Select all

int search(int depth, int ply){

    while (move){
        ...    
    }  
    
    if (incheck_and_all_moves_invalid){
        // this is how mate scores originate and passed around within search;
        // and this indicates the distance from root for this checkmate position.  
        bestscore = -infi + ply;
        //adjust to Mate_In_N; bestscore - ply == -infi in TT or checkmate.
        storehash(bestscore - ply, depth,...);
        return score;   
    }
    
    return bestscore;
}

In his original post where he searched a KBN_K position which was a mate-in-11 position,
the highest +mate score within TT when he search depth 22 from root is infi - 21, or mate-in-11.
There cannot be any higher mate-in-n stored in TT - like mate-in-50 (infi - 99).
EDIT - with QS disabled.

Best Regards,
Rasjid.

[xmas79]

Hi Sven and Chan,
this is what I do when store/retrieve from TT:

Store:

Code: Select all

	if (abs(boundValue) > MATE_SCORE)
	{
		if (boundValue > 0)
			boundValue += ply;
		else
			boundValue -= ply;
	}

Retrieve:

Code: Select all

			*dest = *htemp; // Copy hash to dest
			if (abs(dest->boundValue) > MATE_SCORE)
			{
				if (dest->boundValue > 0)
					dest->boundValue -= ply;
				else
					dest->boundValue += ply;
			}

where MATE_SCORE is 30000. It seems correct to me. I re-read Chan's post "My program cannot mate KRK/KQK", and it seems I'm doing nothing different.

To Chan:
I first though it was impossible to have mate scores < MATE_IN_11 (less than 32000-21), but tonight (dusing sleep) I thought about it and I'm convinced it's possible. The "problem" is the hashtable. Low mate scores get overwritten over and over with scores less than MATE_IN_11, that's why we are seeing that stuff.... Let me convince you with an example, (note i'm using always replace policy for TT):

1) You find a mate in 7 plies position.
2) _SOME_ parent of this position have a "mated in 8 plies" score
3) _SOME_ parent of the position at point 2 have a "mated in 9 plies" score
4) ... and so on until we get at root, with a score let's say "mate in 15 plies"
5) Now let's move to another completery branch of the tree... Here you encounter after making 14 plies the mate in 9 plies. That position has a mate in 21 plies, and since I have a beta of 6.50 this position gets stored too with a "mate in 21 plies" score.
6) Now let's move to another completery branch of the tree again... Here you encounter after making 12 plies the mate in 21 plies. That position has a mate in 33 plies, and since I have a beta of 6.50 this position gets stored too with a "mate in 33 plies" score.
7) and so on...

That's why I get that crazy mate scores... HT entries get overwritten over and over with lowers and lowers scores.

To confirm that behaviour, I just run the program with 512MB hashtable (all previous stuff is with simply 8MB), just to avoid hash collision... The output is this:

Code: Select all

--------------------------------------------------------------------------------
 00:00:01.316   15     Bd1-c2      14.0M    +6.00        1. Bd1-c2    Kh1-g1
                                                         2. Bc2-b1    Kg1-f1
                                                         3. Bb1-a2    Kf1-g1
                                                         4. Ba2-b1    Kg1-f1
                                                         5. Bb1-a2    Kf1-g1
                                                         6. Ba2-b3    Kg1-f1
                                                         7. Bb3-d1    Kf1-g1
                                                         8. Bd1-c2
 00:00:01.878   15     Kd6-e5      12.7M  +MATE24 > 1
 00:00:01.879   15     Kd6-e5     129.0K  +MATE22 > 2
 00:00:01.880   15     Kd6-e5     205.0K  +MATE21 > 3
 00:00:01.881   15     Kd6-e5     241.0K  +MATE19 > 4
 00:00:01.884   15     Kd6-e5       3.7M  +MATE15 > 5
 00:00:01.890   15     Kd6-e5      10.3M    +6.00        1. Kd6-e5    Kh1-g1
                                                         2. Bd1-c2    Kg1-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1
--------------------------------------------------------------------------------
 00:00:02.479   16     Kd6-e5       8.7M  +MATE30 > 1
 00:00:02.499   16     Kd6-e5       7.4M  +MATE29 > 2
 00:00:02.500   16     Kd6-e5     917.0K  +MATE28 > 3
 00:00:02.505   16     Kd6-e5       6.1M  +MATE26 > 4
 00:00:02.508   16     Kd6-e5       6.9M  +MATE22 > 5
 00:00:02.529   16     Kd6-e5       8.3M    +6.00        1. Kd6-e5    Kh1-g1
                                                         2. Bd1-c2    Kg1-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1    Kg1-f1
--------------------------------------------------------------------------------
 00:00:03.382   17     Kd6-e5      13.1M  +MATE28 > 1
 00:00:03.383   17     Kd6-e5     154.0K  +MATE27 > 2
 00:00:03.388   17     Kd6-e5       8.3M  +MATE26 > 3
 00:00:03.396   17     Kd6-e5      11.1M  +MATE24 > 4
 00:00:03.401   17     Kd6-e5      12.5M  +MATE20 > 5
 00:00:03.852   17     Kd6-e5      11.8M  +MATE12 > 6
 00:00:03.859   17     Kd6-e5       9.7M    +6.00        1. Kd6-e5    Kh1-g1
                                                         2. Bd1-c2    Kg1-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1    Kg1-f1
                                                         9. Bd1-c2
--------------------------------------------------------------------------------
 00:00:05.004   18     Kd6-e5       8.4M  +MATE27 > 1
 00:00:05.061   18     Kd6-e5       7.9M  +MATE24 > 2
 00:00:05.061   18     Kd6-e5             +MATE23 > 3
 00:00:05.073   18     Kd6-e5       6.1M  +MATE21 > 4
 00:00:05.079   18     Kd6-e5       8.0M  +MATE17 > 5
 00:00:05.702   18     Kd6-e5       8.2M    +6.00        1. Kd6-e5    Kh1-g2
                                                         2. Bd1-c2    Kg2-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1    Kg1-f1
                                                         9. Bd1-c2    Kf1-g1
--------------------------------------------------------------------------------
 00:00:07.205   19     Kd6-e5      11.1M  +MATE38 > 1
 00:00:07.206   19     Kd6-e5       2.5M  +MATE31 > 2
 00:00:07.817   19     Kd6-e5      10.5M  +MATE27 > 3
 00:00:08.237   19     Kd6-e5      10.3M  +MATE25 > 4
 00:00:08.250   19     Kd6-e5       8.6M  +MATE21 > 5
 00:00:08.327   19     Kd6-e5      11.2M  +MATE13 > 6
 00:00:08.460   19     Kd6-e5      10.8M    +6.00        1. Kd6-e5    Kh1-g2
                                                         2. Bd1-c2    Kg2-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1    Kg1-f1
                                                         9. Bd1-c2    Kf1-g1
                                                        10. Bc2-b1
--------------------------------------------------------------------------------
 00:00:10.179   20     Kd6-e5       8.1M  +MATE44 > 1
 00:00:10.180   20     Kd6-e5     890.0K  +MATE43 > 2
 00:00:10.182   20     Kd6-e5     417.5K  +MATE42 > 3
 00:00:10.188   20     Kd6-e5       6.9M  +MATE40 > 4
 00:00:10.189   20     Kd6-e5       8.1M  +MATE36 > 5
 00:00:10.936   20     Kd6-e5       7.9M  +MATE28 > 6
 00:00:11.567   20     Kd6-e5       7.8M  +MATE12 > 7
 00:00:12.694   20     Kd6-e5       7.8M    +6.00        1. Kd6-e5    Kh1-g2
                                                         2. Bd1-c2    Kg2-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1    Kg1-f1
                                                         9. Bd1-c2    Kf1-g1
                                                        10. Bc2-b1    Kg1-f1
--------------------------------------------------------------------------------
 00:00:14.683   21     Kd6-e5       9.8M  +MATE50 > 1
 00:00:14.685   21     Kd6-e5       6.5M  +MATE49 > 2
 00:00:14.810   21     Kd6-e5      12.3M  +MATE48 > 3
 00:00:14.810   21     Kd6-e5             +MATE46 > 4
 00:00:14.812   21     Kd6-e5       1.3M  +MATE42 > 5
 00:00:14.848   21     Kd6-e5      10.0M  +MATE34 > 6
 00:00:16.329   21     Kd6-e5       9.2M  +MATE18 > 7
 00:00:18.311   21     Kd6-e5       9.8M    +6.00        1. Kd6-e5    Kh1-g2
                                                         2. Bd1-c2    Kg2-f1
                                                         3. Bc2-b1    Kf1-g1
                                                         4. Bb1-a2    Kg1-f1
                                                         5. Ba2-b1    Kf1-g1
                                                         6. Bb1-a2    Kg1-f1
                                                         7. Ba2-b3    Kf1-g1
                                                         8. Bb3-d1    Kg1-f1
                                                         9. Bd1-c2    Kf1-g1
                                                        10. Bc2-b1    Kg1-f1
                                                        11. Bb1-a2
--------------------------------------------------------------------------------
 00:00:20.683   22     Kd6-e5       7.9M  +MATE76 > 1
 00:00:20.684   22     Kd6-e5       2.0M  +MATE74 > 2
 00:00:20.692   22     Kd6-e5       5.5M  +MATE72 > 3
 00:00:20.693   22     Kd6-e5     686.0K  +MATE70 > 4
 00:00:20.694   22     Kd6-e5       1.4M  +MATE65 > 5
 00:00:20.747   22     Kd6-e5       7.6M  +MATE57 > 6
 00:00:20.749   22     Kd6-e5       5.9M  +MATE41 > 7
 00:00:25.397   22     Kd6-e5!!     7.8M  +MATE11        1. Kd6-e5    Kh1-g2
                                                         2. Ke5-f4    Kg2-h3
                                                         3. Bd1-e2    Kh3-h4
                                                         4. Nd3-e1    Kh4-h3
                                                         5. Be2-g4+   Kh3-h2
                                                         6. Kf4-f3    Kh2-g1
                                                         7. Bg4-h3    Kg1-h2
                                                         8. Kf3-g4    Kh2-g1
                                                         9. Kg4-g3    Kg1-h1
                                                        10. Bh3-g2+   Kh1-g1
                                                        11. Ne1-f3#

25 five seconds search and BUM!
I think avoiding to store mate scores lower than the score already stored could improve the situation, but I'm not sure if it's the right to do...

Best regards,
Natl.

[Chan Rasjid]

Hello Natale,

I first though it was impossible to have mate scores < MATE_IN_11 (less than 32000-21), but tonight (dusing sleep) I thought about it and I'm convinced it's possible. The "problem" is the hashtable. Low mate scores get overwritten over and over with scores less than MATE_IN_11, that's why we are seeing that stuff.... Let me convince you with an example, (note i'm using always replace policy for TT):

1) You find a mate in 7 plies position.
2) _SOME_ parent of this position have a "mated in 8 plies" score
3) _SOME_ parent of the position at point 2 have a "mated in 9 plies" score
4) ... and so on until we get at root, with a score let's say "mate in 15 plies"
5) Now let's move to another completery branch of the tree... Here you encounter after making 14 plies the mate in 9 plies. That position has a mate in 21 plies, and since I have a beta of 6.50 this position gets stored too with a "mate in 21 plies" score.
6) Now let's move to another completery branch of the tree again... Here you encounter after making 12 plies the mate in 21 plies. That position has a mate in 33 plies, and since I have a beta of 6.50 this position gets stored too with a "mate in 33 plies" score.
7) and so on...

That's why I get that crazy mate scores... HT entries get overwritten over and over with lowers and lowers scores.

--------------------------------------------------------------------------------
00:00:20.683 22 Kd6-e5 7.9M +MATE76 > 1
00:00:20.684 22 Kd6-e5 2.0M +MATE74 > 2
00:00:20.692 22 Kd6-e5 5.5M +MATE72 > 3
00:00:20.693 22 Kd6-e5 686.0K +MATE70 > 4
00:00:20.694 22 Kd6-e5 1.4M +MATE65 > 5
00:00:20.747 22 Kd6-e5 7.6M +MATE57 > 6
00:00:20.749 22 Kd6-e5 5.9M +MATE41 > 7
00:00:25.397 22 Kd6-e5!! 7.8M +MATE11 1. Kd6-e5 Kh1-g2
2. Ke5-f4 Kg2-h3
3. Bd1-e2 Kh3-h4
4. Nd3-e1 Kh4-h3
5. Be2-g4+ Kh3-h2
6. Kf4-f3 Kh2-g1
7. Bg4-h3 Kg1-h2
8. Kf3-g4 Kh2-g1
9. Kg4-g3 Kg1-h1
10. Bh3-g2+ Kh1-g1
11. Ne1-f3#

1) Are you sure you cleared your TT before a search? There may be info from a previous search that may be a continuation of your chess tree.

2) Are you sure your TT implementation is ok. Hashing TT positions require a 64-bit hash-signature that are usually > 32 bits extracted from the zobrist key. A hash hit requires that there is a signature match. If it is wrong and you did not initialize you TT to all 0's, there may be problems.

I am not really able to follow your reasoning. But if you can say if I am right or wrong here, then, you probably could know what's wrong with your search, if any.

With a search (without QS ) at root to depth of 22 and say at a node at ply 8, a probe of TT show a hit of a lower/exact +mate score of mate-in-50; ie a TT score of 32000 - 99; adjusted for ply of the probe position (8), you have:
bestscore = 32000 - 99 - 8 = 32000 - 107;
if beta = 6.50, you fail high with the bestscore.

The question is this : the +mate score of 32000 - 107 points to a checkmate position which is 107 plies from the root. But your chess tree have a maximum reach of at most ply 21. For a root search of depth 22, how can your search has knowledge of nodes far beyond the greatest possible chess tree.

Best Regards,
Rasjid.

[Sven]

1) You find a mate in 7 plies position.
2) _SOME_ parent of this position have a "mated in 8 plies" score

Please explain how your program reacts on 1).
Please explain what you mean by 2), and how your program reacts there.

The way you describe your ever growing mate scores sounds very familiar to me, I had exactly the same problem long ago when the hash table code of my oldest engine "Surprise" did not work correctly yet. And it was exactly that mate score conversion that was missing back then ...

Are you really sure that the mate score conversion code you have shown is always being used? Any condition around it? Maybe you add some printf's to see what really happens ...

Sven

[xmas79]

Hi Chan,

1) Are you sure you cleared your TT before a search? There may be info from a previous search that may be a continuation of your chess tree.

Yes. I load the FEN position directly and reset TT with all zeros at the beginning of the search (not iteration).

2) Are you sure your TT implementation is ok. Hashing TT positions require a 64-bit hash-signature that are usually > 32 bits extracted from the zobrist key. A hash hit requires that there is a signature match. If it is wrong and you did not initialize you TT to all 0's, there may be problems.

My hash-signature is 64-bit, as far as I can tell I have no bugs in movegen/make/unmake as I tested extensively before implementing basic search structure. Hash hit requires a signature match and a draft condition (stored draft >= current draft). I also have multiple slots per hash index.

I am not really able to follow your reasoning. But if you can say if I am right or wrong here, then, you probably could know what's wrong with your search, if any.

With a search (without QS ) at root to depth of 22 and say at a node at ply 8, a probe of TT show a hit of a lower/exact +mate score of mate-in-50; ie a TT score of 32000 - 99; adjusted for ply of the probe position (8), you have:
bestscore = 32000 - 99 - 8 = 32000 - 107;
if beta = 6.50, you fail high with the bestscore.

The question is this : the +mate score of 32000 - 107 points to a checkmate position which is 107 plies from the root. But your chess tree have a maximum reach of at most ply 21. For a root search of depth 22, how can your search has knowledge of nodes far beyond the greatest possible chess tree.

Let me explain it more precisely... We already know that original position is mate in 11, and there's no doubt about it. So suppose a ply 22 search returned already that mate score (32000-21 = 31979). Let's suppose I do not stop iterating at ply 22 (as I found the minimal mate and I could stop searching), and keep iterating. Let's suppose we are starting iteration at depth 26. Is it possible to reach the original position at ply different than 0 and get a hash hit? Well, yes, by a long sequence of moves that leads to the same position after exactly 26 plies. We can suppose it can happen because TT entries can be overwritten, PV sometimes is truncated, move order at this point can be completely random and I have no evaluation that drives search towards best moves (and that's another story...)
In this case we are at ply=26 and can get a hash hit (draft condition is OK and hash signature is OK) returning a score back that is 31979. At this point, we will adjust the score by subtracting 26 plies from 31979 ---> 31953 ---> which is a mate in 47 plies even if horizon is at ply 26. So I have just replaced my "mate in 21 plies" TT entry with one that says "mate in 47 plies"... And this entry can be in turn be hit and get replaced by another "mate in 85 plies" and so on...

My intuition says this is happening here, but I can't explain better than this, and I have no other means to explain this behaviour... Maybe what I wrote is completely wrong, but I need something that points my eyes on the (very subdole) bug (if any), because if this is not a "standard" behaviour, well I really don't have idea of what's happening here and of what I'm really doing....


Thanks for your help anyway,
Natl.


P.S. You could test your engine and see if it behaves the same way... It should be easy to disable advanced things and such, and test the plain endgame... Just to be sure I have a bug and you haven't, or you have a bug and I don't... Fail-hard vs Fail-soft doesn't matter, just see if at some point it fails high and on the research the score is back to the evaluation...

[xmas79]

Hi Sven,

1) You find a mate in 7 plies position.
2) _SOME_ parent of this position have a "mated in 8 plies" score

Please explain how your program reacts on 1).

When I find a mate in 7 plies, if i'm iterating at depth >= 7 then it's a minimal mate, so I stop searching (I let the search finish and then stop iterating), else I let the search go on. But in every case I do exactly nothing different.

Please explain what you mean by 2), and how your program reacts there.

By 2) I mean I can reach this position by different paths at different depths, that's why I wrote "SOME". Strictly speaking, a node can have only one parent, but chess tree actually is not a tree, but a graph. So every node whose children are connected to this node can be seen as "parents". Since we can reach the same position by different paths (and plies), it can happen that I reach this node very near the horizon, so I actually call evaluate and not discover it's a mate position. So some of the parents nodes get a mate score, some don't.

The way you describe your ever growing mate scores sounds very familiar to me, I had exactly the same problem long ago when the hash table code of my oldest engine "Surprise" did not work correctly yet. And it was exactly that mate score conversion that was missing back then ...

Are you really sure that the mate score conversion code you have shown is always being used? Any condition around it? Maybe you add some printf's to see what really happens ...

Sven

Yes, printf & friends were the first things I did. Score correction is also the very first thing I do in the StoreHash function...

Thank you,
Natl.

[Sven]

In this case we are at ply=26 and can get a hash hit (draft condition is OK and hash signature is OK) returning a score back that is 31979. At this point, we will adjust the score by subtracting 26 plies from 31979 ---> 31953 ---> which is a mate in 47 plies even if horizon is at ply 26. So I have just replaced my "mate in 21 plies" TT entry with one that says "mate in 47 plies"... And this entry can be in turn be hit and get replaced by another "mate in 85 plies" and so on...

If your description matches the behaviour of your engine then there is a fundamental error, and I would still search for it in the context of mate score handling. Let me explain what *should* happen in the example above.

The score +31979 is "mate in 21 plies from root" from search point of view. If you have initially stored it, say, at ply=20 then it was "mate in 1 ply" relative to that point, so you would have stored +31999 in the hash table. If you visit the same position later on through a different path at ply=26 and you get a hash hit then it is still "mate in 1 ply from here", so you would convert it back into "mate in 27 plies from root" for the search, i.e. +31973.

But this score should not make it up to the root if you already found a shorter mate (and you did, if we assume that your node scored with +31979 was on the PV of the root node).

Now what happens two levels above the node scored +31973? First we have the direct parent at ply=25. Let's say at this level the opponent has no other relevant move, so he gets a -31973 score and stores it as -(31973+25) = -31998 in the TT: "mated in 2 plies from here". The parent at the next level, ply=24, gets +31973, and if that is again the best score he will store +31997 in the TT: "mate in 3 plies from here". At some point you will back up that "mate in 27 plies from root" to a node that knows a shorter mating variation, so it will discard the +31973 and keep its current best score. If that mechanism does not work then you can never find the shortest path to mate correctly (which can sometimes lead to even being unable to mate at all since a mate in 1 is not always seen as better as a mate in 2), and furthermore you get funny effects like the one you describe.

If it is not the mate score conversion code that causes your trouble then it must be some other (probably hashtable-related) code in your search. It is NOT a normal behaviour that you can accept and move on

Sven