Quiescence - Check Evaluation and Depth Control

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 5048
Joined: Tue Feb 28, 2012 10:56 pm

Re: Quiescence - Check Evaluation and Depth Control

Post by syzygy » Thu Nov 15, 2012 5:20 pm

lucasart wrote: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.
Unless QS_LIMIT is set to -2, this won't be entirely accurate. Suppose you set QS_LIMIT to -7, then your hashtable won't distinguish between positions qsearched with depth -6 and positions qsearched with depth -1, but these qsearches clearly have different accuracies.

So to be accurate I think you would have to enter "depth". Since you have just limited depth to >= QS_LIMIT, there is no danger of underflowing.

Of course you could also choose not to hash the qsearch at all, or only hash positions with "high" depth. (I have not found hashing the qsearch to be worth it in my current engine, but I'm sure this is engine-dependent.)

Jan Brouwer
Posts: 201
Joined: Thu Mar 22, 2007 6:12 pm
Location: Netherlands

Re: Quiescence - Check Evaluation and Depth Control

Post by Jan Brouwer » Thu Nov 15, 2012 9:57 pm

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.
Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes :( (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...

syzygy
Posts: 5048
Joined: Tue Feb 28, 2012 10:56 pm

Re: Quiescence - Check Evaluation and Depth Control

Post by syzygy » Fri Nov 16, 2012 12:38 am

Jan Brouwer wrote:Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes :( (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...
Do you do underpromotions in the qsearch?

Jan Brouwer
Posts: 201
Joined: Thu Mar 22, 2007 6:12 pm
Location: Netherlands

Re: Quiescence - Check Evaluation and Depth Control

Post by Jan Brouwer » Fri Nov 16, 2012 11:02 pm

syzygy wrote:
Jan Brouwer wrote:Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes :( (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...
Do you do underpromotions in the qsearch?
No, just queen promotions.

Edsel Apostol
Posts: 801
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by Edsel Apostol » Sat Nov 17, 2012 12:58 am

Jan Brouwer wrote:
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.
Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes :( (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...
Do you check for repetition when moving out of check in qsearch?

User avatar
lucasart
Posts: 3224
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart » Sat Nov 17, 2012 10:10 am

Edsel Apostol wrote: Do you check for repetition when moving out of check in qsearch?
That's a bizarre idea. Do you really get some significant node reduction from that ?
In general, I mean, not this position in particular. My intuition tells me that the cases where it will be used are so rare, that it doesn't make sense to slow down all the check escapes QS nodes for it.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Edsel Apostol
Posts: 801
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by Edsel Apostol » Sat Nov 17, 2012 11:18 am

lucasart wrote:
Edsel Apostol wrote: Do you check for repetition when moving out of check in qsearch?
That's a bizarre idea. Do you really get some significant node reduction from that ?
In general, I mean, not this position in particular. My intuition tells me that the cases where it will be used are so rare, that it doesn't make sense to slow down all the check escapes QS nodes for it.
I'm just thinking of the reasons why it causes search explosion in that particular position. One thing I could think of is that when in giving check it was extended in qsearch and when moving out of check the depth is also extended, so it is possible that there is a check repetition that repeats for the nth time that will bloat the nodecount.

Another thing might be ordering the queen promotion over the queen capture, so all the pawns will be promoted first. Imagine the branching factor with 12 queens on the board.

As for your question if it saves a lot of nodes, I don't think so. I think though that it is important to make the search more accurate than faster in this case. It might be that the check repetition is the only move that saves the game and all the other moves are losing and the engine did not choose this correct move because it didn't score it correctly.

syzygy
Posts: 5048
Joined: Tue Feb 28, 2012 10:56 pm

Re: Quiescence - Check Evaluation and Depth Control

Post by syzygy » Sat Nov 17, 2012 11:33 am

lucasart wrote:
Edsel Apostol wrote:Do you check for repetition when moving out of check in qsearch?
That's a bizarre idea. Do you really get some significant node reduction from that ?
In general, I mean, not this position in particular. My intuition tells me that the cases where it will be used are so rare, that it doesn't make sense to slow down all the check escapes QS nodes for it.
As long as your first test is checking the number of ply since the last capture, this won't slow down the qsearch noticeably. I would certainly want to check for repetition in the first ply of qsearch, unless you do that in the main search right before calling the qsearch. If you give checks in qsearch, I would want to check for repetition as well. Otherwise you're going to miss some draws.

I don't think repetition check wil help in this position though. Captures and promotions are irreversible, so I don't see how a repetition could occur when qsearching this positions (unless one gives unlimited amounts of checks, but I don't think this is the problem here).
Edsel Apostol wrote:Another thing might be ordering the queen promotion over the queen capture, so all the pawns will be promoted first. Imagine the branching factor with 12 queens on the board.
I was thinking of that too. I do captures before non-capturing promotions, and my first ply "only" needs about 640k nodes. (I just recently got rid of underpromotions in the qsearch. The old version needs 48M nodes for the first ply.)

User avatar
lucasart
Posts: 3224
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Quiescence - Check Evaluation and Depth Control

Post by lucasart » Sat Nov 17, 2012 12:36 pm

diep wrote:Yo i'm just a FM but i'd do Qg7+ Kg7 h8Q+ Kg6 Qh6+ mate.
Many paths lead to Rome!
But the shortest mate is simply: Bxf7, followed by Qg8# (regardless of whichever pawn black decides to promote after Bxf7). The point is that your Qh6# cannot be found by a qsearch that doesn't consider quiet checks below depth 0, which is why I posted the mating line: Qg7+ Kxg7 h8=Q+ Kg6 Bxf7+ Kxf7 e8=Q#.
If Diep indeed plays quiet checks until depth = -32 as you mentionned, then it should find the mating line that you gave at depth == 0 (qsearch).
[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Jan Brouwer
Posts: 201
Joined: Thu Mar 22, 2007 6:12 pm
Location: Netherlands

Re: Quiescence - Check Evaluation and Depth Control

Post by Jan Brouwer » Sat Nov 17, 2012 2:33 pm

Edsel Apostol wrote:
Jan Brouwer wrote:
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.
Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes :( (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...
Do you check for repetition when moving out of check in qsearch?
Yes, I check for repetitions everywhere.

Post Reply