Limiting Quiescent Search Depth

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Limiting Quiescent Search Depth

Post by JVMerlino » Wed May 20, 2009 6:53 pm

Here's your Newbie question of the week(tm):

The Chessprogramming Wiki site states that in a quiescent search you should "limit capture search to some depth". But doesn't doing so defeat the purpose of the q-search, which is to test all possible capture sequences out to their conclusion?

While it's true that choosing a depth limit of, for example, 10 plies probably only fails in a very small percentage of cases, it still seems like a potentially dangerous idea to me.

Thoughts?

Many thanks in advance,
jm

Ron Murawski
Posts: 397
Joined: Sun Oct 29, 2006 3:38 am
Location: Schenectady, NY
Contact:

Re: Limiting Quiescent Search Depth

Post by Ron Murawski » Wed May 20, 2009 8:08 pm

JVMerlino wrote:Here's your Newbie question of the week(tm):

The Chessprogramming Wiki site states that in a quiescent search you should "limit capture search to some depth". But doesn't doing so defeat the purpose of the q-search, which is to test all possible capture sequences out to their conclusion?

While it's true that choosing a depth limit of, for example, 10 plies probably only fails in a very small percentage of cases, it still seems like a potentially dangerous idea to me.

Thoughts?

Many thanks in advance,
jm
Hi John,

If a qsearch allows checks, you must set some limit (ie: perpetual check). Bob Hyatt says to just allow checks in the first ply of qsearch. Some engines don't allow checks at all and others allow checks to an arbitrary depth limit. Try all of these approaches and see what works best for you.

Ron

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Limiting Quiescent Search Depth

Post by Edmund » Wed May 20, 2009 8:15 pm

Ron Murawski wrote:
JVMerlino wrote:Here's your Newbie question of the week(tm):

The Chessprogramming Wiki site states that in a quiescent search you should "limit capture search to some depth". But doesn't doing so defeat the purpose of the q-search, which is to test all possible capture sequences out to their conclusion?

While it's true that choosing a depth limit of, for example, 10 plies probably only fails in a very small percentage of cases, it still seems like a potentially dangerous idea to me.

Thoughts?

Many thanks in advance,
jm
Hi John,

If a qsearch allows checks, you must set some limit (ie: perpetual check). Bob Hyatt says to just allow checks in the first ply of qsearch. Some engines don't allow checks at all and others allow checks to an arbitrary depth limit. Try all of these approaches and see what works best for you.

Ron
One of my tests was to only extend checks where the move after the check-evasion was a tactical move (capture or promotion). This restriction is another way to keep the search depth low.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Limiting Quiescent Search Depth

Post by bob » Wed May 20, 2009 8:26 pm

JVMerlino wrote:Here's your Newbie question of the week(tm):

The Chessprogramming Wiki site states that in a quiescent search you should "limit capture search to some depth". But doesn't doing so defeat the purpose of the q-search, which is to test all possible capture sequences out to their conclusion?

While it's true that choosing a depth limit of, for example, 10 plies probably only fails in a very small percentage of cases, it still seems like a potentially dangerous idea to me.

Thoughts?

Many thanks in advance,
jm
Never heard of that one. By definition, searching captures limits the depth because you eventually run out of captures.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Limiting Quiescent Search Depth

Post by Zach Wegner » Wed May 20, 2009 8:36 pm

JVMerlino wrote:Here's your Newbie question of the week(tm):

The Chessprogramming Wiki site states that in a quiescent search you should "limit capture search to some depth". But doesn't doing so defeat the purpose of the q-search, which is to test all possible capture sequences out to their conclusion?

While it's true that choosing a depth limit of, for example, 10 plies probably only fails in a very small percentage of cases, it still seems like a potentially dangerous idea to me.

Thoughts?

Many thanks in advance,
jm
Yes, it's dangerous. I'd recommend other ways of limiting the qsearch. Of course, there's going to be some hard limit to searching based on the search stack size.

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Limiting Quiescent Search Depth

Post by Edmund » Wed May 20, 2009 9:01 pm

Zach Wegner wrote:
JVMerlino wrote:Here's your Newbie question of the week(tm):

The Chessprogramming Wiki site states that in a quiescent search you should "limit capture search to some depth". But doesn't doing so defeat the purpose of the q-search, which is to test all possible capture sequences out to their conclusion?

While it's true that choosing a depth limit of, for example, 10 plies probably only fails in a very small percentage of cases, it still seems like a potentially dangerous idea to me.

Thoughts?

Many thanks in advance,
jm
Yes, it's dangerous. I'd recommend other ways of limiting the qsearch. Of course, there's going to be some hard limit to searching based on the search stack size.
Dear Zach,
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.
Futility pruning. If the static exchange evaluation of a move plus the evaluation is not able to get within a certain margin of alpha, it can be pruned.
I think this is already mentioned on the same page under the name Delta-Pruning. Maybe we should stick to one name to avoid confusion.

regards,
Edmund

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Limiting Quiescent Search Depth

Post by Zach Wegner » Wed May 20, 2009 9:12 pm

Codeman wrote:Dear Zach,
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.
Futility pruning. If the static exchange evaluation of a move plus the evaluation is not able to get within a certain margin of alpha, it can be pruned.
I think this is already mentioned on the same page under the name Delta-Pruning. Maybe we should stick to one name to avoid confusion.

regards,
Edmund
That sounds fine. Probably we should scrap that whole section ("Other Conditions") because pruning losing captures is already mentioned too. The stand pat verify could be transformed into a section about checks in qsearch. I don't know of any program that verifies any moves other than checks.

Generally, if you see something like that, feel free to change it, it's a wiki after all. I used futility pruning because I didn't notice that "delta" was already there. :)

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Limiting Quiescent Search Depth

Post by Edmund » Wed May 20, 2009 9:47 pm

Zach Wegner wrote:
Codeman wrote:Dear Zach,
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.
Futility pruning. If the static exchange evaluation of a move plus the evaluation is not able to get within a certain margin of alpha, it can be pruned.
I think this is already mentioned on the same page under the name Delta-Pruning. Maybe we should stick to one name to avoid confusion.

regards,
Edmund
That sounds fine. Probably we should scrap that whole section ("Other Conditions") because pruning losing captures is already mentioned too. The stand pat verify could be transformed into a section about checks in qsearch. I don't know of any program that verifies any moves other than checks.

Generally, if you see something like that, feel free to change it, it's a wiki after all. I used futility pruning because I didn't notice that "delta" was already there. :)
I think Diep also refuses to standpat if > 1 pieces are hanging. But definitely it would be better discussing this topic separately.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Limiting Quiescent Search Depth

Post by Zach Wegner » Wed May 20, 2009 10:07 pm

Codeman wrote:I think Diep also refuses to standpat if > 1 pieces are hanging. But definitely it would be better discussing this topic separately.
You might be right. Anyways, I just did a major overhaul of that page. If you can find a reference to that, it might be good in the "stand pat" section. :)

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Limiting Quiescent Search Depth

Post by bob » Wed May 20, 2009 11:58 pm

Codeman wrote:
Zach Wegner wrote:
JVMerlino wrote:Here's your Newbie question of the week(tm):

The Chessprogramming Wiki site states that in a quiescent search you should "limit capture search to some depth". But doesn't doing so defeat the purpose of the q-search, which is to test all possible capture sequences out to their conclusion?

While it's true that choosing a depth limit of, for example, 10 plies probably only fails in a very small percentage of cases, it still seems like a potentially dangerous idea to me.

Thoughts?

Many thanks in advance,
jm
Yes, it's dangerous. I'd recommend other ways of limiting the qsearch. Of course, there's going to be some hard limit to searching based on the search stack size.
Dear Zach,
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.
Futility pruning. If the static exchange evaluation of a move plus the evaluation is not able to get within a certain margin of alpha, it can be pruned.
I think this is already mentioned on the same page under the name Delta-Pruning. Maybe we should stick to one name to avoid confusion.

regards,
Edmund
These are two different ideas. The term "delta pruning" is not a very good term, and comes directly from Crafty's q-search where I compute how high the score has to be raised in order to get it above alpha (if a capture can not get the score above alpha it is not worth searching). I use that to exclude captures even though they appear to win material. If I am a queen down, for example, trying a capture that wins only a knight is not going to help me.

futility pruning is a different animal and it is not really a "pruning" algorithm so much as it is a "reduction" algorithm. The two things are completely unrelated...

Post Reply