Author: Robert Hyatt
Date: 05:49:40 01/30/98
Go up one level in this thread
On January 30, 1998 at 00:33:32, Stuart Cracraft wrote: >Sorry about the absurd subject, but I had to get your >attention somehow. :-) > >Here it is... > >When I sort moves, most of the moves don't fall into >a standard category that gets assigned a non-zero score >(killers, captures, hash moves, history heuristic valued, >etc.) Instead, most moves end up in the "other" category. > >This category ends up giving the move a zero score. Most >scores therefore were in the bottom of the heap and chosen >randomly, actually in the order that the move generator >generates them (knights first, then kings, then bishop, >rook, queen, pawns last), since my sort doesn't change >locations of moves or pointers to them and leaves the >zero-scored ones in the same order as the move generator >generated them. > >So recently, I added a centrality perturbation that >added 15 minus the taxicab distance from the move's >destination square to the center of the board (chosen >as E4 since I wanted to avoid real arithmetic to 4.5.) > >Anyway, the result was a major drop in search speed on >certain searches and a drop in results in Win-at-Chess >from 204 to 199 positions solved out of 300, just for >the lousy centrality perturbation of the move sort order. > >Anyone else seen this kind of thing? I didn't even change >the static evaluation. Nothing else was changed. > >--Stuart First, it sounds like you generate all moves, compute some kind of "sort" value and then sort everything. This is grossly slow. you ought to either generate just captures if you can, or move the captures to the top of the list and sort just them. Most of the time these will cause cutoffs if anything is going to cause a cutoff, and you avoid the extra sort overhead. After that much smaller sort, do the killers before generating the rest of the moves if you can, otherwise try the killers and remove 'em from the move list. Then use a selection sort to try "N" history moves (I use N=4 I believe). If you haven't gotten a cutoff by then, simply try the rest of the moves in random order. This cuts out most of that sorting nonsense that only slows you down. In Cray Blitz, Harry played games with the order in which we generated the moves so that the move list came out ordered with the most 'attacking' type moves at the front, the 'retreating' moves at the rear. It hardly ever helped. or hurt. But sorting the entire move list is, at best, an N log N algorithm. If N is small, this is ok. If N is > 20, this can run a while. The selection sort is an M * N algorithm, but for me, M=4 and M*N is smaller than N log N by a wide margin for large N.
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.