Capture ordering

[Casey]

I am considering two ways to implement capture ordering:

Method 1:
- Moves which less value pieces capture more or equal value ones
- Moves of positive gains, proved by SEE

Method 2:
- Moves of positive gains, proved by SEE

The advantage of method 1 is that if cut off occurs, we can save some calls of SEE. However, the method 2 seems to give us a better move ordering even SEE is called more than one.

Other methods and/or comments are highly appreciated.

[Dann Corbit]

I am considering two ways to implement capture ordering:

Method 1:
- Moves which less value pieces capture more or equal value ones
- Moves of positive gains, proved by SEE

Method 2:
- Moves of positive gains, proved by SEE

The advantage of method 1 is that if cut off occurs, we can save some calls of SEE. However, the method 2 seems to give us a better move ordering even SEE is called more than one.

Other methods and/or comments are highly appreciated.

1. MVV/LVA (most valuable victim, least valuable agressor) is the most common.
2. MVV/MVA (most valuable victim, most valuable agressor) is a surprising stategy that I have heard did well.
3. BMO (best move only, but do not search any non-pv nodes, so if they are not in the hash table, they will need evaluated to choose) It's basically a branching factor of 1 search forward. You have to decide on a stopping decision, because 'no more captures' or 'all subsequent captures are bad' does not apply here.
4. Rely on quiescent search.
5. Rely on hash, history and IID (and eval when the chips are down)

I guess that #1 is both easiest and best most of the time.
#4 is too expensive
#5 is probably of poor quality
#3 is hard to tune
#2 is counter-intuitive, but I know of one study that said it worked great.

[bob]

I am considering two ways to implement capture ordering:

Method 1:
- Moves which less value pieces capture more or equal value ones
- Moves of positive gains, proved by SEE

Method 2:
- Moves of positive gains, proved by SEE

The advantage of method 1 is that if cut off occurs, we can save some calls of SEE. However, the method 2 seems to give us a better move ordering even SEE is called more than one.

Other methods and/or comments are highly appreciated.

Crafty has always used #1 as you described. SEE is not that expensive, but it is not tree, and trying moves like PxR is an intuitive good move. Whether it wins the rook outright or just wins a rook for a pawn doesn't matter much.

The point to remember is that with alpha/beta, you don't need to search the _best_ move first. You just need to search one that will cause a cutoff first... That's a less rigorous requirement that can be used to save computation cycles...

[Michael Sherwin]

I am considering two ways to implement capture ordering:

Method 1:
- Moves which less value pieces capture more or equal value ones
- Moves of positive gains, proved by SEE

Method 2:
- Moves of positive gains, proved by SEE

The advantage of method 1 is that if cut off occurs, we can save some calls of SEE. However, the method 2 seems to give us a better move ordering even SEE is called more than one.

Other methods and/or comments are highly appreciated.

1. MVV/LVA (most valuable victim, least valuable agressor) is the most common.
2. MVV/MVA (most valuable victim, most valuable agressor) is a surprising stategy that I have heard did well.
3. BMO (best move only, but do not search any non-pv nodes, so if they are not in the hash table, they will need evaluated to choose) It's basically a branching factor of 1 search forward. You have to decide on a stopping decision, because 'no more captures' or 'all subsequent captures are bad' does not apply here.
4. Rely on quiescent search.
5. Rely on hash, history and IID (and eval when the chips are down)

I guess that #1 is both easiest and best most of the time.
#4 is too expensive
#5 is probably of poor quality
#3 is hard to tune
#2 is counter-intuitive, but I know of one study that said it worked great.

You left out, 'poor blind man's SEE' that I use in RomiChess.

During move generation a bit is set in a u64 variable for every square that is attacked and then stored by ply.

So for move ordering it simply becomes (victim - fs-val + ts-val - (sqrAttacked) ? attacker/2 : 0;

The accuracy sucks, however, it is blazingly fast.

Gerd Isenberg also has mentioned switching to a 'poor mans SEE'!

And (not sure, not sure, not sure) but, the new Glaurung may use something similar.

[cms271828]

I was looking at the crafty code earlier, and noticed it uses bubblesort to order captures(I think)

If you were using MVV/LVA would you order the captures by the value V-A going from largest to smallest, where V is victim, A is the attacker?

Eg V=3(knight) A=1(pawn), V-A=2
And V=9(queen) A=5(rook), V-A=4

So there you would play RxQ before PxN

Thats how I would implement this, is this wrong?

Thanks

[Harald Johnsen]

Count the number of nodes you get for some test positions, count the number of cuts on the first move, etc. Then use the method that gives you the lowest number of nodes, all other things being equal.

Nobody can say if capturing a queen is better than capturing a knight (remember that your engine is spending most of it's time searching positions that have no sense at all).
Intuitively capturing the queen has a bigger impact on the score and on the move count, but that's all, check the number by yourself.

HJ.

[hgm]

Ordering by V-A is not optimal. If you have the choice between NxR and PxN it is in general better to try capture of the Rook first. Because it puts the opponent under more pressure to just recapture the Rook, rather than trying something fanciful. (i.e., fanciful replies will be cut by alpha-beta pruning much more quickly.)

So it is better to use something like 16*V-A as sort key.

In Joker I replace V by SEE value for High x Low captures. And, when there is a pre-existing threat agains one of my pieces, (deduced from the refutation of the null move), I even replace V by SEE value whenever V is lower than the value of the threatened piece.

[cms271828]

Oh I see, using 16V-A gives emphasis on the victims value before the attackers.

Currently, for normal search, not QS..
I do:
hashMove
Captures
Non-Captures

And for QS, just captures.

So is it wise to use the 16V-A sorting on both captures in normal search and QS?

Thanks

[hgm]

In my engines I do not sort differently in QS then in main search.

[pedrox]

You can also include promotions