Author: Vincent Diepeveen
Date: 16:24:04 12/24/02
Go up one level in this thread
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.
Of course you need fail soft to profit from all these effects a bit more.
Fail hard is years 70s.
>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
This page took 0.01 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.