MVV/LVA

[lucasart]

My move sorting is basically as follows:
* captures (incl. promotions) are sorted by SEE
* quiet moves are order by history score, and fitted into [-Pawn,+Pawn] interval

But everyone says MVV/LVA is better than SEE for sorting captures. So let's say I order captures by MVV/LVA. The problem is, how do I compare captures MVV/LVA scores to quiet moves history scores ?

[mar]

My move sorting is basically as follows:
* captures (incl. promotions) are sorted by SEE
* quiet moves are order by history score, and fitted into [-Pawn,+Pawn] interval

But everyone says MVV/LVA is better than SEE for sorting captures. So let's say I order captures by MVV/LVA. The problem is, how do I compare captures MVV/LVA scores to quiet moves history scores ?

Here is what I do:

I sort (*) all captures (by MVV/LVA) above the noncaptures. Then whenever I want to get a new move from the generator and it's a capture I do SEE (only sign matters => <0 => bad capture, >= => good capture).
If the capture is bad I add the move to bad captures list (*you can simply add them to the end of your list because i don't use sorting, just pick the best move and adjust; so the sorting is incremental). Bad captures are examined last. When I'm doing qsearch i don't add them to any list and simply throw them away. Hope it helps.

[Don]

My move sorting is basically as follows:
* captures (incl. promotions) are sorted by SEE
* quiet moves are order by history score, and fitted into [-Pawn,+Pawn] interval

But everyone says MVV/LVA is better than SEE for sorting captures. So let's say I order captures by MVV/LVA. The problem is, how do I compare captures MVV/LVA scores to quiet moves history scores ?

For sorting consider all non-losing captures as better than quiet moves (except for the hash table move.) Some programs even consider losing captures as better than most quiet moves. I think most typical is this:

1. Hash table
2. non-losing MVV/LVA
3. 2 killer moves
4. losing captures in MVV/LVA order
5. quiet moves in history order

I don't fully understand what you are trying to do. Are you trying to mix in captures with high scoring history moves?

[Kempelen]

My move sorting is basically as follows:
* captures (incl. promotions) are sorted by SEE
* quiet moves are order by history score, and fitted into [-Pawn,+Pawn] interval

But everyone says MVV/LVA is better than SEE for sorting captures. So let's say I order captures by MVV/LVA. The problem is, how do I compare captures MVV/LVA scores to quiet moves history scores ?

Normal is to have 1.Winning captures, 2.quiet moves 3.bad captures. (basically, although you must order fist hash move or pv move if have it, killers an so on).

Just use a const to get sorted correctly:

#define WIN_CAP 1000
#define NORMAL_MOV 100
#define BAD_CAP 10

and when computing sorting value, add the see score to win_cap (if positive) or bad_cap (if negative). Add history to normal_mov.
Of course, you must assure you dont overpass limits (99, 999)

[lucasart]

My move sorting is basically as follows:
* captures (incl. promotions) are sorted by SEE
* quiet moves are order by history score, and fitted into [-Pawn,+Pawn] interval

But everyone says MVV/LVA is better than SEE for sorting captures. So let's say I order captures by MVV/LVA. The problem is, how do I compare captures MVV/LVA scores to quiet moves history scores ?

For sorting consider all non-losing captures as better than quiet moves (except for the hash table move.) Some programs even consider losing captures as better than most quiet moves. I think most typical is this:

1. Hash table
2. non-losing MVV/LVA
3. 2 killer moves
4. losing captures in MVV/LVA order
5. quiet moves in history order

I don't fully understand what you are trying to do. Are you trying to mix in captures with high scoring history moves?

"loosing" (by MVV/LVA) captures before quiet moves ?

I never thought about that, but yes, it does solve my problem. I'll do some testing

Thank you

[Don]

My move sorting is basically as follows:
* captures (incl. promotions) are sorted by SEE
* quiet moves are order by history score, and fitted into [-Pawn,+Pawn] interval

But everyone says MVV/LVA is better than SEE for sorting captures. So let's say I order captures by MVV/LVA. The problem is, how do I compare captures MVV/LVA scores to quiet moves history scores ?

For sorting consider all non-losing captures as better than quiet moves (except for the hash table move.) Some programs even consider losing captures as better than most quiet moves. I think most typical is this:

1. Hash table
2. non-losing MVV/LVA
3. 2 killer moves
4. losing captures in MVV/LVA order
5. quiet moves in history order

I don't fully understand what you are trying to do. Are you trying to mix in captures with high scoring history moves?

"loosing" (by MVV/LVA) captures before quiet moves ?

It's almost universal that you should at least try the killer moves (which are quiet) before the losing captures.

But the concept is that even bad captures produce tiny trees and resist accurate analysis (even with SEE) so it does not hurt to place them before most quiet moves.

I never thought about that, but yes, it does solve my problem. I'll do some testing

Thank you

[jdart]

Many engines do an initial sort by MVV/LVA and then when the move is about to be searched, do a see() if MVV/LVA is <=0, and if SEE is < 0, put the move at the end of the move list. The theory is that if you get cutoff before the move is selected, you never have to do the see() call.

(This is outside of the qsearch - in the qsearch, you also do the SEE test only when the move is selected, but moves that have negative SEE or fail the futility test are pruned).

This both gives you better ordering and increases speed.

[tpetzke]

Whatever you do only affects a small subset of nodes. Last time I measured the 1st move searched produced a cutoff in 95.3% of all cases where a move was able to cause a cutoff. And in 2.5% it was the 2nd move.

So for me it works exactly in that order given by Don. I search losing captures after killers and equal captures but before the other moves. If most of the promising moves tried before did not cause a cutoff, chances are high I don't get a cutoff at all and so I try the moves first that have a smaller tree. And in a case where one piece is lost anyway (e.g. in a fork) it is usually better to let it perform a capture than to do something quiet.

I don't do history based ordering at all, I simply order the quiet moves by moving piece type and moving direction. History scores were not able to improve the move ordering when measured but slowed down the search a bit.

Thomas...

PS.: Here was my test result, I guess it looks in most of the engines very similar

Code: Select all

Total recorded cut offs:         251,607,401
CutOff with 1st move:                 95.368%
CutOff with 2nd move:                  2.519%
Avg. move no that causes cut off:      1.174
CutOff in remaining moves*:        8,643,777   (3.43%)
CutOff move no in remaining moves:     3.022
Cutoff with a losing capture:      1,558,615   (0.62%)


*after hash, captures and killers

[Don]

Whatever you do only affects a small subset of nodes. Last time I measured the 1st move searched produced a cutoff in 95.3% of all cases where a move was able to cause a cutoff. And in 2.5% it was the 2nd move.

So for me it works exactly in that order given by Don.

Which is actually NOT the way Komodo does it, but I believe most good program do it this way.

I search losing captures after killers and equal captures but before the other moves. If most of the promising moves tried before did not cause a cutoff, chances are high I don't get a cutoff at all and so I try the moves first that have a smaller tree. And in a case where one piece is lost anyway (e.g. in a fork) it is usually better to let it perform a capture than to do something quiet.

I don't do history based ordering at all, I simply order the quiet moves by moving piece type and moving direction. History scores were not able to improve the move ordering when measured but slowed down the search a bit.

Thomas...

PS.: Here was my test result, I guess it looks in most of the engines very similar

Code: Select all

Total recorded cut offs:         251,607,401
CutOff with 1st move:                 95.368%
CutOff with 2nd move:                  2.519%
Avg. move no that causes cut off:      1.174
CutOff in remaining moves*:        8,643,777   (3.43%)
CutOff move no in remaining moves:     3.022
Cutoff with a losing capture:      1,558,615   (0.62%)


*after hash, captures and killers