From fbdabe2975c0e86a04b01c36c9f3eec5494ecf0d Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Thu, 14 Jul 2011 12:12:49 +0100 Subject: [PATCH] Use std library to sort moves Functional change due to the fact that now pick_best() is stable, but should be no change in strenght. Example code and ideas by Rein Halbersma. Signed-off-by: Marco Costalba --- src/bitboard.h | 2 +- src/move.h | 57 +----------------------------------------------- src/movepick.cpp | 27 ++++++++++++++++++----- src/position.cpp | 8 +++---- src/search.cpp | 24 ++++++++------------ 5 files changed, 36 insertions(+), 82 deletions(-) diff --git a/src/bitboard.h b/src/bitboard.h index 0177df8c..55f40eee 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -245,7 +245,7 @@ inline Bitboard attack_span_mask(Color c, Square s) { inline bool squares_aligned(Square s1, Square s2, Square s3) { return (BetweenBB[s1][s2] | BetweenBB[s1][s3] | BetweenBB[s2][s3]) - & ((1ULL << s1) | (1ULL << s2) | (1ULL << s3)); + & ( SetMaskBB[s1] | SetMaskBB[s2] | SetMaskBB[s3]); } diff --git a/src/move.h b/src/move.h index d014dc77..3d977997 100644 --- a/src/move.h +++ b/src/move.h @@ -55,7 +55,7 @@ inline bool operator<(const MoveStack& f, const MoveStack& s) { return f.score < // An helper insertion sort implementation, works with pointers and iterators template -inline void insertion_sort(K firstMove, K lastMove) +inline void sort(K firstMove, K lastMove) { T value; K cur, p, d; @@ -74,61 +74,6 @@ inline void insertion_sort(K firstMove, K lastMove) } } -// Our dedicated sort in range [firstMove, lastMove), first splits -// positive scores from ramining then order seaprately the two sets. -template -inline void sort_moves(T* firstMove, T* lastMove, T** lastPositive) -{ - T tmp; - T *p, *d; - - d = lastMove; - p = firstMove - 1; - - d->score = -1; // right guard - - // Split positives vs non-positives - do { - while ((++p)->score > 0) {} - - if (p != d) - { - while (--d != p && d->score <= 0) {} - - tmp = *p; - *p = *d; - *d = tmp; - } - - } while (p != d); - - // Sort just positive scored moves, remaining only when we get there - insertion_sort(firstMove, p); - *lastPositive = p; -} - -// Picks up the best move in range [curMove, lastMove), one per cycle. -// It is faster then sorting all the moves in advance when moves are few, -// as normally are the possible captures. Note that is not a stable alghoritm. -template -inline T pick_best(T* curMove, T* lastMove) -{ - T bestMove, tmp; - - bestMove = *curMove; - while (++curMove != lastMove) - { - if (bestMove < *curMove) - { - tmp = *curMove; - *curMove = bestMove; - bestMove = tmp; - } - } - return bestMove; -} - - inline Square move_from(Move m) { return Square((m >> 6) & 0x3F); } diff --git a/src/movepick.cpp b/src/movepick.cpp index 07e8ef9d..b9594ba1 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -18,6 +18,7 @@ along with this program. If not, see . */ +#include #include #include "movegen.h" @@ -49,6 +50,19 @@ namespace { 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 ramining + // 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; } + + // Picks and pushes to the front the best move in range [firstMove, lastMove), + // it is faster then sorting all the moves in advance when moves are few, as + // normally are the possible captures. + inline MoveStack* pick_best(MoveStack* firstMove, MoveStack* lastMove) + { + std::swap(*firstMove, *std::max_element(firstMove, lastMove)); + return firstMove; + } } /// Constructors for the MovePicker class. As arguments we pass information @@ -164,14 +178,15 @@ void MovePicker::go_next_phase() { case PH_NONCAPTURES_1: lastNonCapture = lastMove = generate(pos, moves); score_noncaptures(); - sort_moves(moves, lastNonCapture, &lastMove); + lastMove = std::partition(curMove, lastMove, has_positive_score); + sort(curMove, lastMove); return; case PH_NONCAPTURES_2: curMove = lastMove; lastMove = lastNonCapture; if (depth >= 3 * ONE_PLY) - insertion_sort(curMove, lastMove); + sort(curMove, lastMove); return; case PH_BAD_CAPTURES: @@ -306,7 +321,7 @@ Move MovePicker::get_next_move() { break; case PH_GOOD_CAPTURES: - move = pick_best(curMove++, lastMove).move; + move = pick_best(curMove++, lastMove)->move; if (move != ttMove) { assert(captureThreshold <= 0); // Otherwise we must use see instead of see_sign @@ -324,7 +339,7 @@ Move MovePicker::get_next_move() { break; case PH_GOOD_PROBCUT: - move = pick_best(curMove++, lastMove).move; + move = pick_best(curMove++, lastMove)->move; if ( move != ttMove && pos.see(move) > captureThreshold) return move; @@ -349,12 +364,12 @@ Move MovePicker::get_next_move() { break; case PH_BAD_CAPTURES: - move = pick_best(curMove++, lastMove).move; + move = pick_best(curMove++, lastMove)->move; return move; case PH_EVASIONS: case PH_QCAPTURES: - move = pick_best(curMove++, lastMove).move; + move = pick_best(curMove++, lastMove)->move; if (move != ttMove) return move; break; diff --git a/src/position.cpp b/src/position.cpp index 281109b1..cb5370d5 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -513,14 +513,14 @@ bool Position::pl_move_is_legal(Move m, Bitboard pinned) const { assert(piece_color(piece_on(from)) == us); assert(piece_on(king_square(us)) == make_piece(us, KING)); - // En passant captures are a tricky special case. Because they are - // rather uncommon, we do it simply by testing whether the king is attacked - // after the move is made + // En passant captures are a tricky special case. Because they are rather + // uncommon, we do it simply by testing whether the king is attacked after + // the move is made. if (move_is_ep(m)) { Color them = opposite_color(us); Square to = move_to(m); - Square capsq = make_square(square_file(to), square_rank(from)); + Square capsq = to + Square(us == WHITE ? -8 : 8); Square ksq = king_square(us); Bitboard b = occupied_squares(); diff --git a/src/search.cpp b/src/search.cpp index 41992efb..829e1bbe 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -79,16 +79,9 @@ namespace { Move pv[PLY_MAX_PLUS_2]; }; - // RootMoveList struct is just a vector of RootMove objects, - // with an handful of methods above the standard ones. + // RootMoveList struct is mainly a std::vector of RootMove objects struct RootMoveList : public std::vector { - - typedef std::vector Base; - void init(Position& pos, Move searchMoves[]); - void sort() { insertion_sort(begin(), end()); } - void sort_first(int n) { insertion_sort(begin(), begin() + n); } - int bestMoveChanges; }; @@ -1219,7 +1212,7 @@ split_point_start: // At split points actual search starts from here // because all the values but the first are usually set to // -VALUE_INFINITE and we want to keep the same order for all // the moves but the new PV that goes to head. - Rml.sort_first(moveCount); + sort(Rml.begin(), Rml.begin() + moveCount); // Update alpha. In multi-pv we don't use aspiration window, so set // alpha equal to minimum score among the PV lines searched so far. @@ -1555,7 +1548,7 @@ split_point_start: // At split points actual search starts from here bool connected_moves(const Position& pos, Move m1, Move m2) { Square f1, t1, f2, t2; - Piece p; + Piece p1, p2; assert(m1 && move_is_ok(m1)); assert(m2 && move_is_ok(m2)); @@ -1573,17 +1566,18 @@ split_point_start: // At split points actual search starts from here return true; // Case 3: Moving through the vacated square - if ( piece_is_slider(pos.piece_on(f2)) + p2 = pos.piece_on(f2); + if ( piece_is_slider(p2) && bit_is_set(squares_between(f2, t2), f1)) return true; // Case 4: The destination square for m2 is defended by the moving piece in m1 - p = pos.piece_on(t1); - if (bit_is_set(pos.attacks_from(p, t1), t2)) + p1 = pos.piece_on(t1); + if (bit_is_set(pos.attacks_from(p1, t1), t2)) return true; // Case 5: Discovered check, checking piece is the piece moved in m1 - if ( piece_is_slider(p) + if ( piece_is_slider(p1) && bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), f2) && !bit_is_set(squares_between(t1, pos.king_square(pos.side_to_move())), t2)) { @@ -2093,7 +2087,7 @@ split_point_start: // At split points actual search starts from here break; } - Rml.sort(); + sort(Rml.begin(), Rml.end()); } } // namespace -- 2.39.2