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