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]);
}
// An helper insertion sort implementation, works with pointers and iterators
template<typename T, typename K>
-inline void insertion_sort(K firstMove, K lastMove)
+inline void sort(K firstMove, K lastMove)
{
T value;
K cur, p, d;
}
}
-// Our dedicated sort in range [firstMove, lastMove), first splits
-// positive scores from ramining then order seaprately the two sets.
-template<typename T>
-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<T, T*>(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<typename T>
-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);
}
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
+#include <algorithm>
#include <cassert>
#include "movegen.h"
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
case PH_NONCAPTURES_1:
lastNonCapture = lastMove = generate<MV_NON_CAPTURE>(pos, moves);
score_noncaptures();
- sort_moves(moves, lastNonCapture, &lastMove);
+ lastMove = std::partition(curMove, lastMove, has_positive_score);
+ sort<MoveStack>(curMove, lastMove);
return;
case PH_NONCAPTURES_2:
curMove = lastMove;
lastMove = lastNonCapture;
if (depth >= 3 * ONE_PLY)
- insertion_sort<MoveStack>(curMove, lastMove);
+ sort<MoveStack>(curMove, lastMove);
return;
case PH_BAD_CAPTURES:
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
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;
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;
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();
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<RootMove> {
-
- typedef std::vector<RootMove> Base;
-
void init(Position& pos, Move searchMoves[]);
- void sort() { insertion_sort<RootMove, Base::iterator>(begin(), end()); }
- void sort_first(int n) { insertion_sort<RootMove, Base::iterator>(begin(), begin() + n); }
-
int bestMoveChanges;
};
// 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<RootMove>(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.
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));
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))
{
break;
}
- Rml.sort();
+ sort<RootMove>(Rml.begin(), Rml.end());
}
} // namespace
projects / stockfish / commitdiff