View Single Post
  #3  
Old January 30th 06, 07:41 AM posted to rec.games.chess.computer
external usenet poster
 
Posts: n/a
Default capture search depth


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.

Ads
 

Credit Cards - Vegas Hotel - The eBay Song - Personal Loan - CreditCards