Move Ordering?

[cetormenter]

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

[mar]

First, welcome to talkchess.

Your move ordering looks reasonable, how do you sort root moves?
High BF can happen.
It also depends on how much you prune/reduce.

Btw. could you tell us more about your engine?
There are many who might be interested.
And as a bonus you get a logo for free.

Martin

[cetormenter]

I sort root moves the same way I do other moves. The move that scored the highest from the previous depth first (tt move) and then the rest based on what I stated earlier. Is this incorrect?

Well the engine isn't really anything to write home about. I just started it because I wanted to learn how to program in C++. The engine uses 12x10 board. It only uses a single core. It uses aspiration windows, null move pruning, delta pruning and late move reductions in order to trim its search tree. The evaluation function is fairly stupid and uses mobility as its main evaluation term. This can lead the engine into arriving at some very stupid positions where it will create a completely locked position where it has control of slightly more squares and the engine is content with keeping it this way. In terms of playing strength, according to various gauntlets I have run it through and the STS test suite the engine is somewhere in the 2200-2300 range.

[tpetzke]

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

[mcostalba]

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.

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.

[lucasart]

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.

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.

[mar]

I sort root moves the same way I do other moves. The move that scored the highest from the previous depth first (tt move) and then the rest based on what I stated earlier. Is this incorrect?

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.

[mar]

It uses aspiration windows, null move pruning, delta pruning and late move reductions in order to trim its search tree.

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.

[Don]

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

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.

[AlvaroBegue]

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.