0b887c99d0afb31abc3c963e7645a4224d082d3a
[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-2009 Marco Costalba
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
22 ////
23 //// Includes
24 ////
25
26 #include <algorithm>
27 #include <cassert>
28
29 #include "history.h"
30 #include "evaluate.h"
31 #include "movegen.h"
32 #include "movepick.h"
33 #include "search.h"
34 #include "value.h"
35
36
37 ////
38 //// Local definitions
39 ////
40
41 namespace {
42
43   /// Variables
44
45   CACHE_LINE_ALIGNMENT
46   const MovegenPhaseT MainSearchPhaseTable[] = { PH_STOP, PH_TT_MOVES, PH_GOOD_CAPTURES, PH_KILLERS, PH_NONCAPTURES, PH_BAD_CAPTURES, PH_STOP};
47   const MovegenPhaseT EvasionsPhaseTable[] = { PH_STOP, PH_EVASIONS, PH_STOP};
48   const MovegenPhaseT QsearchWithChecksPhaseTable[] = { PH_STOP, PH_TT_MOVES, PH_QCAPTURES, PH_QCHECKS, PH_STOP};
49   const MovegenPhaseT QsearchWithoutChecksPhaseTable[] = { PH_STOP, PH_TT_MOVES, PH_QCAPTURES, PH_STOP};
50 }
51
52
53 ////
54 //// Functions
55 ////
56
57
58 /// Constructor for the MovePicker class.  Apart from the position for which
59 /// it is asked to pick legal moves, MovePicker also wants some information
60 /// to help it to return the presumably good moves first, to decide which
61 /// moves to return (in the quiescence search, for instance, we only want to
62 /// search captures, promotions and some checks) and about how important good
63 /// move ordering is at the current node.
64
65 MovePicker::MovePicker(const Position& p, Move ttm, Depth d,
66                        const History& h, SearchStack* ss) : pos(p), H(h) {
67   ttMoves[0] = ttm;
68   if (ss)
69   {
70       ttMoves[1] = (ss->mateKiller == ttm)? MOVE_NONE : ss->mateKiller;
71       killers[0] = ss->killers[0];
72       killers[1] = ss->killers[1];
73   } else
74       ttMoves[1] = killers[0] = killers[1] = MOVE_NONE;
75
76   movesPicked = numOfMoves = numOfBadCaptures = 0;
77   finished = false;
78
79   if (p.is_check())
80       phasePtr = EvasionsPhaseTable;
81   else if (d > Depth(0))
82       phasePtr = MainSearchPhaseTable;
83   else if (d == Depth(0))
84       phasePtr = QsearchWithChecksPhaseTable;
85   else
86       phasePtr = QsearchWithoutChecksPhaseTable;
87
88   Color us = pos.side_to_move();
89
90   dc = p.discovered_check_candidates(us);
91   pinned = p.pinned_pieces(us);
92 }
93
94
95 /// MovePicker::get_next_move() is the most important method of the MovePicker
96 /// class.  It returns a new legal move every time it is called, until there
97 /// are no more moves left of the types we are interested in.
98
99 Move MovePicker::get_next_move() {
100
101   Move move;
102
103   while (true)
104   {
105     // If we already have a list of generated moves, pick the best move from
106     // the list, and return it.
107     move = pick_move_from_list();
108     if (move != MOVE_NONE)
109     {
110         assert(move_is_ok(move));
111         return move;
112     }
113
114     // Next phase
115     phasePtr++;
116     switch (*phasePtr) {
117
118     case PH_TT_MOVES:
119         movesPicked = 0; // This is used as index to ttMoves[]
120         break;
121
122     case PH_GOOD_CAPTURES:
123         numOfMoves = generate_captures(pos, moves);
124         score_captures();
125         std::sort(moves, moves + numOfMoves);
126         movesPicked = 0;
127         break;
128
129     case PH_KILLERS:
130         movesPicked = 0; // This is used as index to killers[]
131         break;
132
133     case PH_NONCAPTURES:
134         numOfMoves = generate_noncaptures(pos, moves);
135         score_noncaptures();
136         std::sort(moves, moves + numOfMoves);
137         movesPicked = 0;
138         break;
139
140     case PH_BAD_CAPTURES:
141         // Bad captures SEE value is already calculated so just sort them
142         // to get SEE move ordering.
143         std::sort(badCaptures, badCaptures + numOfBadCaptures);
144         movesPicked = 0;
145         break;
146
147     case PH_EVASIONS:
148         assert(pos.is_check());
149         numOfMoves = generate_evasions(pos, moves, pinned);
150         score_evasions();
151         std::sort(moves, moves + numOfMoves);
152         movesPicked = 0;
153         break;
154
155     case PH_QCAPTURES:
156         numOfMoves = generate_captures(pos, moves);
157         score_captures();
158         std::sort(moves, moves + numOfMoves);
159         movesPicked = 0;
160         break;
161
162     case PH_QCHECKS:
163         // Perhaps we should order moves move here?  FIXME
164         numOfMoves = generate_non_capture_checks(pos, moves, dc);
165         movesPicked = 0;
166         break;
167
168     case PH_STOP:
169         return MOVE_NONE;
170
171     default:
172         assert(false);
173         return MOVE_NONE;
174     }
175   }
176 }
177
178
179 /// A variant of get_next_move() which takes a lock as a parameter, used to
180 /// prevent multiple threads from picking the same move at a split point.
181
182 Move MovePicker::get_next_move(Lock &lock) {
183
184    lock_grab(&lock);
185    if (finished)
186    {
187        lock_release(&lock);
188        return MOVE_NONE;
189    }
190    Move m = get_next_move();
191    if (m == MOVE_NONE)
192        finished = true;
193
194    lock_release(&lock);
195    return m;
196 }
197
198
199 /// MovePicker::score_captures(), MovePicker::score_noncaptures(),
200 /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a
201 /// numerical move ordering score to each move in a move list.  The moves
202 /// with highest scores will be picked first by pick_move_from_list().
203
204 void MovePicker::score_captures() {
205   // Winning and equal captures in the main search are ordered by MVV/LVA.
206   // Suprisingly, this appears to perform slightly better than SEE based
207   // move ordering. The reason is probably that in a position with a winning
208   // capture, capturing a more valuable (but sufficiently defended) piece
209   // first usually doesn't hurt. The opponent will have to recapture, and
210   // the hanging piece will still be hanging (except in the unusual cases
211   // where it is possible to recapture with the hanging piece). Exchanging
212   // big pieces before capturing a hanging piece probably helps to reduce
213   // the subtree size.
214   // In main search we want to push captures with negative SEE values to
215   // badCaptures[] array, but instead of doing it now we delay till when
216   // the move has been picked up in pick_move_from_list(), this way we save
217   // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).
218   Move m;
219
220   // Use MVV/LVA ordering
221   for (int i = 0; i < numOfMoves; i++)
222   {
223       m = moves[i].move;
224       if (move_is_promotion(m))
225           moves[i].score = QueenValueMidgame;
226       else
227           moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m)))
228                           -int(pos.type_of_piece_on(move_from(m)));
229   }
230 }
231
232 void MovePicker::score_noncaptures() {
233   // First score by history, when no history is available then use
234   // piece/square tables values. This seems to be better then a
235   // random choice when we don't have an history for any move.
236   Piece piece;
237   Square from, to;
238   int hs;
239
240   for (int i = 0; i < numOfMoves; i++)
241   {
242       from = move_from(moves[i].move);
243       to = move_to(moves[i].move);
244       piece = pos.piece_on(from);
245       hs = H.move_ordering_score(piece, to);
246
247       // Ensure history is always preferred to pst
248       if (hs > 0)
249           hs += 1000;
250
251       // pst based scoring
252       moves[i].score = hs + pos.pst_delta<Position::MidGame>(piece, from, to);
253   }
254 }
255
256 void MovePicker::score_evasions() {
257
258   for (int i = 0; i < numOfMoves; i++)
259   {
260       Move m = moves[i].move;
261       if (m == ttMoves[0])
262           moves[i].score = 2*HistoryMax;
263       else if (!pos.square_is_empty(move_to(m)))
264       {
265           int seeScore = pos.see(m);
266           moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore;
267       } else
268           moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m));
269   }
270 }
271
272
273 /// MovePicker::pick_move_from_list() picks the move with the biggest score
274 /// from a list of generated moves (moves[] or badCaptures[], depending on
275 /// the current move generation phase).  It takes care not to return the
276 /// transposition table move if that has already been serched previously.
277
278 Move MovePicker::pick_move_from_list() {
279
280   assert(movesPicked >= 0);
281   assert(!pos.is_check() || *phasePtr == PH_EVASIONS || *phasePtr == PH_STOP);
282   assert( pos.is_check() || *phasePtr != PH_EVASIONS);
283
284   switch (*phasePtr) {
285
286   case PH_TT_MOVES:
287         while (movesPicked < 2) {
288             Move move = ttMoves[movesPicked++];
289             if (   move != MOVE_NONE
290                 && move_is_legal(pos, move, pinned))
291                 return move;
292         }
293         break;
294
295   case PH_GOOD_CAPTURES:
296       while (movesPicked < numOfMoves)
297       {
298           Move move = moves[movesPicked++].move;
299           if (   move != ttMoves[0]
300               && move != ttMoves[1]
301               && pos.pl_move_is_legal(move, pinned))
302           {
303               // Check for a non negative SEE now
304               int seeValue = pos.see_sign(move);
305               if (seeValue >= 0)
306                   return move;
307
308               // Losing capture, move it to the badCaptures[] array, note
309               // that move has now been already checked for legality.
310               assert(numOfBadCaptures < 63);
311               badCaptures[numOfBadCaptures].move = move;
312               badCaptures[numOfBadCaptures++].score = seeValue;
313           }
314       }
315       break;
316
317   case PH_KILLERS:
318         while (movesPicked < 2) {
319             Move move = killers[movesPicked++];
320             if (   move != MOVE_NONE
321                 && move != ttMoves[0]
322                 && move != ttMoves[1]
323                 && move_is_legal(pos, move, pinned)
324                 && !pos.move_is_capture(move))
325                 return move;
326         }
327         break;
328
329   case PH_NONCAPTURES:
330       while (movesPicked < numOfMoves)
331       {
332           Move move = moves[movesPicked++].move;
333           if (   move != ttMoves[0]
334               && move != ttMoves[1]
335               && move != killers[0]
336               && move != killers[1]
337               && pos.pl_move_is_legal(move, pinned))
338               return move;
339       }
340       break;
341
342   case PH_EVASIONS:
343       if (movesPicked < numOfMoves)
344           return moves[movesPicked++].move;
345       break;
346
347   case PH_BAD_CAPTURES:
348       if (movesPicked < numOfBadCaptures)
349           return badCaptures[movesPicked++].move;
350       break;
351
352   case PH_QCAPTURES:
353   case PH_QCHECKS:
354       while (movesPicked < numOfMoves)
355       {
356           Move move = moves[movesPicked++].move;
357           // Maybe postpone the legality check until after futility pruning?
358           if (   move != ttMoves[0]
359               && pos.pl_move_is_legal(move, pinned))
360               return move;
361       }
362       break;
363
364   default:
365       break;
366   }
367   return MOVE_NONE;
368 }