Move ordering

[cms271828]

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

[Dann Corbit]

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

Here is the stockfish move picker (the only thing that seem to be left out is promotion moves):

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;
    }
  }
}

[mcostalba]

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).

[hgm]

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.

[Jan Brouwer]

(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?

[Sven]

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

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.

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

[xsadar]

(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?

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]

(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?

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.

That would probably be the most robust approach to construct such a testset.
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.