Root move order (again)

[asanjuan]

I'm planning to change the move order at the root node for Rhetoric.

Currently, there's nothing different at the root. I'm using the TT move, good and equal captures based on See and ordered in MVVLVA, killers, quiet moves ordered by history and bad captures. Also, move generation is staged in different phases.

I readed that at least Bob Hyatt is using node counters to sort the root moves, and that makes sense to me. But the cuestion is:

- the node count affects to every move, or only the quiet moves?
- what happens with the good captures and killers? May I order these kind of moves before the "node count section"?


I'm too lazy to test each approach properly, Can anybody give me an advice?

Thanks in advance.

[bob]

I'm planning to change the move order at the root node for Rhetoric.

Currently, there's nothing different at the root. I'm using the TT move, good and equal captures based on See and ordered in MVVLVA, killers, quiet moves ordered by history and bad captures. Also, move generation is staged in different phases.

I readed that at least Bob Hyatt is using node counters to sort the root moves, and that makes sense to me. But the cuestion is:

- the node count affects to every move, or only the quiet moves?
- what happens with the good captures and killers? May I order these kind of moves before the "node count section"?


I'm too lazy to test each approach properly, Can anybody give me an advice?

Thanks in advance.

I use node counts on ALL moves, with one exception. I force the best move from the last iteration to the top of the list. It can, on occasion, not have the largest node count, but it still needs to be searched first, although I actually have not tested this hypothesis to be sure it is correct. I just sort the root moves based on the individual node counts, but give the PV/best move a big counter to make sure it comes out first.

Been doing this since somewhere around 1981 or so...

[AlvaroBegue]

For the depth-1 search, I use the (-Infinity,+Infinity) window for all the moves, so I get exact scores. I sort the moves based on that score initially. Whenever a move becomes the new best move, I move it to the top of the list, sliding the moves that were before it.

My old program Ruy-López also did something else that was a bit funky, but worked well: Partially sort the moves that have never been at the top by number of nodes it took to refute them. The "partially" here means doing three passes of bubble sort in such a way that a move with a high node count can move all the way to the top of the never-best moves, but a move that occasionally has a very low node count will not be pushed more that three steps down.

I used to do a full sort, but we often found that the last move in the list ended up being selected. This was happening at depth D because the move had been very promising at depth D-2 (it passed the PVS null-window test with reductions and was therefore re-examined at full depth). Then at depth D-1 it was refuted immediately because of the hash hit, and moved to the back of the list.

After doing this the program would very rarely pick a move that was near the end of the list.

I should try this idea in my new engine, but I doubt I will be able to measure an Elo improvement.

[Evert]

I readed that at least Bob Hyatt is using node counters to sort the root moves, and that makes sense to me. But the cuestion is:

- the node count affects to every move, or only the quiet moves?
- what happens with the good captures and killers? May I order these kind of moves before the "node count section"?

What I do is this:

For the first iteration, I sort based on the transposition table, killers etc. I use a quiescence search to sort the moves that don't fall in any of those categories. I think the main thing is to sort the move from the TT first though, the rest doesn't matter so much (they're all nominally worse than the first move and if that's indeed true then none of them will improve alpha and the order in which you search them doesn't matter).

Then after each iteration I sort based on the number of nodes used to search that particular move; for the best move I use the total number of nodes to make sure it is searched first.

At an ALL node in the search, I store the move with the largest subtree as the "best" move. Not so important, but it tested as slightly better back when I added this.

Either of these was slightly better, but I don't remember by how much. Perhaps 5 elo or so.

[Daniel Shawul]

At an ALL node in the search, I store the move with the largest subtree as the "best" move. Not so important, but it tested as slightly better back when I added this.

That seems to be a good idea. I still store a 'best move' at an ALL node,i.e the move happens to be at the front of the move list. A similar idea I wanted to experiment with a while ago but didn't is using nodes count for move ordering also for internal nodes through IID. Just like the 'external ID' , you can use nodes count ordering since the data will be immediately available. Currently I do IID at PV/CUT nodes so it may be worth the effort since those type of nodes benefit from better ordering. I guess for the ALL nodes that I do not use IID for, I could do like you do i.e store the move with the largest node count in TT.

[Don]

I'm planning to change the move order at the root node for Rhetoric.

Currently, there's nothing different at the root. I'm using the TT move, good and equal captures based on See and ordered in MVVLVA, killers, quiet moves ordered by history and bad captures. Also, move generation is staged in different phases.

I readed that at least Bob Hyatt is using node counters to sort the root moves, and that makes sense to me. But the cuestion is:

- the node count affects to every move, or only the quiet moves?
- what happens with the good captures and killers? May I order these kind of moves before the "node count section"?


I'm too lazy to test each approach properly, Can anybody give me an advice?

Thanks in advance.

I think you have to test to see what works for you, but to make an actual improvement you will have to run more games that you would probably think worthwhile. In the end it does not make too much difference.

I'll tell you what I do, but it may not be best. Before doing my first search I sort the moves according to the evaluation function but with no regard to quies. This will put all captures first of course and in general will put good moves ahead of bad. In addition I call the static exchange evaluation on all the moves and give a heavy penalty to the moves that are losing. I also have a static threat routine which tells if a move constitutes a viable threat. Those get a bonus. The idea is to start with a move list that is in a very reasonable order but without doing any real work.

Then we begin searching. Whenever a best move is found I "slide it to the top" so that the move list ordering is not upset except for this. I do this when the iteration completes but it could perhaps be done better whenever there is a PV change period.

This has proved to be slightly better than going by node counts. Your mileage may vary. One strength of this system is that if a move is good in one iteration it will stay near the top of the list - but that could be a bad thing if it turns out that this same move is horrible and that is why it got replaced. Most of the time however the search choice is between just 1 or 2 moves and this guarantees that will stay the first 2 entries.

Don

[Daniel Shawul]

This has proved to be slightly better than going by node counts. Your mileage may vary. One strength of this system is that if a move is good in one iteration it will stay near the top of the list - but that could be a bad thing if it turns out that this same move is horrible and that is why it got replaced. Most of the time however the search choice is between just 1 or 2 moves and this guarantees that will stay the first 2 entries.

Well there are two ways to do the root move ordering by nodes. The first one uses number of nodes spent on a move only at the previous iteration of iterative deepening. The other method (and the one i use) saves the cumulative nodes from all the previous iterations so if a move proved best at any of the previous iterations, it will hang around the top of the move list. This has the same effect as your approach and probably allows for a smoother overtaking if a best moves becomes bad.

[asanjuan]

I tested both ideas [node count and cummulative node count], but they performed slightly worse than the standard schema: (godd captures, killers, quiet moves ordered by history.. etc).

I can't really imagine how people can use this kind of move ordering without any subtle trick. Or is that it just doesn't works for me. Or is because I didn't run enough games.

Well, it's time to try with Don's suggestions.

Thanks again.

[Don]

This has proved to be slightly better than going by node counts. Your mileage may vary. One strength of this system is that if a move is good in one iteration it will stay near the top of the list - but that could be a bad thing if it turns out that this same move is horrible and that is why it got replaced. Most of the time however the search choice is between just 1 or 2 moves and this guarantees that will stay the first 2 entries.

Well there are two ways to do the root move ordering by nodes. The first one uses number of nodes spent on a move only at the previous iteration of iterative deepening. The other method (and the one i use) saves the cumulative nodes from all the previous iterations so if a move proved best at any of the previous iterations, it will hang around the top of the move list. This has the same effect as your approach and probably allows for a smoother overtaking if a best moves becomes bad.

I have commented out code where I basically sort by nodes and then place the best move at the front if it's not already there. I think I go by the total accumulated nodes though. I did not try the other way but it could be better.

We are probably talking about less than 1 ELO improvement no matter how you do it. Of course Komodo tries hard to always finish an iteration which means it will see every move - but we do LMR at the root and if a good move is late in the list it might not get discovered on a given iteration if it's profound. That would imply that sorting by nodes could be a slight win as it is sometimes the case that a good move starts taking more nodes to search even before it is discovered.

[Daniel Shawul]

I tested both ideas [node count and cummulative node count], but they performed slightly worse than the standard schema: (godd captures, killers, quiet moves ordered by history.. etc).

I can't really imagine how people can use this kind of move ordering without any subtle trick. Or is that it just doesn't works for me. Or is because I didn't run enough games.

The idea is bad moves, such as Queen sacrifices, are refuted quickly. Ofcourse when the search senses that the sac is turning out good, it will take more and more to refute it so its sub-tree size will increase.

Well, it's time to try with Don's suggestions.

Thanks again.

His method is poorer than nodes count because at a given iteration you make adjustments to only one move's score (i.e the best). The rest just get fail lows (score=alpha) which is a waste of information. Even when the moves have all equal scores , their node counts are different. If for some reason adjusting the best move only is important, you can achieve the same effect by multiplying the best moves node count by some big factor. So unless a move was best at any iteration it will remain with a low score. That should give you the same result as his scheme. You can also try multiplying factors dependent on depth. It doesn't make sense to keep a move that was best at depth=2 while searching depth=19. So this scheme is already better. But anyway I do not think it is such a good idea to focus only on the best move, and just plain cumulative nodes + best-move should be very good.

Daniel