Author: David Rasmussen
Date: 01:24:57 04/24/01
Go up one level in this thread
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. 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.
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.