Author: Rafael Andrist
Date: 02:55:09 04/24/01
Go up one level in this thread
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
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.