Move Ordering?

[JVMerlino]

Move ordering at the root.

Take this example, where white gets these scores for his 9 moves in fx iteration 4.

1, - score +40 new best move
2, - score +30
3, - score +10
4, - score +70 new best move
5, - score +50
6, - score +50
7, - score +90 new best move
8, - score +80
9, - score +60

Iteration 5 must no doubt start with move 7 which got a score of 90.

But should the next move be move 8 that got the next best score of 80?
Or should it be move 4, the previous best move?

If we choose move 7, 4 and 1 as the 3 first moves, what do we try first after that?

You can also argue, that move 2 and 3 were harder for black to refuse than move 8 and 9.
For move 2 and 3 black black had to get a score lower than +40.
For move 8 and 9 he only had to get below +90.
So it is likely, that black only searched a few moves to refute move 8 and 9.
(and could have found moves that scored even lower).
And perhaps black searched almost all his moves to refute move 2 and 3.

But you can also argue, that iteration 3 gave the move order we use here (from best move to worst move).
So move 2 and 3 might still be better than move 8 and 9 although they scored less?

I once made a function in Dabbaba, that adjusted the scores to compensate for these levels.
But I never really tested seriously if it had any effect.

Someone mentions, that the number of nodes searched for each move can be used...

What is the right thing to do?

Shouldn't you be using a PVs search at root? Wouldn't this make it so that it is impossible (barring search instability) to get a score that is less than the current best score?

Code: Select all

if (playedmoves == 1 || -Alphabeta(depth-1, -alpha-1, -alpha, !PV) > alpha )
{
	val = -Alphabeta(depth-1, -INFINITY, INFINITY, PV);
}

if (val > alpha)
{...}

I could be wrong, but I think he's only talking about the score used for move ordering, not the eval returned by the search.

Is that right, Jens?

jm

[JBNielsen]

I could be wrong, but I think he's only talking about the score used for move ordering, not the eval returned by the search.

Is that right, Jens?

jm

No John, it is actually the score from the search.
Whites first move gave a score of +40.
When I examine whites second move, I find a black move that would give him a score of +30.
It gives a cut-off. Of course I don't transfer this score to the root, but I store the value +30 together with whites second move.

Maybe this is useless information?!

But if the best move turns out to be bad, it must be important to try with our best guess of the second best move...

[bob]

Move ordering at the root.

Take this example, where white gets these scores for his 9 moves in fx iteration 4.

1, - score +40 new best move
2, - score +30
3, - score +10
4, - score +70 new best move
5, - score +50
6, - score +50
7, - score +90 new best move
8, - score +80
9, - score +60

Iteration 5 must no doubt start with move 7 which got a score of 90.

But should the next move be move 8 that got the next best score of 80?
Or should it be move 4, the previous best move?

If we choose move 7, 4 and 1 as the 3 first moves, what do we try first after that?

You can also argue, that move 2 and 3 were harder for black to refuse than move 8 and 9.
For move 2 and 3 black black had to get a score lower than +40.
For move 8 and 9 he only had to get below +90.
So it is likely, that black only searched a few moves to refute move 8 and 9.
(and could have found moves that scored even lower).
And perhaps black searched almost all his moves to refute move 2 and 3.

But you can also argue, that iteration 3 gave the move order we use here (from best move to worst move).
So move 2 and 3 might still be better than move 8 and 9 although they scored less?

I once made a function in Dabbaba, that adjusted the scores to compensate for these levels.
But I never really tested seriously if it had any effect.

Someone mentions, that the number of nodes searched for each move can be used...

What is the right thing to do?

I have tried lots of things. using the node-count for each ply-1 move has always tested better for me. The reason is somewhat subtle, but it has been used since the 1980's and Cray Blitz for me...

The larger the ply-1 sub-tree, the harder that tree is to search, which can in many cases mean it is getting better and better. I have a flag I can use to dump the ply-1 move list and node counts after each search.

Here's a trivial example to keep the output short.

Position fine 70. Best move (only winning move) is Kb1

Three iterations before it finds Kb1, it produces these node counts:

Code: Select all

       move       nodes     R/P/3*  1. Kb1     (1.3Mnps)             
        Kb2       13256     0 0
        Ka2         123     1 1
        Kb1          64     1 1
      total       13443

Notice Kb2 (the PV/best move) has a huge number of nodes compared to the other two which are pretty puny.

Now two iterations before it discovers Kb1 is winning:

Code: Select all

       move       nodes     R/P/3*  1. Kb1     (2.3Mnps)             
        Kb2        8129     0 0
        Ka2        1138     1 1
        Kb1        1107     1 1
      total       10374

and then the iteration right before Kb1 fails high:

Code: Select all

       move       nodes     R/P/3*  1. Kb1     (1.8Mnps)             
        Kb2       11080     0 0
        Kb1        5486     1 0
        Ka2         338     1 1
      total       16904

Notice that Kb2 is still best, but also notice how Kb1 has climbed in node count. Because what was getting lots of cutoffs has become harder and harder to prove "inferior" to Kb2.

By ordering on those node counts, I search Kb1 before Ka2 the next time and do about as well as I could do. This works for any type of position.

I even use that in my parallel search. When I start that last iteration above, Kb1 is so much larger than the rest of the moves (the third move in this case) I do not split at the root until both Kb2 AND Kb1 have been searched, one at a time, using a full parallel search on each move. I get a score/best move back quicker if I have all CPUs searching on Kb1 as opposed to half of them on Kb1 and half on Ka2...

If you have questions, fire away. I can't guarantee you it is best for all programs. It is, and has been for years, best for mine, however.

[Aleks Peshkov]

Whites first move gave a score of +40.
When I examine whites second move, I find a black move that would give him a score of +30.
It gives a cut-off. Of course I don't transfer this score to the root, but I store the value +30 together with whites second move.

Maybe this is useless information?!

But if the best move turns out to be bad, it must be important to try with our best guess of the second best move...

Unless you switch off alpha-beta pruning at the root, you cannot be sure that the second move is +30, you only know that is +30 or less. Third move with cut off score +20 have a good probability to be better the second, making cut off score ordering almost random.

[JBNielsen]

I have tried lots of things. using the node-count for each ply-1 move has always tested better for me. The reason is somewhat subtle, but it has been used since the 1980's and Cray Blitz for me...

....

If you have questions, fire away. I can't guarantee you it is best for all programs. It is, and has been for years, best for mine, however.

Thanks for the input.

I will try this when I have released my current changes.

I will try to combine it with my idea of adjusting the levels due to the different windows the moves are searched with.

A test with a lot of ordinary test positions searched to a fixed depth will hopefully indicate what is the best solution.

[jd1]

Do you have any rules that cause you to try to do better move ordering once you reach a certain depth? It is fairly common for some programs to attempt better move ordering when the depth is greater as the overhead impacts the program much less.

Interesting, I did not know that. How would this better move ordering be done?

Thanks,
Jerry

[JBNielsen]

I have tried lots of things. using the node-count for each ply-1 move has always tested better for me. The reason is somewhat subtle, but it has been used since the 1980's and Cray Blitz for me...

The larger the ply-1 sub-tree, the harder that tree is to search, which can in many cases mean it is getting better and better. I have a flag I can use to dump the ply-1 move list and node counts after each search.

..............

If you have questions, fire away. I can't guarantee you it is best for all programs. It is, and has been for years, best for mine, however.

I have tried to use number of nodes instead of scores to order the moves at the root, but with my testpositions it gives almost the same result as my original move ordering by scores.

But when I add my level-adjustment, I have ca. 5% speed-up.

What is this level-adjustment?

Take this example with these scores for white:

Code: Select all

1, - score +40 new best move 
2, - score +30 
3, - score +10 
4, - score +70 new best move 
5, - score +55 
6, - score +30 
7, - score +40 
8, - score +45 
9, - score +50 

When I get a new-best-move at move 4, it is 70-40=30 better in score than move 1.

Now we have a new situation:
It is much easier for black (more possible moves) to refute whites next moves because
1) the white moves are weaker (if we have ordered them well from previous iterations)
2) the moves can now also be refuted by scores in the range of 41 to 70

Move 5 is refuted by a score of 55.
Perhaps it was not by blacks best move which may have given a score of 5.

This is bad for the move ordering.
So whenever I get a new best move after the first move, I adjust the scores of the previous moves.

I could fx add +25 to the 3 first moves (move 1 must not be better than move 4).
This helps to keep the good move order.

It seems to give my engine an increase in speed of 5%.
An easy way to get an increase in speed.

(I tried briefly to do the same adjustment with the number of nodes, but in vain)

[bob]

I have tried lots of things. using the node-count for each ply-1 move has always tested better for me. The reason is somewhat subtle, but it has been used since the 1980's and Cray Blitz for me...

The larger the ply-1 sub-tree, the harder that tree is to search, which can in many cases mean it is getting better and better. I have a flag I can use to dump the ply-1 move list and node counts after each search.

..............

If you have questions, fire away. I can't guarantee you it is best for all programs. It is, and has been for years, best for mine, however.

I have tried to use number of nodes instead of scores to order the moves at the root, but with my testpositions it gives almost the same result as my original move ordering by scores.

But when I add my level-adjustment, I have ca. 5% speed-up.

What is this level-adjustment?

Take this example with these scores for white:

Code: Select all

1, - score +40 new best move 
2, - score +30 
3, - score +10 
4, - score +70 new best move 
5, - score +55 
6, - score +30 
7, - score +40 
8, - score +45 
9, - score +50 

When I get a new-best-move at move 4, it is 70-40=30 better in score than move 1.

Now we have a new situation:
It is much easier for black (more possible moves) to refute whites next moves because
1) the white moves are weaker (if we have ordered them well from previous iterations)
2) the moves can now also be refuted by scores in the range of 41 to 70

Move 5 is refuted by a score of 55.
Perhaps it was not by blacks best move which may have given a score of 5.

This is bad for the move ordering.
So whenever I get a new best move after the first move, I adjust the scores of the previous moves.

I could fx add +25 to the 3 first moves (move 1 must not be better than move 4).
This helps to keep the good move order.

It seems to give my engine an increase in speed of 5%.
An easy way to get an increase in speed.

(I tried briefly to do the same adjustment with the number of nodes, but in vain)

Where do you get the scores for each root move? Scored at the root? Static eval? What?

The number of nodes is useful for other things as well. If the 2nd move is within "range" of the first move, one can avoid searching the second move with just one processor (letting the others take the third, etc, classic YBW) since it appears it is "trying" to become best since the node count is climbing, iteration by iteration. Etc.

[JBNielsen]

I have tried lots of things. using the node-count for each ply-1 move has always tested better for me. The reason is somewhat subtle, but it has been used since the 1980's and Cray Blitz for me...

The larger the ply-1 sub-tree, the harder that tree is to search, which can in many cases mean it is getting better and better. I have a flag I can use to dump the ply-1 move list and node counts after each search.

..............

If you have questions, fire away. I can't guarantee you it is best for all programs. It is, and has been for years, best for mine, however.

I have tried to use number of nodes instead of scores to order the moves at the root, but with my testpositions it gives almost the same result as my original move ordering by scores.

But when I add my level-adjustment, I have ca. 5% speed-up.

What is this level-adjustment?

Take this example with these scores for white:

Code: Select all

1, - score +40 new best move 
2, - score +30 
3, - score +10 
4, - score +70 new best move 
5, - score +55 
6, - score +30 
7, - score +40 
8, - score +45 
9, - score +50 

When I get a new-best-move at move 4, it is 70-40=30 better in score than move 1.

Now we have a new situation:
It is much easier for black (more possible moves) to refute whites next moves because
1) the white moves are weaker (if we have ordered them well from previous iterations)
2) the moves can now also be refuted by scores in the range of 41 to 70

Move 5 is refuted by a score of 55.
Perhaps it was not by blacks best move which may have given a score of 5.

This is bad for the move ordering.
So whenever I get a new best move after the first move, I adjust the scores of the previous moves.

I could fx add +25 to the 3 first moves (move 1 must not be better than move 4).
This helps to keep the good move order.

It seems to give my engine an increase in speed of 5%.
An easy way to get an increase in speed.

(I tried briefly to do the same adjustment with the number of nodes, but in vain)

Where do you get the scores for each root move? Scored at the root? Static eval? What?

The number of nodes is useful for other things as well. If the 2nd move is within "range" of the first move, one can avoid searching the second move with just one processor (letting the others take the third, etc, classic YBW) since it appears it is "trying" to become best since the node count is climbing, iteration by iteration. Etc.

As I wrote in an earlier post here ( http://www.talkchess.com/forum/viewtop ... 5&t=46605 )

My engine is probably not written the standard way. I started it 18 years ago based on what I had read and my intuition and logic.
When a white move at the root is refused by a given black move, I store the score for the move that gave the cuf-off.

[bob]

I have tried lots of things. using the node-count for each ply-1 move has always tested better for me. The reason is somewhat subtle, but it has been used since the 1980's and Cray Blitz for me...

The larger the ply-1 sub-tree, the harder that tree is to search, which can in many cases mean it is getting better and better. I have a flag I can use to dump the ply-1 move list and node counts after each search.

..............

If you have questions, fire away. I can't guarantee you it is best for all programs. It is, and has been for years, best for mine, however.

I have tried to use number of nodes instead of scores to order the moves at the root, but with my testpositions it gives almost the same result as my original move ordering by scores.

But when I add my level-adjustment, I have ca. 5% speed-up.

What is this level-adjustment?

Take this example with these scores for white:

Code: Select all

1, - score +40 new best move 
2, - score +30 
3, - score +10 
4, - score +70 new best move 
5, - score +55 
6, - score +30 
7, - score +40 
8, - score +45 
9, - score +50 

When I get a new-best-move at move 4, it is 70-40=30 better in score than move 1.

Now we have a new situation:
It is much easier for black (more possible moves) to refute whites next moves because
1) the white moves are weaker (if we have ordered them well from previous iterations)
2) the moves can now also be refuted by scores in the range of 41 to 70

Move 5 is refuted by a score of 55.
Perhaps it was not by blacks best move which may have given a score of 5.

This is bad for the move ordering.
So whenever I get a new best move after the first move, I adjust the scores of the previous moves.

I could fx add +25 to the 3 first moves (move 1 must not be better than move 4).
This helps to keep the good move order.

It seems to give my engine an increase in speed of 5%.
An easy way to get an increase in speed.

(I tried briefly to do the same adjustment with the number of nodes, but in vain)

Where do you get the scores for each root move? Scored at the root? Static eval? What?

The number of nodes is useful for other things as well. If the 2nd move is within "range" of the first move, one can avoid searching the second move with just one processor (letting the others take the third, etc, classic YBW) since it appears it is "trying" to become best since the node count is climbing, iteration by iteration. Etc.

As I wrote in an earlier post here ( http://www.talkchess.com/forum/viewtop ... 5&t=46605 )

My engine is probably not written the standard way. I started it 18 years ago based on what I had read and my intuition and logic.
When a white move at the root is refused by a given black move, I store the score for the move that gave the cuf-off.

So you are not doing alpha/beta at all???