Author: Robert Hyatt
Date: 21:10:31 01/04/02
Go up one level in this thread
On January 04, 2002 at 01:39:47, John Coffey wrote: >There has been some confusion in my mind for years >about move ordering. I know that good move ordering will reduce the size of >the tree. How important is it to get all the moves in the best order as >oppose to just starting with the best candidate? > It is not important at all. At positions where you are going to fail high, you want to search a move good enough to produce the fail high. It really doesn't even have to be the _best_ move, just _good enough_ to produce the fail high. At positions where you are going to fail low, you have to search all moves _anyway_ and move ordering at those nodes is meaningless... >For example, I read that some programs generate the entire move list, and >then scan through the list to find the move with the best score (by some >criteria such as the value of captures) and then rescan the list when it is >time to try the next move. Both this scheme and sorting seem very time >consuming to me because we could be talking about N^2 compares. Cutoffs >will reduce the time a great deal. > >If you start with a move from the hash table/transposition table, then how >important is it to >order the remaining moves? If it weren't important, then you wouldn't have >to generate the entire move list, but as I understand it, most programs >generate the entire move list anyway? I think that Crafty does. > >John Coffey Crafty generates moves in two passes... It first generates just captures/ promotions, and if the good ones of those don't produce a fail high, it generates the rest of the moves. I try the moves in the following order: 1. hash move prior to generating _anything_. 2. captures that appear to _win_ material (SEE order) followed by captures that appear to break even. 3. two killer moves (these are non-captures _always_ and are tried before generating any non-capture moves). 4. four "history" moves (history heuristic). 5. remainder of the moves including losing captures in the order they are in the list... Those are good enough to produce the fail-high condition on the first move 92-94% of the time. Anything over 90% qualifies as a "strongly-ordered game tree."
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.