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 ?
Move ordering ?
Moderators: hgm, Rebel, chrisw
-
- Posts: 1437
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Move ordering ?
SEE (Static Exchange Evaluation). It is worth for both move ordering and quiescence search:MahmoudUthman wrote: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 ?
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)
For me, killer, history heuristics or any implementations for move ordering by equalities, directions... are almost useless.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 ?
-
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
Re: Move ordering ?
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.
-
- Posts: 180
- Joined: Mon Sep 03, 2007 9:15 am
Re: Move ordering ?
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering ?
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'.
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'.
-
- Posts: 892
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
Re: Move ordering ?
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.
Always searching in the same rigid MVV-LVA order seems stupid.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering ?
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:
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.)
So I was thinking of the following:
Code: Select all
QS(alpha, beta, threshold)
{
int curMove;
int nrCapts = GenCaptures();
for(i=0; i<nrCapts; i++) { // prioritize captures
if(value[victim] - value[piece] > threshold ||
value[victim] > threshold && !Protected(victim)) return MATE+1; // abort <--------------
move[i].key = 16*value[victim] - value[piece]; // MVV/LVA
}
for(curMove=0; curMove < nrCaptures; curMove++) {
int i, first, maxKey = 0;
for(i=curMove; i<nrCapts; i++) { // extract move with highest priority of remaining
if(move[i].key > maxKey) first = i, maxKey = move[i].key;
}
SwapMoves(first, curMove);
MakeMove(curMove);
score =-QS(-beta, -alpha, move[curMove].key > 6 ? value[victim] : MATE);
UnMake();
if(score < -MATE) move[curMove--].key = 6; else // postpone aborted move <------------
if(score > alpha) {
alpha = score;
if(score > beta) return beta;
}
}
return alpha;
}
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.)