]> git.sesse.net Git - stockfish/blob - src/movepick.cpp
Remove recaptures stage in qsearch
[stockfish] / src / movepick.cpp
1 /*
2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3   Copyright (C) 2004-2023 The Stockfish developers (see AUTHORS file)
4
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.
9
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.
14
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/>.
17 */
18
19 #include "movepick.h"
20
21 #include <algorithm>
22 #include <cassert>
23 #include <iterator>
24 #include <utility>
25
26 #include "bitboard.h"
27 #include "position.h"
28
29 namespace Stockfish {
30
31 namespace {
32
33 enum Stages {
34     // generate main search moves
35     MAIN_TT,
36     CAPTURE_INIT,
37     GOOD_CAPTURE,
38     REFUTATION,
39     QUIET_INIT,
40     QUIET,
41     BAD_CAPTURE,
42
43     // generate evasion moves
44     EVASION_TT,
45     EVASION_INIT,
46     EVASION,
47
48     // generate probcut moves
49     PROBCUT_TT,
50     PROBCUT_INIT,
51     PROBCUT,
52
53     // generate qsearch moves
54     QSEARCH_TT,
55     QCAPTURE_INIT,
56     QCAPTURE,
57     QCHECK_INIT,
58     QCHECK
59 };
60
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) {
64
65     for (ExtMove *sortedEnd = begin, *p = begin + 1; p < end; ++p)
66         if (p->value >= limit)
67         {
68             ExtMove tmp = *p, *q;
69             *p          = *++sortedEnd;
70             for (q = sortedEnd; q != begin && *(q - 1) < tmp; --q)
71                 *q = *(q - 1);
72             *q = tmp;
73         }
74 }
75
76 }  // namespace
77
78
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.
84
85 // MovePicker constructor for the main search
86 MovePicker::MovePicker(const Position&              p,
87                        Move                         ttm,
88                        Depth                        d,
89                        const ButterflyHistory*      mh,
90                        const CapturePieceToHistory* cph,
91                        const PieceToHistory**       ch,
92                        const PawnHistory*           ph,
93                        Move                         cm,
94                        const Move*                  killers) :
95     pos(p),
96     mainHistory(mh),
97     captureHistory(cph),
98     continuationHistory(ch),
99     pawnHistory(ph),
100     ttMove(ttm),
101     refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}},
102     depth(d) {
103     assert(d > 0);
104
105     stage = (pos.checkers() ? EVASION_TT : MAIN_TT) + !(ttm && pos.pseudo_legal(ttm));
106 }
107
108 // Constructor for quiescence search
109 MovePicker::MovePicker(const Position&              p,
110                        Move                         ttm,
111                        Depth                        d,
112                        const ButterflyHistory*      mh,
113                        const CapturePieceToHistory* cph,
114                        const PieceToHistory**       ch,
115                        const PawnHistory*           ph) :
116     pos(p),
117     mainHistory(mh),
118     captureHistory(cph),
119     continuationHistory(ch),
120     pawnHistory(ph),
121     ttMove(ttm),
122     depth(d) {
123     assert(d <= 0);
124
125     stage = (pos.checkers() ? EVASION_TT : QSEARCH_TT) + !(ttm && pos.pseudo_legal(ttm));
126 }
127
128 // Constructor for ProbCut: we generate captures with SEE greater
129 // than or equal to the given threshold.
130 MovePicker::MovePicker(const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph) :
131     pos(p),
132     captureHistory(cph),
133     ttMove(ttm),
134     threshold(th) {
135     assert(!pos.checkers());
136
137     stage = PROBCUT_TT
138           + !(ttm && pos.capture_stage(ttm) && pos.pseudo_legal(ttm) && pos.see_ge(ttm, threshold));
139 }
140
141 // Assigns a numerical value to each move in a list, used
142 // for sorting. Captures are ordered by Most Valuable Victim (MVV), preferring
143 // captures with a good history. Quiets moves are ordered using the history tables.
144 template<GenType Type>
145 void MovePicker::score() {
146
147     static_assert(Type == CAPTURES || Type == QUIETS || Type == EVASIONS, "Wrong type");
148
149     [[maybe_unused]] Bitboard threatenedByPawn, threatenedByMinor, threatenedByRook,
150       threatenedPieces;
151     if constexpr (Type == QUIETS)
152     {
153         Color us = pos.side_to_move();
154
155         threatenedByPawn = pos.attacks_by<PAWN>(~us);
156         threatenedByMinor =
157           pos.attacks_by<KNIGHT>(~us) | pos.attacks_by<BISHOP>(~us) | threatenedByPawn;
158         threatenedByRook = pos.attacks_by<ROOK>(~us) | threatenedByMinor;
159
160         // Pieces threatened by pieces of lesser material value
161         threatenedPieces = (pos.pieces(us, QUEEN) & threatenedByRook)
162                          | (pos.pieces(us, ROOK) & threatenedByMinor)
163                          | (pos.pieces(us, KNIGHT, BISHOP) & threatenedByPawn);
164     }
165
166     for (auto& m : *this)
167         if constexpr (Type == CAPTURES)
168             m.value =
169               (7 * int(PieceValue[pos.piece_on(to_sq(m))])
170                + (*captureHistory)[pos.moved_piece(m)][to_sq(m)][type_of(pos.piece_on(to_sq(m)))])
171               / 16;
172
173         else if constexpr (Type == QUIETS)
174         {
175             Piece     pc   = pos.moved_piece(m);
176             PieceType pt   = type_of(pos.moved_piece(m));
177             Square    from = from_sq(m);
178             Square    to   = to_sq(m);
179
180             // histories
181             m.value = 2 * (*mainHistory)[pos.side_to_move()][from_to(m)];
182             m.value += 2 * (*pawnHistory)[pawn_structure(pos)][pc][to];
183             m.value += 2 * (*continuationHistory[0])[pc][to];
184             m.value += (*continuationHistory[1])[pc][to];
185             m.value += (*continuationHistory[2])[pc][to] / 4;
186             m.value += (*continuationHistory[3])[pc][to];
187             m.value += (*continuationHistory[5])[pc][to];
188
189             // bonus for checks
190             m.value += bool(pos.check_squares(pt) & to) * 16384;
191
192             // bonus for escaping from capture
193             m.value += threatenedPieces & from ? (pt == QUEEN && !(to & threatenedByRook)   ? 50000
194                                                   : pt == ROOK && !(to & threatenedByMinor) ? 25000
195                                                   : !(to & threatenedByPawn)                ? 15000
196                                                                                             : 0)
197                                                : 0;
198
199             // malus for putting piece en prise
200             m.value -= !(threatenedPieces & from)
201                        ? (pt == QUEEN ? bool(to & threatenedByRook) * 50000
202                                           + bool(to & threatenedByMinor) * 10000
203                                           + bool(to & threatenedByPawn) * 20000
204                           : pt == ROOK ? bool(to & threatenedByMinor) * 25000
205                                            + bool(to & threatenedByPawn) * 10000
206                           : pt != PAWN ? bool(to & threatenedByPawn) * 15000
207                                        : 0)
208                        : 0;
209         }
210
211         else  // Type == EVASIONS
212         {
213             if (pos.capture_stage(m))
214                 m.value = PieceValue[pos.piece_on(to_sq(m))] - Value(type_of(pos.moved_piece(m)))
215                         + (1 << 28);
216             else
217                 m.value = (*mainHistory)[pos.side_to_move()][from_to(m)]
218                         + (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)]
219                         + (*pawnHistory)[pawn_structure(pos)][pos.moved_piece(m)][to_sq(m)];
220         }
221 }
222
223 // Returns the next move satisfying a predicate function.
224 // It never returns the TT move.
225 template<MovePicker::PickType T, typename Pred>
226 Move MovePicker::select(Pred filter) {
227
228     while (cur < endMoves)
229     {
230         if constexpr (T == Best)
231             std::swap(*cur, *std::max_element(cur, endMoves));
232
233         if (*cur != ttMove && filter())
234             return *cur++;
235
236         cur++;
237     }
238     return MOVE_NONE;
239 }
240
241 // Most important method of the MovePicker class. It
242 // returns a new pseudo-legal move every time it is called until there are no more
243 // moves left, picking the move with the highest score from a list of generated moves.
244 Move MovePicker::next_move(bool skipQuiets) {
245
246 top:
247     switch (stage)
248     {
249
250     case MAIN_TT :
251     case EVASION_TT :
252     case QSEARCH_TT :
253     case PROBCUT_TT :
254         ++stage;
255         return ttMove;
256
257     case CAPTURE_INIT :
258     case PROBCUT_INIT :
259     case QCAPTURE_INIT :
260         cur = endBadCaptures = moves;
261         endMoves             = generate<CAPTURES>(pos, cur);
262
263         score<CAPTURES>();
264         partial_insertion_sort(cur, endMoves, std::numeric_limits<int>::min());
265         ++stage;
266         goto top;
267
268     case GOOD_CAPTURE :
269         if (select<Next>([&]() {
270                 // Move losing capture to endBadCaptures to be tried later
271                 return pos.see_ge(*cur, Value(-cur->value)) ? true
272                                                             : (*endBadCaptures++ = *cur, false);
273             }))
274             return *(cur - 1);
275
276         // Prepare the pointers to loop over the refutations array
277         cur      = std::begin(refutations);
278         endMoves = std::end(refutations);
279
280         // If the countermove is the same as a killer, skip it
281         if (refutations[0].move == refutations[2].move
282             || refutations[1].move == refutations[2].move)
283             --endMoves;
284
285         ++stage;
286         [[fallthrough]];
287
288     case REFUTATION :
289         if (select<Next>([&]() {
290                 return *cur != MOVE_NONE && !pos.capture_stage(*cur) && pos.pseudo_legal(*cur);
291             }))
292             return *(cur - 1);
293         ++stage;
294         [[fallthrough]];
295
296     case QUIET_INIT :
297         if (!skipQuiets)
298         {
299             cur      = endBadCaptures;
300             endMoves = generate<QUIETS>(pos, cur);
301
302             score<QUIETS>();
303             partial_insertion_sort(cur, endMoves, -1960 - 3130 * depth);
304         }
305
306         ++stage;
307         [[fallthrough]];
308
309     case QUIET :
310         if (!skipQuiets && select<Next>([&]() {
311                 return *cur != refutations[0].move && *cur != refutations[1].move
312                     && *cur != refutations[2].move;
313             }))
314             return *(cur - 1);
315
316         // Prepare the pointers to loop over the bad captures
317         cur      = moves;
318         endMoves = endBadCaptures;
319
320         ++stage;
321         [[fallthrough]];
322
323     case BAD_CAPTURE :
324         return select<Next>([]() { return true; });
325
326     case EVASION_INIT :
327         cur      = moves;
328         endMoves = generate<EVASIONS>(pos, cur);
329
330         score<EVASIONS>();
331         ++stage;
332         [[fallthrough]];
333
334     case EVASION :
335         return select<Best>([]() { return true; });
336
337     case PROBCUT :
338         return select<Next>([&]() { return pos.see_ge(*cur, threshold); });
339
340     case QCAPTURE :
341         if (select<Next>([]() { return true; }))
342             return *(cur - 1);
343
344         // If we did not find any move and we do not try checks, we have finished
345         if (depth != DEPTH_QS_CHECKS)
346             return MOVE_NONE;
347
348         ++stage;
349         [[fallthrough]];
350
351     case QCHECK_INIT :
352         cur      = moves;
353         endMoves = generate<QUIET_CHECKS>(pos, cur);
354
355         ++stage;
356         [[fallthrough]];
357
358     case QCHECK :
359         return select<Next>([]() { return true; });
360     }
361
362     assert(false);
363     return MOVE_NONE;  // Silence warning
364 }
365
366 }  // namespace Stockfish