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?
Move ordering - what's best?
Moderators: hgm, Rebel, chrisw
-
- Posts: 12568
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move ordering - what's best?
You might examine how Stockfish does it in movepick.cpp
Stockfish has the following categories (not sorted by rank here):
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.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 1568
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Move ordering - what's best?
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.
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.
-
- Posts: 266
- Joined: Fri Jul 10, 2015 9:23 pm
- Location: Russia
-
- Posts: 327
- Joined: Sat Mar 27, 2010 7:15 pm
Re: Move ordering - what's best?
Thanks, maybe I'll try a second killer as the next step.Joost Buijs wrote: ↑Wed Feb 20, 2019 2: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.
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
-
- Posts: 1568
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Move ordering - what's best?
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.silentshark wrote: ↑Wed Feb 20, 2019 6: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
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.
-
- Posts: 327
- Joined: Sat Mar 27, 2010 7:15 pm
Re: Move ordering - what's best?
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:Joost Buijs wrote: ↑Wed Feb 20, 2019 7:36 pmMost 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.silentshark wrote: ↑Wed Feb 20, 2019 6: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
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.
1. Hash move
2. Winning and equal SEE captures
3. Killer
4. Quiet moves
5. Losing SEE captures
-
- Posts: 1568
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Move ordering - what's best?
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.
-
- Posts: 7221
- Joined: Mon May 27, 2013 10:31 am
Re: Move ordering - what's best?
What I remember is that doing SEE near the leaves is quite expensive and near the root it doesn't help.Joost Buijs wrote: ↑Thu Feb 21, 2019 7: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.
So finally I removed SEE. Maybe bad choice.
-
- Posts: 1568
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Move ordering - what's best?
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.Henk wrote: ↑Thu Feb 21, 2019 9:35 amWhat I remember is that doing SEE near the leaves is quite expensive and near the root it doesn't help.Joost Buijs wrote: ↑Thu Feb 21, 2019 7: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.
So finally I removed SEE. Maybe bad choice.
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.