Author: Dan Newman
Date: 15:03:30 10/15/99
Go up one level in this thread
On October 15, 1999 at 12:20:56, Robert Hyatt wrote: >On October 15, 1999 at 05:56:45, Jari Huikari wrote: > >>On October 14, 1999 at 16:37:49, Frank Schneider wrote: >> >>>What do others do? >> >>(In the root I sort moves according to their scores, which doesn't take >> much time anyway.) >> >>Elsewhere: In move generation I give a number of priority for each generated >>move. e.g. if pawn captures queen, its priority is 1, non-captures priority >>is 7 and so on... Then in search routine I have a loop I:=1 to 7 and I >>try in the first round the moves of priority 1, then those of priority 2etc. >>So I don't have to sort the moves. >> >> Jari > >that is still an N^2 algorithm, as you make N passes over N moves. Unless you >get an early cutoff. This is called a 'selection sort' and is the way I order >the non-captures in crafty. I try 4 passes thru the 'selection sort' taking >the best history score each time. After 4 passes, I quit the selection sort >and take the moves in the order they were generated, as it has become very >likely that this is an ALL node and there will be no cutoff anyway. This turns >the N^2 algorithm into a 4N algorithm which when N=40+, is significantly faster. One trick to avoid the N^2 problem would be to generate the moves into 7 separate move lists indexed by the priority number, then you'd only need to loop over the 7 lists, trying each move in each list in turn. There would be some overhead of course... -Dan.
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.