root move ordering

[edwardyu]

Why node counts (or accumulated node counts) are used in ordering root moves? Why not use the scores obtained for each root moves after each iteration?

[Gian-Carlo Pascutto]

Why not use the scores obtained for each root moves after each iteration?

Because, well, you don't actually obtain those?

[edwardyu]

Why not use the scores obtained for each root moves after each iteration?

Because, well, you don't actually obtain those?

The first root move ordering is by the scores obtained by calling Quiesce Search for each moves. I suppose the scores for each moves will be more accurate as iterative deepening is performed. The use of node counts seems to heuristic only with no theoretic backing.

[Gian-Carlo Pascutto]

I suppose the scores for each moves will be more accurate as iterative deepening is performed.

No, you don't get a score for anything but the best move, as I already said.

The use of a quiescent search on the first iteration is to have a starting point and detect easy recaptures.

The use of node counts seems to heuristic only with no theoretic backing.

Yes, the idea being that a large subtree means the move is hard to refute.

[AlvaroBegue]

I implemented a hybrid approach that worked really well for me in Ruy-López. I first ran quiescence search with full window on every move and sorted based on the resulting score.

Then whenever a move is selected as the new best-so-far, I move it to the beginning of the list. I also remember how many different moves have been the best at some point. I keep those in whatever order they are (which means they are sorted by how long ago they were the best).

For the remaining moves (the ones that have never been best), I kind of sort them based on nodes spent, but I do it by running only three passes of the bubble sort loop. This means that a move that all of a sudden has a huge number of nodes, will move to the front. But a move won't ever retreat more than 3 steps from wherever it was.

I don't have any hard data to show that it works well, but very often the good move would be early on even when we still hadn't found the right score for it.

Another idea I've been wanting to explore for a long time and never found the time for is trying to use a similar sorting procedure for some other nodes (perhaps up to distance 3 from the root, or simply whatever fits in a specialized hash table). Has anyone tried something like this?

[bob]

I implemented a hybrid approach that worked really well for me in Ruy-López. I first ran quiescence search with full window on every move and sorted based on the resulting score.

Then whenever a move is selected as the new best-so-far, I move it to the beginning of the list. I also remember how many different moves have been the best at some point. I keep those in whatever order they are (which means they are sorted by how long ago they were the best).

For the remaining moves (the ones that have never been best), I kind of sort them based on nodes spent, but I do it by running only three passes of the bubble sort loop. This means that a move that all of a sudden has a huge number of nodes, will move to the front. But a move won't ever retreat more than 3 steps from wherever it was.

I don't have any hard data to show that it works well, but very often the good move would be early on even when we still hadn't found the right score for it.

Another idea I've been wanting to explore for a long time and never found the time for is trying to use a similar sorting procedure for some other nodes (perhaps up to distance 3 from the root, or simply whatever fits in a specialized hash table). Has anyone tried something like this?

I've been doing the q-search root ordering for years in Crafty, and it works well for a first cut. But once I start searching, I always force the best move to the top of the list, and the rest get ordered by the size of their trees. I tried keeping old best moves at the front, but it was not as good as just sorting everything but the best move based on the size of the tree they produce. Usually as you advance deeper, early best moves are proven bad as deeper tactics are discovered, and they seem to get worse and worse as the search progresses. I could not see any reason to keep them near the front, just because they were best 15 iterations ago...

Sorting the other moves using the same approach doesn't seem as attractive. The root move list has to be completely searched. at plies 2-3 most of those do not require this, and for many of them ordering is irrelevant anyway (ALL nodes). You could try it, but I think it will offer very little above hash, captures and killers that most already use inside the tree. Worth trying? Certainly. But high expectations? probably not.

[AlvaroBegue]

I've been doing the q-search root ordering for years in Crafty, and it works well for a first cut. But once I start searching, I always force the best move to the top of the list, and the rest get ordered by the size of their trees. I tried keeping old best moves at the front, but it was not as good as just sorting everything but the best move based on the size of the tree they produce. Usually as you advance deeper, early best moves are proven bad as deeper tactics are discovered, and they seem to get worse and worse as the search progresses. I could not see any reason to keep them near the front, just because they were best 15 iterations ago...

I can see that. Did you ever try something like the half-baked bubble sort I described? I found that some promising moves would be skipped over fast on some depths, and then they would be pushed all the way back. The limit of moving at most 3 steps back seems to have fixed the problem.

We did have some forward pruning scheme that made the situation above very common. So perhaps other programs would benefit less or not at all by this idea.

Sorting the other moves using the same approach doesn't seem as attractive. The root move list has to be completely searched. at plies 2-3 most of those do not require this, and for many of them ordering is irrelevant anyway (ALL nodes). You could try it, but I think it will offer very little above hash, captures and killers that most already use inside the tree. Worth trying? Certainly. But high expectations? probably not.

Well, we know that move ordering is important inside the tree as well (e.g., history heuristic works).

[bob]

I've been doing the q-search root ordering for years in Crafty, and it works well for a first cut. But once I start searching, I always force the best move to the top of the list, and the rest get ordered by the size of their trees. I tried keeping old best moves at the front, but it was not as good as just sorting everything but the best move based on the size of the tree they produce. Usually as you advance deeper, early best moves are proven bad as deeper tactics are discovered, and they seem to get worse and worse as the search progresses. I could not see any reason to keep them near the front, just because they were best 15 iterations ago...

I can see that. Did you ever try something like the half-baked bubble sort I described? I found that some promising moves would be skipped over fast on some depths, and then they would be pushed all the way back. The limit of moving at most 3 steps back seems to have fixed the problem.

We did have some forward pruning scheme that made the situation above very common. So perhaps other programs would benefit less or not at all by this idea.

Sorting the other moves using the same approach doesn't seem as attractive. The root move list has to be completely searched. at plies 2-3 most of those do not require this, and for many of them ordering is irrelevant anyway (ALL nodes). You could try it, but I think it will offer very little above hash, captures and killers that most already use inside the tree. Worth trying? Certainly. But high expectations? probably not.

Well, we know that move ordering is important inside the tree as well (e.g., history heuristic works).

Here's the question. When you say "solved the problem" how do you measure that? My measurement tool is to play 30,000 games with the change and compare that to the previous version. That is a real objective measure that is hard to ignore.

Yes ordering inside the tree is important. But most nodes are either ALL or CUT. If most of your CUT nodes fail high after 1 move (92% of the time this happens in Crafty) then ordering beyond the hash move, the good captures and killers doesn't help that much. I removed history ordering a couple of years back when cluster testing produced better testing without it.

As I said, it is easy enough to try your idea and see what happens. We tried the idea many years ago when Harry Nelson first suggested the root-move sort based on node counts idea while we were working on Cray Blitz. We never found any benefit beyond the root. But at the root, it does work. But remember, we know we need to search every move at the root. That is the only such node we have a guarantee on.

[AlvaroBegue]

Here's the question. When you say "solved the problem" how do you measure that? My measurement tool is to play 30,000 games with the change and compare that to the previous version. That is a real objective measure that is hard to ignore.

We used a small battery of test positions that we understood really well. We also observed the program during games, and it was clear that the very last move searched turned out to be chosen surprisingly often.

Hardly scientific, but still somewhat meaningful. Think of it as a craft, more than a science.

Yes ordering inside the tree is important. But most nodes are either ALL or CUT. If most of your CUT nodes fail high after 1 move (92% of the time this happens in Crafty) then ordering beyond the hash move, the good captures and killers doesn't help that much. I removed history ordering a couple of years back when cluster testing produced better testing without it.

Ah, that is all interesting information. When I measured similar stats on my program, the numbers weren't nearly as clear. I'll revisit the issue.

As I said, it is easy enough to try your idea and see what happens. We tried the idea many years ago when Harry Nelson first suggested the root-move sort based on node counts idea while we were working on Cray Blitz. We never found any benefit beyond the root. But at the root, it does work. But remember, we know we need to search every move at the root. That is the only such node we have a guarantee on.

That makes sense. I'll report results if I get around to running the test.

[hgm]

Sorting the other moves using the same approach doesn't seem as attractive. The root move list has to be completely searched. at plies 2-3 most of those do not require this, and for many of them ordering is irrelevant anyway (ALL nodes). You could try it, but I think it will offer very little above hash, captures and killers that most already use inside the tree. Worth trying? Certainly. But high expectations? probably not.

Is there any reason to treat the root different from any other PV node? I can imagine that little can be gained in ALL or CUT nodes (either because the ordering doesn't matter at all, or because in most moves in ALL nodes are so poor that the refutation in the subsequent CUT node is trivial to find). But it seems to me that what is good in the root, must be good in other PV nodes. The problem you are facing in those nodes is exactly the same.