root sort

Discussion of chess software programming and technical issues.

Moderator: Ras

AndrewShort

root sort

Post by AndrewShort »

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?
Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 9:19 pm
Location: Oslo, Norway

Re: root sort

Post by Tord Romstad »

AndrewShort wrote:I am curious why many (all?) engines sort the root differently from other plies.
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.

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
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: root sort

Post by bob »

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?
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 Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 9:19 pm
Location: Oslo, Norway

Re: root sort

Post by Tord Romstad »

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.
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.

Tord
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: root sort

Post by michiguel »

Tord Romstad wrote:
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.
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.

Tord
This has been in my to do list for at least six years... darn it... I wish I had more time...
I have the intuition that this will work well.

Miguel
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: root sort

Post by bob »

Tord Romstad wrote:
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.
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.

Tord
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...
AndrewShort

Re: root sort

Post by AndrewShort »

Tord Romstad wrote:
AndrewShort wrote:I am curious why many (all?) engines sort the root differently from other plies.
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. ...
Tord
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?
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: root sort

Post by Sven »

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?
I would say "no".

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
User avatar
Zach Wegner
Posts: 1922
Joined: Thu Mar 09, 2006 12:51 am
Location: Earth

Re: root sort

Post by Zach Wegner »

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?
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

Re: root sort

Post by AndrewShort »

Zach Wegner wrote:
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?
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.
oops, good point.