Author: Andrew Williams
Date: 14:46:32 08/03/99
Go up one level in this thread
On August 03, 1999 at 14:59:48, Scott Gasch wrote: >Recently I have been trying to limit the number of qeval positions my program >deals with in order to have it spend its time more wisely looking at relevant >positions. In a previous thread Bob Hyatt had a really good suggestion about >how to limit seemingly irrelivant positions -- to recap, if score is way below >alpha in the qeval routine and the value of a capture does + your greatest >possible positional bonus does not bring it over alpha, no sense in considering >the position caused by this capture. > >I am also limiting hte max depth of the qeval search to depth + 12 ply (6 >captures on each side). This causes moderate improvement in very "busy" >positions. I chose 12 because it is even (each side gets to capture the same >number of times) and I have rarely seen a chess game where the best course of >action is a string of 6 captures per side in a row. However, I am returning the >static "eval" of the position at this depth and I am worried that this may lead >to inaccuracy...? But I can't think of another score to assign this depth >qnode. > This won't work - see Jon's comment below - but you shouldn't need to do this anyway. >I am still seeing poor performance, in qeval. In a typical "busy" middlegame I >am seeing about 4 million qeval calls with about 2 million "cuts" due to the >alpha rule (above) and about 200,000 cuts due to max depth exceeded. In these >types of positions it takes about 45 sec just to finish searching at 4 ply >depth! > >Does anyone have comments on these techniques for pruning qeval paths and/or >have any better ideas? > >Scott Here are some ideas. (1) Before you generate any moves at all, you call your evaluate() routine, correct? If the score you get is >= beta, don't bother to search this position, just return beta. (because whoseturn is already doing fine in this position, and doesn't need to capture anything). (2) MAKE SURE YOUR MOVE ORDERING IS SENSIBLE (This is of CRITICAL importance in alpha-beta searching, whatever the flavour you are using). The more the capture gains, the sooner you want to search it. If you haven't got a static exchange evaluator (see below), you can use the Most Valuable Victim-Least Valuable Attacker approach (you should use this in all your searching, by the way). This means that if a Pawn takes a Queen, you should give it a "score" 900-1. If a Knight takes a Rook you should give the capture a score of 500-3. If a Queen takes a Rook that gets a score of 500-9 etc. You sort the captures on these scores before searching them. In this case, you'd search PxQ then NxR then QxR. You'll find your cutoffs much sooner this way, and reduce your number of nodes dramatically. (Incidentally, you'll find that there's a tradeoff between the amount of effort you put into ordering your moves and the NPS speed of your program. Paradoxically, your depths will increase as your NPS goes down. Because your program is doing more *useful* work and looking at fewer stupid nodes). (3) Have you got a static exchange evaluator? If so, just chuck away any captures that (in the opinion of the SEE) lose material (because static exchange evaluators are faster than searching). Andrew Williams
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.