Lazy Sort Issue

[Chessnut1071]

Agreed. Usually the captures and non-captures are added to the move list by different pieces of code. Because the sort key has to be calculated in a different way. So you might as well store those in separate lists, so that the sort doesn't have to separate them. In 'The Mailbox Trials' I generated captures in MVV / LVA order. So no reason to sort those.

If you want to sort non-captures by history, you can divide the history range into narrow bins, and maintain a separate list for each bin. If the bins are narrow enough there will hadly ever be more than a single move per bin, and if there are their history score will be so similar that the order doesn't matter. So no reason to sort within the bins. Just run through the bins top-down to search the moves they contain, without any additional sort. E.g. for storing a move into bin n of 64 you can do:

Code: Select all

uint64_t used = 0; // at start of non-capture generation

// for each generated move
int u = used >> n & 1;   // test whether bin empty
int h = (ptr[n] + 1)*u; // initialize or increment depending on u
ptr[n] = h;
bin[n][h] = MOVE; // store the move
used |= 1 << n; // mark as non-empty

For searching just extract the next bit in 'used', and run through the moves in the corresponding bin.

Actually, that approach doesn't work for me. You're assuming those bins are mutually exclusive and in my case they're not. For example, I sum the 10 metrics for an evaluation score: a double check, with a positive history and a slider capture would score 192 + 155 + 73 = 420. I tried the mutually exclusive bins and priority approach and I lose 18% at 10-ply and more at higher ply. I never found a way around a direct sort, YET!

[Ras]

I'm using a lazy lazy (sic) sort approach: the first move goes via selection sort to put the "best" move to the top and try it. If that doesn't work, I sort the remainder of the list via Shellsort, which is among the best for the relatively short lists in chess positions. However, if I have a validated hash move, I don't generate any moves at all and first try the hash move because in that case, the odds of a beta cut-off are at least 90%.

[Chessnut1071]

I'm using a lazy lazy (sic) sort approach: the first move goes via selection sort to put the "best" move to the top and try it. If that doesn't work, I sort the remainder of the list via Shellsort, which is among the best for the relatively short lists in chess positions. However, if I have a validated hash move, I don't generate any moves at all and first try the hash move because in that case, the odds of a beta cut-off are at least 90%.

Like you, I found the Shell Sort has a little better performance over the Quick Sort & Bubble Sort, but, not very much. Your approach is probably better suited for ELO optimization than mate finding. Many authors like to start with Queen sacrifices and obscure pawn moves which wouldn't be obvious. The only cut off I can use is checkmate or on the final ply enemy king moves > 5. thx for the reply

[hgm]

Actually, that approach doesn't work for me. You're assuming those bins are mutually exclusive and in my case they're not. For example, I sum the 10 metrics for an evaluation score: a double check, with a positive history and a slider capture would score 192 + 155 + 73 = 420. I tried the mutually exclusive bins and priority approach and I lose 18% at 10-ply and more at higher ply. I never found a way around a direct sort, YET!

I don't get what you are driving at. Bins by definition span non-overlapping ranges, and are thus 'mutually exclusive'. If your sort key spans the range 0-420 you can use 421 bins, one for each possible value of the sort key.

My guess is that your sort key is not very good for mate finding, btw, which would explain why you get such a poor speedup of only a factor 100. I would expect king safety to be the most important criterion, and you don't seem to weight that into the key at all.