Hi
In my non-qs nodes, I order moves by Hash Move, Captures(MVV-LVA sorted), non-captures.
I don't yet have killers or history heuristic.
I was thinking that moves that give check should be considered before captures, or at least before non-captures. (*)
I currently don't test to see if a move gives check, but in the node that follows, I see if the position is in check (by looking at the last moved piece, and possible discovery attacks arrising from this).
So in theory I could switch this, and test for check after generating moves (allowing me to order them as described above (*)), then pass a boolean to the next node, so it instantly knows if the side to play is in check or not.
I guess there could be some cost to performance, since the way it is currently set up, when a cutoff is performed, some nodes are not reached, so by switching it around, those unreached nodes will also be tested for check unneseccarily, when they weren't before.
Any thoughts/suggestions/ideas/advice/critisms? Thanks
Move ordering
Moderators: hgm, Rebel, chrisw
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Move ordering
Here is the stockfish move picker (the only thing that seem to be left out is promotion moves):cms271828 wrote:Hi
In my non-qs nodes, I order moves by Hash Move, Captures(MVV-LVA sorted), non-captures.
I don't yet have killers or history heuristic.
I was thinking that moves that give check should be considered before captures, or at least before non-captures. (*)
I currently don't test to see if a move gives check, but in the node that follows, I see if the position is in check (by looking at the last moved piece, and possible discovery attacks arrising from this).
So in theory I could switch this, and test for check after generating moves (allowing me to order them as described above (*)), then pass a boolean to the next node, so it instantly knows if the side to play is in check or not.
I guess there could be some cost to performance, since the way it is currently set up, when a cutoff is performed, some nodes are not reached, so by switching it around, those unreached nodes will also be tested for check unneseccarily, when they weren't before.
Any thoughts/suggestions/ideas/advice/critisms? Thanks
Code: Select all
/// MovePicker::get_next_move() is the most important method of the MovePicker
/// class. It returns a new legal move every time it is called, until there
/// are no more moves left of the types we are interested in.
Move MovePicker::get_next_move() {
Move move;
while (true)
{
// If we already have a list of generated moves, pick the best move from
// the list, and return it.
move = pick_move_from_list();
if (move != MOVE_NONE)
{
assert(move_is_ok(move));
return move;
}
// Next phase
phaseIndex++;
switch (PhaseTable[phaseIndex]) {
case PH_TT_MOVE:
if (ttMove != MOVE_NONE)
{
assert(move_is_ok(ttMove));
if (move_is_legal(pos, ttMove, pinned))
return ttMove;
}
break;
case PH_MATE_KILLER:
if (mateKiller != MOVE_NONE)
{
assert(move_is_ok(mateKiller));
if (move_is_legal(pos, mateKiller, pinned))
return mateKiller;
}
break;
case PH_GOOD_CAPTURES:
numOfMoves = generate_captures(pos, moves);
score_captures();
std::sort(moves, moves + numOfMoves);
movesPicked = 0;
checkLegal = true;
break;
case PH_KILLERS:
movesPicked = numOfMoves = 0;
checkLegal = false;
if (killer1 != MOVE_NONE && move_is_legal(pos, killer1, pinned) && !pos.move_is_capture(killer1))
moves[numOfMoves++].move = killer1;
if (killer2 != MOVE_NONE && move_is_legal(pos, killer2, pinned) && !pos.move_is_capture(killer2) )
moves[numOfMoves++].move = killer2;
break;
case PH_NONCAPTURES:
checkKillers = (numOfMoves != 0); // previous phase is PH_KILLERS
numOfMoves = generate_noncaptures(pos, moves);
score_noncaptures();
std::sort(moves, moves + numOfMoves);
movesPicked = 0;
checkLegal = true;
break;
case PH_BAD_CAPTURES:
// Bad captures SEE value is already calculated by score_captures()
// so just sort them to get SEE move ordering.
std::sort(badCaptures, badCaptures + numOfBadCaptures);
movesPicked = 0;
break;
case PH_EVASIONS:
assert(pos.is_check());
numOfMoves = generate_evasions(pos, moves, pinned);
score_evasions();
std::sort(moves, moves + numOfMoves);
movesPicked = 0;
break;
case PH_QCAPTURES:
numOfMoves = generate_captures(pos, moves);
score_qcaptures();
std::sort(moves, moves + numOfMoves);
movesPicked = 0;
break;
case PH_QCHECKS:
// Perhaps we should order moves move here? FIXME
numOfMoves = generate_non_capture_checks(pos, moves, dc);
movesPicked = 0;
break;
case PH_STOP:
return MOVE_NONE;
default:
assert(false);
return MOVE_NONE;
}
}
}
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Move ordering
Dann Corbit wrote:
Here is the stockfish move picker (the only thing that seem to be left out is promotion moves):
Queen promotions are generated among the PH_GOOD_CAPTURES moves, underpromotions among the PH_NONCAPTURES ones.
Queen promotions score equals a QUEEN value, so it is probable that a promotion to queen move ends up as the first among the good captures (i.e. capture moves with non-negative SEE value).
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering
If you do check extension, that would be a very good reason to postpone searching checks as much as you can. Searching a single check with an extension will likely take more time than searching all other moves together. (Especially if you use LMR.) So better search the others first, and hope for a cutoff.
Checks are usually poor moves anyway.
Checks are usually poor moves anyway.
-
- Posts: 201
- Joined: Thu Mar 22, 2007 7:12 pm
- Location: Netherlands
Re: Move ordering - test positions?
(If I my hijack this thread for a moment..)
I'm looking for a set of test positions to improve the move ordering of my program.
In the past I have used LCT II for this purpose, but the number of positions in that set is quite low (35).
Any suggestions for a larger test set (> 100 positions), preferably one which somehow mirrors the positions encountered in a typical game?
I'm looking for a set of test positions to improve the move ordering of my program.
In the past I have used LCT II for this purpose, but the number of positions in that set is quite low (35).
Any suggestions for a larger test set (> 100 positions), preferably one which somehow mirrors the positions encountered in a typical game?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering
Checks very often lead to a tree explosion without being helpful in any kind. Most people extend their search when detecting that the side to move is currently in check but explicitly trying checks earlier than other moves can be counter-productive, better get a cheap cutoff before even trying the checking move.cms271828 wrote:Hi
In my non-qs nodes, I order moves by Hash Move, Captures(MVV-LVA sorted), non-captures.
I don't yet have killers or history heuristic.
I was thinking that moves that give check should be considered before captures, or at least before non-captures. (*)
I currently don't test to see if a move gives check, but in the node that follows, I see if the position is in check (by looking at the last moved piece, and possible discovery attacks arrising from this).
So in theory I could switch this, and test for check after generating moves (allowing me to order them as described above (*)), then pass a boolean to the next node, so it instantly knows if the side to play is in check or not.
I guess there could be some cost to performance, since the way it is currently set up, when a cutoff is performed, some nodes are not reached, so by switching it around, those unreached nodes will also be tested for check unneseccarily, when they weren't before.
Any thoughts/suggestions/ideas/advice/critisms? Thanks
Also it *can* be quite expensive, depending on things like your board representation or how you are handling attacks in general, to identify checks without making moves on the board.
Sven
-
- Posts: 147
- Joined: Wed Jun 06, 2007 10:01 am
- Location: United States
- Full name: Mike Leany
Re: Move ordering - test positions?
What if you have your engine play a lot of games against different opponents of approximately the same strength, then randomly select positions encountered in those games.Jan Brouwer wrote:(If I my hijack this thread for a moment..)
I'm looking for a set of test positions to improve the move ordering of my program.
In the past I have used LCT II for this purpose, but the number of positions in that set is quite low (35).
Any suggestions for a larger test set (> 100 positions), preferably one which somehow mirrors the positions encountered in a typical game?
-
- Posts: 201
- Joined: Thu Mar 22, 2007 7:12 pm
- Location: Netherlands
Re: Move ordering - test positions?
That would probably be the most robust approach to construct such a testset.xsadar wrote:What if you have your engine play a lot of games against different opponents of approximately the same strength, then randomly select positions encountered in those games.Jan Brouwer wrote:(If I my hijack this thread for a moment..)
I'm looking for a set of test positions to improve the move ordering of my program.
In the past I have used LCT II for this purpose, but the number of positions in that set is quite low (35).
Any suggestions for a larger test set (> 100 positions), preferably one which somehow mirrors the positions encountered in a typical game?
In the meantime I have started using the "silent but deadly" testset by Dann Corbit from the chess programmers wiki, but I may switch to your proposal.