Author: Vincent Diepeveen
Date: 06:26:36 04/24/01
Go up one level in this thread
On April 24, 2001 at 05:55:09, Rafael Andrist wrote: >On April 24, 2001 at 04:24:57, David Rasmussen wrote: > >>On April 23, 2001 at 11:12:55, Rafael Andrist wrote: >> >>>In my chessprog, I'm using an Alpha-Beta-Search with an infinite window. After >>>adding a hashtable, only half of the nodes need to be searched, but I get still >>>a branching factor around 9. The use of Iterative Deepening didn't change much. >>>So now my question is what can I do to improve the search? Should I try to >>>improve the move-sorting? Or is it necessary to use other pruning techniques >>>like Nullmove? >>> >>>Thanks >>> >>>Rafael B. Andrist >> >>You don't say much about your move ordering. But it is very important. In the >>beginning, I didn't even sort captures first, by descending expected gain (after >>hashmove, if you have hash), I just had history move ordering. When I added >>capture (MVV/LVA) move ordering, my BF improved vastly. This is because most of >>the lines in the game tree (especially during quiescence search (do you have >>that? You should)) is hanging a piece or taking a pawn with a queen and the >>losing the queen in the next move. These lines makes the entire subtree >>uninteresting (unless it is an exceptional case such as a sound queen sacrifice, >>which the search will eventually discover), and thus should be cutoff. This is >>the very idea of alpha-beta. > >Of course I have a qsearch, otherwise my prog would make stupid moves. I do also >sort the captures. (If I wouldn't sort them, the BF would be about 12). > >I've now added a killer heuristic, which helps. That means, the BF is now ~7. > >>I think that MVV/LVA is the single most important move ordering term, more >>important than hashmove. Of course, having a Static Exchange Evaluator makes the >>estimates of the gain of a capture even more precise, and improves move ordering >>further. In my program, it is worth the extra time of an SEE to use it at all >>plies in the search. > >Where can I find informations how SEE works? > >Thanks > >Rafael B. Andrist Question is not so stupid. A very efficient Qsearch will greatly reduce overhead and if it gives back accurate scores it will greatly influence branching factor too. SEE means actually: static exchange evaluation. that's an evaluation which replaces qsearch completely. However it last few years get used in crafty to 'estimate' whether a move is not losing material. If it doesn't, then it is tried in qsearch. So your SEE can have any size or quality. In general the more code used to select good moves in qsearch the more efficient it might get and the better scores it will return to the search procedure! without nullmove my b.f. is about 4.5 Best Regards, Vincent
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.