2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2023 The Stockfish developers (see AUTHORS file)
5 Stockfish is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
10 Stockfish is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
34 // generate main search moves
43 // generate evasion moves
48 // generate probcut moves
53 // generate qsearch moves
61 // Sort moves in descending order up to and including
62 // a given limit. The order of moves smaller than the limit is left unspecified.
63 void partial_insertion_sort(ExtMove* begin, ExtMove* end, int limit) {
65 for (ExtMove *sortedEnd = begin, *p = begin + 1; p < end; ++p)
66 if (p->value >= limit)
70 for (q = sortedEnd; q != begin && *(q - 1) < tmp; --q)
79 // Constructors of the MovePicker class. As arguments, we pass information
80 // to help it return the (presumably) good moves first, to decide which
81 // moves to return (in the quiescence search, for instance, we only want to
82 // search captures, promotions, and some checks) and how important a good
83 // move ordering is at the current node.
85 // MovePicker constructor for the main search
86 MovePicker::MovePicker(const Position& p,
89 const ButterflyHistory* mh,
90 const CapturePieceToHistory* cph,
91 const PieceToHistory** ch,
92 const PawnHistory* ph,
94 const Move* killers) :
98 continuationHistory(ch),
101 refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}},
105 stage = (pos.checkers() ? EVASION_TT : MAIN_TT) + !(ttm && pos.pseudo_legal(ttm));
108 // Constructor for quiescence search
109 MovePicker::MovePicker(const Position& p,
112 const ButterflyHistory* mh,
113 const CapturePieceToHistory* cph,
114 const PieceToHistory** ch,
115 const PawnHistory* ph,
120 continuationHistory(ch),
127 stage = (pos.checkers() ? EVASION_TT : QSEARCH_TT) + !(ttm && pos.pseudo_legal(ttm));
130 // Constructor for ProbCut: we generate captures with SEE greater
131 // than or equal to the given threshold.
132 MovePicker::MovePicker(const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph) :
137 assert(!pos.checkers());
140 + !(ttm && pos.capture_stage(ttm) && pos.pseudo_legal(ttm) && pos.see_ge(ttm, threshold));
143 // Assigns a numerical value to each move in a list, used
144 // for sorting. Captures are ordered by Most Valuable Victim (MVV), preferring
145 // captures with a good history. Quiets moves are ordered using the history tables.
146 template<GenType Type>
147 void MovePicker::score() {
149 static_assert(Type == CAPTURES || Type == QUIETS || Type == EVASIONS, "Wrong type");
151 [[maybe_unused]] Bitboard threatenedByPawn, threatenedByMinor, threatenedByRook,
153 if constexpr (Type == QUIETS)
155 Color us = pos.side_to_move();
157 threatenedByPawn = pos.attacks_by<PAWN>(~us);
159 pos.attacks_by<KNIGHT>(~us) | pos.attacks_by<BISHOP>(~us) | threatenedByPawn;
160 threatenedByRook = pos.attacks_by<ROOK>(~us) | threatenedByMinor;
162 // Pieces threatened by pieces of lesser material value
163 threatenedPieces = (pos.pieces(us, QUEEN) & threatenedByRook)
164 | (pos.pieces(us, ROOK) & threatenedByMinor)
165 | (pos.pieces(us, KNIGHT, BISHOP) & threatenedByPawn);
168 for (auto& m : *this)
169 if constexpr (Type == CAPTURES)
171 (7 * int(PieceValue[pos.piece_on(to_sq(m))])
172 + (*captureHistory)[pos.moved_piece(m)][to_sq(m)][type_of(pos.piece_on(to_sq(m)))])
175 else if constexpr (Type == QUIETS)
177 Piece pc = pos.moved_piece(m);
178 PieceType pt = type_of(pos.moved_piece(m));
179 Square from = from_sq(m);
180 Square to = to_sq(m);
183 m.value = 2 * (*mainHistory)[pos.side_to_move()][from_to(m)];
184 m.value += 2 * (*pawnHistory)[pawn_structure(pos)][pc][to];
185 m.value += 2 * (*continuationHistory[0])[pc][to];
186 m.value += (*continuationHistory[1])[pc][to];
187 m.value += (*continuationHistory[2])[pc][to] / 4;
188 m.value += (*continuationHistory[3])[pc][to];
189 m.value += (*continuationHistory[5])[pc][to];
192 m.value += bool(pos.check_squares(pt) & to) * 16384;
194 // bonus for escaping from capture
195 m.value += threatenedPieces & from ? (pt == QUEEN && !(to & threatenedByRook) ? 50000
196 : pt == ROOK && !(to & threatenedByMinor) ? 25000
197 : !(to & threatenedByPawn) ? 15000
201 // malus for putting piece en prise
202 m.value -= !(threatenedPieces & from)
203 ? (pt == QUEEN ? bool(to & threatenedByRook) * 50000
204 + bool(to & threatenedByMinor) * 10000
205 + bool(to & threatenedByPawn) * 20000
206 : pt == ROOK ? bool(to & threatenedByMinor) * 25000
207 + bool(to & threatenedByPawn) * 10000
208 : pt != PAWN ? bool(to & threatenedByPawn) * 15000
213 else // Type == EVASIONS
215 if (pos.capture_stage(m))
216 m.value = PieceValue[pos.piece_on(to_sq(m))] - Value(type_of(pos.moved_piece(m)))
219 m.value = (*mainHistory)[pos.side_to_move()][from_to(m)]
220 + (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)]
221 + (*pawnHistory)[pawn_structure(pos)][pos.moved_piece(m)][to_sq(m)];
225 // Returns the next move satisfying a predicate function.
226 // It never returns the TT move.
227 template<MovePicker::PickType T, typename Pred>
228 Move MovePicker::select(Pred filter) {
230 while (cur < endMoves)
232 if constexpr (T == Best)
233 std::swap(*cur, *std::max_element(cur, endMoves));
235 if (*cur != ttMove && filter())
243 // Most important method of the MovePicker class. It
244 // returns a new pseudo-legal move every time it is called until there are no more
245 // moves left, picking the move with the highest score from a list of generated moves.
246 Move MovePicker::next_move(bool skipQuiets) {
262 cur = endBadCaptures = moves;
263 endMoves = generate<CAPTURES>(pos, cur);
266 partial_insertion_sort(cur, endMoves, std::numeric_limits<int>::min());
271 if (select<Next>([&]() {
272 // Move losing capture to endBadCaptures to be tried later
273 return pos.see_ge(*cur, Value(-cur->value)) ? true
274 : (*endBadCaptures++ = *cur, false);
278 // Prepare the pointers to loop over the refutations array
279 cur = std::begin(refutations);
280 endMoves = std::end(refutations);
282 // If the countermove is the same as a killer, skip it
283 if (refutations[0].move == refutations[2].move
284 || refutations[1].move == refutations[2].move)
291 if (select<Next>([&]() {
292 return *cur != MOVE_NONE && !pos.capture_stage(*cur) && pos.pseudo_legal(*cur);
301 cur = endBadCaptures;
302 endMoves = generate<QUIETS>(pos, cur);
305 partial_insertion_sort(cur, endMoves, -1960 - 3130 * depth);
312 if (!skipQuiets && select<Next>([&]() {
313 return *cur != refutations[0].move && *cur != refutations[1].move
314 && *cur != refutations[2].move;
318 // Prepare the pointers to loop over the bad captures
320 endMoves = endBadCaptures;
326 return select<Next>([]() { return true; });
330 endMoves = generate<EVASIONS>(pos, cur);
337 return select<Best>([]() { return true; });
340 return select<Next>([&]() { return pos.see_ge(*cur, threshold); });
344 [&]() { return depth > DEPTH_QS_RECAPTURES || to_sq(*cur) == recaptureSquare; }))
347 // If we did not find any move and we do not try checks, we have finished
348 if (depth != DEPTH_QS_CHECKS)
356 endMoves = generate<QUIET_CHECKS>(pos, cur);
362 return select<Next>([]() { return true; });
366 return MOVE_NONE; // Silence warning
369 } // namespace Stockfish