Move ordering - what's best?

[silentshark]

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]

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:

[Joost Buijs]

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.

[Kotlov]

6. Moves with negative history (sorted by history)

It really works?

[silentshark]

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]

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.

[silentshark]

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]

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]

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]

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.