Author: Dieter Buerssner
Date: 15:31:03 12/23/02
Go up one level in this thread
On December 23, 2002 at 18:08:15, Martin Bauer wrote: >Hello, > >i have a queastion about move ordering. There are many sources with move >ordering heuristics like killer heuristic, history and so on... > >But I found no description _how_ to program the move ordering in an _efficient_ >way. In my own enginge I use an integer value together with the move and put it >on the move stack. Moves that should be searched first, become a high value and >the less important moves a low one. Then there is a function named >"NextBestMove" that that looks for the highest value at the actual searchdepth >on the movestack. Therefore it must look at all possible moves in the actual >position. When the best move is found, the value is set to -Matescore, so it can >not get the best move the next time the function is called. This is the normal way to do it, I think. Instead of giving a "marker score", to not search the move again, you could shift the move to the start or to the end of the array, and remember the new bounds (incrementing a pointer may be enough for this). This will save a few CPU cycles. It is essentially the inner loop of a normal selection sort. >This algorithm must have a look at all possible moves in the position at the >actual depth, even if the frist 10 best moves are searched. This look not >efficient to me, because it is an O(n) algorithm in reading the best move and >O(1) in storing the best move. I think, there is no practical better way. Sorting the whole move list can easily be done faster (especially, when it has some considerable length, so not just relpy to check). But often, the work will be done for nothing, because one move will be enough for a cutoff. I experimented a bit with the following idea: Try to guess, when we expect a fail high node: use the selection sort method above. Whe expecting a fail low node, do a qsort (the Standard C-language qsort would probably be a bit slow for this, because of all the calls to the compare function, I had written my own). But, I really could not measure any performance increase, so I gave up on the idea. It just made the code bigger ... Other ideas would be: create the move list sorted. To add a new generated move, a binary search for the position in the list would be enough. I doubt, that one can save significant time. That is all in the context, that you generate all moves at one time. When you have some sort of incremental move generation, the reasoning will differ. Regards, Dieter
This page took 0.02 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.