X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.cpp;h=4529af7dd73edcca6a8e887799f129e727a1099b;hp=b20d67105d796f51260660c98e4d61cd7ab1d3b3;hb=50f92bed06e6416df4b343b121b1ba66500ab842;hpb=cd1cc39b04f261f74250285d19c5f4916abdc8c9 diff --git a/src/movepick.cpp b/src/movepick.cpp index b20d6710..4529af7d 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -1,7 +1,7 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008 Marco Costalba + Copyright (C) 2008-2009 Marco Costalba Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -63,23 +63,25 @@ namespace { /// search captures, promotions and some checks) and about how important good /// move ordering is at the current node. -MovePicker::MovePicker(const Position& p, bool pv, Move ttm, - const SearchStack& ss, Depth d) : pos(p) { - pvNode = pv; +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, + const History& h, SearchStack* ss) : pos(p), H(h) { ttMove = ttm; - mateKiller = (ss.mateKiller == ttm)? MOVE_NONE : ss.mateKiller; - killer1 = ss.killers[0]; - killer2 = ss.killers[1]; - depth = d; - movesPicked = 0; - numOfMoves = 0; - numOfBadCaptures = 0; + if (ss) + { + mateKiller = (ss->mateKiller == ttm)? MOVE_NONE : ss->mateKiller; + killer1 = ss->killers[0]; + killer2 = ss->killers[1]; + } else + mateKiller = killer1 = killer2 = MOVE_NONE; + + movesPicked = numOfMoves = numOfBadCaptures = 0; + checkKillers = checkLegal = finished = false; if (p.is_check()) phaseIndex = EvasionsPhaseIndex; - else if (depth > Depth(0)) + else if (d > Depth(0)) phaseIndex = MainSearchPhaseIndex; - else if (depth == Depth(0)) + else if (d == Depth(0)) phaseIndex = QsearchWithChecksPhaseIndex; else phaseIndex = QsearchWithoutChecksPhaseIndex; @@ -141,18 +143,30 @@ Move MovePicker::get_next_move() { movesPicked = 0; break; - case PH_BAD_CAPTURES: - // It's probably a good idea to use SEE move ordering here. FIXME - movesPicked = 0; + case PH_KILLERS: + movesPicked = numOfMoves = 0; + 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 + checkLegal = true; numOfMoves = generate_noncaptures(pos, moves); score_noncaptures(); std::sort(moves, moves + numOfMoves); movesPicked = 0; break; + case PH_BAD_CAPTURES: + // Bad captures SEE value is already calculated 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); @@ -163,7 +177,7 @@ Move MovePicker::get_next_move() { case PH_QCAPTURES: numOfMoves = generate_captures(pos, moves); - score_qcaptures(); + score_captures(); std::sort(moves, moves + numOfMoves); movesPicked = 0; break; @@ -213,38 +227,28 @@ Move MovePicker::get_next_move(Lock &lock) { void MovePicker::score_captures() { // Winning and equal captures in the main search are ordered by MVV/LVA. // Suprisingly, this appears to perform slightly better than SEE based - // move ordering. The reason is probably that in a position with a winning + // move ordering. The reason is probably that in a position with a winning // capture, capturing a more valuable (but sufficiently defended) piece - // first usually doesn't hurt. The opponent will have to recapture, and + // first usually doesn't hurt. The opponent will have to recapture, and // the hanging piece will still be hanging (except in the unusual cases // where it is possible to recapture with the hanging piece). Exchanging // big pieces before capturing a hanging piece probably helps to reduce // the subtree size. - // While scoring captures it moves all captures with negative SEE values - // to the badCaptures[] array. + // In main search we want to push captures with negative SEE values to + // badCaptures[] array, but instead of doing it now we delay till when + // the move has been picked up in pick_move_from_list(), this way we save + // some SEE calls in case we get a cutoff (idea from Pablo Vazquez). Move m; - int seeValue; + // Use MVV/LVA ordering for (int i = 0; i < numOfMoves; i++) { m = moves[i].move; - seeValue = pos.see(m); - if (seeValue >= 0) - { - if (move_promotion(m)) - moves[i].score = QueenValueMidgame; - else - moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m))) - -int(pos.type_of_piece_on(move_from(m))); - } + if (move_is_promotion(m)) + moves[i].score = QueenValueMidgame; else - { - // Losing capture, move it to the badCaptures[] array - assert(numOfBadCaptures < 63); - moves[i].score = seeValue; - badCaptures[numOfBadCaptures++] = moves[i]; - moves[i--] = moves[--numOfMoves]; - } + moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m))) + -int(pos.type_of_piece_on(move_from(m))); } } @@ -252,26 +256,23 @@ void MovePicker::score_noncaptures() { // First score by history, when no history is available then use // piece/square tables values. This seems to be better then a // random choice when we don't have an history for any move. - Move m; + Piece piece; + Square from, to; int hs; for (int i = 0; i < numOfMoves; i++) { - m = moves[i].move; - - if (m == killer1) - hs = HistoryMax + 2; - else if (m == killer2) - hs = HistoryMax + 1; - else - hs = H.move_ordering_score(pos.piece_on(move_from(m)), m); + from = move_from(moves[i].move); + to = move_to(moves[i].move); + piece = pos.piece_on(from); + hs = H.move_ordering_score(piece, to); // Ensure history is always preferred to pst if (hs > 0) hs += 1000; // pst based scoring - moves[i].score = hs + pos.mg_pst_delta(m); + moves[i].score = hs + pos.pst_delta(piece, from, to); } } @@ -287,21 +288,7 @@ void MovePicker::score_evasions() { int seeScore = pos.see(m); moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore; } else - moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), m); - } -} - -void MovePicker::score_qcaptures() { - - // Use MVV/LVA ordering - for (int i = 0; i < numOfMoves; i++) - { - Move m = moves[i].move; - if (move_promotion(m)) - moves[i].score = QueenValueMidgame; - else - moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m))) - -int(pos.type_of_piece_on(move_from(m))); + moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m)); } } @@ -320,13 +307,35 @@ Move MovePicker::pick_move_from_list() { switch (PhaseTable[phaseIndex]) { case PH_GOOD_CAPTURES: - case PH_NONCAPTURES: while (movesPicked < numOfMoves) { Move move = moves[movesPicked++].move; if ( move != ttMove && move != mateKiller && pos.pl_move_is_legal(move, pinned)) + { + // Check for a non negative SEE now + int seeValue = pos.see_sign(move); + if (seeValue >= 0) + return move; + + // Losing capture, move it to the badCaptures[] array, note + // that move has now been already checked for legality. + assert(numOfBadCaptures < 63); + badCaptures[numOfBadCaptures].move = move; + badCaptures[numOfBadCaptures++].score = seeValue; + } + } + break; + case PH_KILLERS: + case PH_NONCAPTURES: + while (movesPicked < numOfMoves) + { + Move move = moves[movesPicked++].move; + if ( move != ttMove + && move != mateKiller + && (!checkKillers || (move != killer1 && move != killer2)) + && (!checkLegal || pos.pl_move_is_legal(move, pinned))) return move; } break; @@ -334,18 +343,11 @@ Move MovePicker::pick_move_from_list() { case PH_EVASIONS: if (movesPicked < numOfMoves) return moves[movesPicked++].move; - break; case PH_BAD_CAPTURES: - while (movesPicked < numOfBadCaptures) - { - Move move = badCaptures[movesPicked++].move; - if ( move != ttMove - && move != mateKiller - && pos.pl_move_is_legal(move, pinned)) - return move; - } + if (movesPicked < numOfBadCaptures) + return badCaptures[movesPicked++].move; break; case PH_QCAPTURES: @@ -381,9 +383,7 @@ void MovePicker::init_phase_table() { PhaseTable[i++] = PH_TT_MOVE; PhaseTable[i++] = PH_MATE_KILLER; PhaseTable[i++] = PH_GOOD_CAPTURES; - // PH_KILLER_1 and PH_KILLER_2 are not yet used. - // PhaseTable[i++] = PH_KILLER_1; - // PhaseTable[i++] = PH_KILLER_2; + PhaseTable[i++] = PH_KILLERS; PhaseTable[i++] = PH_NONCAPTURES; PhaseTable[i++] = PH_BAD_CAPTURES; PhaseTable[i++] = PH_STOP;