From 595a90dfd0cd393a8805f4f51cf5c5d8b264c121 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Wed, 26 Aug 2009 14:33:17 +0100 Subject: [PATCH] Clean killers handling in movepicker Original patch from Joona with added optimizations by me. Great cleanup of MovePicker with speed improvment of 1% No functional change. Signed-off-by: Marco Costalba --- src/application.cpp | 1 - src/movepick.cpp | 144 ++++++++++++++++---------------------------- src/movepick.h | 43 ++++++------- 3 files changed, 71 insertions(+), 117 deletions(-) diff --git a/src/application.cpp b/src/application.cpp index 83eba40b..2e6adcac 100644 --- a/src/application.cpp +++ b/src/application.cpp @@ -47,7 +47,6 @@ Application::Application() { init_uci_options(); Position::init_zobrist(); Position::init_piece_square_tables(); - MovePicker::init_phase_table(); init_eval(1); init_bitbases(); init_threads(); diff --git a/src/movepick.cpp b/src/movepick.cpp index 77c42efa..0b887c99 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -43,11 +43,10 @@ namespace { /// Variables CACHE_LINE_ALIGNMENT - int MainSearchPhaseIndex; - int EvasionsPhaseIndex; - int QsearchWithChecksPhaseIndex; - int QsearchWithoutChecksPhaseIndex; - uint8_t PhaseTable[32]; + const MovegenPhaseT MainSearchPhaseTable[] = { PH_STOP, PH_TT_MOVES, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES, PH_BAD_CAPTURES, PH_STOP}; + const MovegenPhaseT EvasionsPhaseTable[] = { PH_STOP, PH_EVASIONS, PH_STOP}; + const MovegenPhaseT QsearchWithChecksPhaseTable[] = { PH_STOP, PH_TT_MOVES, PH_QCAPTURES, PH_QCHECKS, PH_STOP}; + const MovegenPhaseT QsearchWithoutChecksPhaseTable[] = { PH_STOP, PH_TT_MOVES, PH_QCAPTURES, PH_STOP}; } @@ -65,33 +64,31 @@ namespace { MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss) : pos(p), H(h) { - ttMove = ttm; + ttMoves[0] = ttm; if (ss) { - mateKiller = (ss->mateKiller == ttm)? MOVE_NONE : ss->mateKiller; - killer1 = ss->killers[0]; - killer2 = ss->killers[1]; + ttMoves[1] = (ss->mateKiller == ttm)? MOVE_NONE : ss->mateKiller; + killers[0] = ss->killers[0]; + killers[1] = ss->killers[1]; } else - mateKiller = killer1 = killer2 = MOVE_NONE; + ttMoves[1] = killers[0] = killers[1] = MOVE_NONE; movesPicked = numOfMoves = numOfBadCaptures = 0; - checkKillers = checkLegal = finished = false; + finished = false; if (p.is_check()) - phaseIndex = EvasionsPhaseIndex; + phasePtr = EvasionsPhaseTable; else if (d > Depth(0)) - phaseIndex = MainSearchPhaseIndex; + phasePtr = MainSearchPhaseTable; else if (d == Depth(0)) - phaseIndex = QsearchWithChecksPhaseIndex; + phasePtr = QsearchWithChecksPhaseTable; else - phaseIndex = QsearchWithoutChecksPhaseIndex; + phasePtr = QsearchWithoutChecksPhaseTable; Color us = pos.side_to_move(); dc = p.discovered_check_candidates(us); pinned = p.pinned_pieces(us); - - finished = false; } @@ -115,25 +112,11 @@ Move MovePicker::get_next_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; + phasePtr++; + switch (*phasePtr) { - case PH_MATE_KILLER: - if (mateKiller != MOVE_NONE) - { - assert(move_is_ok(mateKiller)); - if (move_is_legal(pos, mateKiller, pinned)) - return mateKiller; - } + case PH_TT_MOVES: + movesPicked = 0; // This is used as index to ttMoves[] break; case PH_GOOD_CAPTURES: @@ -144,16 +127,10 @@ Move MovePicker::get_next_move() { break; 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; + movesPicked = 0; // This is used as index to killers[] 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); @@ -281,7 +258,7 @@ void MovePicker::score_evasions() { for (int i = 0; i < numOfMoves; i++) { Move m = moves[i].move; - if (m == ttMove) + if (m == ttMoves[0]) moves[i].score = 2*HistoryMax; else if (!pos.square_is_empty(move_to(m))) { @@ -301,17 +278,26 @@ void MovePicker::score_evasions() { Move MovePicker::pick_move_from_list() { assert(movesPicked >= 0); - assert(!pos.is_check() || PhaseTable[phaseIndex] == PH_EVASIONS || PhaseTable[phaseIndex] == PH_STOP); - assert( pos.is_check() || PhaseTable[phaseIndex] != PH_EVASIONS); + assert(!pos.is_check() || *phasePtr == PH_EVASIONS || *phasePtr == PH_STOP); + assert( pos.is_check() || *phasePtr != PH_EVASIONS); + + switch (*phasePtr) { - switch (PhaseTable[phaseIndex]) { + case PH_TT_MOVES: + while (movesPicked < 2) { + Move move = ttMoves[movesPicked++]; + if ( move != MOVE_NONE + && move_is_legal(pos, move, pinned)) + return move; + } + break; case PH_GOOD_CAPTURES: while (movesPicked < numOfMoves) { Move move = moves[movesPicked++].move; - if ( move != ttMove - && move != mateKiller + if ( move != ttMoves[0] + && move != ttMoves[1] && pos.pl_move_is_legal(move, pinned)) { // Check for a non negative SEE now @@ -327,15 +313,28 @@ Move MovePicker::pick_move_from_list() { } } break; + case PH_KILLERS: + while (movesPicked < 2) { + Move move = killers[movesPicked++]; + if ( move != MOVE_NONE + && move != ttMoves[0] + && move != ttMoves[1] + && move_is_legal(pos, move, pinned) + && !pos.move_is_capture(move)) + return move; + } + break; + 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))) + if ( move != ttMoves[0] + && move != ttMoves[1] + && move != killers[0] + && move != killers[1] + && pos.pl_move_is_legal(move, pinned)) return move; } break; @@ -356,7 +355,7 @@ Move MovePicker::pick_move_from_list() { { Move move = moves[movesPicked++].move; // Maybe postpone the legality check until after futility pruning? - if ( move != ttMove + if ( move != ttMoves[0] && pos.pl_move_is_legal(move, pinned)) return move; } @@ -367,42 +366,3 @@ Move MovePicker::pick_move_from_list() { } return MOVE_NONE; } - - -/// MovePicker::init_phase_table() initializes the PhaseTable[], -/// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex -/// and QsearchWithoutChecksPhaseIndex. It is only called once during -/// program startup, and never again while the program is running. - -void MovePicker::init_phase_table() { - - int i = 0; - - // Main search - MainSearchPhaseIndex = i - 1; - PhaseTable[i++] = PH_TT_MOVE; - PhaseTable[i++] = PH_MATE_KILLER; - PhaseTable[i++] = PH_GOOD_CAPTURES; - PhaseTable[i++] = PH_KILLERS; - PhaseTable[i++] = PH_NONCAPTURES; - PhaseTable[i++] = PH_BAD_CAPTURES; - PhaseTable[i++] = PH_STOP; - - // Check evasions - EvasionsPhaseIndex = i - 1; - PhaseTable[i++] = PH_EVASIONS; - PhaseTable[i++] = PH_STOP; - - // Quiescence search with checks - QsearchWithChecksPhaseIndex = i - 1; - PhaseTable[i++] = PH_TT_MOVE; - PhaseTable[i++] = PH_QCAPTURES; - PhaseTable[i++] = PH_QCHECKS; - PhaseTable[i++] = PH_STOP; - - // Quiescence search without checks - QsearchWithoutChecksPhaseIndex = i - 1; - PhaseTable[i++] = PH_TT_MOVE; - PhaseTable[i++] = PH_QCAPTURES; - PhaseTable[i++] = PH_STOP; -} diff --git a/src/movepick.h b/src/movepick.h index 920a9757..a5ecb066 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -35,9 +35,22 @@ //// Types //// -struct EvalInfo; struct SearchStack; +enum MovegenPhase { + PH_TT_MOVES, // Transposition table move and mate killer + PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= 0 + PH_KILLERS, // Killer moves from the current ply + PH_NONCAPTURES, // Non-captures and underpromotions + PH_BAD_CAPTURES, // Queen promotions and captures with SEE values < 0 + PH_EVASIONS, // Check evasions + PH_QCAPTURES, // Captures in quiescence search + PH_QCHECKS, // Non-capture checks in quiescence search + PH_STOP +}; + +typedef uint8_t MovegenPhaseT; + /// MovePicker is a class which is used to pick one legal move at a time from /// the current position. It is initialized with a Position object and a few /// moves we have reason to believe are good. The most important method is @@ -51,28 +64,12 @@ class MovePicker { MovePicker& operator=(const MovePicker&); // silence a warning under MSVC public: - - enum MovegenPhase { - PH_TT_MOVE, // Transposition table move - PH_MATE_KILLER, // Mate killer from the current ply - PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= 0 - PH_KILLERS, // Killer moves from the current ply - PH_NONCAPTURES, // Non-captures and underpromotions - PH_BAD_CAPTURES, // Queen promotions and captures with SEE values < 0 - PH_EVASIONS, // Check evasions - PH_QCAPTURES, // Captures in quiescence search - PH_QCHECKS, // Non-capture checks in quiescence search - PH_STOP - }; - MovePicker(const Position& p, Move ttm, Depth d, const History& h, SearchStack* ss = NULL); Move get_next_move(); Move get_next_move(Lock& lock); int number_of_moves() const; Bitboard discovered_check_candidates() const; - static void init_phase_table(); - private: void score_captures(); void score_noncaptures(); @@ -81,14 +78,12 @@ private: const Position& pos; const History& H; - Move ttMove, mateKiller, killer1, killer2; - Bitboard pinned, dc; - MoveStack moves[256], badCaptures[64]; - int phaseIndex; - int numOfMoves, numOfBadCaptures; - int movesPicked; - bool checkKillers, checkLegal; + Move ttMoves[2], killers[2]; + const MovegenPhaseT* phasePtr; + int movesPicked, numOfMoves, numOfBadCaptures; bool finished; + Bitboard dc, pinned; + MoveStack moves[256], badCaptures[64]; }; -- 2.39.2