Author: John Lowe
Date: 07:04:00 12/24/02
Go up one level in this thread
On December 24, 2002 at 05:46:02, Dave Gomboc wrote: >On December 24, 2002 at 05:41:50, John Lowe wrote: > >>On December 24, 2002 at 05:32:06, Uri Blass wrote: >> >>>On December 24, 2002 at 04:16:11, John Lowe wrote: >>> >>>>On December 23, 2002 at 20:23:04, Robert Hyatt wrote: >>>> >>>>>On December 23, 2002 at 19:21:57, Uri Blass wrote: >>>>> >>>>>>On December 23, 2002 at 18:31:03, Dieter Buerssner wrote: >>>>>> >>>>>>>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 ... >>>>>> >>>>>>If you expect a fail low move you can simply not care about order of moves. >>>>>>Latest movei does not continue to sort the moves if the first 10 moves did not >>>>>>give a fail high(I do not know if 10 is the best number but the gain that I may >>>>>>get from changing it is small because movei is not a fast searcher). >>>>>> >>>>>>Uri >>>>> >>>>>I've done this in crafty for many years. I try the hash move, the good capture >>>>>moves, the killer moves (2), and then if the first 4 history moves don't produce >>>>>a fail high, I just take the remaining moves in the order they were generated. >>>>> >>>>>saves time. >>>> >>>>I have understood good capture, killer and history but could you expand "hash >>>>move" a little. (Terra incognita for me) >>> >>>hash move is a move that you remember from the hash tables and caused a fail >>>high in the same position in previous search. >>> >>>Uri >> >>That's what I thought but why "try" again - have some parameters changed? > >Yes, you're searching one ply deeper this time. :-) > >Dave So the hash move is just a term for the best-so-far and nothing to do with duplication of positions?
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.