Add Null move support to MovePicker.
[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_NULL_MOVE, 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, bool useNullMove) : 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_NULL_MOVE:
119         break;
120
121     case PH_TT_MOVES:
122         movesPicked = 0; // This is used as index to ttMoves[]
123         break;
124
125     case PH_GOOD_CAPTURES:
126         numOfMoves = generate_captures(pos, moves);
127         score_captures();
128         std::sort(moves, moves + numOfMoves);
129         movesPicked = 0;
130         break;
131
132     case PH_KILLERS:
133         movesPicked = 0; // This is used as index to killers[]
134         break;
135
136     case PH_NONCAPTURES:
137         numOfMoves = generate_noncaptures(pos, moves);
138         score_noncaptures();
139         std::sort(moves, moves + numOfMoves);
140         movesPicked = 0;
141         break;
142
143     case PH_BAD_CAPTURES:
144         // Bad captures SEE value is already calculated so just sort them
145         // to get SEE move ordering.
146         std::sort(badCaptures, badCaptures + numOfBadCaptures);
147         movesPicked = 0;
148         break;
149
150     case PH_EVASIONS:
151         assert(pos.is_check());
152         numOfMoves = generate_evasions(pos, moves, pinned);
153         score_evasions();
154         std::sort(moves, moves + numOfMoves);
155         movesPicked = 0;
156         break;
157
158     case PH_QCAPTURES:
159         numOfMoves = generate_captures(pos, moves);
160         score_captures();
161         std::sort(moves, moves + numOfMoves);
162         movesPicked = 0;
163         break;
164
165     case PH_QCHECKS:
166         // Perhaps we should order moves move here?  FIXME
167         numOfMoves = generate_non_capture_checks(pos, moves, dc);
168         movesPicked = 0;
169         break;
170
171     case PH_STOP:
172         return MOVE_NONE;
173
174     default:
175         assert(false);
176         return MOVE_NONE;
177     }
178   }
179 }
180
181
182 /// A variant of get_next_move() which takes a lock as a parameter, used to
183 /// prevent multiple threads from picking the same move at a split point.
184
185 Move MovePicker::get_next_move(Lock &lock) {
186
187    lock_grab(&lock);
188    if (finished)
189    {
190        lock_release(&lock);
191        return MOVE_NONE;
192    }
193    Move m = get_next_move();
194    if (m == MOVE_NONE)
195        finished = true;
196
197    lock_release(&lock);
198    return m;
199 }
200
201
202 /// MovePicker::score_captures(), MovePicker::score_noncaptures(),
203 /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a
204 /// numerical move ordering score to each move in a move list.  The moves
205 /// with highest scores will be picked first by pick_move_from_list().
206
207 void MovePicker::score_captures() {
208   // Winning and equal captures in the main search are ordered by MVV/LVA.
209   // Suprisingly, this appears to perform slightly better than SEE based
210   // move ordering. The reason is probably that in a position with a winning
211   // capture, capturing a more valuable (but sufficiently defended) piece
212   // first usually doesn't hurt. The opponent will have to recapture, and
213   // the hanging piece will still be hanging (except in the unusual cases
214   // where it is possible to recapture with the hanging piece). Exchanging
215   // big pieces before capturing a hanging piece probably helps to reduce
216   // the subtree size.
217   // In main search we want to push captures with negative SEE values to
218   // badCaptures[] array, but instead of doing it now we delay till when
219   // the move has been picked up in pick_move_from_list(), this way we save
220   // some SEE calls in case we get a cutoff (idea from Pablo Vazquez).
221   Move m;
222
223   // Use MVV/LVA ordering
224   for (int i = 0; i < numOfMoves; i++)
225   {
226       m = moves[i].move;
227       if (move_is_promotion(m))
228           moves[i].score = QueenValueMidgame;
229       else
230           moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m)))
231                           -int(pos.type_of_piece_on(move_from(m)));
232   }
233 }
234
235 void MovePicker::score_noncaptures() {
236   // First score by history, when no history is available then use
237   // piece/square tables values. This seems to be better then a
238   // random choice when we don't have an history for any move.
239   Piece piece;
240   Square from, to;
241   int hs;
242
243   for (int i = 0; i < numOfMoves; i++)
244   {
245       from = move_from(moves[i].move);
246       to = move_to(moves[i].move);
247       piece = pos.piece_on(from);
248       hs = H.move_ordering_score(piece, to);
249
250       // Ensure history is always preferred to pst
251       if (hs > 0)
252           hs += 1000;
253
254       // pst based scoring
255       moves[i].score = hs + pos.pst_delta<Position::MidGame>(piece, from, to);
256   }
257 }
258
259 void MovePicker::score_evasions() {
260
261   for (int i = 0; i < numOfMoves; i++)
262   {
263       Move m = moves[i].move;
264       if (m == ttMoves[0])
265           moves[i].score = 2*HistoryMax;
266       else if (!pos.square_is_empty(move_to(m)))
267       {
268           int seeScore = pos.see(m);
269           moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore;
270       } else
271           moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m));
272   }
273 }
274
275
276 /// MovePicker::pick_move_from_list() picks the move with the biggest score
277 /// from a list of generated moves (moves[] or badCaptures[], depending on
278 /// the current move generation phase).  It takes care not to return the
279 /// transposition table move if that has already been serched previously.
280
281 Move MovePicker::pick_move_from_list() {
282
283   assert(movesPicked >= 0);
284   assert(!pos.is_check() || *phasePtr == PH_EVASIONS || *phasePtr == PH_STOP);
285   assert( pos.is_check() || *phasePtr != PH_EVASIONS);
286
287   switch (*phasePtr) {
288
289   case PH_TT_MOVES:
290         while (movesPicked < 2) {
291             Move move = ttMoves[movesPicked++];
292             if (   move != MOVE_NONE
293                 && move_is_legal(pos, move, pinned))
294                 return move;
295         }
296         break;
297
298   case PH_GOOD_CAPTURES:
299       while (movesPicked < numOfMoves)
300       {
301           Move move = moves[movesPicked++].move;
302           if (   move != ttMoves[0]
303               && move != ttMoves[1]
304               && pos.pl_move_is_legal(move, pinned))
305           {
306               // Check for a non negative SEE now
307               int seeValue = pos.see_sign(move);
308               if (seeValue >= 0)
309                   return move;
310
311               // Losing capture, move it to the badCaptures[] array, note
312               // that move has now been already checked for legality.
313               assert(numOfBadCaptures < 63);
314               badCaptures[numOfBadCaptures].move = move;
315               badCaptures[numOfBadCaptures++].score = seeValue;
316           }
317       }
318       break;
319
320   case PH_KILLERS:
321         while (movesPicked < 2) {
322             Move move = killers[movesPicked++];
323             if (   move != MOVE_NONE
324                 && move != ttMoves[0]
325                 && move != ttMoves[1]
326                 && move_is_legal(pos, move, pinned)
327                 && !pos.move_is_capture(move))
328                 return move;
329         }
330         break;
331
332   case PH_NONCAPTURES:
333       while (movesPicked < numOfMoves)
334       {
335           Move move = moves[movesPicked++].move;
336           if (   move != ttMoves[0]
337               && move != ttMoves[1]
338               && move != killers[0]
339               && move != killers[1]
340               && pos.pl_move_is_legal(move, pinned))
341               return move;
342       }
343       break;
344
345   case PH_EVASIONS:
346       if (movesPicked < numOfMoves)
347           return moves[movesPicked++].move;
348       break;
349
350   case PH_BAD_CAPTURES:
351       if (movesPicked < numOfBadCaptures)
352           return badCaptures[movesPicked++].move;
353       break;
354
355   case PH_QCAPTURES:
356   case PH_QCHECKS:
357       while (movesPicked < numOfMoves)
358       {
359           Move move = moves[movesPicked++].move;
360           // Maybe postpone the legality check until after futility pruning?
361           if (   move != ttMoves[0]
362               && pos.pl_move_is_legal(move, pinned))
363               return move;
364       }
365       break;
366
367   default:
368       break;
369   }
370   return MOVE_NONE;
371 }