jdart wrote:
Unfortunately, it just doesn't seem to work. I removed that move ordering and reverted to the original crafty approach of a new best move goes to the front, the rest move down one slot, keeping past best moves near the front. Only thing I do a bit differently is that when a move goes to the front, I save an "age" with it (currently using 4). At the end of each iteration, all the ages are reduced by 1, with a lower bound of zero. If a move has a non-zero age, it is not searched in parallel with any other move, nor is it reduced at the root. This handles the flip-flop case that occasionally happens, where the thing keeps changing its mind.
Based on this thread, I tried a variant of this. Arasan actually searches the first few iterations with all moves having a nonzero window, for easy move detection. So I actually have scores for the moves at that point and for those iterations I sort on the scores. This gives a rough starting ordering.
Formerly after the wide window part of the search I sorted on node counts but I tried as you suggested just moving the new PV to the front and pushing all other moves down.
I think from what you said this is a better founded approach. However, in fact, this tested equal with a sort based on node counts. It wasn't any better, but it wasn't worse either.
I've sorted several different ways during recent testing. None really matter as much as simply getting the best move from the previous iteration sorted first. That covers approximately 85% of the searches, since only about 15% of the time we change to a new best move.
However, for me, there was a small gain in parallel search. Remember that I have an adaptive split at the root algorithm, previously controlled by node counts. For moves (after the first) with significant node counts, I would set a flag that said "do not search in parallel" so I could get through the best move candidates and get a solid alpha bound before starting a parallel search at the root. If you do this, there are two outcomes. (1) if you are NOT going to change your mind, this is less efficient than splitting at the root outright, because the latter will have no search overhead. (2) if you do change your mind, you get a better alpha bound before starting a parallel split at the root, reducing overhead. Unfortunately, it turned out the node count approach was avoiding parallel searches on too many root moves, increasing overhead.
I now avoid splitting at the root until I have searched each move that has been best during the 3 previous iterations. Has proven to be MUCH more accurate for me.
If not for that, perhaps no gain. And one other thing I almost forgot, I do a similar trick for reducing at the root. Makes little sense to reduce a candidate best move because that makes it harder for it to pop to the top. So I am probably getting a more accurate "do not reduce" case as well.
If you don't do either of those, root move ordering is not going to be very significant. Unless you are like me and do not try to complete an iteration before stopping. If you stop when time runs out, you have to hope you have searched the good moves already. Better ordering helps a bit there.
