Author: David Blackman
Date: 02:15:14 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 Both! 9 is a bit too high even without null-move. Somewhere around 5.5 to 7.5 should be achievable for "typical mid-game positions". Look at improving your move ordering. Stuff like killers, or history heuristic, or both. Also some primitive ordering like MVV-LVA for captures, assuming you don't do that already. Using a limited width window for alpha-beta also should help. After that, null-move might be a good idea. All the top programs now seem to use either null-move, or some secret selective search method that seems to work at least as well. If null-move is done well, it can get the branch factor down to 3 or even a bit lower. It will cause you to miss some stuff, but the extra depth probably makes it worth it. (If null-move is done really aggresively it can get the branch factor down to 2, but this is not necessarily a good idea :-)
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.