Author: Robert Hyatt
Date: 19:56:57 02/21/03
Go up one level in this thread
On February 20, 2003 at 17:48:32, Andrew Dados wrote:
>On February 20, 2003 at 16:30:55, Ricardo Gibert wrote:
>
>>On February 20, 2003 at 15:30:45, Peter McKenzie wrote:
>>
>>><snip>
>>>>
>>>>Remember the trick to sort values in small range WITHOUT actually sorting
>>>>anything?
>>>
>>>No time to read in detail, but I assume you will be describing some sort of
>>>radix sort.
>>>
>>>Peter
>>>
>>>>
>>>>First consider how could you do it IF your 'preeval' returned all unique values
>>>>( means all V=table[move_to] - table[move_from] were unique):
>>>>
>>>>For this we define move_number to be array [0..255] of move NUMBERS, not values
>>>>(that is pointers to actual move array). You need to initialize it to some
>>>>unique value if your array of moves is zero-based, so make it 255
>>>>
>>>> Then all you do for each move is:
>>>>
>>>>(N means move number in move list)
>>>>move_number[table[move_to] - table[move_from]]=N;
>>>>
>>>>now to get them all in sorted order:
>>>>for (i=254;i>0;i--)
>>>> if (move_number[i] !=255) search(moves[i]);
>>>>
>>>>
>>>>Now if values are not unique then move_number table is not enough.
>>>>We need to keep array of all move values and another array of unique flags.
>>>>Hopefully those arrays don't need to be initialized:
>>>>
>>>>unsorted_values,notunique: array [0..255] of char;
>>>>
>>>>now loop generating move values will look:
>>>>
>>>>temp v,moveno: char;
>>>>
>>>>initialize_move_number_to_255;
>>>>moveno=0;
>>>>for each moveno :
>>>>{
>>>> v = table[move_to] - table[move_from];
>>>> if (move_number[v]==255)
>>>> { //first move of value v:
>>>> move_number[v]=moveno;
>>>> notunique[v]=0;
>>>> } else
>>>> { //move with value c was previously generated;
>>>> notunique[v]++;
>>>> }
>>>> unsorted_values[moveno]=v;
>>>>moveno++;
>>>>}
>>>>
>>>>----
>>>> Now to get it all in sorted order:
>>
>>
>>This is the problem. With perhaps only 40 legal moves scattered accross a 256
>>element array, it will be much slower going thru it than to do what Ed is
>>already doing.
>>
>>To make it work better, you would need to index by the 5 highest order bits to
>>shrink the array from 256 elements to 32 (or maybe 4 bits for 16 elements would
>>be even better) so that the array is not so sparsely populated.
>>
>
>Eds problem can be improved in 2 ways imo.
>
>We know hashtable move + 2 killers produce cutoff in about 95% in FH nodes.
>So if there is HT move and/or killers are legal Ed can postpone generating that
>moveordering table.
>
>For FL nodes all moves will be checked. So for 30 moves it is 900 comparisons in
>'naive' approach. You are definitely right here that array is sparsely
>populated. Lets limit our values to 0..128 (shr is fast).
>
>I actually took 20 min and wrote simple routine to compare times to return n-th
>best move. In array of 128 possible values with 30 moves distribution sort
>breaks even when returning 5th best (it takes about 2x more time when all we
>request is first element in sorted order).
>
>However it was over _4 times_ faster when we want all 30 elements sorted (FL
>nodes).
>
the problem is at FL nodes, you don't even need to do this stuff, which is
the problem. IE if you don't get a cutoff after a few, bail out as order
is meaningless...
>As usual YMMV - asm optimization may change those fugures.
>
>-Andrew-
>
>>Still, it is probably all too much much work for so few moves to sort. Sometimes
>>the naive algorithm is best.
>>
>>BTW, the sort you describe is known by many names: bin sort, distribution sort,
>>histogram sort, etc.
>
>Thanks, english is not my native language.
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.