An idea for move ordering at the root

[sje]

I have an idea for parametrized move ordering at the root (I call the root "ply zero", by the way). Perhaps this has been tried before, but I don't recall seeing it.

A common technique for root move ordering is to loop through each move, execute the move, do a capture search, retract the move, and assign a preliminary score from the capture search result. Obviously, A/B is not used at the first ply so that the preliminary scores are independent as is needed for later sorting.

My idea is to vary the depth of a preliminary A/B full width analysis from zero plies (as above) to up to several ply depending on the position and the clock. So for each root move: execute, perform an N ply full width search with a capture search at depth >= N plies, retract, and then assign the result as the preliminary score.

Yes, this will take more time. But today's machines are of course far, far faster than those of the days when doing simply ordering was a significant time eater.

The motivation for the idea is to get a better ordering which will speed the rest of the search by reducing preliminary scoring error caused by entering a capture search at a too shallow depth.

[Mincho Georgiev]

I've tried exactly that couple of weeks ago, it didn't work for me over the qsearch sorting.
What I'm testing right now is a combined approach - the returned node counts plus the result of a 2 ply search for each move, something like this:

Code: Select all

for(each root move)
{  nodes = 0;
   cleanup_for_all_search_add_ons();
   depth = 2*PLY;
   make_move();
   r = alphabetasearch(-beta, -alpha, depth);
   unmake_move();
   rmovescore = (nodes - r);
}

So far, this was the only idea that brings some improvement for me over the qsearch result, but that doesn't mean it's good, I may do something wrong.

[jdart]

I do regular iterative searching but the first few iterations have a wider than normal root window (plus or minus two pawns I think), instead of using the PVS method of setting the window to zero width after the first move. That allows each move to get a score that is meaningful. I then sort on those scores before doing the next iteration.

After that phase, when I am actually using a narrow window, I used to use node counts to sort but now am just putting the PV move first and pushing all other moves down the stack.

This is working reasonably well. The initial wide window phase of the search is usually over very quickly, even in a fast time control game.

--Jon

[Mincho Georgiev]

I've tried exactly that couple of weeks ago, it didn't work for me over the qsearch sorting.
What I'm testing right now is a combined approach - the returned node counts plus the result of a 2 ply search for each move, something like this:

Code: Select all

for(each root move)
{  nodes = 0;
   cleanup_for_all_search_add_ons();
   depth = 2*PLY;
   make_move();
   r = alphabetasearch(-beta, -alpha, depth);
   unmake_move();
   rmovescore = (nodes - r);
}

So far, this was the only idea that brings some improvement for me over the qsearch result, but that doesn't mean it's good, I may do something wrong.

Correction: After couple of thousand games, it doesn't seem to look any good.

[Don]

I have an idea for parametrized move ordering at the root (I call the root "ply zero", by the way). Perhaps this has been tried before, but I don't recall seeing it.

A common technique for root move ordering is to loop through each move, execute the move, do a capture search, retract the move, and assign a preliminary score from the capture search result. Obviously, A/B is not used at the first ply so that the preliminary scores are independent as is needed for later sorting.

My idea is to vary the depth of a preliminary A/B full width analysis from zero plies (as above) to up to several ply depending on the position and the clock. So for each root move: execute, perform an N ply full width search with a capture search at depth >= N plies, retract, and then assign the result as the preliminary score.

Yes, this will take more time. But today's machines are of course far, far faster than those of the days when doing simply ordering was a significant time eater.

The motivation for the idea is to get a better ordering which will speed the rest of the search by reducing preliminary scoring error caused by entering a capture search at a too shallow depth.

I like the idea, but I have to say that this is definitely not "low hanging fruit" as they say. I've done a lot of experimentation with move ordering at the root and if there is a gain it's pretty small. Whatever is used on the first iteration, our algorithm is to simply keep the list in the same order as it was
in the previous iteration other than sliding any new "best move" to the front.

In principle though I think this is how things should be done and I do not think your idea will hurt the program at all if the depth is small enough relative to the actual depth of the search.

[bob]

I have an idea for parametrized move ordering at the root (I call the root "ply zero", by the way). Perhaps this has been tried before, but I don't recall seeing it.

A common technique for root move ordering is to loop through each move, execute the move, do a capture search, retract the move, and assign a preliminary score from the capture search result. Obviously, A/B is not used at the first ply so that the preliminary scores are independent as is needed for later sorting.

My idea is to vary the depth of a preliminary A/B full width analysis from zero plies (as above) to up to several ply depending on the position and the clock. So for each root move: execute, perform an N ply full width search with a capture search at depth >= N plies, retract, and then assign the result as the preliminary score.

Yes, this will take more time. But today's machines are of course far, far faster than those of the days when doing simply ordering was a significant time eater.

The motivation for the idea is to get a better ordering which will speed the rest of the search by reducing preliminary scoring error caused by entering a capture search at a too shallow depth.

The old belle did something like this, since the software only did a 2 ply search and the hardware did the rest. He just used his hardware search at the root to get true scores for all the moves. I tried that on Cray Blitz, but back then it was simply too expensive to do 4-6 ply searches with an infinite window, to get ordering scores...

I'm not sure it would help today, since we start at ply=1 and as moves fail high they get moved to the top of the list naturally...

[bob]

I do regular iterative searching but the first few iterations have a wider than normal root window (plus or minus two pawns I think), instead of using the PVS method of setting the window to zero width after the first move. That allows each move to get a score that is meaningful. I then sort on those scores before doing the next iteration.

After that phase, when I am actually using a narrow window, I used to use node counts to sort but now am just putting the PV move first and pushing all other moves down the stack.

This is working reasonably well. The initial wide window phase of the search is usually over very quickly, even in a fast time control game.

--Jon

Should this not just return a lot of fail lows with the same score? The first move establishes alpha, and normally everything (or almost everything) will fail low on that score...

[sje]

I like the idea, but I have to say that this is definitely not "low hanging fruit" as they say. I've done a lot of experimentation with move ordering at the root and if there is a gain it's pretty small. Whatever is used on the first iteration, our algorithm is to simply keep the list in the same order as it was
in the previous iteration other than sliding any new "best move" to the front.

In principle though I think this is how things should be done and I do not think your idea will hurt the program at all if the depth is small enough relative to the actual depth of the search.

Yes, my above idea is intended for use only once per search for the initial ordering. Further, it is secondary to forcing the PV move or a TT move to the front of the list.

As part of the initial ordering, Symbolic has a tradition of looking for forced mates and forced losses. At first this was limited to MateIn1 and LoseIn1. With faster hardware, this has grown to include MateIn2, LoseIn2, and MateIn3 -- so the program will never miss a mate in three. The only drawback is that this could take a lot of time in pathological positions, like having 18 queens on the board.

[sje]

The old belle did something like this, since the software only did a 2 ply search and the hardware did the rest. He just used his hardware search at the root to get true scores for all the moves. I tried that on Cray Blitz, but back then it was simply too expensive to do 4-6 ply searches with an infinite window, to get ordering scores...

The Slate/Atkins Chess 4.x program did much the same; instead of doing iterations 1, 2, 3, etc. all in the same way, iteration one was a special case with the A/B window reset to full open after each root move was searched. Note that the report said that the iterations started with number two, and that's why.

[sje]

I've tried using subtree node counts as an ordering heuristic, and while it may have helped slightly, I recall seeing lots of oscillation from one iteration to the next which probably wasn't all that good.

With high resolution CPU usage clock system calls available nowadays, perhaps using processor usage instead of node counts might be a better approach.