root move ordering
Moderators: hgm, Rebel, chrisw
-
- Posts: 34
- Joined: Mon Nov 17, 2008 6:58 am
root move ordering
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?
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: root move ordering
Because, well, you don't actually obtain those?edwardyu wrote:Why not use the scores obtained for each root moves after each iteration?
-
- Posts: 34
- Joined: Mon Nov 17, 2008 6:58 am
Re: root move ordering
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 wrote:Because, well, you don't actually obtain those?edwardyu wrote:Why not use the scores obtained for each root moves after each iteration?
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: root move ordering
No, you don't get a score for anything but the best move, as I already said.edwardyu wrote: I suppose the scores for each moves will be more accurate as iterative deepening is performed.
The use of a quiescent search on the first iteration is to have a starting point and detect easy recaptures.
Yes, the idea being that a large subtree means the move is hard to refute.The use of node counts seems to heuristic only with no theoretic backing.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: root move ordering
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?
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?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: root move ordering
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...AlvaroBegue wrote: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?
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.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: root move ordering
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.bob wrote: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...
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.
Well, we know that move ordering is important inside the tree as well (e.g., history heuristic works).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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: root move ordering
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.AlvaroBegue wrote: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.bob wrote: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...
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.
Well, we know that move ordering is important inside the tree as well (e.g., history heuristic works).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.
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.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: root move ordering
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.bob wrote: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.
Hardly scientific, but still somewhat meaningful. Think of it as a craft, more than a science.
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.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.
That makes sense. I'll report results if I get around to running the test.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.
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: root move ordering
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.bob wrote: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.