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 ramining
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 then 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 SearchStack* 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
92 // depth and far from beta.
93 if (ss && ss->eval < beta - PawnValueMidgame && d < 3 * ONE_PLY)
94 captureThreshold = -PawnValueMidgame;
96 phasePtr = MainSearchTable;
99 ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
100 phasePtr += int(ttMove == MOVE_NONE) - 1;
104 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, Square recaptureSq)
107 assert(d <= DEPTH_ZERO);
110 phasePtr = EvasionTable;
111 else if (d >= DEPTH_QS_CHECKS)
112 phasePtr = QsearchWithChecksTable;
113 else if (d >= DEPTH_QS_RECAPTURES)
115 phasePtr = QsearchWithoutChecksTable;
117 // Skip TT move if is not a capture or a promotion, this avoids
118 // qsearch tree explosion due to a possible perpetual check or
119 // similar rare cases when TT table is full.
120 if (ttm != MOVE_NONE && !pos.move_is_capture_or_promotion(ttm))
125 phasePtr = QsearchRecapturesTable;
126 recaptureSquare = recaptureSq;
130 ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
131 phasePtr += int(ttMove == MOVE_NONE) - 1;
135 MovePicker::MovePicker(const Position& p, Move ttm, const History& h, PieceType parentCapture)
138 assert (!pos.in_check());
140 // In ProbCut we consider only captures better than parent's move
141 captureThreshold = piece_value_midgame(Piece(parentCapture));
142 phasePtr = ProbCutTable;
144 if ( ttm != MOVE_NONE
145 && (!pos.move_is_capture(ttm) || pos.see(ttm) <= captureThreshold))
148 ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
149 phasePtr += int(ttMove == MOVE_NONE) - 1;
154 /// MovePicker::go_next_phase() generates, scores and sorts the next bunch
155 /// of moves when there are no more moves to try for the current phase.
157 void MovePicker::go_next_phase() {
160 phase = *(++phasePtr);
164 lastMove = curMove + 1;
167 case PH_GOOD_CAPTURES:
168 case PH_GOOD_PROBCUT:
169 lastMove = generate<MV_CAPTURE>(pos, moves);
175 lastMove = curMove + 2;
178 case PH_NONCAPTURES_1:
179 lastNonCapture = lastMove = generate<MV_NON_CAPTURE>(pos, moves);
181 lastMove = std::partition(curMove, lastMove, has_positive_score);
182 sort<MoveStack>(curMove, lastMove);
185 case PH_NONCAPTURES_2:
187 lastMove = lastNonCapture;
188 if (depth >= 3 * ONE_PLY)
189 sort<MoveStack>(curMove, lastMove);
192 case PH_BAD_CAPTURES:
193 // Bad captures SEE value is already calculated so just pick
194 // them in order to get SEE move ordering.
195 curMove = badCaptures;
196 lastMove = moves + MAX_MOVES;
200 assert(pos.in_check());
201 lastMove = generate<MV_EVASION>(pos, moves);
206 lastMove = generate<MV_CAPTURE>(pos, moves);
211 lastMove = generate<MV_CAPTURE>(pos, moves);
215 lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
219 lastMove = curMove + 1; // Avoid another go_next_phase() call
229 /// MovePicker::score_captures(), MovePicker::score_noncaptures() and
230 /// MovePicker::score_evasions() assign a numerical move ordering score
231 /// to each move in a move list. The moves with highest scores will be
232 /// picked first by get_next_move().
234 void MovePicker::score_captures() {
235 // Winning and equal captures in the main search are ordered by MVV/LVA.
236 // Suprisingly, this appears to perform slightly better than SEE based
237 // move ordering. The reason is probably that in a position with a winning
238 // capture, capturing a more valuable (but sufficiently defended) piece
239 // first usually doesn't hurt. The opponent will have to recapture, and
240 // the hanging piece will still be hanging (except in the unusual cases
241 // where it is possible to recapture with the hanging piece). Exchanging
242 // big pieces before capturing a hanging piece probably helps to reduce
244 // In main search we want to push captures with negative SEE values to
245 // badCaptures[] array, but instead of doing it now we delay till when
246 // the move has been picked up in pick_move_from_list(), this way we save
247 // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).
250 // Use MVV/LVA ordering
251 for (MoveStack* cur = moves; cur != lastMove; cur++)
254 cur->score = piece_value_midgame(pos.piece_on(move_to(m)))
255 - piece_type(pos.piece_on(move_from(m)));
257 if (move_is_promotion(m))
258 cur->score += QueenValueMidgame;
262 void MovePicker::score_noncaptures() {
267 for (MoveStack* cur = moves; cur != lastMove; cur++)
271 cur->score = H.value(pos.piece_on(from), move_to(m));
275 void MovePicker::score_evasions() {
276 // Try good captures ordered by MVV/LVA, then non-captures if
277 // destination square is not under attack, ordered by history
278 // value, and at the end bad-captures and non-captures with a
279 // negative SEE. This last group is ordered by the SEE score.
283 // Skip if we don't have at least two moves to order
284 if (lastMove < moves + 2)
287 for (MoveStack* cur = moves; cur != lastMove; cur++)
290 if ((seeScore = pos.see_sign(m)) < 0)
291 cur->score = seeScore - History::MaxValue; // Be sure we are at the bottom
292 else if (pos.move_is_capture(m))
293 cur->score = piece_value_midgame(pos.piece_on(move_to(m)))
294 - piece_type(pos.piece_on(move_from(m))) + History::MaxValue;
296 cur->score = H.value(pos.piece_on(move_from(m)), move_to(m));
300 /// MovePicker::get_next_move() is the most important method of the MovePicker
301 /// class. It returns a new pseudo legal move every time it is called, until there
302 /// are no more moves left. It picks the move with the biggest score from a list
303 /// of generated moves taking care not to return the tt move if has already been
304 /// searched previously. Note that this function is not thread safe so should be
305 /// lock protected by caller when accessed through a shared MovePicker object.
307 Move MovePicker::get_next_move() {
313 while (curMove == lastMove)
323 case PH_GOOD_CAPTURES:
324 move = pick_best(curMove++, lastMove)->move;
327 assert(captureThreshold <= 0); // Otherwise we must use see instead of see_sign
329 // Check for a non negative SEE now
330 int seeValue = pos.see_sign(move);
331 if (seeValue >= captureThreshold)
334 // Losing capture, move it to the tail of the array, note
335 // that move has now been already checked for pseudo legality.
336 (--badCaptures)->move = move;
337 badCaptures->score = seeValue;
341 case PH_GOOD_PROBCUT:
342 move = pick_best(curMove++, lastMove)->move;
344 && pos.see(move) > captureThreshold)
349 move = (curMove++)->move;
350 if ( move != MOVE_NONE
351 && pos.move_is_pl(move)
353 && !pos.move_is_capture(move))
357 case PH_NONCAPTURES_1:
358 case PH_NONCAPTURES_2:
359 move = (curMove++)->move;
361 && move != killers[0].move
362 && move != killers[1].move)
366 case PH_BAD_CAPTURES:
367 move = pick_best(curMove++, lastMove)->move;
372 move = pick_best(curMove++, lastMove)->move;
378 move = (curMove++)->move;
379 if (move_to(move) == recaptureSquare)
384 move = (curMove++)->move;