Author: Roberto Waldteufel
Date: 02:14:32 09/16/98
Go up one level in this thread
On September 15, 1998 at 18:51:00, John Coffey wrote: >Let say hypothetically that I have a program that is doing a simple >3 ply search, but will extend its look ahead for every capture. The question >becomes, how far should the look ahead be extended? The last time I wrote >a chess program (1987) I found that the program would examine frivilous >captures out to infinity if I didn't put a limit on it. (I literally had >20 captures in a row.) > >So say I limit the extensions to 2*N, where if N is 3 then 2*N equals 6. >Seems to me that this might not yield an accurate result and could still give >lots of frivilous captures. > >John Coffey Firstly, as I think Bob has said in his reply, the captures cannot go on forever because each capture removes a piece from the board. But that still leaves way too many silly lines of 20 to 30 or so plies of captures, so some forward pruning is necessary. Here is what I do in Rabbit. At each node in the quiescence search, I calculate the evaluation, and the side to move is allowed to either accept the score (stand pat, ie stop searching that line) or to try and improve the score by means of a capture. This is how the Northwestern University program Chess 4.x did it, and that's where I got the idea. I think most of the deep search based programs use the same approach for the quiescence search. It does a reasonable job of controlling the tree size, but sometimes fails to find serious tactical possibilities involving things like forks and double attacks, where the side to move cannot avoid loss of material. Here standing pat is going to miss the threat, and I have found no adequate answer to this other than deeper searching. One last point: if the side to move is in check, then standing pat is not allowed, and all legal replies are examined just like in the full width part of the tree. This adds a bit more overhead, but is necessary to detect mate. I hope the above outline is usefull. If you want more details, try reading Slate & Atkins account of Chess 4.x, which was widely published. Best wishes, Roberto
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.