Shame

[hgm]

This is indeed what causes the mate to be found so quickly. If I remove the single-reply out of check extension the mate isn't found until a nominal depth of 6.

This, on the other hand, is a bit late. Joker finds it in 4 ply, and this is what I would expect for a search with check extension. All moves leading to the mate are checks. So if the evasions are free, 4 ply should be enough to search the 4 checks, and end at d=0 in a leaf where there is check and no evasions. Is it that Sjaak and Jazz do not extend negative-SEE checks?

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
  7	+100.04 	26342  	0:00.03	e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  7	+100.04 	18640  	0:00.03	* e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  6	+100.04 	17044  	0:00.01	e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  6	+100.04 	10133  	0:00.01	* e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  5	+100.04 	8445    	0:00.01	e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  5	+100.04 	6689    	0:00.00	* e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  4	+100.04 	4831    	0:00.00	e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  4	+100.04 	4689    	0:00.00	* e4f6 g7f6 a3f8 g8f8 c1h6 f8g8 e1e8
  4	 -2.46 	3184    	0:00.00	* f2f1 c8f5 f3g5 b8c6
  3	 -2.35 	1690    	0:00.00	f2f1 c8f5 f3g5
  3	 -2.35 	1112    	0:00.00	* f2f1 c8f5 f3g5
  2	 -2.35 	548      	0:00.00	f2f1 b8c6
  2	 -2.35 	351      	0:00.00	* f2f1 b8c6
  2	 -3.26 	237      	0:00.00	* f2g1 d4d3 c1e3 b6e3 e1e3 d3c2
  1	 -1.46 	131      	0:00.00	f2g1

[Henk]

If I use alpha beta with nothing else but only quiescence search I only reach depths 4, 5, 6 within five seconds. But it doesn't use iterative deepening then for it uses no hash table.

[Sven]

If I use alpha beta with nothing else but only quiescence search I only reach depths 4, 5, 6 within five seconds. But it doesn't use iterative deepening then for it uses no hash table.

Can you give an example with PV + time + node count? E.g. the mate-in-4 puzzle above for depth=4, 5 and 6?

[Henk]

If I use alpha beta with nothing else but only quiescence search I only reach depths 4, 5, 6 within five seconds. But it doesn't use iterative deepening then for it uses no hash table.

Can you give an example with PV + time + node count? E.g. the mate-in-4 puzzle above for depth=4, 5 and 6?

I just removed mate detection from level 0 for I thought it wasn't really necessary. Now solving a mate in 3 already needs depth = 7 and costs a minute search time. So a mate in 4 would probably need level 9 and perhaps a few hours search time.

I also don't generate legal moves anymore but pseudo legal moves. So only king captures detects a mate. But one ply too late.

That explains the extra two ply needed to find a mate. (no mate detection at level 0 + king capture)

[hgm]

My engines don't do legal-move-only generation, but usually they do detect in-check, and extend for the evasion if they are. That is enough to detect mate at d=0, as the the QS following the pseudo-legal evasions will always detect the King capture.

In Joker I speeded up the move generator by not generating moves with pinned pieces (other than those along the pin line). So there the only non-legal moves that are generated are King moves, and possibly e.p. captures where it was not obvious the Pawn was pinned (along a rank).

[Henk]

If I use alpha beta with nothing else but only quiescence search I only reach depths 4, 5, 6 within five seconds. But it doesn't use iterative deepening then for it uses no hash table.

Can you give an example with PV + time + node count? E.g. the mate-in-4 puzzle above for depth=4, 5 and 6?

I just removed mate detection from level 0 for I thought it wasn't really necessary. Now solving a mate in 3 already needs depth = 7 and costs a minute search time. So a mate in 4 would probably need level 9 and perhaps a few hours search time.

I also don't generate legal moves anymore but pseudo legal moves. So only king captures detects a mate. But one ply too late.

That explains the extra two ply needed to find a mate. (no mate detection at level 0 + king capture)

See it cannot solve the mate in 4 puzzle at these lower depths. Time in seconds of course. A pawn is about 10000 points.

Code: Select all

Depth  Value   Time
  1  -12187.00   0.015        62          h2h4 
  2  -18631.00   0.026        731         a3d3 
  3  -12503.00   0.081        7091        a3b3 
  4  -20991.00   0.548        52393       a3d3 
  5  -14610.00   6.438        702612      e4c5 
  6  -22067.00   62.641       5444069     a3d3 

[Robert Pope]

I just tried the mate in 4 and Abbess solved it in well under a second.

Code: Select all

 1   -172       1        132 f2g1
 2   -252       2       3022 f2f1
 3   -231       8      51021 f2f1
 4  32760      28     367038 e4f6
 5  32760      63    1028552 e4f6

I've intentionally not added nullmove, hashtables or anything fancy yet, as I want to make sure the things I do are solid this time around. I do recaptures, check extensions, IID sorting, and that's about it. Pseudolegal move generation, with a not-in-check validation after the move.

I think one thing I realized from working on Beaches is that it is easy to hammer new features on early in the process, and they may improve the engine, even when they are broken.

But then it tends to be harder to go back and look at basic things later on, like move ordering. And after a few layers of these not-quite-right enhancements, your engine starts doing bad things at odd times, which is an even bigger nightmare to track down.

[Sven]

If I use alpha beta with nothing else but only quiescence search I only reach depths 4, 5, 6 within five seconds. But it doesn't use iterative deepening then for it uses no hash table.

Can you give an example with PV + time + node count? E.g. the mate-in-4 puzzle above for depth=4, 5 and 6?

I just removed mate detection from level 0 for I thought it wasn't really necessary. Now solving a mate in 3 already needs depth = 7 and costs a minute search time. So a mate in 4 would probably need level 9 and perhaps a few hours search time.

I also don't generate legal moves anymore but pseudo legal moves. So only king captures detects a mate. But one ply too late.

That explains the extra two ply needed to find a mate. (no mate detection at level 0 + king capture)

That is not correct, you don't need "king captures" to detect a mate in N moves within 2*N-1 iterations. All you need is check extension (if (inCheck) ++depth), and of course counting all legal moves (the ones that you don't find to be illegal after making them) within the move loop. Then add this below the move loop:

Code: Select all

if (numberOfLegalMoves == 0) return (isInCheck ? -(MATE_VALUE - ply) : 0);

By adding check extension you ensure that you never start a quiescence search when being in check (but also checks at internal nodes are extended). Counting legal moves is simple enough to avoid more explanations.

It is quite likely that some of the basic problems of your engine are related to an unfavorable handling of in-check detection, legality, and similar stuff, according to what you are writing here. But I also suspect that your move ordering is wrong, otherwise you would not report these enormous search times for the very first few iterations.

I think you should fix these issues in a version where TT, null move, and other advanced stuff is disabled, but with iterative deepening enabled (otherwise it is hard to measure progress). Also the best move of the previous iteration should always be tried first.

How can we help you?

[hgm]

..., and of course counting all legal moves (the ones that you don't find to be illegal after making them) within the move loop.

Actually in a fail-soft setting you don't even have to do that. You initialize bestScore to -INFINITE, and if there were no legal moves it stays there. And as this happens to be exactly the score you need when you are checkmated, you don't need to do anything. Only stalemate would require a correction of the score to 0, in case it got stuck at -INFINITE.

[Henk]

If I use alpha beta with nothing else but only quiescence search I only reach depths 4, 5, 6 within five seconds. But it doesn't use iterative deepening then for it uses no hash table.

Can you give an example with PV + time + node count? E.g. the mate-in-4 puzzle above for depth=4, 5 and 6?

I just removed mate detection from level 0 for I thought it wasn't really necessary. Now solving a mate in 3 already needs depth = 7 and costs a minute search time. So a mate in 4 would probably need level 9 and perhaps a few hours search time.

I also don't generate legal moves anymore but pseudo legal moves. So only king captures detects a mate. But one ply too late.

That explains the extra two ply needed to find a mate. (no mate detection at level 0 + king capture)

That is not correct, you don't need "king captures" to detect a mate in N moves within 2*N-1 iterations. All you need is check extension (if (inCheck) ++depth), and of course counting all legal moves (the ones that you don't find to be illegal after making them) within the move loop. Then add this below the move loop:

Code: Select all

if (numberOfLegalMoves == 0) return (isInCheck ? -(MATE_VALUE - ply) : 0);

By adding check extension you ensure that you never start a quiescence search when being in check (but also checks at internal nodes are extended). Counting legal moves is simple enough to avoid more explanations.

It is quite likely that some of the basic problems of your engine are related to an unfavorable handling of in-check detection, legality, and similar stuff, according to what you are writing here. But I also suspect that your move ordering is wrong, otherwise you would not report these enormous search times for the very first few iterations.

I think you should fix these issues in a version where TT, null move, and other advanced stuff is disabled, but with iterative deepening enabled (otherwise it is hard to measure progress). Also the best move of the previous iteration should always be tried first.

How can we help you?

Check extensions only works if you only allow legal moves otherwise you get an infinite loop. (It took me two hours to understand what was going on. So I have had enough misery for today).

Checking if a move is legal is costly for you have to iterate over all moves to check if there is a king capture. So I don't like to add that to the search.

Solving mate in n puzzles quickly is not that important. I use it to check if alpha beta works correctly.