To those with knowledge of chess programming - how many plies of capture
(quiescence?) search are included beyond the stated ply? I assume it varies
greatly between typical middle game positions and simple endgame positions.

"Buller" wrote in message
news:G4aDf.53282$8r1.17574@trnddc05...
To those with knowledge of chess programming - how many plies of capture
(quiescence?) search are included beyond the stated ply? I assume it
varies greatly between typical middle game positions and simple endgame
positions.

There is no specific amount.

Some programs do it until captures are exhausted.

Some will do just a few plies and then use a static exchange evaluator.

Some will do a few plies of captures and other interesting moves (checking,
etc.) and then switch to something more restrictive as it gets deeper. And
possibly doing a SEE when it cuts off.

Some will limit the total depth. Some will limit the total quiescience
plies. Some will vary depending on the situation.

There's a whole lot of variation in how people do it.

About the only thing you can say for sure is that an unbounded capture
search is a bad thing. Too great a chance of a capture search explosion.
Too much time spent doing stupid captures & checking moves. Too great an
impact on time consumption, which can cause time difficulties during the
game.


Most programs these days search pretty deep considering the hardware they
are running on. So a q-search is really more about insurance against making
a stupid move, rather than a critical part of the search that will help find
a good move, like it was back in the days of the 8-bit micros.



----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Buller wrote:
To those with knowledge of chess programming - how many plies of capture
(quiescence?) search are included beyond the stated ply? I assume it varies
greatly between typical middle game positions and simple endgame positions.

The definition of a "quiet" position is one where the side to move
cannot make a threat, nor can there be one existing. The defintion of
"threat" may vary slightly. Most programs agree a threat is a position
where if you "do nothing" your opponent would definitely take material
off of the board next, or maybe even inflict mate. This is often
referred to as a "Null Move" threat. A threat may also be any move that
delivers check.

There are four meaningful "depth numbers" that are needed to accurately
describe what is going on in a position being searched.

Nominal Depth - This is what everyone thinks about as being the "ply"
when they see a program searching.

Extended Depth - The deepest line from the root of the tree that has
been explored, mostly due to search extensions, null move, etc. I have
seen depths here that are 3 or 4 times the Nominal Depth. While 8-ply
nominal depths typically can hit 16-18 ply of Extended Depth, 30 or
more ply can occur in turbulent positions.

P.V. Extended Depth - Usually shallower than the Extended Depth is the
deepest line explored in the Principal Variation. This will not feature
the "ridiculously long" depths seen in the Extended Depth category, but
usually this number can be 2 to 2.5 times the nominal Depth.

Average Depth - Another interesting number is the average depth of all
nodes searched. This is computed by accumulating the depth values every
time the evaluation function returns a score, then dividing it by the
total nodes searched. With proper windowing selections and a good
evaluation function, I have seen the Average Depth be 2 ply less than
the nominal depth. So, while your program shows "8 ply" being
"completed", in reality, it may have only looked at each legal move
through 6 ply and the P.V. though the 8, as shown.

The best way to prevent runway search extensions is to check how far
you are from the root before making a decision to extend or not. For
example, if you are at iteration 6 (doing the 6th ply of search) and
you encounter a node that triggers a sequence of trades, which may
trigger additional search extensions, set up a control variable to
curtail it when a certain criterion is met. The OpenSource program
Crafty has just such a routine. You pass in the current depth, and the
request to extend a certain number of plies, and the routine will scale
the extension and return a smaller number, and this is the deepest you
will go from that point.

The best way to proceed is simply experiment for yourself.