Move size & ordering ?

[MahmoudUthman]

Right now I'm using the following representation :

Code: Select all

struct Move
{
	U32 move;
	int Score;//for move ordering
};//64 bit

has anyone tested an ordering score spanning a 4 byte int range against one that with only 2 bytes ?
in other words which one is supposed to give better performance due to better ordering , the 4 byte ordering score allows for much larger history range, but is such a range really rely needed ?

[tomitank]

I use this range for History:
0 - 2048
Default = 1024

[Pio]

Hi Mahmoud!

There is no problem storing the move in 16 bits and if you need to compress the scores to 16 bits, you can always transform the normal centipawn or millipawn scores to probability based scores. The advantage of storing the score as a probability is that the resolution is very high where it is needed and low where it does not matter. Who cares if you are leading with one or two queens?

BR
/Pio

[jdart]

I have never seen move ordering be any significant fraction of search time.

--Jon

[hgm]

I always use a single 32-bit unsigned int for moves in the move list. The sort key is stored in the upper byte, the 24 lowest bits are available for encoding the move. This allows direct comparison of the entire 32-bit quantity for extracting the one with the highest key.

Only captures have a non-zero key, 16*seeVal[victim] - seeVal[attacker], to implement MVV/LVA (with seeVal[] = {1, 3, 3, 5, 9}). For HxL captures this is can be replaced by 16*SEE, or, SEE-less, reduced to 1 for postponing them when the victim is found to be protected when their turn comes up. When I use history for the non-captures I use qsort(), and the comparison routine I pass to it directly accesses the history array, using the move as an index. So no need to store any sort key with the move, then.

When I would want to speed up the non-capture sorting, I would not try to speed up the comparison in qsort() to avoid the extra indirection, but use a faster sort algorithm. This would use the upper byte of the move to store the move number of the 'successor move' in a linked list of moves with a similar history score. The entire range of history scores would be logarithmically subdivided into 256 'classes', and every move would be linked into the list for the class corresponding to its history score. a 256-element array of move numbers would indicate the first move in each list. The move extraction would just run through the linked lists, starting with the one for the highest history score range.

[Kotlov]

Use uint64 for all record.
(score, move from, move to ...)

[cdani]

Right now I'm using the following representation :

Code: Select all

struct Move
{
	U32 move;
	int Score;//for move ordering
};//64 bit

has anyone tested an ordering score spanning a 4 byte int range against one that with only 2 bytes ?
in other words which one is supposed to give better performance due to better ordering , the 4 byte ordering score allows for much larger history range, but is such a range really rely needed ?

I tried various setups and faster was int (4 bytes) for score. But I use 8 bytes for sorting root moves, as they contain number of moves searched for each one, and this numbers can be very big.

And I also just changed some move stuff on Andscacs from 2 to 4 bytes, and was faster. But I store the move inside hash with 2 bytes.