I am curious why many (all?) engines sort the root differently from other plies.
Presently I sort the root the same as any other ply - pv move, hash best move (and if not available, an IID best move), captures, killers, promotions, history, etc, I've forgotten my exact order but you get the point.
I see other engines sort the root of each iteration in descending order of node count, where node count is the number of nodes (including hash hits) it took in the previous iteration. Iteration 1 is special case, since there is no previous iteration (not sure how root of iteration 1 would be sorted, but it probably doesn't matter....)
Why, theoretically/practically, is sorting the root the same way as the other plies inferior to say, the node count search?
root sort
Moderator: Ras
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: root sort
Because good move ordering at the root is far more important than at any other node. You don't want to just search the move with the biggest probability of being the best move first, you want to search all the moves in descending order of probability of being best, because every fail-high followed by a re-search with a big window will be very expensive. At most internal nodes, you search with a zero window, and the most important thing is whether the first move causes a beta cutoff. If it does, you have finished searching the node, and it doesn't really matter much whether one of the remaining moves would theoretically have been even stronger. If the first move doesn't cause a beta cutoff, the remaining moves probably also won't, and move ordering at this node isn't very important.AndrewShort wrote:I am curious why many (all?) engines sort the root differently from other plies.
On the other hand, you may argue that internal PV nodes should be handled in the same way as the root node. Using the same move ordering strategy at internal PV nodes (at least at PV nodes with a big remaining depth) as at the root node makes a lot of sense, and experimenting with this has been on my todo list since a long time. I'm not sure whether it has already been tried by somebody else.
Tord
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: root sort
One major reason: at the root you have information that would be impossible to obtain for non-root moves. Such as "which move was the previous best move here?" Or "which move is producing an increasing tree size and might become a new best move soon?" Those are cheap to measure at the root, very expensive to measure at interior nodes.AndrewShort wrote:I am curious why many (all?) engines sort the root differently from other plies.
Presently I sort the root the same as any other ply - pv move, hash best move (and if not available, an IID best move), captures, killers, promotions, history, etc, I've forgotten my exact order but you get the point.
I see other engines sort the root of each iteration in descending order of node count, where node count is the number of nodes (including hash hits) it took in the previous iteration. Iteration 1 is special case, since there is no previous iteration (not sure how root of iteration 1 would be sorted, but it probably doesn't matter....)
Why, theoretically/practically, is sorting the root the same way as the other plies inferior to say, the node count search?
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: root sort
Very expensive to measure at all interior nodes, but not so expensive if you limit it to PV nodes, which was my proposal. Just introduce a second transposition table for PV nodes, where you stuff all the information you need to do root-like move ordering into the transposition table entries. The entries will be huge, but you can keep the number of entries in the table quite small, because there are so few PV nodes.bob wrote:One major reason: at the root you have information that would be impossible to obtain for non-root moves. Such as "which move was the previous best move here?" Or "which move is producing an increasing tree size and might become a new best move soon?" Those are cheap to measure at the root, very expensive to measure at interior nodes.
Tord
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: root sort
This has been in my to do list for at least six years... darn it... I wish I had more time...Tord Romstad wrote:Very expensive to measure at all interior nodes, but not so expensive if you limit it to PV nodes, which was my proposal. Just introduce a second transposition table for PV nodes, where you stuff all the information you need to do root-like move ordering into the transposition table entries. The entries will be huge, but you can keep the number of entries in the table quite small, because there are so few PV nodes.bob wrote:One major reason: at the root you have information that would be impossible to obtain for non-root moves. Such as "which move was the previous best move here?" Or "which move is producing an increasing tree size and might become a new best move soon?" Those are cheap to measure at the root, very expensive to measure at interior nodes.
Tord
I have the intuition that this will work well.
Miguel
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: root sort
I don't even _have_ some of the information. What was the second-best move last iteration, for example? But if you change your mind from A to B, you can keep A near the top of the list to search it first since it is a known good move and might help you if B drops the next iteration. I don't know how you would get this inside the normal alpha/beta search...Tord Romstad wrote:Very expensive to measure at all interior nodes, but not so expensive if you limit it to PV nodes, which was my proposal. Just introduce a second transposition table for PV nodes, where you stuff all the information you need to do root-like move ordering into the transposition table entries. The entries will be huge, but you can keep the number of entries in the table quite small, because there are so few PV nodes.bob wrote:One major reason: at the root you have information that would be impossible to obtain for non-root moves. Such as "which move was the previous best move here?" Or "which move is producing an increasing tree size and might become a new best move soon?" Those are cheap to measure at the root, very expensive to measure at interior nodes.
Tord
Re: root sort
Interesting, thanks, I hadn't thought of it that way. As an academic question, wouldn't it be true that if your engine does not use aspiration windows (in other words, you search the root every time with [-inf, inf] as your alphabeta window), then there would be no point in sorting the root at all? You would never fail low or high, and you would never re-search the root - you simply plow through the root once, and even if the moves were in exactly the wrong (reverse) order, it wouldn't matter.... I guess it would matter on timeout, because when an iteration times out you want the best move found so far from the timed out iteration. But academically, if you were doing fixed depth searches (no timeout) with no aspiration windows, then sorting the root would have zero effect. Correct?Tord Romstad wrote:Because good move ordering at the root is far more important than at any other node. You don't want to just search the move with the biggest probability of being the best move first, you want to search all the moves in descending order of probability of being best, because every fail-high followed by a re-search with a big window will be very expensive. ...AndrewShort wrote:I am curious why many (all?) engines sort the root differently from other plies.
Tord
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: root sort
I would say "no".AndrewShort wrote:But academically, if you were doing fixed depth searches (no timeout) with no aspiration windows, then sorting the root would have zero effect. Correct?
Let's assume iteration N returns A as best move and B as "second best" (whatever that means, of course this can't be determined exactly most of the time since cutoffs do not deliver exact values).
Now in iteration N+1 you search A first (let's say not due to root ordering but since you want to start with the PV in general) and all other moves including B in random order.
If you change your mind in this iteration and find B to be better than A then searching all other root moves will in most cases require less nodes if B is searched before them, due to a smaller window for the other moves.
Aspiration windows help by starting with a small window even for the first root move but not using them does not make move ordering at root useless IMHO.
Sven
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: root sort
No, because searching with an open window doesn't mean alpha and beta aren't modified. You search the first move with (-inf,inf), and then later moves with (alpha,inf). Some people (including me) use PVS at the root as well.AndrewShort wrote:Interesting, thanks, I hadn't thought of it that way. As an academic question, wouldn't it be true that if your engine does not use aspiration windows (in other words, you search the root every time with [-inf, inf] as your alphabeta window), then there would be no point in sorting the root at all? You would never fail low or high, and you would never re-search the root - you simply plow through the root once, and even if the moves were in exactly the wrong (reverse) order, it wouldn't matter.... I guess it would matter on timeout, because when an iteration times out you want the best move found so far from the timed out iteration. But academically, if you were doing fixed depth searches (no timeout) with no aspiration windows, then sorting the root would have zero effect. Correct?
Re: root sort
oops, good point.Zach Wegner wrote:No, because searching with an open window doesn't mean alpha and beta aren't modified. You search the first move with (-inf,inf), and then later moves with (alpha,inf). Some people (including me) use PVS at the root as well.AndrewShort wrote:Interesting, thanks, I hadn't thought of it that way. As an academic question, wouldn't it be true that if your engine does not use aspiration windows (in other words, you search the root every time with [-inf, inf] as your alphabeta window), then there would be no point in sorting the root at all? You would never fail low or high, and you would never re-search the root - you simply plow through the root once, and even if the moves were in exactly the wrong (reverse) order, it wouldn't matter.... I guess it would matter on timeout, because when an iteration times out you want the best move found so far from the timed out iteration. But academically, if you were doing fixed depth searches (no timeout) with no aspiration windows, then sorting the root would have zero effect. Correct?