Move Ordering?

[PK]

One thing that helped in Rodent, was null move threat evasion. That is, more often than not, null move is refuted by a capture. Now if we record a square on which this capture takes place, we may promote escapes from that square a bit higher (I do it simply by adding constant to history score and then multiplying it by a constant - the move is still sorted as "ordinary", but closer to the top).

And speaking of "the wall" You hit at certain depth - another cause of a slowdown may be saturation (or, in extreme cases, overflow) of history counters. If this is the case, dividing them by 2 once one of them becomes too big would help.

[bob]

Hello all,

I have been working on a chess engine as a sort of hobby of mine for a while now and now that I think I have finally worked out most of the major bugs I have been wanting to improve its strength.

I noticed that the engine seemed to be hitting a wall so to speak at around depth 12 where the branching factor increased from a little over 2 to 5 (sometimes even 10 or more!).

I chalked this up to poor move ordering so I decided to improve this drastically.

I changed my previous scheme to one closer to one that goes as such,
TT move
Winning captures based off see (including Queen Promotions)
Normal queen promotions
Neutral captures based off see
Killer Moves
Castling
Under promotions
Quiet moves based off of History Table using Depth * Depth
Bad captures (see < 0)

I noticed that there was a slight improvement to the branching factor but now the same thing occurs as before just at about depth 13. However there was still improvement so quantify this data I added some code that counted the number of beta cutoff that were occurring during the search and it counted move at which this cut off occurred at. I then ran my engine through the arasan15 test suite at 10 seconds per move.
Before changing my move ordering scheme I got:

0.133717 (Ratio of cutoffs that occurred at move >1 / cutoffs at move 1)

Highest: 69 Average: 3.9772 Overall Avg: 1.35115 (Highest cutoff, Average cut off for move > 1, Average cutoff)

Afterwards:
0.046523
Highest: 64 Average: 6.41822 Overall Avg: 1.24087

I also then saw what these non first move cutoffs were and what was the average move at which they occurred at.
GOODCAPTURES: 0.249906 KILLERS: 0.24404 QUIETMOVES: 0.468246 CASTLES: 0.0017051 PROMOTES: 0.0210633 BADCAPTURES: 0.0131616 EPCAPS 0.00186287 PROMOTESCAPTURES: 1.46763e-005
GOODCAPTURES: 7.48367 KILLERS: 2.66608 QUIETMOVES: 7.25414 CASTLES: 2.40897 PROMOTES: 2.18646 BADCAPTURES: 28.9154 EPCAPS 14.168 PROMOTESCAPTURES: 6.375

As you can see if there is a beta cutoff the first move is now more likely to cause that cut off and on average the engine has to work 8% less to get this cutoff. However, the average moves when this cut off does not occur on the first move has gone up over 50%. I was wondering if results like these were typical in other engines and also if there is a better way to quantify move ordering other than this method.

Thank you for your time,

Thomas

One thing that can cause a "wall" is a transposition table problem. Searching the TT move first is a big win. IF you do it. But if your replacement policy is ineffective, you can lose that TT move and that does hurt. Of course, losing the cutoffs will also hurt. Another "wall" could be history. Do you do something to avoid all values climbing so high that there is no real difference between them (aging or whatever)???

[cetormenter]

Hi Thomas,

welcome to the community.

I've done a fairly comprehensive analyses about the move ordering in my engine a while back and posted the results here.

http://macechess.blogspot.de/2011/08/ch ... stics.html

So in average I get a first move cutoff in 95% of the positions. If I get to the remaining move list the average move number that caused a cutoff was about 3.

BTW.: I don't use a history table and I order losing captures before the non capture moves for three reasons.

1. I generate captures before quiet moves, so if I get a cutoff with a losing capture I save the move generation of quiet moves.
2. SEE declared losing captures are not always really losing, because a capture sequence that involves more than 1 square is not always predicted correctly.
3. If the capture is really bad it is refuted quickly so not much effort is wasted.

Thomas...

I tried ordering Bad Captures first but this proved to be worse in my testing. I generate all moves at once so your method is not really an option for me.

Hi Thomas, welcome here !

Your move ordering seems already good and I would say even more complex than what is normally required (even in the strongest engines).

One little increase you can have ordering the captures by MVV/LVA (most valuable victim/Least Valuable attacker) and then use SEE only to move the bad captures to the tail, but without changing the captures' s order.

Regarding testing method, unfortunately I have to say that the only reliable way is to play real games (and a lot of them) sorry but until today nobody found a better system that proves reliable, and a lot of people have looked at the problem because testing requires a lot of time.

I was talking more about only looking at nodes where beta is returned. Obviously the more data you collect (usually from playing a large number of games) is better than what I am doing but this seems sufficient.

It seems everyone is doing that. But it's never worked for me. I did quite some testing, and concluded that (as far as DiscoCheck is concerned): MVV/LVA works best for QS captures, but SEE works best for search captures.

Another thing that I discovered in testing, but seems counter-intuitive. Underpromotions are useless in QS (that's obvious), but actually useful in the search.

Anyway, your mileage may vary. But you should try MVV/LVA for QS captures to begin with, and see if it works (it should). Whether it works for the search may vary from one engine to the other.

I tried ordering by MVV/LVA in QS but this did not seem to improve matters. In my original test I only looked at moves in the AB part of the search. Now looking also in Qsearch with my normal move ordering I got,

0.0862112
Highest: 64 Average: 3.88894 Overall Avg: 1.24906

Using MVV/LVA,

0.0683254
Highest: 68 Average: 14.8053 Overall Avg: 1.94325.

It more often cuts off on the first move but now it takes almost 4 times as long on average to get the move when it isn't the first move.

Starting with best move from previous iteration (tt) is obvious. You can try to order the rest of root moves by number of nodes searched, the higher the better.


Sounds pretty good already. Does your engine have a name?
Do you plan to release it? It's always fun to see how it does against other engines and a good motivation to improve further.

Hmm I will have to try that out. It might fix some of the stupid moves that the engine makes when its under time pressure during the endgame.

Its called Nirvana Chess. It played on the FICS for a little while before I took it down because Arena randomly decided that it only wanted to play one game at a time and I couldn't find another free GUI that I knew how to set up. I am not sure if I plan on releasing it. Maybe some time later after I have groomed it some more. Right now its just a personal project.

Based on what you wrote I suspect the BF problem is not related to move ordering or else there is a bug in it. One quick thing to check - Are you absolutely sure you are putting the best move first at the root?

You should not suddenly get an increase in BF at some depth. Even if you have bad move ordering this should not happen. It could happen if something about the way you do more ordering changes however. 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.

Yes I have checked that I am ordering the best move first. I have looked at the pv and the values the engine is returning and it seems to be all in order.

I do not change how move are ordered based on depth.

One possible explanation for a sudden increase in BF could be a problem with transposition tables. If your tables get filled up and you are using a bad replacement scheme, you could easily see this type of thing happening. Try changing the size of the TT dramatically up or down and see if the transition happens at a different point then. Also, monitor how full your TT is, and see if the slowdown coincides with the TT getting full.

Perhaps it has nothing to do with this, but it is worth checking.

I use the same replacement scheme that the chess programming wiki does. I am sure there are better ones than this but from what I have seen most engines use something very similar to it.

One thing that helped in Rodent, was null move threat evasion. That is, more often than not, null move is refuted by a capture. Now if we record a square on which this capture takes place, we may promote escapes from that square a bit higher (I do it simply by adding constant to history score and then multiplying it by a constant - the move is still sorted as "ordinary", but closer to the top).

And speaking of "the wall" You hit at certain depth - another cause of a slowdown may be saturation (or, in extreme cases, overflow) of history counters. If this is the case, dividing them by 2 once one of them becomes too big would help.

PostPosted: Fri Dec 28, 2012 3:55 pm Post subject: Re: Move Ordering?
cetormenter wrote:
Hello all,

I have been working on a chess engine as a sort of hobby of mine for a while now and now that I think I have finally worked out most of the major bugs I have been wanting to improve its strength.

I noticed that the engine seemed to be hitting a wall so to speak at around depth 12 where the branching factor increased from a little over 2 to 5 (sometimes even 10 or more!).

I chalked this up to poor move ordering so I decided to improve this drastically.

I changed my previous scheme to one closer to one that goes as such,
TT move
Winning captures based off see (including Queen Promotions)
Normal queen promotions
Neutral captures based off see
Killer Moves
Castling
Under promotions
Quiet moves based off of History Table using Depth * Depth
Bad captures (see < 0)

I noticed that there was a slight improvement to the branching factor but now the same thing occurs as before just at about depth 13. However there was still improvement so quantify this data I added some code that counted the number of beta cutoff that were occurring during the search and it counted move at which this cut off occurred at. I then ran my engine through the arasan15 test suite at 10 seconds per move.
Before changing my move ordering scheme I got:

0.133717 (Ratio of cutoffs that occurred at move >1 / cutoffs at move 1)

Highest: 69 Average: 3.9772 Overall Avg: 1.35115 (Highest cutoff, Average cut off for move > 1, Average cutoff)

Afterwards:
0.046523
Highest: 64 Average: 6.41822 Overall Avg: 1.24087

I also then saw what these non first move cutoffs were and what was the average move at which they occurred at.
GOODCAPTURES: 0.249906 KILLERS: 0.24404 QUIETMOVES: 0.468246 CASTLES: 0.0017051 PROMOTES: 0.0210633 BADCAPTURES: 0.0131616 EPCAPS 0.00186287 PROMOTESCAPTURES: 1.46763e-005
GOODCAPTURES: 7.48367 KILLERS: 2.66608 QUIETMOVES: 7.25414 CASTLES: 2.40897 PROMOTES: 2.18646 BADCAPTURES: 28.9154 EPCAPS 14.168 PROMOTESCAPTURES: 6.375

As you can see if there is a beta cutoff the first move is now more likely to cause that cut off and on average the engine has to work 8% less to get this cutoff. However, the average moves when this cut off does not occur on the first move has gone up over 50%. I was wondering if results like these were typical in other engines and also if there is a better way to quantify move ordering other than this method.

Thank you for your time,

Thomas


One thing that can cause a "wall" is a transposition table problem. Searching the TT move first is a big win. IF you do it. But if your replacement policy is ineffective, you can lose that TT move and that does hurt. Of course, losing the cutoffs will also hurt. Another "wall" could be history. Do you do something to avoid all values climbing so high that there is no real difference between them (aging or whatever)???

I suspected that this was the issue that was occurring so I had the engine print out its highest history table value. I noticed that value was getting very close to the value at which I scored things like killer moves and captures. I then fooled around with not incrementing the history table if depth < 3. This made the history table not get nearly as close to the scores of captures but it did not fix the wall issue. Where exactly should this "aging" occur? I already age the history table at the start of every new search. I would think that the only place that this would be cost efficient would be at the root but this would not solve the issue because entries could grow too large in the middle of an iteration.

[lucasart]

It seems everyone is doing that. But it's never worked for me. I did quite some testing, and concluded that (as far as DiscoCheck is concerned): MVV/LVA works best for QS captures, but SEE works best for search captures.

Another thing that I discovered in testing, but seems counter-intuitive. Underpromotions are useless in QS (that's obvious), but actually useful in the search.

Anyway, your mileage may vary. But you should try MVV/LVA for QS captures to begin with, and see if it works (it should). Whether it works for the search may vary from one engine to the other.

I tried ordering by MVV/LVA in QS but this did not seem to improve matters. In my original test I only looked at moves in the AB part of the search. Now looking also in Qsearch with my normal move ordering I got,

0.0862112
Highest: 64 Average: 3.88894 Overall Avg: 1.24906

Using MVV/LVA,

0.0683254
Highest: 68 Average: 14.8053 Overall Avg: 1.94325.

It more often cuts off on the first move but now it takes almost 4 times as long on average to get the move when it isn't the first move.

Try to compare SEE and MVV/LVA (only for captures in QS), by using QS node count as a comparison. Of course you'll need to search a lot of "random" positions, in order to make meaningful statistics.

MVV/LVA is not as good as SEE in giving you the best capture. But in the QS< you typically don't use PVS, so it's not as important to get the best move first as it is in the search. And if MVV/LVA doesn't give you the best move first, it does often enough (when pieces are not defended at least), and when it doesn't (eg. QxN but N is defended by P) then you've still managed to raise the best score by searching a subtree that has a lower branching factor (eg. N is gone, and Q is gone after PxQ which is first in MVV/LVA).

[PK]

Rodent does it as follows: when reading history score for move ordering purposes, it checks if it's not too high:

Code: Select all

int sHistory::GetMoveHistoryValue(int pc, int sq_from, int sq_to) 
{
    int val = history[pc][sq_to];
	if ( val > &#40;1 << 15&#41; ) History.Reduce&#40;);
	return val;
&#125;

and the function to reduce scores:

Code: Select all

void sHistory::Reduce(void)
{
  int i, j;

  for &#40;i = 0; i < 12; i++)
    for &#40;j = 0; j < 64; j++)
      history&#91;i&#93;&#91;j&#93; /= 2;
&#125;

as for reducing between searches, it zeroes the table upon obtaining new game commands and divides it by 8 or some other constant when searching new move of the same game.

[cetormenter]

Rodent does it as follows: when reading history score for move ordering purposes, it checks if it's not too high:

Code: Select all

int sHistory::GetMoveHistoryValue(int pc, int sq_from, int sq_to) 
{
    int val = history[pc][sq_to];
	if ( val > &#40;1 << 15&#41; ) History.Reduce&#40;);
	return val;
&#125;

and the function to reduce scores:

Code: Select all

void sHistory::Reduce(void)
{
  int i, j;

  for &#40;i = 0; i < 12; i++)
    for &#40;j = 0; j < 64; j++)
      history&#91;i&#93;&#91;j&#93; /= 2;
&#125;

as for reducing between searches, it zeroes the table upon obtaining new game commands and divides it by 8 or some other constant when searching new move of the same game.

This seems to have worked quite well. I thought that something like this would have caused a major slow down but there seems to be no change at all. The branching factor now stays pretty consistently at around 2ish until the hash becomes full. Thank you very much!

P.S. If anybody is legitimately interested in the engine just send me a message and I'll send you a copy of the binary. Just don't expect too much out of it.

[hgm]

One thing that helped in Rodent, was null move threat evasion. That is, more often than not, null move is refuted by a capture. Now if we record a square on which this capture takes place, we may promote escapes from that square a bit higher (I do it simply by adding constant to history score and then multiplying it by a constant - the move is still sorted as "ordinary", but closer to the top).

In Joker I even singled out one such evasion (to a SEE-wise safe square) to sort with the captures. This helped. And I think it is a logical thing to do: if the previous opponent move inadvertantly attacked your Queen with a Knight, it should obviously have a better chance for success to save the Queen than to capture a hanging Rook. So I would value such moves as if the captured Q-N.

[JBNielsen]

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?

[cetormenter]

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)
{...}

[JBNielsen]

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?

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.

If that is normally not done, it might be difficult to answer my question.

But what is the standard best way to order the moves at the root if you refer to my fictive example?