root sort

[FrancoisK]

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

In BugChess2 I am using something like this. I have a hash table that keep the ordered moves for PV nodes. The improvement was not huge but significant. Of course it also helps LMR in PV nodes. I still have to try to order the moves by number of searched nodes.

François

[Tord Romstad]

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

Simply by remembering everything I need and re-using it at the next time the same position occurs as a PV node.

This is how my root move ordering works at the moment: Before the first iteration, I execute every legal move and calls the quiescence search with an infinite window. The scores from these searches are used to order the moves in the first iteration. At later iterations, I always search the best move from the previous iteration first (of course), and the remaining moves are sorted by their cumulative node counts from all the previous iterations. I think Crafty used to do something very similar (perhaps it still does), if I recall correctly I stole the root move ordering scheme from some ancient Crafty version.

It would be easy to do almost exactly the same at internal PV nodes. If an identical position has occured at some PV node earlier, search the best move found at that time first, and search the remaining moves ordered by node count. If the position hasn't occured at a PV node earlier, order the moves by qsearch scores. When the search of the node is completed, write the data you want to use the next time the position occurs at a PV node back to the PV node hash table.

Tord

[Aleks Peshkov]

Tord, why an extra hash table is needed?
Why not to use a plain list/vector of root moves?

[Zach Wegner]

Tord, why an extra hash table is needed?
Why not to use a plain list/vector of root moves?

Two reasons I can think of. I tried Tord's idea (briefly), but I put the information into the SEARCH_BLOCK structure in my code. Because I only have one search function for all searching, this ended up being another big chunk of memory that got used on every ply, and seemed to slow the search down. Second, I only used it for IID. I believe Tord is saying to use it for every PV node, but use the hash table to keep the information on each PV move persistently from iteration to iteration.

Also, there is no reason not to use a plain list with this method. The hash table is indexed by node. The entries might look something like this:

Code: Select all

struct entry {
   HASHKEY key;
   MOVE move[MAX_MOVES];
   BITBOARD nodes[MAX_MOVES];
   int depth;
};

[michiguel]

Tord, why an extra hash table is needed?
Why not to use a plain list/vector of root moves?

A hash table is convenient because you may have different PV nodes from iteration to iteration. To store all that information with some sort of stacks or lists can blow everything out of proportion and the access will be really clumsy. It is doable by really inconvenient, IMHO. A hashtable is quicker (not important though in PV nodes) and easier to handle. Some move maybe lost, but since this is related to ordering, it may not be too problematic if it is a rare occurrence.

Miguel

[Don]

This is how my root move ordering works at the moment: Before the first iteration, I execute every legal move and calls the quiescence search with an infinite window. The scores from these searches are used to order the moves in the first iteration. At later iterations, I always search the best move from the previous iteration first (of course), and the remaining moves are sorted by their cumulative node counts from all the previous iterations. I think Crafty used to do something very similar (perhaps it still does), if I recall correctly I stole the root move ordering scheme from some ancient Crafty version.
Tord

I went ahead and tried this with my program and it's ever so slightly worse than what I already do based on 1000 position test of node counts.

What I do is this:

I execute every legal move, score and sort it just like you do. I keep a static copy of the move list of course and this is what I work from. Then ...

Whenever a new "best move" appears, I pluck it out and move it to the front (by sliding all entries before this forward.)

Ocassionally, 2 or 3 or more moves will get moved to the front during a single iteration and these were apparently interesting enough to be considered best. So every move that was ever considered good is near the front.

It's not obvious why your scheme should not work better. If what appears to be a good move is really a horrible move, it will tend to stay near the front of the list and in your scheme it would not.

The difference is extremely negligible for speed purposes. But now I wonder if your scheme is better for actual play (regardless of node counts) because you certainly want to try only the best moves first.