Sorting algorithms

[Evert]

There's even one nice safeguard feature in doing it this way: it prevents negative effects when there is a true hash collision. Since the hash move is matched against the generated move list, this ensures that a possible illegal hash move can't affect the system. That's pretty much the same design as for the opening book.

You should certainly verify that the has move is legal before making it (unless you know that your engine can handle and correctly recover from illegal positions, including those that arise from king-capture and capturing your own pieces) but that is still cheap compared to full move generation.

[hgm]

There should be no chance to overwrite the hash move if the sorting algorithm would sort it to the top. In a way this seems odd, because you only get there if the move wasn't good enough.

I am not sure how that is helpful. To sort the hash move in front, you would have to recgnize it amongst the generated moves to give it a high key. If you recognize it, you might as well suppress its generation, so that it doesn't have to be sorted at all.

This is not so clean if the hash move needs special treatment (unless you hide it next_move()/first_move() in some sort of staged move generator.

I guess separating hash move from the rest is indeed the first onset to staged generation. Indeed this is most cleanly to implement in next_move(). First_move() can be split in gen_init() followed by a next_move(), to keep things simple. Gen_init() can be as simple as setting a variable stage=0, which is then passed to / shared with next_move().

In the "iferno thread", for efficiency reasons, I put the test whether the next move has already been generated in the move loop of search() itself, and then only call a routine more_moves() if there isn't. Like

Code: Select all

if(current >= moveList.end && !more_moves(&moveList)) break; // out of move loop
if(moveList.sort > 1) ExtractBest(&moveList); // swap highest-priority move to front (decrements moveList.sort)
move = moveList.moves[current];

The initialization then consists of setting moveList.stage = moveList.end = 0, and putting the hash move in the list if there is one (moveList.moves[moveList.end++] = hashMove). If there is a PV move separate from the hash move, you could put that in the list too, before starting the first depth iteration.