Limiting Quiescent Search Depth

[JVMerlino]

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]

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]

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]

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.

[Zach Wegner]

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]

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

[Zach Wegner]

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]

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.

[Zach Wegner]

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]

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