Move ordering ?

[MahmoudUthman]

1-What is the typical order to use ? on CPW :

1.PV-move of the principal variation from the previous iteration of an iterative deepening framework for the leftmost path, often implicitly done by 2.
2.Hash move from hash tables
3.Winning captures/promotions
4.Equal captures/promotions
5.Killer moves (non capture), often with mate killers first
6.Non-captures sorted by history heuristic and that like
7.Losing captures (* but see below
*) Depending on the implementation, the board representation, whether and where SEE is used, the extension policy (recapture extensions) and other stuff - many programmers favor losing captures before other none-captures - directly behind the killers. They are kind of forced, and one possibly has to deal with all kind of tactical motives and interactions, one may not consider in move ordering. Such as pins, batteries, discovered attacks and overloaded defenders. Otherwise, obviously losing captures are likely refuted cheaply. But if a losing capture fails high for some reason, we have saved the effort to generate, and more importantly to search other non-captures at all.

*Is it better to swap 6 & 7 ?
*should I use SEE instead of MVV-LVA to order moves at PV nodes ? and if so should I use it only for captures or should I use it for all moves ?
*where should "Threat Move" be placed ?
2-how do you score capture-promotions using MVV-LVA , and where should non capture promotions be placed (see 1) ? same for enpassant moves should they be ordered by MVV-LVA or should they be ordered using history , killers ...etc ? and where to place them (see 1)?
3-CPW:

Less common techniques
These techniques are well known theoretically for non-captures, but not all programmers use them:
•Mate Killers
•Countermove Heuristic [5]
•Guard Heuristic
•Last Best Reply
•Butterfly Heuristic [6]
•Threat Move from null move refutations
•Enhanced Transposition Cutoff (ETC)
•Refutation Table

are these techniques good in theory bad in practice , or why does most engines refrain from using most of them ?
4-Is there any techniques that shouldn't be mixed ?
5-should evasions/PVnodes/NonPVNodes/QsearchNodes be ordered differently ?

[jdart]

A lot of this you have to try and measure.

A fairly standard technique in the qsearch is to use MVV-LVA for ordering and then do SEE as moves are actually being used. Moves with negative SEE then are pruned. By doing this you avoid the overhead of calling SEE on all moves and sorting on those values. Many times the first move causes cutoff and then you skip a bunch of SEE calls.

You can do a similar thing in the main search by ordering on MVV-LVA and then if moves have negative SEE, defer them until the end of the move list

--Jon

[Evert]

*Is it better to swap 6 & 7 ?

No. Losing captures are expected to be bad moves. Why would you want to search them ahead of perfectly fine quiet moves?

*should I use SEE instead of MVV-LVA to order moves at PV nodes ? and if so should I use it only for captures or should I use it for all moves ?

You should probably not do anything different at PV nodes. SEE is not free, use it sparingly.

*where should "Threat Move" be placed ?

Depends. Can it be a capture? Then it should be pretty high. Otherwise, somewhere around the killer moves.

2-how do you score capture-promotions using MVV-LVA , and where should non capture promotions be placed (see 1) ?

MVV-LVA works exactly the same as for other types of capture. If the promotion is safe, boost the score by the value of the promoted piece (don't forget to subtract the pawn).

same for enpassant moves should they be ordered by MVV-LVA or should they be ordered using history , killers ...etc ? and where to place them (see 1)?

They're captures. Order them as such.
Not that makes a big difference, they're pretty rare.

Less common techniques
These techniques are well known theoretically for non-captures, but not all programmers use them:
•Mate Killers
•Countermove Heuristic [5]
•Guard Heuristic
•Last Best Reply
•Butterfly Heuristic [6]
•Threat Move from null move refutations
•Enhanced Transposition Cutoff (ETC)
•Refutation Table

are these techniques good in theory bad in practice , or why does most engines refrain from using most of them ?

Mate killers are good for solving mate problems. They do nothing for playing strength in actual games.
Counter move is fairly common, I think.
Threat moves are unreliable, I think, but worth checking.
Enhanced transposition cutoffs trash the CPU cache by jumping around the transposition table. I don't think it hurts, but it doesn't help.

These are all small fish though.

5-should evasions/PVnodes/NonPVNodes/QsearchNodes be ordered differently ?

Possibly.
Move ordering is irrelevant in ALL nodes, for instance. Detecting those up-front with sufficient accuracy is hard though.

[hgm]

Note that winning captures should not have priority over equal captures. It is better to search Q x protected Q (equal capture) before P x B (winning capture). Because when Q x Q is possible, the 'winning' capture P x B might lose you a Queen (PxB, QxQ).

So you order non-losing captures by victim value, and only treat the losing captures later.

Note that 'losing' captures can gain gain a lot of material.

Conclusions can differ if the capture sorting pays attetion to counter threats, i.e. adds the value of a threatened piece of your own to the victim value when you capture the piece that threatened it, or make the capture with the threatened piece.

[MahmoudUthman]

*Is it better to swap 6 & 7 ?

No. Losing captures are expected to be bad moves. Why would you want to search them ahead of perfectly fine quiet moves?

I wouldn't , I was just asking because of the CPW * statement .

MVV-LVA works exactly the same as for other types of capture. If the promotion is safe, boost the score by the value of the promoted piece (don't forget to subtract the pawn).

What do you mean by safe ?

Note that winning captures should not have priority over equal captures. It is better to search Q x protected Q (equal capture) before P x B (winning capture). Because when Q x Q is possible, the 'winning' capture P x B might lose you a Queen (PxB, QxQ).

So you order non-losing captures by victim value, and only treat the losing captures later.

Note that 'losing' captures can gain gain a lot of material.

Conclusions can differ if the capture sorting pays attetion to counter threats, i.e. adds the value of a threatened piece of your own to the victim value when you capture the piece that threatened it, or make the capture with the threatened piece.

In the first statement by wining/equal/losing do you mean according to MVV-LVA ? and in regard to counter threat shouldn't SEE take care of this automatically or is there a lighter/faster algorithm to do that ?

[hgm]

In the first statement by wining/equal/losing do you mean according to MVV-LVA ? and in regard to counter threat shouldn't SEE take care of this automatically or is there a lighter/faster algorithm to do that ?

I mean according to SEE. P x (unprotected) B has SEE = +3, and is thus a 'winning capture'.(unprotected) Q x (protected) Q has SEE = 0, and is an 'equal' capture. Playing P x B, however, will lose you a Queen against a Bishop. Something SEE will not take into account, as it will consider only recaptureson the square of the Bishop (which there aren't). Q x Q will usually win you a Bishop though (except in the rare case that that Bishop happened to be the protector of the Q).

[Evert]

MVV-LVA works exactly the same as for other types of capture. If the promotion is safe, boost the score by the value of the promoted piece (don't forget to subtract the pawn).

What do you mean by safe ?

SEE >= 0

[Evert]

In the first statement by wining/equal/losing do you mean according to MVV-LVA ? and in regard to counter threat shouldn't SEE take care of this automatically or is there a lighter/faster algorithm to do that ?

I mean according to SEE. P x (unprotected) B has SEE = +3, and is thus a 'winning capture'.(unprotected) Q x (protected) Q has SEE = 0, and is an 'equal' capture. Playing P x B, however, will lose you a Queen against a Bishop. Something SEE will not take into account, as it will consider only recaptureson the square of the Bishop (which there aren't). Q x Q will usually win you a Bishop though (except in the rare case that that Bishop happened to be the protector of the Q).

It's a fair point. I think I mainly use SEE for pruning decisions close to the leaves, but I should take another look at move ordering to see how I handle these cases. I don't think I do anything special, so I may be mis-handling them.

[hgm]

Well, this is usually taken care of by the rule that you primarily order captures by MVV/LVA, and only subject HxL captures to SEE to decide if you want to postpone (or prune) them (when SEE <0). In Joker I did this by replacing the MVV by the SEE value in the sort key for such moves once they come up, and resorting them.

If the engine is aware of the threats against it you can use that to upgrade the sort key of moves with threatened pieces, or capture of their attacker, with the SEE value of the threat. Usually you are not aware of this, however.

Note that in the face of a threat, even 'good' captures can be very much poorer than a non-capture. E.g. if the opponent threatens my Queen with a Pawn, B x (unprotected) R is a very bad idea, and my priority should lie with moving the Queen to safety. Capture of an unprotected piece with the Queen would do that, but in absence of such an opportunity a non-capture would be called for. In Joker it helped to identify one safe non-capture evasion of the threatened piece, and sort that with the captures. (It has MVV = 0, but is upgraded with the SEE-value of the threat because it moves the threatened piece, so that it can get a high priority if that SEE value is large.)