X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fmovepick.cpp;h=5c0f4f5b775c57f811a382746936b519043c9710;hb=97dd7568edf74f8797e152258ebe30ecdc8bac0d;hp=57b5e1e9b6cd2993880fcbc929d983665460b47b;hpb=6cf28d4aa733447373430708fd2c35dee4469b10;p=stockfish diff --git a/src/movepick.cpp b/src/movepick.cpp index 57b5e1e9..5c0f4f5b 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -27,7 +27,6 @@ #include #include "history.h" -#include "evaluate.h" #include "movegen.h" #include "movepick.h" #include "search.h" @@ -40,12 +39,8 @@ namespace { - /// Variables - CACHE_LINE_ALIGNMENT - const MovegenPhaseT MainSearchPhaseTable[] = { PH_NULL_MOVE, PH_TT_MOVES, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES, PH_BAD_CAPTURES, PH_STOP}; - const MovegenPhaseT MainSearchNoNullPhaseTable[] = { PH_TT_MOVES, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES, PH_BAD_CAPTURES, PH_STOP}; - const MovegenPhaseT LowSearchPhaseTable[] = { PH_TT_MOVES, PH_GOOD_CAPTURES, PH_NULL_MOVE, PH_KILLERS, PH_NONCAPTURES, PH_BAD_CAPTURES, PH_STOP}; + const MovegenPhaseT MainSearchPhaseTable[] = { PH_TT_MOVES, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES, PH_BAD_CAPTURES, PH_STOP}; const MovegenPhaseT EvasionsPhaseTable[] = { PH_EVASIONS, PH_STOP}; const MovegenPhaseT QsearchWithChecksPhaseTable[] = { PH_TT_MOVES, PH_QCAPTURES, PH_QCHECKS, PH_STOP}; const MovegenPhaseT QsearchWithoutChecksPhaseTable[] = { PH_TT_MOVES, PH_QCAPTURES, PH_STOP}; @@ -57,7 +52,7 @@ namespace { //// -/// Constructor for the MovePicker class. Apart from the position for which +/// Constructor for the MovePicker class. Apart from the position for which /// it is asked to pick legal moves, MovePicker also wants some information /// to help it to return the presumably good moves first, to decide which /// moves to return (in the quiescence search, for instance, we only want to @@ -65,18 +60,20 @@ namespace { /// move ordering is at the current node. MovePicker::MovePicker(const Position& p, Move ttm, Depth d, - const History& h, SearchStack* ss, bool useNullMove) : pos(p), H(h) { - ttMoves[0] = ttm; + const History& h, SearchStack* ss) : pos(p), H(h) { + int searchTT = ttm; + ttMoves[0].move = ttm; if (ss) { - ttMoves[1] = (ss->mateKiller == ttm)? MOVE_NONE : ss->mateKiller; - killers[0] = ss->killers[0]; - killers[1] = ss->killers[1]; + ttMoves[1].move = (ss->mateKiller == ttm)? MOVE_NONE : ss->mateKiller; + searchTT |= ttMoves[1].move; + killers[0].move = ss->killers[0]; + killers[1].move = ss->killers[1]; } else - ttMoves[1] = killers[0] = killers[1] = MOVE_NONE; + ttMoves[1].move = killers[0].move = killers[1].move = MOVE_NONE; - numOfBadCaptures = 0; finished = false; + numOfBadCaptures = 0; Color us = pos.side_to_move(); @@ -85,14 +82,12 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, if (p.is_check()) phasePtr = EvasionsPhaseTable; - else if (d >= Depth(3 * OnePly)) - phasePtr = useNullMove ? MainSearchPhaseTable : MainSearchNoNullPhaseTable; else if (d > Depth(0)) - phasePtr = useNullMove ? LowSearchPhaseTable : MainSearchNoNullPhaseTable; + phasePtr = MainSearchPhaseTable + !searchTT; else if (d == Depth(0)) - phasePtr = QsearchWithChecksPhaseTable; + phasePtr = QsearchWithChecksPhaseTable + !searchTT; else - phasePtr = QsearchWithoutChecksPhaseTable; + phasePtr = QsearchWithoutChecksPhaseTable + !searchTT; phasePtr--; go_next_phase(); @@ -100,58 +95,64 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, /// MovePicker::go_next_phase() generates, scores and sorts the next bunch -/// of moves when there are no more moves to try for the currrent phase. +/// of moves when there are no more moves to try for the current phase. void MovePicker::go_next_phase() { - movesPicked = 0; + curMove = moves; phase = *(++phasePtr); switch (phase) { - case PH_NULL_MOVE: case PH_TT_MOVES: + curMove = ttMoves; + lastMove = curMove + 2; return; case PH_GOOD_CAPTURES: - numOfMoves = generate_captures(pos, moves); + lastMove = generate_captures(pos, moves); score_captures(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; case PH_KILLERS: + curMove = killers; + lastMove = curMove + 2; return; case PH_NONCAPTURES: - numOfMoves = generate_noncaptures(pos, moves); + lastMove = generate_noncaptures(pos, moves); score_noncaptures(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; 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); + curMove = badCaptures; + lastMove = badCaptures + numOfBadCaptures; + std::sort(badCaptures, lastMove); return; case PH_EVASIONS: assert(pos.is_check()); - numOfMoves = generate_evasions(pos, moves, pinned); + lastMove = generate_evasions(pos, moves, pinned); score_evasions(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; case PH_QCAPTURES: - numOfMoves = generate_captures(pos, moves); + lastMove = generate_captures(pos, moves); score_captures(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; case PH_QCHECKS: // Perhaps we should order moves move here? FIXME - numOfMoves = generate_non_capture_checks(pos, moves, dc); + lastMove = generate_non_capture_checks(pos, moves, dc); return; case PH_STOP: + lastMove = curMove + 1; // hack to be friendly for get_next_move() return; default: @@ -161,10 +162,10 @@ void MovePicker::go_next_phase() { } -/// MovePicker::score_captures(), MovePicker::score_noncaptures(), -/// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a -/// numerical move ordering score to each move in a move list. The moves -/// with highest scores will be picked first by pick_move_from_list(). +/// 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(). void MovePicker::score_captures() { // Winning and equal captures in the main search are ordered by MVV/LVA. @@ -183,14 +184,14 @@ void MovePicker::score_captures() { Move m; // Use MVV/LVA ordering - for (int i = 0; i < numOfMoves; i++) + for (MoveStack* cur = moves; cur != lastMove; cur++) { - m = moves[i].move; + m = cur->move; if (move_is_promotion(m)) - moves[i].score = QueenValueMidgame; + cur->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))); + cur->score = int(pos.midgame_value_of_piece_on(move_to(m))) + -int(pos.type_of_piece_on(move_from(m))); } } @@ -198,14 +199,16 @@ 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++) + for (MoveStack* cur = moves; cur != lastMove; cur++) { - from = move_from(moves[i].move); - to = move_to(moves[i].move); + m = cur->move; + from = move_from(m); + to = move_to(m); piece = pos.piece_on(from); hs = H.move_ordering_score(piece, to); @@ -214,23 +217,25 @@ void MovePicker::score_noncaptures() { hs += 1000; // pst based scoring - moves[i].score = hs + pos.pst_delta(piece, from, to); + cur->score = hs + pos.pst_delta(piece, from, to); } } void MovePicker::score_evasions() { - for (int i = 0; i < numOfMoves; i++) + Move m; + + for (MoveStack* cur = moves; cur != lastMove; cur++) { - Move m = moves[i].move; - if (m == ttMoves[0]) - moves[i].score = 2*HistoryMax; + m = cur->move; + if (m == ttMoves[0].move) + cur->score = 2 * HistoryMax; else if (!pos.square_is_empty(move_to(m))) { int seeScore = pos.see(m); - moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore; + cur->score = seeScore + (seeScore >= 0 ? HistoryMax : 0); } else - moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m)); + cur->score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m)); } } @@ -242,33 +247,28 @@ void MovePicker::score_evasions() { Move MovePicker::get_next_move() { - assert(movesPicked >= 0); assert(!pos.is_check() || *phasePtr == PH_EVASIONS || *phasePtr == PH_STOP); assert( pos.is_check() || *phasePtr != PH_EVASIONS); + Move move; + while (true) { - switch (phase) { - - case PH_NULL_MOVE: - go_next_phase(); - return MOVE_NULL; - - 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 != ttMoves[0] - && move != ttMoves[1] + while (curMove != lastMove) + { + move = (curMove++)->move; + + switch (phase) { + + case PH_TT_MOVES: + if ( move != MOVE_NONE + && move_is_legal(pos, move, pinned)) + return move; + break; + + case PH_GOOD_CAPTURES: + if ( move != ttMoves[0].move + && move != ttMoves[1].move && pos.pl_move_is_legal(move, pinned)) { // Check for a non negative SEE now @@ -282,66 +282,48 @@ Move MovePicker::get_next_move() { badCaptures[numOfBadCaptures].move = move; badCaptures[numOfBadCaptures++].score = seeValue; } - } - 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 != ttMoves[0] - && move != ttMoves[1] - && move != killers[0] - && move != killers[1] + break; + + case PH_KILLERS: + if ( move != MOVE_NONE + && move != ttMoves[0].move + && move != ttMoves[1].move + && move_is_legal(pos, move, pinned) + && !pos.move_is_capture(move)) + return move; + break; + + case PH_NONCAPTURES: + if ( move != ttMoves[0].move + && move != ttMoves[1].move + && move != killers[0].move + && move != killers[1].move && pos.pl_move_is_legal(move, pinned)) return move; - } - break; - - case PH_EVASIONS: - if (movesPicked < numOfMoves) - return moves[movesPicked++].move; - break; - - case PH_BAD_CAPTURES: - if (movesPicked < numOfBadCaptures) - return badCaptures[movesPicked++].move; - break; - - case PH_QCAPTURES: - case PH_QCHECKS: - while (movesPicked < numOfMoves) - { - Move move = moves[movesPicked++].move; + break; + + case PH_EVASIONS: + case PH_BAD_CAPTURES: + return move; + + case PH_QCAPTURES: + case PH_QCHECKS: // Maybe postpone the legality check until after futility pruning? - if ( move != ttMoves[0] + if ( move != ttMoves[0].move && pos.pl_move_is_legal(move, pinned)) return move; - } - break; + break; - case PH_STOP: - return MOVE_NONE; + case PH_STOP: + return MOVE_NONE; - default: - assert(false); - break; + default: + assert(false); + break; + } } go_next_phase(); } - return MOVE_NONE; } /// A variant of get_next_move() which takes a lock as a parameter, used to