TalkChess.com

I am currently implementing some simple move ordering techniques (killers and history heuristic for now) and I am beginning to wonder what to do after scoring them.

Previously I just looked through all remaining moves in the list, found the one with the highest score and placed this at the index I was currently at in the alphabeta moves loop: But I am wondering if it would be faster to just sort all the moves (using some kind of fast sorting algorithm) right after generating them, instead of doing it for each iteration in the alphabeta moves loop.
I this a viable option? Is it better to sort all moves in advance or should the highest ordered move just be found at each iteration instead?

Thanks in advance

In vast majority of cases your engine would get a cutt-off after 1 or 2 moves tried, so sorting all moves is generally not good

Picking the next best is a bit better in general because sorting all is often useless as only a few (and maybe on the first) will be used in case of cut-off.
I tried both inside Minic and I get a little more performances using a picker instead of sorting them all.

By the way, not generating move at all is the best thing to try when possible (try TT first without generating)

niel5946 wrote: ↑Thu Feb 04, 2021 10:12 am I am currently implementing some simple move ordering techniques (killers and history heuristic for now) and I am beginning to wonder what to do after scoring them.

Previously I just looked through all remaining moves in the list, found the one with the highest score and placed this at the index I was currently at in the alphabeta moves loop:

Code: Select all

void orderMoves(int index, MoveList* ml){
	int best_index = index;
	int best_score = ml[best_index].score;

	for (int i = best_index; i < ml->size(); i++){
		if (ml[i].score > best_score){
			best_index = i;
			best_score = ml[i].score;
		}
	}
	Move_t temp_move = ml[index];
	
	ml[index] = ml[best_index];
	ml[best_index] = temp_move;
}

But I am wondering if it would be faster to just sort all the moves (using some kind of fast sorting algorithm) right after generating them, instead of doing it for each iteration in the alphabeta moves loop.
I this a viable option? Is it better to sort all moves in advance or should the highest ordered move just be found at each iteration instead?

Thanks in advance

I might be a little bit faster to choose the "pick next best" variant.

But if you combine the "sort movelist" strategy with staged move generation it won't make a big difference.
Using staged move generation will improve the speed anyway. The move lists for the early stages like TT / captures / killers
are really short and move ordering is not an issue for the first moves. It becomes intersting with the quiets then...
But quiets are not part of qs() ... and there are components that are more expensive than move ordering of captures in qs(), like SEE...

Well, in a staged move generation scheme the "sort complete list" is not a problem if you don't fight for a single elo already.
You can use it without headache i would say. If you need to know exaclty what is going on you need to measure the elo difference
of both versions.

But i guess in your stage of development there are more important things that can be focussed at the moment.
For example, if you don't have staged move generation implemented, that would be a component that you need to improve you engine
in long run.

Move sorting is not a 'monolithic' problem, and there are many ways to approach it. Captures have to be sorted on other criteria as non-captures (MVV-LVA & SEE vs history / killer). Some sort algorithms are more efficient than others (qsort, shell sort), but these are often difficult to perform in a 'staged' way. Extracting the best move every time is one of the slowest sorting methods (O(N^2)), but if you get a beta cutoff after the first move, you have spent only O(N) time, and never have to do the remaining part of the sort.

It also depends on how you separate the captures from the non-captures. Before you even can start sorting you have to assign a sort key to the moves, and to determine what key to use, you have to determine whether the move is a capture. I usually do that already during move generation. With a mailbox design this information becomes available as a side effect: you have to examin destination squares to see whether they contain an enemy or a friend, and if they contain an enemy so that you generate the capture you can add an MVV/LVA sort key to the move. I then just store the captures at the beginning of the move list, while non-captures go at the end. In bitboard designs you can also use different loops to extract captures and non-captures, and store them in seperate places.

When you already start with the captures separated from the non-captures, the sorting of the captures (which you will search first) is not a big deal, as there are only few of those. So you don't care too much if the sorting algoritm is O(N^2), O(N*log(N)) or O(N), and you just extract the next in line. This is different for the non-captures, but by the time you get to those, the chances that you will still get a beta cutoff are rather slim. Extracting killers is not really a soring problem; you have to identify them in the list. And after you have searched those the prospects for a beta cutoff are even slimmer. So it could help to have an efficient algorithm for the history sort, even when this needs to be completed before you can search your first move.

Now it happens to be not to difficult to do a complete history sort in O(N) steps. The idea is to 'bin' the moves by history score, distributing them over a number of bins that is so large that there will be hardly any bin that gets more than a single move in it. You can then loop through the bins from high to low history score, and search the moves you encounter in them. When a bin occasionally contains more than one move, you could in principle sort that small number. But since they will have very nearly the same history score, this would probably be a waste of time, and you might as well search them in any order.

You could reserve an array of 64 bytes for the bins, which each could contain the number of a move in the move list. And you could use the high byte of the moves in that list (normally used for the sort key) to indicate there are more moves in the same bin (i.e. use it as a link in a linked list). To quickly loop through a large and sparsely filled set of bins, you would assign a bit to each bin in a set of larger integer variables, which you set to 1 when you put a move in the bin; You can then loop over the bins by extracting the 1 bits from this 'bin directory', and then run through the linked list they contain (usually of length 1) to search the moves there. To make efficient use of the bins you could keep track of the largest history score in the table, and take the history scores relative to that. (E.g. you could do the history calculation in 32-bit floting point, but read it back for scoring the moves as 32-bit integer, to get it on an approximately logarithmic scale.)

What about quicksorting only the left half of the move array recursively? The more important the moves are the more they are sorted.
You can play a little with the pivot element being the median of three elements if you like.

Harald wrote: ↑Thu Feb 04, 2021 6:03 pm What about quicksorting only the left half of the move array recursively?
...

I think I'd be concerned that a particular pivot may give sub-optimal results.

You can divide quicksort in stages that way. But why would you, if there is a simpler O(N) method available?

If you are using some sort of historyscore for the sorting of quiet moves, the historyscore of moves change while searching the current quiet move. If you presort the quiet moves, you don't use the changes in historyscore for the still to search quiet moves which can lead to a different order of those moves.

Ronald wrote: ↑Thu Feb 04, 2021 6:57 pm If you are using some sort of historyscore for the sorting of quiet moves, the historyscore of moves change while searching the current quiet move. If you presort the quiet moves, you don't use the changes in historyscore for the still to search quiet moves which can lead to a different order of those moves.

Interesting. I never thought of that. (Had a lot of trouble that killers changes when you searched them with IID, though. Leading to the most important non-captures not being searched in the higher iterations!) Is there really a measurable effect from this?