Sync with master
[stockfish] / src / movegen.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-2015 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   Stockfish is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <cassert>
21
22 #include "movegen.h"
23 #include "position.h"
24
25 namespace {
26
27   template<CastlingRight Cr, bool Checks, bool Chess960>
28   ExtMove* generate_castling(const Position& pos, ExtMove* moveList, Color us, const CheckInfo* ci) {
29
30     static const bool KingSide = (Cr == WHITE_OO || Cr == BLACK_OO);
31
32     if (pos.castling_impeded(Cr) || !pos.can_castle(Cr))
33         return moveList;
34
35     // After castling, the rook and king final positions are the same in Chess960
36     // as they would be in standard chess.
37     Square kfrom = pos.king_square(us);
38     Square rfrom = pos.castling_rook_square(Cr);
39     Square kto = relative_square(us, KingSide ? SQ_G1 : SQ_C1);
40     Bitboard enemies = pos.pieces(~us);
41
42     assert(!pos.checkers());
43
44     const Square K = Chess960 ? kto > kfrom ? DELTA_W : DELTA_E
45                               : KingSide    ? DELTA_W : DELTA_E;
46
47     for (Square s = kto; s != kfrom; s += K)
48         if (pos.attackers_to(s) & enemies)
49             return moveList;
50
51     // Because we generate only legal castling moves we need to verify that
52     // when moving the castling rook we do not discover some hidden checker.
53     // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
54     if (Chess960 && (attacks_bb<ROOK>(kto, pos.pieces() ^ rfrom) & pos.pieces(~us, ROOK, QUEEN)))
55         return moveList;
56
57     Move m = make<CASTLING>(kfrom, rfrom);
58
59     if (Checks && !pos.gives_check(m, *ci))
60         return moveList;
61
62     *moveList++ = m;
63
64     return (void)ci, moveList; // Silence a warning under MSVC
65   }
66
67
68   template<GenType Type, Square Delta>
69   inline ExtMove* make_promotions(ExtMove* moveList, Square to, const CheckInfo* ci) {
70
71     if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS)
72         *moveList++ = make<PROMOTION>(to - Delta, to, QUEEN);
73
74     if (Type == QUIETS || Type == EVASIONS || Type == NON_EVASIONS)
75     {
76         *moveList++ = make<PROMOTION>(to - Delta, to, ROOK);
77         *moveList++ = make<PROMOTION>(to - Delta, to, BISHOP);
78         *moveList++ = make<PROMOTION>(to - Delta, to, KNIGHT);
79     }
80
81     // Knight promotion is the only promotion that can give a direct check
82     // that's not already included in the queen promotion.
83     if (Type == QUIET_CHECKS && (StepAttacksBB[W_KNIGHT][to] & ci->ksq))
84         *moveList++ = make<PROMOTION>(to - Delta, to, KNIGHT);
85
86     return (void)ci, moveList; // Silence a warning under MSVC
87   }
88
89
90   template<Color Us, GenType Type>
91   ExtMove* generate_pawn_moves(const Position& pos, ExtMove* moveList,
92                                Bitboard target, const CheckInfo* ci) {
93
94     // Compute our parametrized parameters at compile time, named according to
95     // the point of view of white side.
96     const Color    Them     = (Us == WHITE ? BLACK    : WHITE);
97     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB  : Rank1BB);
98     const Bitboard TRank7BB = (Us == WHITE ? Rank7BB  : Rank2BB);
99     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB  : Rank6BB);
100     const Square   Up       = (Us == WHITE ? DELTA_N  : DELTA_S);
101     const Square   Right    = (Us == WHITE ? DELTA_NE : DELTA_SW);
102     const Square   Left     = (Us == WHITE ? DELTA_NW : DELTA_SE);
103
104     Bitboard emptySquares;
105
106     Bitboard pawnsOn7    = pos.pieces(Us, PAWN) &  TRank7BB;
107     Bitboard pawnsNotOn7 = pos.pieces(Us, PAWN) & ~TRank7BB;
108
109     Bitboard enemies = (Type == EVASIONS ? pos.pieces(Them) & target:
110                         Type == CAPTURES ? target : pos.pieces(Them));
111
112     // Single and double pawn pushes, no promotions
113     if (Type != CAPTURES)
114     {
115         emptySquares = (Type == QUIETS || Type == QUIET_CHECKS ? target : ~pos.pieces());
116
117         Bitboard b1 = shift_bb<Up>(pawnsNotOn7)   & emptySquares;
118         Bitboard b2 = shift_bb<Up>(b1 & TRank3BB) & emptySquares;
119
120         if (Type == EVASIONS) // Consider only blocking squares
121         {
122             b1 &= target;
123             b2 &= target;
124         }
125
126         if (Type == QUIET_CHECKS)
127         {
128             b1 &= pos.attacks_from<PAWN>(ci->ksq, Them);
129             b2 &= pos.attacks_from<PAWN>(ci->ksq, Them);
130
131             // Add pawn pushes which give discovered check. This is possible only
132             // if the pawn is not on the same file as the enemy king, because we
133             // don't generate captures. Note that a possible discovery check
134             // promotion has been already generated amongst the captures.
135             if (pawnsNotOn7 & ci->dcCandidates)
136             {
137                 Bitboard dc1 = shift_bb<Up>(pawnsNotOn7 & ci->dcCandidates) & emptySquares & ~file_bb(ci->ksq);
138                 Bitboard dc2 = shift_bb<Up>(dc1 & TRank3BB) & emptySquares;
139
140                 b1 |= dc1;
141                 b2 |= dc2;
142             }
143         }
144
145         while (b1)
146         {
147             Square to = pop_lsb(&b1);
148             *moveList++ = make_move(to - Up, to);
149         }
150
151         while (b2)
152         {
153             Square to = pop_lsb(&b2);
154             *moveList++ = make_move(to - Up - Up, to);
155         }
156     }
157
158     // Promotions and underpromotions
159     if (pawnsOn7 && (Type != EVASIONS || (target & TRank8BB)))
160     {
161         if (Type == CAPTURES)
162             emptySquares = ~pos.pieces();
163
164         if (Type == EVASIONS)
165             emptySquares &= target;
166
167         Bitboard b1 = shift_bb<Right>(pawnsOn7) & enemies;
168         Bitboard b2 = shift_bb<Left >(pawnsOn7) & enemies;
169         Bitboard b3 = shift_bb<Up   >(pawnsOn7) & emptySquares;
170
171         while (b1)
172             moveList = make_promotions<Type, Right>(moveList, pop_lsb(&b1), ci);
173
174         while (b2)
175             moveList = make_promotions<Type, Left >(moveList, pop_lsb(&b2), ci);
176
177         while (b3)
178             moveList = make_promotions<Type, Up   >(moveList, pop_lsb(&b3), ci);
179     }
180
181     // Standard and en-passant captures
182     if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS)
183     {
184         Bitboard b1 = shift_bb<Right>(pawnsNotOn7) & enemies;
185         Bitboard b2 = shift_bb<Left >(pawnsNotOn7) & enemies;
186
187         while (b1)
188         {
189             Square to = pop_lsb(&b1);
190             *moveList++ = make_move(to - Right, to);
191         }
192
193         while (b2)
194         {
195             Square to = pop_lsb(&b2);
196             *moveList++ = make_move(to - Left, to);
197         }
198
199         if (pos.ep_square() != SQ_NONE)
200         {
201             assert(rank_of(pos.ep_square()) == relative_rank(Us, RANK_6));
202
203             // An en passant capture can be an evasion only if the checking piece
204             // is the double pushed pawn and so is in the target. Otherwise this
205             // is a discovery check and we are forced to do otherwise.
206             if (Type == EVASIONS && !(target & (pos.ep_square() - Up)))
207                 return moveList;
208
209             b1 = pawnsNotOn7 & pos.attacks_from<PAWN>(pos.ep_square(), Them);
210
211             assert(b1);
212
213             while (b1)
214                 *moveList++ = make<ENPASSANT>(pop_lsb(&b1), pos.ep_square());
215         }
216     }
217
218     return moveList;
219   }
220
221
222   template<PieceType Pt, bool Checks> FORCE_INLINE
223   ExtMove* generate_moves(const Position& pos, ExtMove* moveList, Color us,
224                           Bitboard target, const CheckInfo* ci) {
225
226     assert(Pt != KING && Pt != PAWN);
227
228     const Square* pl = pos.list<Pt>(us);
229
230     for (Square from = *pl; from != SQ_NONE; from = *++pl)
231     {
232         if (Checks)
233         {
234             if (    (Pt == BISHOP || Pt == ROOK || Pt == QUEEN)
235                 && !(PseudoAttacks[Pt][from] & target & ci->checkSq[Pt]))
236                 continue;
237
238             if (ci->dcCandidates && (ci->dcCandidates & from))
239                 continue;
240         }
241
242         Bitboard b = pos.attacks_from<Pt>(from) & target;
243
244         if (Checks)
245             b &= ci->checkSq[Pt];
246
247         while (b)
248             *moveList++ = make_move(from, pop_lsb(&b));
249     }
250
251     return moveList;
252   }
253
254
255   template<Color Us, GenType Type> FORCE_INLINE
256   ExtMove* generate_all(const Position& pos, ExtMove* moveList, Bitboard target,
257                         const CheckInfo* ci = nullptr) {
258
259     const bool Checks = Type == QUIET_CHECKS;
260
261     moveList = generate_pawn_moves<Us, Type>(pos, moveList, target, ci);
262     moveList = generate_moves<KNIGHT, Checks>(pos, moveList, Us, target, ci);
263     moveList = generate_moves<BISHOP, Checks>(pos, moveList, Us, target, ci);
264     moveList = generate_moves<  ROOK, Checks>(pos, moveList, Us, target, ci);
265     moveList = generate_moves< QUEEN, Checks>(pos, moveList, Us, target, ci);
266
267     if (Type != QUIET_CHECKS && Type != EVASIONS)
268     {
269         Square ksq = pos.king_square(Us);
270         Bitboard b = pos.attacks_from<KING>(ksq) & target;
271         while (b)
272             *moveList++ = make_move(ksq, pop_lsb(&b));
273     }
274
275     if (Type != CAPTURES && Type != EVASIONS && pos.can_castle(Us))
276     {
277         if (pos.is_chess960())
278         {
279             moveList = generate_castling<MakeCastling<Us,  KING_SIDE>::right, Checks, true>(pos, moveList, Us, ci);
280             moveList = generate_castling<MakeCastling<Us, QUEEN_SIDE>::right, Checks, true>(pos, moveList, Us, ci);
281         }
282         else
283         {
284             moveList = generate_castling<MakeCastling<Us,  KING_SIDE>::right, Checks, false>(pos, moveList, Us, ci);
285             moveList = generate_castling<MakeCastling<Us, QUEEN_SIDE>::right, Checks, false>(pos, moveList, Us, ci);
286         }
287     }
288
289     return moveList;
290   }
291
292 } // namespace
293
294
295 /// generate<CAPTURES> generates all pseudo-legal captures and queen
296 /// promotions. Returns a pointer to the end of the move list.
297 ///
298 /// generate<QUIETS> generates all pseudo-legal non-captures and
299 /// underpromotions. Returns a pointer to the end of the move list.
300 ///
301 /// generate<NON_EVASIONS> generates all pseudo-legal captures and
302 /// non-captures. Returns a pointer to the end of the move list.
303
304 template<GenType Type>
305 ExtMove* generate(const Position& pos, ExtMove* moveList) {
306
307   assert(Type == CAPTURES || Type == QUIETS || Type == NON_EVASIONS);
308   assert(!pos.checkers());
309
310   Color us = pos.side_to_move();
311
312   Bitboard target =  Type == CAPTURES     ?  pos.pieces(~us)
313                    : Type == QUIETS       ? ~pos.pieces()
314                    : Type == NON_EVASIONS ? ~pos.pieces(us) : 0;
315
316   return us == WHITE ? generate_all<WHITE, Type>(pos, moveList, target)
317                      : generate_all<BLACK, Type>(pos, moveList, target);
318 }
319
320 // Explicit template instantiations
321 template ExtMove* generate<CAPTURES>(const Position&, ExtMove*);
322 template ExtMove* generate<QUIETS>(const Position&, ExtMove*);
323 template ExtMove* generate<NON_EVASIONS>(const Position&, ExtMove*);
324
325
326 /// generate<QUIET_CHECKS> generates all pseudo-legal non-captures and knight
327 /// underpromotions that give check. Returns a pointer to the end of the move list.
328 template<>
329 ExtMove* generate<QUIET_CHECKS>(const Position& pos, ExtMove* moveList) {
330
331   assert(!pos.checkers());
332
333   Color us = pos.side_to_move();
334   CheckInfo ci(pos);
335   Bitboard dc = ci.dcCandidates;
336
337   while (dc)
338   {
339      Square from = pop_lsb(&dc);
340      PieceType pt = type_of(pos.piece_on(from));
341
342      if (pt == PAWN)
343          continue; // Will be generated together with direct checks
344
345      Bitboard b = pos.attacks_from(Piece(pt), from) & ~pos.pieces();
346
347      if (pt == KING)
348          b &= ~PseudoAttacks[QUEEN][ci.ksq];
349
350      while (b)
351          *moveList++ = make_move(from, pop_lsb(&b));
352   }
353
354   return us == WHITE ? generate_all<WHITE, QUIET_CHECKS>(pos, moveList, ~pos.pieces(), &ci)
355                      : generate_all<BLACK, QUIET_CHECKS>(pos, moveList, ~pos.pieces(), &ci);
356 }
357
358
359 /// generate<EVASIONS> generates all pseudo-legal check evasions when the side
360 /// to move is in check. Returns a pointer to the end of the move list.
361 template<>
362 ExtMove* generate<EVASIONS>(const Position& pos, ExtMove* moveList) {
363
364   assert(pos.checkers());
365
366   Color us = pos.side_to_move();
367   Square ksq = pos.king_square(us);
368   Bitboard sliderAttacks = 0;
369   Bitboard sliders = pos.checkers() & ~pos.pieces(KNIGHT, PAWN);
370
371   // Find all the squares attacked by slider checkers. We will remove them from
372   // the king evasions in order to skip known illegal moves, which avoids any
373   // useless legality checks later on.
374   while (sliders)
375   {
376       Square checksq = pop_lsb(&sliders);
377       sliderAttacks |= LineBB[checksq][ksq] ^ checksq;
378   }
379
380   // Generate evasions for king, capture and non capture moves
381   Bitboard b = pos.attacks_from<KING>(ksq) & ~pos.pieces(us) & ~sliderAttacks;
382   while (b)
383       *moveList++ = make_move(ksq, pop_lsb(&b));
384
385   if (more_than_one(pos.checkers()))
386       return moveList; // Double check, only a king move can save the day
387
388   // Generate blocking evasions or captures of the checking piece
389   Square checksq = lsb(pos.checkers());
390   Bitboard target = between_bb(checksq, ksq) | checksq;
391
392   return us == WHITE ? generate_all<WHITE, EVASIONS>(pos, moveList, target)
393                      : generate_all<BLACK, EVASIONS>(pos, moveList, target);
394 }
395
396
397 /// generate<LEGAL> generates all the legal moves in the given position
398
399 template<>
400 ExtMove* generate<LEGAL>(const Position& pos, ExtMove* moveList) {
401
402   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
403   Square ksq = pos.king_square(pos.side_to_move());
404   ExtMove* cur = moveList;
405
406   moveList = pos.checkers() ? generate<EVASIONS    >(pos, moveList)
407                             : generate<NON_EVASIONS>(pos, moveList);
408   while (cur != moveList)
409       if (   (pinned || from_sq(*cur) == ksq || type_of(*cur) == ENPASSANT)
410           && !pos.legal(*cur, pinned))
411           *cur = (--moveList)->move;
412       else
413           ++cur;
414
415   return moveList;
416 }