Move ordering ?

[MahmoudUthman]

So far I've implement the following :
TT-Move , MVV-LVA , Killer-2Slots , History[From][to] .
what should the next method(s) to implement be ?

and how should I order equal moves ? all I could think of was (Direction(Forward/Backward) or proximity to the enemy king) ?

Last thing is there any advantage to one form of the history heuristic ([From][To],[Piece][To]) over the other ?

[phhnguyen]

So far I've implement the following :
TT-Move , MVV-LVA , Killer-2Slots , History[From][to] .
what should the next method(s) to implement be ?

SEE (Static Exchange Evaluation). It is worth for both move ordering and quiescence search:

https://chessprogramming.wikispaces.com ... Evaluation

The recursive version of SEE is very easy to implement.

Once you have implemented the SEE, you may implement typical move ordering:

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
(https://chessprogramming.wikispaces.com/Move+Ordering)

and how should I order equal moves ? all I could think of was (Direction(Forward/Backward) or proximity to the enemy king) ?

Last thing is there any advantage to one form of the history heuristic ([From][To],[Piece][To]) over the other ?

For me, killer, history heuristics or any implementations for move ordering by equalities, directions... are almost useless.

[Aleks Peshkov]

New moves (moves made possible because of recent moves of both sides) should be considered first. AFAIK Stockfish does so for LMR decisions, but not sure about ordering.

[Volker Annuss]

When you don't have a TT-move you can sort the move that captures the last moved piece with the least valuable attacker before the normal MVV-LVA.

[hgm]

That did not always work for me. There is a very strong case for preferring the MVV; even if the opponent just hung his latest moved piece, the most certain way to collect it is by first taking the MVV, and only taking the moved piece after he recaptures there.

Only if the last-moved piece makes an important threat it pays to take it first. But the chances that the MVV is making an important threat are higher; it is a more powerful piece, after all. That capturing that same MVV did not produce a cutoff two ply earlier (as evidenced by the fact that you have to search this move at all), doesn't mean it will not produce a cutoff now, if the opponent just hung an extra piece. But when you take the threats opponent pieces make as part of their victim value, this will be done automatically. And it would also work when the last moved piece discovered a threat by another piece, as you would then go for the latter.

It might be too expensive to figure all that out in QS, however. And it might be rare that the last move did create an important threat, so most of the time the effort would be wasted. A solution could be to make an abortable QS, which aborts moves that on closer inspection against expectation run into trouble. E.g. if the MVV is a Rook, and I can do NxR, it does look like a very promising first try. But if then on another square BxQ follows, because the opponent's last-moved B attacked my Q (or because my Knight was soft-pinned by the B), NxR suddenly does not look so hot anymore. The pattern is that his best MVV/LVA capture now promises a SEE of at least 6 (Q for B), while I only took 5 (R). So these two ply just made it 1 Pawn harder for me to reach beta. You could make the node fail 'ultra-high' on discovery of the BxQ during move generation, so that the parent can see that the move was no good, and reschedule its search to after the point where it has tried capturing the B attacking your Q, or making a capture with the attacked Q, both of which would not run into the problem of a 'devastating retaliation'.

[Aleks Peshkov]

Null-move search should find the best "null move" refutation. If new move (instead of null-move) prevents null-move refutation, then we should find the way to counter that new move.

Always searching in the same rigid MVV-LVA order seems stupid.

[hgm]

True, but this is why I mentioned QS. There one usually does not do any null moves, and doing one for the purpose of ordering the moves would be very expensive.

So I was thinking of the following:

Code: Select all

QS(alpha, beta, threshold)
{
  int curMove;
  int nrCapts = GenCaptures();
  for&#40;i=0; i<nrCapts; i++) &#123; // prioritize captures
    if&#40;value&#91;victim&#93; - value&#91;piece&#93; > threshold || 
       value&#91;victim&#93; > threshold && !Protected&#40;victim&#41;) return MATE+1; // abort <--------------
    move&#91;i&#93;.key = 16*value&#91;victim&#93; - value&#91;piece&#93;; // MVV/LVA
  &#125;
  for&#40;curMove=0; curMove < nrCaptures; curMove++) &#123;
    int i, first, maxKey = 0;
    for&#40;i=curMove; i<nrCapts; i++) &#123; // extract move with highest priority of remaining
      if&#40;move&#91;i&#93;.key > maxKey&#41; first = i, maxKey = move&#91;i&#93;.key;
    &#125;
    SwapMoves&#40;first, curMove&#41;;
    MakeMove&#40;curMove&#41;;
    score =-QS&#40;-beta, -alpha, move&#91;curMove&#93;.key > 6 ? value&#91;victim&#93; &#58; MATE&#41;;
    UnMake&#40;);
    if&#40;score < -MATE&#41; move&#91;curMove--&#93;.key = 6; else // postpone aborted move <------------
    if&#40;score > alpha&#41; &#123;
      alpha = score;
      if&#40;score > beta&#41; return beta;
    &#125;
  &#125;
  return alpha;
&#125;

The lines marked with <--- are the unusual ones, which would cause captures that run into a devastating counter-strike (which includes HxL captures with negative SEE) to be postponed, at the cost of a capture generation. (Note that if you did capture generation in MVV order this would never be very expesive.)

Main snag is that you would have to know if pieces are protected. The reason is that you don't want to postpone a PxB just because the opponent can do a Q x protected Q trade. (And suppose that initiating that trade yourself, which you of course searched before, did not gain you the Bishop afterwards, because he happens to recapture your Q with that.)