Quiescence - Check Evaluation and Depth Control

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart »

Michel wrote:Just for curiosity what is your quiescence score on this position?

GNU Chess's score is too high I think since the quiescence search does not see
the concealed threat against Ne5 (it might be a bug).
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
My qsearch returns +51
depth=0 score=51 nodes=126

And now the search
depth=1 score=34 nodes=863
depth=2 score=34 nodes=5056
depth=3 score=14 nodes=6577
depth=4 score=13 nodes=44541
depth=5 score=-2 nodes=144937
depth=6 score=-2 nodes=1111852
depth=7 score=-41 nodes=4652132
depth=8 score=-46 nodes=42208215
depth=9 score=-63 nodes=184392047

Don't take this for gospel truth though. As you can see my search and eval are very very basic
https://github.com/lucasart/chess/
(search.cc and eval.cc)
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart »

Jan Brouwer wrote: It takes my program 24M nodes to finish a one ply search.
Well your qsearch has some serious issues then. In the qasearch, you should only consider queen promotions, never under promotions:
[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1

Code: Select all

depth=0	score=2126	nodes=7
depth=1	score=2955	nodes=55
depth=2	score=31995	nodes=1295
depth=3	score=31997	nodes=4875
depth=4	score=31997	nodes=59827
depth=5	score=31997	nodes=236821
depth=6	score=31997	nodes=4816131
depth=7	score=31997	nodes=20792248
Yes, that ONLY 7 nodes of qsearch, including the root node. And the reason is simply:
* 5 promotions (to queen only), then black stands pat
* Bxf7 and blacks stands pat.

My mate score is 32000, so 31997 is mate in 3 plies. There are of course many ways to reach the mate in 3 plies in this position.

In this position, mate distance pruning in the search is important. Here are my results WITHOUT mate distance pruning:

Code: Select all

depth=0	score=2126	nodes=7
depth=1	score=2955	nodes=55
depth=2	score=31995	nodes=1295
depth=3	score=31997	nodes=6817
depth=4	score=31997	nodes=83122
depth=5	score=31997	nodes=461003
depth=6	score=31997	nodes=7267964
depth=7	score=31997	nodes=31952786
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart »

lucasart wrote:
Jan Brouwer wrote: It takes my program 24M nodes to finish a one ply search.
[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
Without alpha/beta pruning

Code: Select all

depth=0	score=2126	nodes=25
Without alpha/beta pruning, and without SEE pruning (note that I even consider quiet checks at depth 0, which triggers deep lines like Qg7+ Kxg7 h7=Q+ Kg6 e8=Q+ and so on)

Code: Select all

depth=0	score=2126	nodes=948
So there's no way the full tree even has 24 M nodes. I don't know what moves you are searching in the qsearch, but I think the problem lies there, even before looking at search techniques (like alpha/beta and SEE pruning).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
Michel
Posts: 2278
Joined: Mon Sep 29, 2008 1:50 am

Re: Quiescence - Check Evaluation and Depth Control

Post by Michel »

My qsearch returns +51
depth=0 score=51 nodes=126

And now the search
depth=1 score=34 nodes=863
depth=2 score=34 nodes=5056
depth=3 score=14 nodes=6577
depth=4 score=13 nodes=44541
depth=5 score=-2 nodes=144937
depth=6 score=-2 nodes=1111852
depth=7 score=-41 nodes=4652132
depth=8 score=-46 nodes=42208215
depth=9 score=-63 nodes=184392047
Ok thanks. GNU Chess returns a way more optimistic
quiescence score
show quiesce
score=125 nodes=63 best_move=e2a6
The score becomes -103 after a 9 ply search. I have to understand this.
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart »

[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
Actually, if you allow quiet checks at depth 0, and remove SEE pruning, the QS will consider Qg7 and find this mate:
Qg7+ Kxg7 h8=Q+ Kg6 Bxf7+ Kxf7 e8=Q#
[d]4Q2Q/PPPP1k2/8/7R/7K/8/pppppp2/6B1 b - -
The point is that:
1/ Qg7+ is a quiet check, and even though it has a SEE < 0 it will be considered
2/ all the following moves are captures and promotions, and the black king can never stand pat, because he's always in check

This is not the shortest mate, and only a search could sanely find the shortest mate, but it's a nice and forceful one!

That being said, I would not advise removing SEE pruning. But I need to test it and find out why my program didn't find this mate with SEE pruning removed.

This is a very particular examle, and in general you shouldn't trust the qsearch to find non trivial mates, because of the stand pat option. In this case however, the stand pat option is removed every step of the way. This forcefulness is what makes the mate pretty IMO.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Quiescence - Check Evaluation and Depth Control

Post by diep »

Yo i'm just a FM but i'd do Qg7+ Kg7 h8Q+ Kg6 Qh6+ mate.

This is a 1 ply problem isn't it?

p.s. i checked at Diep - yeah it finds it at plydepth=1, though with Rg5+ mate rather than Qh6 as the last move in the above line. At 2 ply it finds a mate in 2.
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Quiescence - Check Evaluation and Depth Control

Post by Sven »

diep wrote:Yo i'm just a FM but i'd do Qg7+ Kg7 h8Q+ Kg6 Qh6+ mate.

This is a 1 ply problem isn't it?

p.s. i checked at Diep - yeah it finds it at plydepth=1, though with Rg5+ mate rather than Qh6 as the last move in the above line. At 2 ply it finds a mate in 2.
Both 1.Qg7+ and 3.Qh6+ (resp. 3.Rg5+) are quiet checks which will not always be considered during QS (perhaps except 1.Qg7+ if you include checks at the first QS ply, or if we talk about 1 ply full-width followed by QS), while 3.Bxf7+ Kxf7 4.e8Q+ has no quiet checks. I think that was the point here.

Sven
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart »

lucasart wrote:[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
(...) I need to test it and find out why my program didn't find this mate with SEE pruning removed.
with or without SEE pruning it should find it, so long as checking moves are not subject to SEE pruning (like Qg7+ and later Bxf7+).

I found the bug in my program. I was not generating promotions!

So Jan Brouwer was right. This position really *is* a qsearch explosion.

I'll experiment with forcefully limiting the depth of the qsearch.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
lucasart
Posts: 3238
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart »

lucasart wrote:
lucasart wrote:[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
(...) I need to test it and find out why my program didn't find this mate with SEE pruning removed.
with or without SEE pruning it should find it, so long as checking moves are not subject to SEE pruning (like Qg7+ and later Bxf7+).

I found the bug in my program. I was not generating promotions!

So Jan Brouwer was right. This position really *is* a qsearch explosion.

I'll experiment with forcefully limiting the depth of the qsearch.
I decided to fix this qsearch explosion problem by introducing a depth limit. Basically when the depth is QS_LIMIT, we don't call qsearch() recursively, and return eval + SEE instead.

This will make the implementation of the hash table a bit trickier. The depth that I'll have to enter in the hash entries will have to be

Code: Select all

depth == 0 ? 0 &#58; &#40;depth <= QS_LIMIT &#58; -2 &#58; -1&#41;
Something to remember for when I implement a hash table.

Here's my qsearch() so far:

Code: Select all

#define QS_LIMIT	-6

int qsearch&#40;Board& B, int alpha, int beta, int depth, int ply&#41;
&#123;
	assert&#40;depth <= 0&#41;;
	assert&#40;alpha < beta&#41;;
	
	node_count++;
	bool in_check = B.is_check&#40;);
	int best_score = -INF, static_eval = -INF;

	// stand pat
	if (!in_check&#41; &#123;
		best_score = static_eval = eval&#40;B&#41;;
		alpha = std&#58;&#58;max&#40;alpha, best_score&#41;;
		if &#40;alpha >= beta&#41;
			return alpha;
	&#125;
	
	MoveSort MS&#40;&B, depth < 0 ? MoveSort&#58;&#58;CAPTURES &#58; MoveSort&#58;&#58;CAPTURES_CHECKS&#41;;
	move_t *m;
	int cnt = 0;
	
	while ( alpha < beta && &#40;m = MS.next&#40;)) ) &#123;
		cnt++;
		int check = move_is_check&#40;B, *m&#41;;
		
		if (!in_check && check != DISCO_CHECK && see&#40;B, *m&#41; < 0&#41;
			continue;
		
		int score;
		
		if &#40;depth <= QS_LIMIT && !in_check&#41;
			score = static_eval + see&#40;B,*m&#41;;	// prevent qsearch explosion
		else &#123;
			B.play&#40;*m&#41;;
			score = -qsearch&#40;B, -beta, -alpha, depth-1, ply+1&#41;;
			B.undo&#40;);
		&#125;
		
		best_score = std&#58;&#58;max&#40;best_score, score&#41;;
		alpha = std&#58;&#58;max&#40;alpha, score&#41;;
	&#125;
	
	if &#40;B.is_check&#40;) && !cnt&#41;
		return ply-MATE;
	
	return best_score;
&#125;
This means that the qsearch() cannot find the mate anymore, as black will always manage to get the qsearch() deeper than QS_LIMIT and get a pseudo-standpat on -[eval(White)+see(white move)].

Overall the gain should easily compensate the pain. A single position like that in the game and the consequences can be disastrous, if the engine doesn't even finish a depth 1...

Sample run (I don't have hash tables yet)

Code: Select all

depth=0	score=2955	nodes=2996
depth=1	score=2955	nodes=8099
depth=2	score=31997	nodes=101867
depth=3	score=31997	nodes=418299
depth=4	score=31997	nodes=2040988
depth=5	score=31997	nodes=6859752
The mate is found at depth 2, not 1, because I don't extend checks in the search. And even when I implement that, I will not extend checks with a SEE < 0 (unless discovered checks where the SEE is irrelevant in most cases).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
diep
Posts: 1822
Joined: Thu Mar 09, 2006 11:54 pm
Location: The Netherlands

Re: Quiescence - Check Evaluation and Depth Control

Post by diep »

Sven Schüle wrote:
diep wrote:Yo i'm just a FM but i'd do Qg7+ Kg7 h8Q+ Kg6 Qh6+ mate.

This is a 1 ply problem isn't it?

p.s. i checked at Diep - yeah it finds it at plydepth=1, though with Rg5+ mate rather than Qh6 as the last move in the above line. At 2 ply it finds a mate in 2.
Both 1.Qg7+ and 3.Qh6+ (resp. 3.Rg5+) are quiet checks which will not always be considered during QS (perhaps except 1.Qg7+ if you include checks at the first QS ply, or if we talk about 1 ply full-width followed by QS), while 3.Bxf7+ Kxf7 4.e8Q+ has no quiet checks. I think that was the point here.

Sven
Didn't try 0 ply search with Diep.
Diep finds the mate at plydepth=1 with its qsearch.

I limit for a few years the number of selective plies tried in mainsearch dramatically. In 90s that was all different....