First post (and FailHigh question!)

[Chan Rasjid]

Hello Natale,

I think I now understand why search (without QS) may see +mate score of mate-in-25(50 plies from the root) when it is still in the root iteration for a low depth of, say, 15. It is the working of chess position transposition in combination with TT hashing. If we have not encountered such situations before, the first impression is that since the search horizon is ply 14, search should not have knowledge about nodes beyond its horizon.

Transposition is the situation where two different nodes of the chess tree represent identical chess positions. What it means is that a position may be reached through different paths or sequences of moves. Say there is a node A at ply 3 which is found to have a +mate best-score of infi - 5 (mate-in 3) and which is hashed in the TT. If through a different path, the same position is reached at node B with ply 12, very near the horizon; there is no need to search this node B as a probe of the TT means we can return with an exact hit; the best score here retrieved from the TT would be: infi - 5 - 12 = infi - 17. And infi - 17 (17 plies from the root) refers to a mate node beyond the horizon of ply 14 - it seems a little illogical. It may be explained as a transplant of the sub-branch of the node A onto node B; and this sub-branch now will extend the chess tree beyond its original horizon of ply 14. So this is how transposition, together with TT hash tables, allows search to know of positions that seem to be beyond its tree horizon.

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

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.

Best Regards,
Rasjid.

[Patrice Duhamel]

I have wrong mate scores in some end game positions, I don't know if it's the same problem.

I know it's wrong, but I disabled mate score adjustment until I found the problem, because only when I'm using it I have this problem of wrong mate scores.

It's an old problem and I still not found a solution.

[xmas79]

Hi Chan,

Transposition is the
...
that seem to be beyond its tree horizon.

Yeah you got it!

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

[xmas79]

What kind of mate scores you get? Can you post some output and see what's happening?

[Patrice Duhamel]

With the position you give at the begining of your post :
FEN: 8/8/3K4/8/8/3N4/8/3B3k w - - 0 1

(I give only the first move in pv, for readability)

Note that it should play Ke5, I found the move in the previous version of my engine, I think it's another problem.

Without mate score adjustment :

Code: Select all

 27/39	00:05	  32 735 997	6 244 944	+8,37	Bd1-f3+ 
 28/39+	00:05	  33 157 343	6 232 583	+8,77	Bd1-f3+
 28/39	00:05	  35 461 483	6 296 428	+M10	Bd1-f3+
 29/39	00:06	  41 155 465	6 403 526	+M11	Bd1-f3+ 
 30/39	00:07	  52 058 735	6 568 925	+M11	Bd1-f3+ 
 31/39	00:08	  57 545 473	6 610 622	+M11	Bd1-f3+
 32/39	00:09	  64 383 855	6 667 756	+M11	Bd1-f3+
 33/39	00:10	  73 447 982	6 735 875	+M11	Bd1-f3+
 34/39	00:12	  83 693 327	6 791 084	+M11	Bd1-f3+
 35/39	00:14	  96 213 885	6 845 040	+M11	Bd1-f3+

With mate score adjustment :

Code: Select all

 27/39	00:05	  32 737 695	6 264 388	+8,37	Bd1-f3+
 28/39+	00:05	  33 159 223	6 269 469	+8,77	Bd1-f3+
 28/39	00:06	  41 257 146	6 325 842	+8,37	Bd1-f3+
 29/41	00:08	  55 063 603	6 324 787	+8,37	Bd1-f3+
 30/41+	00:08	  55 303 998	6 329 861	+8,77	Bd1-f3+
 30/41	00:11	  75 576 403	6 424 925	+M27	Bd1-f3+
 31/41	00:14	  94 578 941	6 483 782	+M23	Bd1-f3+
 32/43	00:18	 123 988 159	6 584 607	+M26	Bd1-f3+
 33/49	00:27	 181 059 292	6 677 704	+M30	Bd1-f3+
 34/49	00:36	 246 564 475	6 699 757	+M18	Bd1-f3+

[xmas79]

With the position you give at the begining of your post :
FEN: 8/8/3K4/8/8/3N4/8/3B3k w - - 0 1

(I give only the first move in pv, for readability)

Note that it should play Ke5, I found the move in the previous version of my engine, I think it's another problem.

Without mate score adjustment :

Code: Select all

 27/39	00:05	  32 735 997	6 244 944	+8,37	Bd1-f3+ 
 28/39+	00:05	  33 157 343	6 232 583	+8,77	Bd1-f3+
 28/39	00:05	  35 461 483	6 296 428	+M10	Bd1-f3+
 29/39	00:06	  41 155 465	6 403 526	+M11	Bd1-f3+ 
 30/39	00:07	  52 058 735	6 568 925	+M11	Bd1-f3+ 
 31/39	00:08	  57 545 473	6 610 622	+M11	Bd1-f3+
 32/39	00:09	  64 383 855	6 667 756	+M11	Bd1-f3+
 33/39	00:10	  73 447 982	6 735 875	+M11	Bd1-f3+
 34/39	00:12	  83 693 327	6 791 084	+M11	Bd1-f3+
 35/39	00:14	  96 213 885	6 845 040	+M11	Bd1-f3+

With mate score adjustment :

Code: Select all

 27/39	00:05	  32 737 695	6 264 388	+8,37	Bd1-f3+
 28/39+	00:05	  33 159 223	6 269 469	+8,77	Bd1-f3+
 28/39	00:06	  41 257 146	6 325 842	+8,37	Bd1-f3+
 29/41	00:08	  55 063 603	6 324 787	+8,37	Bd1-f3+
 30/41+	00:08	  55 303 998	6 329 861	+8,77	Bd1-f3+
 30/41	00:11	  75 576 403	6 424 925	+M27	Bd1-f3+
 31/41	00:14	  94 578 941	6 483 782	+M23	Bd1-f3+
 32/43	00:18	 123 988 159	6 584 607	+M26	Bd1-f3+
 33/49	00:27	 181 059 292	6 677 704	+M30	Bd1-f3+
 34/49	00:36	 246 564 475	6 699 757	+M18	Bd1-f3+

What's active in this search? Q-search? IID? LMR? Have you debugged your search ONLY? e.g. post output when not using advanced tricks and means. Only plain search (and no QS). The less things active, the lesser the headache...

EDIT: that line
28/39 00:05 35 461 483 6 296 428 +M10 Bd1-f3+
is very strange... your engine cannot see a mate in 10... you cannot propagate a mate in 10 moves to root, until you have a problem in the move generator/fetcher, (often you skip some move, and the search sees no moves were done and BAM! a mate score...)

[Patrice Duhamel]

What's active in this search? Q-search? IID? LMR? Have you debugged your search ONLY? e.g. post output when not using advanced tricks and means. Only plain search (and no QS). The less things active, the lesser the headache...

My search is a fail hard alpha beta with pvs, quiescence search without checks (and without hash), null moves pruning, IID, futility pruning,
lmr, mate distance pruning, extension for checks, pawn on 7th, and mate threat.
With Search + quiescence only, the problem is still here.

I didn't debugged for this recently, your post remembered me this problem.

is very strange... your engine cannot see a mate in 10... you cannot propagate a mate in 10 moves to root, until you have a problem in the move generator/fetcher, (often you skip some move, and the search sees no moves were done and BAM! a mate score...)

I add staged move generation few weeks ago, and made lots of tests on my move generation, I don't think the problem is here,
but I will check again.

[xmas79]

What's active in this search? Q-search? IID? LMR? Have you debugged your search ONLY? e.g. post output when not using advanced tricks and means. Only plain search (and no QS). The less things active, the lesser the headache...

My search is a fail hard alpha beta with pvs, quiescence search without checks (and without hash), null moves pruning, IID, futility pruning,
lmr, mate distance pruning, extension for checks, pawn on 7th, and mate threat.
With Search + quiescence only, the problem is still here.

I didn't debugged for this recently, your post remembered me this problem.

is very strange... your engine cannot see a mate in 10... you cannot propagate a mate in 10 moves to root, until you have a problem in the move generator/fetcher, (often you skip some move, and the search sees no moves were done and BAM! a mate score...)

I add staged move generation few weeks ago, and made lots of tests on my move generation, I don't think the problem is here,
but I will check again.

Do you mean without hash probing in QS? BTW, with all this stuff on debugging is a real pain.... You cannot change any single line of code because it will change completely the search... That's why is important to disable everything.

Be sure your movegen is OK, disable mating tables and advanced evaluation, keep only material scores and see how the search is (apart being slow...). And remove QS, just call evaluate instead of Qsearch. Localize your problem. With search only the problem can be:

- search(alpha, beta) function
- trasposition tables
- move gen

No other places. If you still get bad mate scores then I would zoom in the movegen firstly, second in TT.

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

Code: Select all

int perft(int depth)
{
int moves = 0;
genallmoves()
foreach move
   moves += perft(depth - 1);
end for
}

do this:

Code: Select all

int perft(int depth)
{
int moves = 0;

while (getnextmove())
   moves += perft(depth - 1);
end while
}

Good night,
Natale.

[Chan Rasjid]

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.

[Patrice Duhamel]

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.