Move ordering - what's best?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
silentshark
Posts: 198
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Move ordering - what's best?

Post by silentshark » Tue Feb 19, 2019 9:14 pm

Hello folks,

For a long time (like 20 years!), my program has used the following to order moves in the main bit of the search:

1. Hash move
2. All captures (sorted by MVV/LVA)
3. One Killer move
4. All other quiet moves, ordered by history heuristic

What should I focus on next to improve move ordering? More than one killer? Losing captures to be searched later?

Dann Corbit
Posts: 9320
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Move ordering - what's best?

Post by Dann Corbit » Tue Feb 19, 2019 9:23 pm

You might examine how Stockfish does it in movepick.cpp

Stockfish has the following categories (not sorted by rank here):

Code: Select all

BAD_CAPTURE:
CAPTURE_INIT:
EVASION:
EVASION_INIT:
EVASION_TT:
GOOD_CAPTURE:
MAIN_TT:
PROBCUT:
PROBCUT_INIT:
PROBCUT_TT:
QCAPTURE:
QCAPTURE_INIT:
QCHECK:
QCHECK_INIT:
QSEARCH_TT:
QUIET:
QUIET_INIT:
REFUTATION:
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Joost Buijs
Posts: 806
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Move ordering - what's best?

Post by Joost Buijs » Wed Feb 20, 2019 1:02 pm

In my current program I do:

1. Hash move
2. Winning captures (sorted by SEE)
3. 2 Killers
4. Moves with positive history (sorted by history)
5. Losing captures (sorted by SEE)
6. Moves with negative history (sorted by history)

Whether this can be improved? I really don't know. Maybe the losing captures have to go last.

My program has a high branching factor compared to others. Possibly I prune less because my search is still very ancient. The best move order is what gives you the highest rating, personally I never tried to optimize it any further. I still have plans to improve my search, but after 43 years of doing computer-chess I can't set myself to it.

User avatar
Kotlov
Posts: 197
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

Re: Move ordering - what's best?

Post by Kotlov » Wed Feb 20, 2019 4:27 pm

Joost Buijs wrote:
Wed Feb 20, 2019 1:02 pm
6. Moves with negative history (sorted by history)
It really works?
Eugene Kotlov
Hedgehog 2.0 64-bit coming soon...

User avatar
silentshark
Posts: 198
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: Move ordering - what's best?

Post by silentshark » Wed Feb 20, 2019 5:44 pm

Joost Buijs wrote:
Wed Feb 20, 2019 1:02 pm
In my current program I do:

1. Hash move
2. Winning captures (sorted by SEE)
3. 2 Killers
4. Moves with positive history (sorted by history)
5. Losing captures (sorted by SEE)
6. Moves with negative history (sorted by history)

Whether this can be improved? I really don't know. Maybe the losing captures have to go last.

My program has a high branching factor compared to others. Possibly I prune less because my search is still very ancient. The best move order is what gives you the highest rating, personally I never tried to optimize it any further. I still have plans to improve my search, but after 43 years of doing computer-chess I can't set myself to it.
Thanks, maybe I'll try a second killer as the next step.

How important is it to downgrade bad captures? I just use mvv/lva for sorting, but I could use SEE, to get visbility of the bad captures

Joost Buijs
Posts: 806
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Move ordering - what's best?

Post by Joost Buijs » Wed Feb 20, 2019 6:36 pm

silentshark wrote:
Wed Feb 20, 2019 5:44 pm
How important is it to downgrade bad captures? I just use mvv/lva for sorting, but I could use SEE, to get visbility of the bad captures
Most captures are bad, like major pieces grabbing protected pawns etc, so downgrading them can help to get your branching factor somewhat lower. I would at least place them behind the killers.

In normal search I use SEE to order captures and in quiescence I use mvv/lva. I also have a version of my engine where I use SEE in quiescence to order captures, somehow there is not much performance difference between both versions. The SEE version is somewhat slower, but the difference is so small that I assume it is not very relevant.

User avatar
silentshark
Posts: 198
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: Move ordering - what's best?

Post by silentshark » Wed Feb 20, 2019 7:26 pm

Joost Buijs wrote:
Wed Feb 20, 2019 6:36 pm
silentshark wrote:
Wed Feb 20, 2019 5:44 pm
How important is it to downgrade bad captures? I just use mvv/lva for sorting, but I could use SEE, to get visbility of the bad captures
Most captures are bad, like major pieces grabbing protected pawns etc, so downgrading them can help to get your branching factor somewhat lower. I would at least place them behind the killers.

In normal search I use SEE to order captures and in quiescence I use mvv/lva. I also have a version of my engine where I use SEE in quiescence to order captures, somehow there is not much performance difference between both versions. The SEE version is somewhat slower, but the difference is so small that I assume it is not very relevant.
Thanks. Ok, going to try doing some better ordering (I'm just going to try this near the root, if I do everywhere it slows stuff down too much). This is what I'm going to try:

1. Hash move
2. Winning and equal SEE captures
3. Killer
4. Quiet moves
5. Losing SEE captures

Joost Buijs
Posts: 806
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Move ordering - what's best?

Post by Joost Buijs » Thu Feb 21, 2019 6:32 am

I don't think it will help much when you only order moves at the root. In my case it is entirely different, at the root I only shift the best move up after each iteration, for the remaining part of the tree I order moves in the way I told.

Henk
Posts: 5491
Joined: Mon May 27, 2013 8:31 am

Re: Move ordering - what's best?

Post by Henk » Thu Feb 21, 2019 8:35 am

Joost Buijs wrote:
Thu Feb 21, 2019 6:32 am
I don't think it will help much when you only order moves at the root. In my case it is entirely different, at the root I only shift the best move up after each iteration, for the remaining part of the tree I order moves in the way I told.
What I remember is that doing SEE near the leaves is quite expensive and near the root it doesn't help.
So finally I removed SEE. Maybe bad choice.

Joost Buijs
Posts: 806
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Move ordering - what's best?

Post by Joost Buijs » Thu Feb 21, 2019 10:52 am

Henk wrote:
Thu Feb 21, 2019 8:35 am
Joost Buijs wrote:
Thu Feb 21, 2019 6:32 am
I don't think it will help much when you only order moves at the root. In my case it is entirely different, at the root I only shift the best move up after each iteration, for the remaining part of the tree I order moves in the way I told.
What I remember is that doing SEE near the leaves is quite expensive and near the root it doesn't help.
So finally I removed SEE. Maybe bad choice.
It depends upon how efficient your SEE function is. When I use SEE to sort captures in quiescence it gives a speed difference of just a few percent compared to MVV-LVA (on the engine overall), and maybe the captures are sorted better when using SEE.

When you use MVV-LVA to sort captures in quiescence you still have to call SEE for each capture you do (at least if you want to skip captures with negative SEE), that is probably why it doesn't make much difference. When the victim has an equal or higher value than the attacker or when the victim is undefended you can skip SEE, but in my engine this happens with only a small fraction of all captures.

Post Reply