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