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/>.
31 PH_TT_MOVE, // Transposition table move
32 PH_GOOD_CAPTURES, // Queen promotions and captures with SEE values >= captureThreshold (captureThreshold <= 0)
33 PH_GOOD_PROBCUT, // Queen promotions and captures with SEE values > captureThreshold (captureThreshold >= 0)
34 PH_KILLERS, // Killer moves from the current ply
35 PH_NONCAPTURES_1, // Non-captures and underpromotions with positive score
36 PH_NONCAPTURES_2, // Non-captures and underpromotions with non-positive score
37 PH_BAD_CAPTURES, // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0)
38 PH_EVASIONS, // Check evasions
39 PH_QCAPTURES, // Captures in quiescence search
40 PH_QRECAPTURES, // Recaptures in quiescence search
41 PH_QCHECKS, // Non-capture checks in quiescence search
46 const uint8_t MainSearchTable[] = { PH_TT_MOVE, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES_1, PH_NONCAPTURES_2, PH_BAD_CAPTURES, PH_STOP };
47 const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP };
48 const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP };
49 const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP };
50 const uint8_t QsearchRecapturesTable[] = { PH_TT_MOVE, PH_QRECAPTURES, PH_STOP };
51 const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP };
54 /// Constructors for the MovePicker class. As arguments we pass information
55 /// to help it to return the presumably good moves first, to decide which
56 /// moves to return (in the quiescence search, for instance, we only want to
57 /// search captures, promotions and some checks) and about how important good
58 /// move ordering is at the current node.
60 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h,
61 SearchStack* ss, Value beta) : pos(p), H(h), depth(d) {
63 badCaptures = moves + MAX_MOVES;
65 assert(d > DEPTH_ZERO);
69 killers[0].move = killers[1].move = MOVE_NONE;
70 phasePtr = EvasionTable;
74 killers[0].move = ss->killers[0];
75 killers[1].move = ss->killers[1];
77 // Consider sligtly negative captures as good if at low
78 // depth and far from beta.
79 if (ss && ss->eval < beta - PawnValueMidgame && d < 3 * ONE_PLY)
80 captureThreshold = -PawnValueMidgame;
82 phasePtr = MainSearchTable;
85 ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
86 phasePtr += int(ttMove == MOVE_NONE) - 1;
90 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h, Square recaptureSq)
93 assert(d <= DEPTH_ZERO);
96 phasePtr = EvasionTable;
97 else if (d >= DEPTH_QS_CHECKS)
98 phasePtr = QsearchWithChecksTable;
99 else if (d >= DEPTH_QS_RECAPTURES)
101 phasePtr = QsearchWithoutChecksTable;
103 // Skip TT move if is not a capture or a promotion, this avoids
104 // qsearch tree explosion due to a possible perpetual check or
105 // similar rare cases when TT table is full.
106 if (ttm != MOVE_NONE && !pos.move_is_capture_or_promotion(ttm))
111 phasePtr = QsearchRecapturesTable;
112 recaptureSquare = recaptureSq;
116 ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
117 phasePtr += int(ttMove == MOVE_NONE) - 1;
121 MovePicker::MovePicker(const Position& p, Move ttm, const History& h, PieceType parentCapture)
124 assert (!pos.in_check());
126 // In ProbCut we consider only captures better than parent's move
127 captureThreshold = piece_value_midgame(Piece(parentCapture));
128 phasePtr = ProbCutTable;
130 if ( ttm != MOVE_NONE
131 && (!pos.move_is_capture(ttm) || pos.see(ttm) <= captureThreshold))
134 ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
135 phasePtr += int(ttMove == MOVE_NONE) - 1;
140 /// MovePicker::go_next_phase() generates, scores and sorts the next bunch
141 /// of moves when there are no more moves to try for the current phase.
143 void MovePicker::go_next_phase() {
146 phase = *(++phasePtr);
150 lastMove = curMove + 1;
153 case PH_GOOD_CAPTURES:
154 case PH_GOOD_PROBCUT:
155 lastMove = generate<MV_CAPTURE>(pos, moves);
161 lastMove = curMove + 2;
164 case PH_NONCAPTURES_1:
165 lastNonCapture = lastMove = generate<MV_NON_CAPTURE>(pos, moves);
167 sort_moves(moves, lastNonCapture, &lastMove);
170 case PH_NONCAPTURES_2:
172 lastMove = lastNonCapture;
173 if (depth >= 3 * ONE_PLY)
174 insertion_sort<MoveStack>(curMove, lastMove);
177 case PH_BAD_CAPTURES:
178 // Bad captures SEE value is already calculated so just pick
179 // them in order to get SEE move ordering.
180 curMove = badCaptures;
181 lastMove = moves + MAX_MOVES;
185 assert(pos.in_check());
186 lastMove = generate<MV_EVASION>(pos, moves);
191 lastMove = generate<MV_CAPTURE>(pos, moves);
196 lastMove = generate<MV_CAPTURE>(pos, moves);
200 lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
204 lastMove = curMove + 1; // Avoid another go_next_phase() call
214 /// MovePicker::score_captures(), MovePicker::score_noncaptures() and
215 /// MovePicker::score_evasions() assign a numerical move ordering score
216 /// to each move in a move list. The moves with highest scores will be
217 /// picked first by get_next_move().
219 void MovePicker::score_captures() {
220 // Winning and equal captures in the main search are ordered by MVV/LVA.
221 // Suprisingly, this appears to perform slightly better than SEE based
222 // move ordering. The reason is probably that in a position with a winning
223 // capture, capturing a more valuable (but sufficiently defended) piece
224 // first usually doesn't hurt. The opponent will have to recapture, and
225 // the hanging piece will still be hanging (except in the unusual cases
226 // where it is possible to recapture with the hanging piece). Exchanging
227 // big pieces before capturing a hanging piece probably helps to reduce
229 // In main search we want to push captures with negative SEE values to
230 // badCaptures[] array, but instead of doing it now we delay till when
231 // the move has been picked up in pick_move_from_list(), this way we save
232 // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).
235 // Use MVV/LVA ordering
236 for (MoveStack* cur = moves; cur != lastMove; cur++)
239 cur->score = piece_value_midgame(pos.piece_on(move_to(m)))
240 - piece_type(pos.piece_on(move_from(m)));
242 if (move_is_promotion(m))
243 cur->score += QueenValueMidgame;
247 void MovePicker::score_noncaptures() {
252 for (MoveStack* cur = moves; cur != lastMove; cur++)
256 cur->score = H.value(pos.piece_on(from), move_to(m));
260 void MovePicker::score_evasions() {
261 // Try good captures ordered by MVV/LVA, then non-captures if
262 // destination square is not under attack, ordered by history
263 // value, and at the end bad-captures and non-captures with a
264 // negative SEE. This last group is ordered by the SEE score.
268 // Skip if we don't have at least two moves to order
269 if (lastMove < moves + 2)
272 for (MoveStack* cur = moves; cur != lastMove; cur++)
275 if ((seeScore = pos.see_sign(m)) < 0)
276 cur->score = seeScore - History::MaxValue; // Be sure we are at the bottom
277 else if (pos.move_is_capture(m))
278 cur->score = piece_value_midgame(pos.piece_on(move_to(m)))
279 - piece_type(pos.piece_on(move_from(m))) + History::MaxValue;
281 cur->score = H.value(pos.piece_on(move_from(m)), move_to(m));
285 /// MovePicker::get_next_move() is the most important method of the MovePicker
286 /// class. It returns a new pseudo legal move every time it is called, until there
287 /// are no more moves left. It picks the move with the biggest score from a list
288 /// of generated moves taking care not to return the tt move if has already been
289 /// searched previously. Note that this function is not thread safe so should be
290 /// lock protected by caller when accessed through a shared MovePicker object.
292 Move MovePicker::get_next_move() {
298 while (curMove == lastMove)
308 case PH_GOOD_CAPTURES:
309 move = pick_best(curMove++, lastMove).move;
312 assert(captureThreshold <= 0); // Otherwise we must use see instead of see_sign
314 // Check for a non negative SEE now
315 int seeValue = pos.see_sign(move);
316 if (seeValue >= captureThreshold)
319 // Losing capture, move it to the tail of the array, note
320 // that move has now been already checked for pseudo legality.
321 (--badCaptures)->move = move;
322 badCaptures->score = seeValue;
326 case PH_GOOD_PROBCUT:
327 move = pick_best(curMove++, lastMove).move;
329 && pos.see(move) > captureThreshold)
334 move = (curMove++)->move;
335 if ( move != MOVE_NONE
336 && pos.move_is_pl(move)
338 && !pos.move_is_capture(move))
342 case PH_NONCAPTURES_1:
343 case PH_NONCAPTURES_2:
344 move = (curMove++)->move;
346 && move != killers[0].move
347 && move != killers[1].move)
351 case PH_BAD_CAPTURES:
352 move = pick_best(curMove++, lastMove).move;
357 move = pick_best(curMove++, lastMove).move;
363 move = (curMove++)->move;
364 if (move_to(move) == recaptureSquare)
369 move = (curMove++)->move;