Author: Uri Blass
Date: 12:33:45 12/25/02
Go up one level in this thread
On December 25, 2002 at 15:21:09, Robert Hyatt 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. > >That is a bug caused by null-move, _not_ by move ordering. Null-move can >introduce several different types of artifacts, but a _proper_ search is not >affected by move ordering... I do not call it a bug. A bug is something that is not supposed to happen. This thing is supposed to be possible for every program that is using null move pruning. Every search that is using null move pruning and most of the searches use it can be effected by order of moves. 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.