Author: Uri Blass
Date: 08:40:22 12/25/02
Go up one level in this thread
On December 25, 2002 at 11:38:26, John Lowe wrote: >On December 25, 2002 at 02:34:22, Uri Blass wrote: > >>On December 24, 2002 at 23:05:09, Robert Hyatt wrote: >> >>>On December 24, 2002 at 19:24:04, Vincent Diepeveen 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. >>>> >>>>This is utter nonsense. >>>> >>>>==> note that it is another years 80 design issue in crafty >>>> >>>>For many reasons sorting is better. To just list a few >>>> a) it *might* give a cutoff now. No heuristic is 100% accurate >>>> going to predict it is going to get a fail low again. >>>> The proof for that is obvious. If you know it for 100% sure you >>>> can simply return alpha and stop searching this node! >>>> b) it goes into hashtable and gets reused later. You perhaps do not >>>> expect a fail low then but the best move saved in the hashtable is >>>> a random move in your case >>>> c) it improves positional play obviously. Suppose you pick a random >>>> move giving 0.001 versus a chosen move 0.001. The chosen move on >>>> average is better. Do not underestimate this effect at all. this is >>>> not a 'once in a million moves i play' scenario. >>> >>>That is utter clap-trap. Why don't you go read Knuth/Moore's paper on >>>alpha beta. There you will find that move ordering does _not_ affect the >>>final score, only the size of the tree. Something every senion-level computer >>>science student should know. >> >>I can imagine a case that it can affect the final score. >> >>Suppose that there are 2 moves that potentialy gives fail high that you did not >>search >>move A and move B. >> >>if you search first move A you get a score for move A and move B is pruned >>by null move pruning. >> >>if you search first move B then move B is not pruned by null move pruning and >>you get a bigger score for move B so you do not play move A. >> >>It does not mean that not sorting is a mistake because being faster is an >>advantage and I do not think that the quality of order by history table is good >>in any case so not sorting after enough moves is an advantage for a lot of >>programs. >> >>Uri > >I thought the idea of move ordering was to predict cut-offs faster to give you >time to look a bit further within the time limit. > >Disproving what you earlier thought was the best will affect the outcome. An >indirect but positive contribution from move ordering. When you calculate perft you calculate number of games and order of moves have no importance. Uri
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.