New extended probcut implementation
[stockfish] / src / movepick.cpp
1 /*
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
5
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.
10
11
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.
16
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/>.
19 */
20
21 #include <cassert>
22
23 #include "movegen.h"
24 #include "movepick.h"
25 #include "search.h"
26 #include "types.h"
27
28 namespace {
29
30   enum MovegenPhase {
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,   // Non-captures and underpromotions
36     PH_BAD_CAPTURES,  // Queen promotions and captures with SEE values < captureThreshold (captureThreshold <= 0)
37     PH_EVASIONS,      // Check evasions
38     PH_QCAPTURES,     // Captures in quiescence search
39     PH_QCHECKS,       // Non-capture checks in quiescence search
40     PH_STOP
41   };
42
43   CACHE_LINE_ALIGNMENT
44   const uint8_t MainSearchTable[] = { PH_TT_MOVE, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES, PH_BAD_CAPTURES, PH_STOP };
45   const uint8_t EvasionTable[] = { PH_TT_MOVE, PH_EVASIONS, PH_STOP };
46   const uint8_t QsearchWithChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_QCHECKS, PH_STOP };
47   const uint8_t QsearchWithoutChecksTable[] = { PH_TT_MOVE, PH_QCAPTURES, PH_STOP };
48   const uint8_t ProbCutTable[] = { PH_TT_MOVE, PH_GOOD_PROBCUT, PH_STOP };
49 }
50
51 /// Constructors for the MovePicker class. As arguments we pass information
52 /// to help it to return the presumably good moves first, to decide which
53 /// moves to return (in the quiescence search, for instance, we only want to
54 /// search captures, promotions and some checks) and about how important good
55 /// move ordering is at the current node.
56
57 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h,
58                        SearchStack* ss, Value beta) : pos(p), H(h) {
59   captureThreshold = 0;
60   badCaptures = moves + MAX_MOVES;
61
62   assert(d > DEPTH_ZERO);
63
64   if (p.in_check())
65   {
66       killers[0].move = killers[1].move = MOVE_NONE;
67       phasePtr = EvasionTable;
68   }
69   else
70   {
71       killers[0].move = ss->killers[0];
72       killers[1].move = ss->killers[1];
73
74       // Consider sligtly negative captures as good if at low
75       // depth and far from beta.
76       if (ss && ss->eval < beta - PawnValueMidgame && d < 3 * ONE_PLY)
77           captureThreshold = -PawnValueMidgame;
78
79       phasePtr = MainSearchTable;
80   }
81
82   ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
83   phasePtr += int(ttMove == MOVE_NONE) - 1;
84   go_next_phase();
85 }
86
87 MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const History& h)
88                       : pos(p), H(h) {
89
90   assert(d <= DEPTH_ZERO);
91
92   if (p.in_check())
93       phasePtr = EvasionTable;
94   else if (d >= DEPTH_QS_CHECKS)
95       phasePtr = QsearchWithChecksTable;
96   else
97   {
98       phasePtr = QsearchWithoutChecksTable;
99
100       // Skip TT move if is not a capture or a promotion, this avoids
101       // qsearch tree explosion due to a possible perpetual check or
102       // similar rare cases when TT table is full.
103       if (ttm != MOVE_NONE && !pos.move_is_capture(ttm) && !move_is_promotion(ttm))
104           ttm = MOVE_NONE;
105   }
106
107   ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
108   phasePtr += int(ttMove == MOVE_NONE) - 1;
109   go_next_phase();
110 }
111
112 MovePicker::MovePicker(const Position& p, Move ttm, const History& h, int parentCapture)
113                        : pos(p), H(h) {
114
115   assert (!pos.in_check());
116
117   // In ProbCut we consider only captures better than parent's move
118   captureThreshold = parentCapture;
119   phasePtr = ProbCutTable;
120
121   if (   ttm != MOVE_NONE
122       && (!pos.move_is_capture(ttm) ||  pos.see(ttm) <= captureThreshold))
123       ttm = MOVE_NONE;
124
125   ttMove = (ttm && pos.move_is_pl(ttm) ? ttm : MOVE_NONE);
126   phasePtr += int(ttMove == MOVE_NONE) - 1;
127   go_next_phase();
128 }
129
130
131 /// MovePicker::go_next_phase() generates, scores and sorts the next bunch
132 /// of moves when there are no more moves to try for the current phase.
133
134 void MovePicker::go_next_phase() {
135
136   curMove = moves;
137   phase = *(++phasePtr);
138   switch (phase) {
139
140   case PH_TT_MOVE:
141       lastMove = curMove + 1;
142       return;
143
144   case PH_GOOD_CAPTURES:
145   case PH_GOOD_PROBCUT:
146       lastMove = generate<MV_CAPTURE>(pos, moves);
147       score_captures();
148       return;
149
150   case PH_KILLERS:
151       curMove = killers;
152       lastMove = curMove + 2;
153       return;
154
155   case PH_NONCAPTURES:
156       lastMove = generate<MV_NON_CAPTURE>(pos, moves);
157       score_noncaptures();
158       sort_moves(moves, lastMove, &lastGoodNonCapture);
159       return;
160
161   case PH_BAD_CAPTURES:
162       // Bad captures SEE value is already calculated so just pick
163       // them in order to get SEE move ordering.
164       curMove = badCaptures;
165       lastMove = moves + MAX_MOVES;
166       return;
167
168   case PH_EVASIONS:
169       assert(pos.in_check());
170       lastMove = generate<MV_EVASION>(pos, moves);
171       score_evasions();
172       return;
173
174   case PH_QCAPTURES:
175       lastMove = generate<MV_CAPTURE>(pos, moves);
176       score_captures();
177       return;
178
179   case PH_QCHECKS:
180       lastMove = generate<MV_NON_CAPTURE_CHECK>(pos, moves);
181       return;
182
183   case PH_STOP:
184       lastMove = curMove + 1; // Avoid another go_next_phase() call
185       return;
186
187   default:
188       assert(false);
189       return;
190   }
191 }
192
193
194 /// MovePicker::score_captures(), MovePicker::score_noncaptures() and
195 /// MovePicker::score_evasions() assign a numerical move ordering score
196 /// to each move in a move list.  The moves with highest scores will be
197 /// picked first by get_next_move().
198
199 void MovePicker::score_captures() {
200   // Winning and equal captures in the main search are ordered by MVV/LVA.
201   // Suprisingly, this appears to perform slightly better than SEE based
202   // move ordering. The reason is probably that in a position with a winning
203   // capture, capturing a more valuable (but sufficiently defended) piece
204   // first usually doesn't hurt. The opponent will have to recapture, and
205   // the hanging piece will still be hanging (except in the unusual cases
206   // where it is possible to recapture with the hanging piece). Exchanging
207   // big pieces before capturing a hanging piece probably helps to reduce
208   // the subtree size.
209   // In main search we want to push captures with negative SEE values to
210   // badCaptures[] array, but instead of doing it now we delay till when
211   // the move has been picked up in pick_move_from_list(), this way we save
212   // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).
213   Move m;
214
215   // Use MVV/LVA ordering
216   for (MoveStack* cur = moves; cur != lastMove; cur++)
217   {
218       m = cur->move;
219       if (move_is_promotion(m))
220           cur->score = QueenValueMidgame;
221       else
222           cur->score =  pos.midgame_value_of_piece_on(move_to(m))
223                       - pos.type_of_piece_on(move_from(m));
224   }
225 }
226
227 void MovePicker::score_noncaptures() {
228
229   Move m;
230   Square from;
231
232   for (MoveStack* cur = moves; cur != lastMove; cur++)
233   {
234       m = cur->move;
235       from = move_from(m);
236       cur->score = H.value(pos.piece_on(from), move_to(m));
237   }
238 }
239
240 void MovePicker::score_evasions() {
241   // Try good captures ordered by MVV/LVA, then non-captures if
242   // destination square is not under attack, ordered by history
243   // value, and at the end bad-captures and non-captures with a
244   // negative SEE. This last group is ordered by the SEE score.
245   Move m;
246   int seeScore;
247
248   // Skip if we don't have at least two moves to order
249   if (lastMove < moves + 2)
250       return;
251
252   for (MoveStack* cur = moves; cur != lastMove; cur++)
253   {
254       m = cur->move;
255       if ((seeScore = pos.see_sign(m)) < 0)
256           cur->score = seeScore - History::MaxValue; // Be sure we are at the bottom
257       else if (pos.move_is_capture(m))
258           cur->score =  pos.midgame_value_of_piece_on(move_to(m))
259                       - pos.type_of_piece_on(move_from(m)) + History::MaxValue;
260       else
261           cur->score = H.value(pos.piece_on(move_from(m)), move_to(m));
262   }
263 }
264
265 /// MovePicker::get_next_move() is the most important method of the MovePicker
266 /// class. It returns a new pseudo legal move every time it is called, until there
267 /// are no more moves left. It picks the move with the biggest score from a list
268 /// of generated moves taking care not to return the tt move if has already been
269 /// searched previously. Note that this function is not thread safe so should be
270 /// lock protected by caller when accessed through a shared MovePicker object.
271
272 Move MovePicker::get_next_move() {
273
274   Move move;
275
276   while (true)
277   {
278       while (curMove == lastMove)
279           go_next_phase();
280
281       switch (phase) {
282
283       case PH_TT_MOVE:
284           curMove++;
285           return ttMove;
286           break;
287
288       case PH_GOOD_CAPTURES:
289           move = pick_best(curMove++, lastMove).move;
290           if (move != ttMove)
291           {
292               assert(captureThreshold <= 0); // Otherwise we must use see instead of see_sign
293
294               // Check for a non negative SEE now
295               int seeValue = pos.see_sign(move);
296               if (seeValue >= captureThreshold)
297                   return move;
298
299               // Losing capture, move it to the tail of the array, note
300               // that move has now been already checked for pseudo legality.
301               (--badCaptures)->move = move;
302               badCaptures->score = seeValue;
303           }
304           break;
305
306      case PH_GOOD_PROBCUT:
307           move = pick_best(curMove++, lastMove).move;
308           if (   move != ttMove
309               && pos.see(move) > captureThreshold)
310               return move;
311           break;
312
313       case PH_KILLERS:
314           move = (curMove++)->move;
315           if (   move != MOVE_NONE
316               && pos.move_is_pl(move)
317               && move != ttMove
318               && !pos.move_is_capture(move))
319               return move;
320           break;
321
322       case PH_NONCAPTURES:
323           // Sort negative scored moves only when we get there
324           if (curMove == lastGoodNonCapture)
325               insertion_sort<MoveStack>(lastGoodNonCapture, lastMove);
326
327           move = (curMove++)->move;
328           if (   move != ttMove
329               && move != killers[0].move
330               && move != killers[1].move)
331               return move;
332           break;
333
334       case PH_BAD_CAPTURES:
335           move = pick_best(curMove++, lastMove).move;
336           return move;
337
338       case PH_EVASIONS:
339       case PH_QCAPTURES:
340           move = pick_best(curMove++, lastMove).move;
341           if (move != ttMove)
342               return move;
343           break;
344
345       case PH_QCHECKS:
346           move = (curMove++)->move;
347           if (move != ttMove)
348               return move;
349           break;
350
351       case PH_STOP:
352           return MOVE_NONE;
353
354       default:
355           assert(false);
356           break;
357       }
358   }
359 }