X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.cpp;h=3da4247a29e3cdff10de95c06838b7ddb173ae1c;hp=0b3b6fd6b0e4d1e88d9052036ce58e07f886d279;hb=e25de55faca30c2196612fcb208d88802ad29bae;hpb=5b8ca1eee77b736c35b418b1cb11da9fc66f83e0 diff --git a/src/movepick.cpp b/src/movepick.cpp index 0b3b6fd6..3da4247a 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-2010 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2008-2012 Marco Costalba, Joona Kiiski, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -28,29 +28,16 @@ namespace { - enum MovegenPhase { - PH_TT_MOVE, // Transposition table move - PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= captureThreshold (captureThreshold <= 0) - PH_GOOD_PROBCUT, // Queen promotions and captures with SEE values > captureThreshold (captureThreshold >= 0) - PH_KILLERS, // Killer moves from the current ply - PH_NONCAPTURES_1, // Non-captures and underpromotions with positive score - PH_NONCAPTURES_2, // Non-captures and underpromotions with non-positive score - PH_BAD_CAPTURES, // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0) - PH_EVASIONS, // Check evasions - PH_QCAPTURES, // Captures in quiescence search - PH_QRECAPTURES, // Recaptures in quiescence search - PH_QCHECKS, // Non-capture checks in quiescence search - PH_STOP + enum Sequencer { + MAIN_SEARCH, TT_MOVE_S1, GOOD_CAPTURES_S1, KILLERS_S1, NONCAPTURES_1_S1, + NONCAPTURES_2_S1, BAD_CAPTURES_S1, STOP_S1, + EVASIONS, TT_MOVE_S2, EVASIONS_S2, STOP_S2, + CAPTURES_AND_CHECKS, TT_MOVE_S3, QCAPTURES_S3, QCHECKS_S3, STOP_S3, + CAPTURES, TT_MOVE_S4, QCAPTURES_S4, STOP_S4, + RECAPTURES, TT_MOVE_S5, RECAPTURES_S5, STOP_S5, + PROBCUT, TT_MOVE_S6, GOOD_CAPTURES_S6, STOP_S6 }; - CACHE_LINE_ALIGNMENT - const uint8_t MainSearchTable[] = { PH_TT_MOVE, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES_1, PH_NONCAPTURES_2, PH_BAD_CAPTURES, PH_STOP }; - const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP }; - const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP }; - const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP }; - const uint8_t QsearchRecapturesTable[] = { PH_TT_MOVE, PH_QRECAPTURES, PH_STOP }; - const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP }; - // Unary predicate used by std::partition to split positive scores from remaining // ones so to sort separately the two sets, and with the second sort delayed. inline bool has_positive_score(const MoveStack& move) { return move.score > 0; } @@ -81,23 +68,26 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, if (p.in_check()) { killers[0].move = killers[1].move = MOVE_NONE; - phasePtr = EvasionTable; + phase = EVASIONS; } else { killers[0].move = ss->killers[0]; killers[1].move = ss->killers[1]; - // Consider sligtly negative captures as good if at low - // depth and far from beta. + // Consider sligtly negative captures as good if at low depth and far from beta if (ss && ss->eval < beta - PawnValueMidgame && d < 3 * ONE_PLY) captureThreshold = -PawnValueMidgame; - phasePtr = MainSearchTable; + // Consider negative captures as good if still enough to reach beta + else if (ss && ss->eval > beta) + captureThreshold = beta - ss->eval; + + phase = MAIN_SEARCH; } ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE); - phasePtr += int(ttMove == MOVE_NONE) - 1; + phase += int(ttMove == MOVE_NONE); go_next_phase(); } @@ -107,12 +97,14 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, S assert(d <= DEPTH_ZERO); if (p.in_check()) - phasePtr = EvasionTable; + phase = EVASIONS; + else if (d >= DEPTH_QS_CHECKS) - phasePtr = QsearchWithChecksTable; + phase = CAPTURES_AND_CHECKS; + else if (d >= DEPTH_QS_RECAPTURES) { - phasePtr = QsearchWithoutChecksTable; + phase = CAPTURES; // Skip TT move if is not a capture or a promotion, this avoids // qsearch tree explosion due to a possible perpetual check or @@ -122,13 +114,13 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, S } else { - phasePtr = QsearchRecapturesTable; + phase = RECAPTURES; recaptureSquare = recaptureSq; ttm = MOVE_NONE; } ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE); - phasePtr += int(ttMove == MOVE_NONE) - 1; + phase += int(ttMove == MOVE_NONE); go_next_phase(); } @@ -139,14 +131,14 @@ MovePicker::MovePicker(const Position& p, Move ttm, const History& h, PieceType // In ProbCut we consider only captures better than parent's move captureThreshold = PieceValueMidgame[Piece(parentCapture)]; - phasePtr = ProbCutTable; + phase = PROBCUT; if ( ttm != MOVE_NONE && (!pos.is_capture(ttm) || pos.see(ttm) <= captureThreshold)) ttm = MOVE_NONE; ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE); - phasePtr += int(ttMove == MOVE_NONE) - 1; + phase += int(ttMove == MOVE_NONE); go_next_phase(); } @@ -157,71 +149,73 @@ MovePicker::MovePicker(const Position& p, Move ttm, const History& h, PieceType void MovePicker::go_next_phase() { curMove = moves; - phase = *(++phasePtr); - switch (phase) { - case PH_TT_MOVE: + switch (++phase) { + + case TT_MOVE_S1: case TT_MOVE_S2: case TT_MOVE_S3: + case TT_MOVE_S4: case TT_MOVE_S5: case TT_MOVE_S6: lastMove = curMove + 1; return; - case PH_GOOD_CAPTURES: - case PH_GOOD_PROBCUT: + case GOOD_CAPTURES_S1: + case GOOD_CAPTURES_S6: lastMove = generate(pos, moves); score_captures(); return; - case PH_KILLERS: + case KILLERS_S1: curMove = killers; lastMove = curMove + 2; return; - case PH_NONCAPTURES_1: + case NONCAPTURES_1_S1: lastNonCapture = lastMove = generate(pos, moves); score_noncaptures(); lastMove = std::partition(curMove, lastMove, has_positive_score); sort(curMove, lastMove); return; - case PH_NONCAPTURES_2: + case NONCAPTURES_2_S1: curMove = lastMove; lastMove = lastNonCapture; if (depth >= 3 * ONE_PLY) sort(curMove, lastMove); return; - case PH_BAD_CAPTURES: + case BAD_CAPTURES_S1: // Bad captures SEE value is already calculated so just pick // them in order to get SEE move ordering. curMove = badCaptures; lastMove = moves + MAX_MOVES; return; - case PH_EVASIONS: + case EVASIONS_S2: assert(pos.in_check()); lastMove = generate(pos, moves); score_evasions(); return; - case PH_QCAPTURES: + case QCAPTURES_S3: + case QCAPTURES_S4: lastMove = generate(pos, moves); score_captures(); return; - case PH_QRECAPTURES: + case RECAPTURES_S5: lastMove = generate(pos, moves); return; - case PH_QCHECKS: + case QCHECKS_S3: lastMove = generate(pos, moves); return; - case PH_STOP: + case STOP_S1: case STOP_S2: case STOP_S3: + case STOP_S4: case STOP_S5: case STOP_S6: lastMove = curMove + 1; // Avoid another go_next_phase() call return; default: assert(false); - return; } } @@ -229,7 +223,7 @@ void MovePicker::go_next_phase() { /// MovePicker::score_captures(), MovePicker::score_noncaptures() and /// MovePicker::score_evasions() assign a numerical move ordering score /// to each move in a move list. The moves with highest scores will be -/// picked first by get_next_move(). +/// picked first by next_move(). void MovePicker::score_captures() { // Winning and equal captures in the main search are ordered by MVV/LVA. @@ -251,8 +245,8 @@ void MovePicker::score_captures() { for (MoveStack* cur = moves; cur != lastMove; cur++) { m = cur->move; - cur->score = PieceValueMidgame[pos.piece_on(move_to(m))] - - type_of(pos.piece_on(move_from(m))); + cur->score = PieceValueMidgame[pos.piece_on(to_sq(m))] + - type_of(pos.piece_moved(m)); if (is_promotion(m)) cur->score += PieceValueMidgame[Piece(promotion_piece_type(m))]; @@ -267,8 +261,8 @@ void MovePicker::score_noncaptures() { for (MoveStack* cur = moves; cur != lastMove; cur++) { m = cur->move; - from = move_from(m); - cur->score = H.value(pos.piece_on(from), move_to(m)); + from = from_sq(m); + cur->score = H.value(pos.piece_on(from), to_sq(m)); } } @@ -290,21 +284,21 @@ void MovePicker::score_evasions() { if ((seeScore = pos.see_sign(m)) < 0) cur->score = seeScore - History::MaxValue; // Be sure we are at the bottom else if (pos.is_capture(m)) - cur->score = PieceValueMidgame[pos.piece_on(move_to(m))] - - type_of(pos.piece_on(move_from(m))) + History::MaxValue; + cur->score = PieceValueMidgame[pos.piece_on(to_sq(m))] + - type_of(pos.piece_moved(m)) + History::MaxValue; else - cur->score = H.value(pos.piece_on(move_from(m)), move_to(m)); + cur->score = H.value(pos.piece_moved(m), to_sq(m)); } } -/// MovePicker::get_next_move() is the most important method of the MovePicker -/// class. It returns a new pseudo legal move every time it is called, until there +/// MovePicker::next_move() is the most important method of the MovePicker class. +/// It returns a new pseudo legal move every time it is called, until there /// are no more moves left. It picks the move with the biggest score from a list /// of generated moves taking care not to return the tt move if has already been /// searched previously. Note that this function is not thread safe so should be /// lock protected by caller when accessed through a shared MovePicker object. -Move MovePicker::get_next_move() { +Move MovePicker::next_move() { Move move; @@ -315,12 +309,13 @@ Move MovePicker::get_next_move() { switch (phase) { - case PH_TT_MOVE: + case TT_MOVE_S1: case TT_MOVE_S2: case TT_MOVE_S3: + case TT_MOVE_S4: case TT_MOVE_S5: case TT_MOVE_S6: curMove++; return ttMove; break; - case PH_GOOD_CAPTURES: + case GOOD_CAPTURES_S1: move = pick_best(curMove++, lastMove)->move; if (move != ttMove) { @@ -337,14 +332,14 @@ Move MovePicker::get_next_move() { } break; - case PH_GOOD_PROBCUT: + case GOOD_CAPTURES_S6: move = pick_best(curMove++, lastMove)->move; if ( move != ttMove && pos.see(move) > captureThreshold) return move; break; - case PH_KILLERS: + case KILLERS_S1: move = (curMove++)->move; if ( move != MOVE_NONE && pos.is_pseudo_legal(move) @@ -353,8 +348,8 @@ Move MovePicker::get_next_move() { return move; break; - case PH_NONCAPTURES_1: - case PH_NONCAPTURES_2: + case NONCAPTURES_1_S1: + case NONCAPTURES_2_S1: move = (curMove++)->move; if ( move != ttMove && move != killers[0].move @@ -362,35 +357,36 @@ Move MovePicker::get_next_move() { return move; break; - case PH_BAD_CAPTURES: + case BAD_CAPTURES_S1: move = pick_best(curMove++, lastMove)->move; return move; - case PH_EVASIONS: - case PH_QCAPTURES: + case EVASIONS_S2: + case QCAPTURES_S3: + case QCAPTURES_S4: move = pick_best(curMove++, lastMove)->move; if (move != ttMove) return move; break; - case PH_QRECAPTURES: + case RECAPTURES_S5: move = (curMove++)->move; - if (move_to(move) == recaptureSquare) + if (to_sq(move) == recaptureSquare) return move; break; - case PH_QCHECKS: + case QCHECKS_S3: move = (curMove++)->move; if (move != ttMove) return move; break; - case PH_STOP: + case STOP_S1: case STOP_S2: case STOP_S3: + case STOP_S4: case STOP_S5: case STOP_S6: return MOVE_NONE; default: assert(false); - break; } } }