Author: Robert Hyatt
Date: 09:20:56 10/15/99
Go up one level in this thread
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.
This page took 0.04 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.