Author: Robert Hyatt
Date: 12:28:55 10/15/99
Go up one level in this thread
On October 15, 1999 at 15:16:00, Antonio Dieguez wrote: >On October 15, 1999 at 15:02:05, Robert Hyatt 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. >>> >>>why did you say N passes over N moves? a pass is a round or a loop right? if I >>>understood what Jari told, there are only 7, or not? (what a coincidence I do 7 >>>rounds too!) >>> >>>bye bye... >>> >>>me. >> >> >>No.. he makes a pass over the entire move list to pick the move with the >>highest 'priority'. Then the next time he wants a move, he does this again. >>One pass per move is the only way I can see to do it unless they are actually >>sorted by priority first, which is a waste of cpu cycles... > >but he has only 7 level prioritis, or he said another thing? sure, but he generates moves in random order and attaches a 'priority' to each one. You have to either (a) scan the entire list and pick the remaining move with the highest priority or (b) know which priority you are looking for and scan (on average) 1/2 of the list to find it, assuming there is a move with such priority. still N^2 basically... no matter how you cut it... > >well, another question, is good to maintain 1 killer capture? I think yes... >who maintains a killer capture? > nobody I know of... why? because we try captures _before_ killers anyway, at least those that don't appear to instantly lose material. So by the time we get to killers, the captures are already rejected. >me. >(the prince of amy mizuno, sailor mercury.)
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.