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
Limiting Quiescent Search Depth
Moderators: hgm, Rebel, chrisw
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
-
- Posts: 397
- Joined: Sun Oct 29, 2006 4:38 am
- Location: Schenectady, NY
Re: Limiting Quiescent Search Depth
Hi John,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
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
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Limiting Quiescent Search Depth
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.Ron Murawski wrote:Hi John,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
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
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Limiting Quiescent Search Depth
Never heard of that one. By definition, searching captures limits the depth because you eventually run out of captures.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
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Limiting Quiescent Search Depth
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.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
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Limiting Quiescent Search Depth
Dear Zach,Zach Wegner wrote: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.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
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.
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.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.
regards,
Edmund
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Limiting Quiescent Search Depth
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.Codeman wrote:Dear Zach,
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.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.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.
regards,
Edmund
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.
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Limiting Quiescent Search Depth
I think Diep also refuses to standpat if > 1 pieces are hanging. But definitely it would be better discussing this topic separately.Zach Wegner wrote: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.Codeman wrote:Dear Zach,
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.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.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.
regards,
Edmund
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.
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Limiting Quiescent Search Depth
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.Codeman wrote:I think Diep also refuses to standpat if > 1 pieces are hanging. But definitely it would be better discussing this topic separately.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Limiting Quiescent Search Depth
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.Codeman wrote:Dear Zach,Zach Wegner wrote: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.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
I saw your recent edit on the Chess Programming Wiki concerning the Futility Pruning.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.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.
regards,
Edmund
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...