2 Stockfish, a UCI chess playing engine derived from Glaurung 2.1
3 Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
4 Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
6 Stockfish is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
12 Stockfish is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
32 PH_TT_MOVE, // Transposition table move
33 PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= captureThreshold (captureThreshold <= 0)
34 PH_GOOD_PROBCUT, // Queen promotions and captures with SEE values > captureThreshold (captureThreshold >= 0)
35 PH_KILLERS, // Killer moves from the current ply
36 PH_NONCAPTURES_1, // Non-captures and underpromotions with positive score
37 PH_NONCAPTURES_2, // Non-captures and underpromotions with non-positive score
38 PH_BAD_CAPTURES, // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0)
39 PH_EVASIONS, // Check evasions
40 PH_QCAPTURES, // Captures in quiescence search
41 PH_QRECAPTURES, // Recaptures in quiescence search
42 PH_QCHECKS, // Non-capture checks in quiescence search
47 const uint8_t MainSearchTable[] = { PH_TT_MOVE, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES_1, PH_NONCAPTURES_2, PH_BAD_CAPTURES, PH_STOP };
48 const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP };
49 const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP };
50 const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP };
51 const uint8_t QsearchRecapturesTable[] = { PH_TT_MOVE, PH_QRECAPTURES, PH_STOP };
52 const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP };
54 // Unary predicate used by std::partition to split positive scores from remaining
55 // ones so to sort separately the two sets, and with the second sort delayed.
56 inline bool has_positive_score(const MoveStack& move) { return move.score > 0; }
58 // Picks and pushes to the front the best move in range [firstMove, lastMove),
59 // it is faster than sorting all the moves in advance when moves are few, as
60 // normally are the possible captures.
61 inline MoveStack* pick_best(MoveStack* firstMove, MoveStack* lastMove)
63 std::swap(*firstMove, *std::max_element(firstMove, lastMove));
68 /// Constructors for the MovePicker class. As arguments we pass information
69 /// to help it to return the presumably good moves first, to decide which
70 /// moves to return (in the quiescence search, for instance, we only want to
71 /// search captures, promotions and some checks) and about how important good
72 /// move ordering is at the current node.
74 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h,
75 Search::Stack* ss, Value beta) : pos(p), H(h), depth(d) {
77 badCaptures = moves + MAX_MOVES;
79 assert(d > DEPTH_ZERO);
83 killers[0].move = killers[1].move = MOVE_NONE;
84 phasePtr = EvasionTable;
88 killers[0].move = ss->killers[0];
89 killers[1].move = ss->killers[1];
91 // Consider sligtly negative captures as good if at low depth and far from beta
92 if (ss && ss->eval < beta - PawnValueMidgame && d < 3 * ONE_PLY)
93 captureThreshold = -PawnValueMidgame;
95 // Consider negative captures as good if still enough to reach beta
96 else if (ss && ss->eval > beta)
97 captureThreshold = beta - ss->eval;
99 phasePtr = MainSearchTable;
102 ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE);
103 phasePtr += int(ttMove == MOVE_NONE) - 1;
107 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, Square recaptureSq)
110 assert(d <= DEPTH_ZERO);
113 phasePtr = EvasionTable;
114 else if (d >= DEPTH_QS_CHECKS)
115 phasePtr = QsearchWithChecksTable;
116 else if (d >= DEPTH_QS_RECAPTURES)
118 phasePtr = QsearchWithoutChecksTable;
120 // Skip TT move if is not a capture or a promotion, this avoids
121 // qsearch tree explosion due to a possible perpetual check or
122 // similar rare cases when TT table is full.
123 if (ttm != MOVE_NONE && !pos.is_capture_or_promotion(ttm))
128 phasePtr = QsearchRecapturesTable;
129 recaptureSquare = recaptureSq;
133 ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE);
134 phasePtr += int(ttMove == MOVE_NONE) - 1;
138 MovePicker::MovePicker(const Position& p, Move ttm, const History& h, PieceType parentCapture)
141 assert (!pos.in_check());
143 // In ProbCut we consider only captures better than parent's move
144 captureThreshold = PieceValueMidgame[Piece(parentCapture)];
145 phasePtr = ProbCutTable;
147 if ( ttm != MOVE_NONE
148 && (!pos.is_capture(ttm) || pos.see(ttm) <= captureThreshold))
151 ttMove = (ttm && pos.is_pseudo_legal(ttm) ? ttm : MOVE_NONE);
152 phasePtr += int(ttMove == MOVE_NONE) - 1;
157 /// MovePicker::go_next_phase() generates, scores and sorts the next bunch
158 /// of moves when there are no more moves to try for the current phase.
160 void MovePicker::go_next_phase() {
163 phase = *(++phasePtr);
167 lastMove = curMove + 1;
170 case PH_GOOD_CAPTURES:
171 case PH_GOOD_PROBCUT:
172 lastMove = generate<MV_CAPTURE>(pos, moves);
178 lastMove = curMove + 2;
181 case PH_NONCAPTURES_1:
182 lastNonCapture = lastMove = generate<MV_NON_CAPTURE>(pos, moves);
184 lastMove = std::partition(curMove, lastMove, has_positive_score);
185 sort<MoveStack>(curMove, lastMove);
188 case PH_NONCAPTURES_2:
190 lastMove = lastNonCapture;
191 if (depth >= 3 * ONE_PLY)
192 sort<MoveStack>(curMove, lastMove);
195 case PH_BAD_CAPTURES:
196 // Bad captures SEE value is already calculated so just pick
197 // them in order to get SEE move ordering.
198 curMove = badCaptures;
199 lastMove = moves + MAX_MOVES;
203 assert(pos.in_check());
204 lastMove = generate<MV_EVASION>(pos, moves);
209 lastMove = generate<MV_CAPTURE>(pos, moves);
214 lastMove = generate<MV_CAPTURE>(pos, moves);
218 lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
222 lastMove = curMove + 1; // Avoid another go_next_phase() call
232 /// MovePicker::score_captures(), MovePicker::score_noncaptures() and
233 /// MovePicker::score_evasions() assign a numerical move ordering score
234 /// to each move in a move list. The moves with highest scores will be
235 /// picked first by next_move().
237 void MovePicker::score_captures() {
238 // Winning and equal captures in the main search are ordered by MVV/LVA.
239 // Suprisingly, this appears to perform slightly better than SEE based
240 // move ordering. The reason is probably that in a position with a winning
241 // capture, capturing a more valuable (but sufficiently defended) piece
242 // first usually doesn't hurt. The opponent will have to recapture, and
243 // the hanging piece will still be hanging (except in the unusual cases
244 // where it is possible to recapture with the hanging piece). Exchanging
245 // big pieces before capturing a hanging piece probably helps to reduce
247 // In main search we want to push captures with negative SEE values to
248 // badCaptures[] array, but instead of doing it now we delay till when
249 // the move has been picked up in pick_move_from_list(), this way we save
250 // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).
253 // Use MVV/LVA ordering
254 for (MoveStack* cur = moves; cur != lastMove; cur++)
257 cur->score = PieceValueMidgame[pos.piece_on(move_to(m))]
258 - type_of(pos.piece_on(move_from(m)));
261 cur->score += PieceValueMidgame[Piece(promotion_piece_type(m))];
265 void MovePicker::score_noncaptures() {
270 for (MoveStack* cur = moves; cur != lastMove; cur++)
274 cur->score = H.value(pos.piece_on(from), move_to(m));
278 void MovePicker::score_evasions() {
279 // Try good captures ordered by MVV/LVA, then non-captures if
280 // destination square is not under attack, ordered by history
281 // value, and at the end bad-captures and non-captures with a
282 // negative SEE. This last group is ordered by the SEE score.
286 // Skip if we don't have at least two moves to order
287 if (lastMove < moves + 2)
290 for (MoveStack* cur = moves; cur != lastMove; cur++)
293 if ((seeScore = pos.see_sign(m)) < 0)
294 cur->score = seeScore - History::MaxValue; // Be sure we are at the bottom
295 else if (pos.is_capture(m))
296 cur->score = PieceValueMidgame[pos.piece_on(move_to(m))]
297 - type_of(pos.piece_on(move_from(m))) + History::MaxValue;
299 cur->score = H.value(pos.piece_on(move_from(m)), move_to(m));
303 /// MovePicker::next_move() is the most important method of the MovePicker class.
304 /// It returns a new pseudo legal move every time it is called, until there
305 /// are no more moves left. It picks the move with the biggest score from a list
306 /// of generated moves taking care not to return the tt move if has already been
307 /// searched previously. Note that this function is not thread safe so should be
308 /// lock protected by caller when accessed through a shared MovePicker object.
310 Move MovePicker::next_move() {
316 while (curMove == lastMove)
326 case PH_GOOD_CAPTURES:
327 move = pick_best(curMove++, lastMove)->move;
330 assert(captureThreshold <= 0); // Otherwise we must use see instead of see_sign
332 // Check for a non negative SEE now
333 int seeValue = pos.see_sign(move);
334 if (seeValue >= captureThreshold)
337 // Losing capture, move it to the tail of the array
338 (--badCaptures)->move = move;
339 badCaptures->score = seeValue;
343 case PH_GOOD_PROBCUT:
344 move = pick_best(curMove++, lastMove)->move;
346 && pos.see(move) > captureThreshold)
351 move = (curMove++)->move;
352 if ( move != MOVE_NONE
353 && pos.is_pseudo_legal(move)
355 && !pos.is_capture(move))
359 case PH_NONCAPTURES_1:
360 case PH_NONCAPTURES_2:
361 move = (curMove++)->move;
363 && move != killers[0].move
364 && move != killers[1].move)
368 case PH_BAD_CAPTURES:
369 move = pick_best(curMove++, lastMove)->move;
374 move = pick_best(curMove++, lastMove)->move;
380 move = (curMove++)->move;
381 if (move_to(move) == recaptureSquare)
386 move = (curMove++)->move;