Big renaming of move's helpers
[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-2012 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 #include <algorithm>
22
23 #include "bitcount.h"
24 #include "movegen.h"
25 #include "position.h"
26
27 // Simple macro to wrap a very common while loop, no facny, no flexibility,
28 // hardcoded list name 'mlist' and from square 'from'.
29 #define SERIALIZE_MOVES(b) while (b) (*mlist++).move = make_move(from, pop_1st_bit(&b))
30
31 // Version used for pawns, where the 'from' square is given as a delta from the 'to' square
32 #define SERIALIZE_MOVES_D(b, d) while (b) { to = pop_1st_bit(&b); (*mlist++).move = make_move(to + (d), to); }
33
34 namespace {
35
36   enum CastlingSide {
37     KING_SIDE,
38     QUEEN_SIDE
39   };
40
41   template<CastlingSide>
42   MoveStack* generate_castle_moves(const Position&, MoveStack*, Color us);
43
44   template<Color, MoveType>
45   MoveStack* generate_pawn_moves(const Position&, MoveStack*, Bitboard, Square);
46
47   template<PieceType Pt>
48   inline MoveStack* generate_discovered_checks(const Position& pos, MoveStack* mlist, Square from) {
49
50     assert(Pt != QUEEN && Pt != PAWN);
51
52     Bitboard b = pos.attacks_from<Pt>(from) & pos.empty_squares();
53
54     if (Pt == KING)
55         b &= ~QueenPseudoAttacks[pos.king_square(flip(pos.side_to_move()))];
56
57     SERIALIZE_MOVES(b);
58     return mlist;
59   }
60
61   template<PieceType Pt>
62   inline MoveStack* generate_direct_checks(const Position& pos, MoveStack* mlist, Color us,
63                                            Bitboard dc, Square ksq) {
64     assert(Pt != KING && Pt != PAWN);
65
66     Bitboard checkSqs, b;
67     Square from;
68     const Square* pl = pos.piece_list(us, Pt);
69
70     if ((from = *pl++) == SQ_NONE)
71         return mlist;
72
73     checkSqs = pos.attacks_from<Pt>(ksq) & pos.empty_squares();
74
75     do
76     {
77         if (   (Pt == QUEEN  && !(QueenPseudoAttacks[from]  & checkSqs))
78             || (Pt == ROOK   && !(RookPseudoAttacks[from]   & checkSqs))
79             || (Pt == BISHOP && !(BishopPseudoAttacks[from] & checkSqs)))
80             continue;
81
82         if (dc && bit_is_set(dc, from))
83             continue;
84
85         b = pos.attacks_from<Pt>(from) & checkSqs;
86         SERIALIZE_MOVES(b);
87
88     } while ((from = *pl++) != SQ_NONE);
89
90     return mlist;
91   }
92
93   template<>
94   FORCE_INLINE MoveStack* generate_direct_checks<PAWN>(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) {
95
96     return (us == WHITE ? generate_pawn_moves<WHITE, MV_CHECK>(p, m, dc, ksq)
97                         : generate_pawn_moves<BLACK, MV_CHECK>(p, m, dc, ksq));
98   }
99
100   template<PieceType Pt, MoveType Type>
101   FORCE_INLINE MoveStack* generate_piece_moves(const Position& p, MoveStack* m, Color us, Bitboard t) {
102
103     assert(Pt == PAWN);
104     assert(Type == MV_CAPTURE || Type == MV_NON_CAPTURE || Type == MV_EVASION);
105
106     return (us == WHITE ? generate_pawn_moves<WHITE, Type>(p, m, t, SQ_NONE)
107                         : generate_pawn_moves<BLACK, Type>(p, m, t, SQ_NONE));
108   }
109
110   template<PieceType Pt>
111   FORCE_INLINE MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
112
113     Bitboard b;
114     Square from;
115     const Square* pl = pos.piece_list(us, Pt);
116
117     if (*pl != SQ_NONE)
118     {
119         do {
120             from = *pl;
121             b = pos.attacks_from<Pt>(from) & target;
122             SERIALIZE_MOVES(b);
123         } while (*++pl != SQ_NONE);
124     }
125     return mlist;
126   }
127
128   template<>
129   FORCE_INLINE MoveStack* generate_piece_moves<KING>(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
130
131     Bitboard b;
132     Square from = pos.king_square(us);
133
134     b = pos.attacks_from<KING>(from) & target;
135     SERIALIZE_MOVES(b);
136     return mlist;
137   }
138
139 }
140
141
142 /// generate<MV_CAPTURE> generates all pseudo-legal captures and queen
143 /// promotions. Returns a pointer to the end of the move list.
144 ///
145 /// generate<MV_NON_CAPTURE> generates all pseudo-legal non-captures and
146 /// underpromotions. Returns a pointer to the end of the move list.
147 ///
148 /// generate<MV_NON_EVASION> generates all pseudo-legal captures and
149 /// non-captures. Returns a pointer to the end of the move list.
150
151 template<MoveType Type>
152 MoveStack* generate(const Position& pos, MoveStack* mlist) {
153
154   assert(!pos.in_check());
155
156   Color us = pos.side_to_move();
157   Bitboard target;
158
159   if (Type == MV_CAPTURE || Type == MV_NON_EVASION)
160       target = pos.pieces(flip(us));
161   else if (Type == MV_NON_CAPTURE)
162       target = pos.empty_squares();
163   else
164       assert(false);
165
166   if (Type == MV_NON_EVASION)
167   {
168       mlist = generate_piece_moves<PAWN, MV_CAPTURE>(pos, mlist, us, target);
169       mlist = generate_piece_moves<PAWN, MV_NON_CAPTURE>(pos, mlist, us, pos.empty_squares());
170       target |= pos.empty_squares();
171   }
172   else
173       mlist = generate_piece_moves<PAWN, Type>(pos, mlist, us, target);
174
175   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
176   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
177   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
178   mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
179   mlist = generate_piece_moves<KING>(pos, mlist, us, target);
180
181   if (Type != MV_CAPTURE && pos.can_castle(us))
182   {
183       if (pos.can_castle(us == WHITE ? WHITE_OO : BLACK_OO))
184           mlist = generate_castle_moves<KING_SIDE>(pos, mlist, us);
185
186       if (pos.can_castle(us == WHITE ? WHITE_OOO : BLACK_OOO))
187           mlist = generate_castle_moves<QUEEN_SIDE>(pos, mlist, us);
188   }
189
190   return mlist;
191 }
192
193 // Explicit template instantiations
194 template MoveStack* generate<MV_CAPTURE>(const Position& pos, MoveStack* mlist);
195 template MoveStack* generate<MV_NON_CAPTURE>(const Position& pos, MoveStack* mlist);
196 template MoveStack* generate<MV_NON_EVASION>(const Position& pos, MoveStack* mlist);
197
198
199 /// generate<MV_NON_CAPTURE_CHECK> generates all pseudo-legal non-captures and knight
200 /// underpromotions that give check. Returns a pointer to the end of the move list.
201 template<>
202 MoveStack* generate<MV_NON_CAPTURE_CHECK>(const Position& pos, MoveStack* mlist) {
203
204   assert(!pos.in_check());
205
206   Bitboard b, dc;
207   Square from;
208   Color us = pos.side_to_move();
209   Square ksq = pos.king_square(flip(us));
210
211   assert(pos.piece_on(ksq) == make_piece(flip(us), KING));
212
213   // Discovered non-capture checks
214   b = dc = pos.discovered_check_candidates();
215
216   while (b)
217   {
218      from = pop_1st_bit(&b);
219      switch (type_of(pos.piece_on(from)))
220      {
221       case PAWN:   /* Will be generated togheter with pawns direct checks */     break;
222       case KNIGHT: mlist = generate_discovered_checks<KNIGHT>(pos, mlist, from); break;
223       case BISHOP: mlist = generate_discovered_checks<BISHOP>(pos, mlist, from); break;
224       case ROOK:   mlist = generate_discovered_checks<ROOK>(pos, mlist, from);   break;
225       case KING:   mlist = generate_discovered_checks<KING>(pos, mlist, from);   break;
226       default: assert(false); break;
227      }
228   }
229
230   // Direct non-capture checks
231   mlist = generate_direct_checks<PAWN>(pos, mlist, us, dc, ksq);
232   mlist = generate_direct_checks<KNIGHT>(pos, mlist, us, dc, ksq);
233   mlist = generate_direct_checks<BISHOP>(pos, mlist, us, dc, ksq);
234   mlist = generate_direct_checks<ROOK>(pos, mlist, us, dc, ksq);
235   return  generate_direct_checks<QUEEN>(pos, mlist, us, dc, ksq);
236 }
237
238
239 /// generate<MV_EVASION> generates all pseudo-legal check evasions when the side
240 /// to move is in check. Returns a pointer to the end of the move list.
241 template<>
242 MoveStack* generate<MV_EVASION>(const Position& pos, MoveStack* mlist) {
243
244   assert(pos.in_check());
245
246   Bitboard b, target;
247   Square from, checksq;
248   int checkersCnt = 0;
249   Color us = pos.side_to_move();
250   Square ksq = pos.king_square(us);
251   Bitboard checkers = pos.checkers();
252   Bitboard sliderAttacks = 0;
253
254   assert(pos.piece_on(ksq) == make_piece(us, KING));
255   assert(checkers);
256
257   // Find squares attacked by slider checkers, we will remove
258   // them from the king evasions set so to early skip known
259   // illegal moves and avoid an useless legality check later.
260   b = checkers;
261   do
262   {
263       checkersCnt++;
264       checksq = pop_1st_bit(&b);
265
266       assert(color_of(pos.piece_on(checksq)) == flip(us));
267
268       switch (type_of(pos.piece_on(checksq)))
269       {
270       case BISHOP: sliderAttacks |= BishopPseudoAttacks[checksq]; break;
271       case ROOK:   sliderAttacks |= RookPseudoAttacks[checksq];   break;
272       case QUEEN:
273           // If queen and king are far we can safely remove all the squares attacked
274           // in the other direction becuase are not reachable by the king anyway.
275           if (squares_between(ksq, checksq) || (RookPseudoAttacks[checksq] & (1ULL << ksq)))
276               sliderAttacks |= QueenPseudoAttacks[checksq];
277
278           // Otherwise, if king and queen are adjacent and on a diagonal line, we need to
279           // use real rook attacks to check if king is safe to move in the other direction.
280           // For example: king in B2, queen in A1 a knight in B1, and we can safely move to C1.
281           else
282               sliderAttacks |= BishopPseudoAttacks[checksq] | pos.attacks_from<ROOK>(checksq);
283
284       default:
285           break;
286       }
287   } while (b);
288
289   // Generate evasions for king, capture and non capture moves
290   b = pos.attacks_from<KING>(ksq) & ~pos.pieces(us) & ~sliderAttacks;
291   from = ksq;
292   SERIALIZE_MOVES(b);
293
294   // Generate evasions for other pieces only if not double check
295   if (checkersCnt > 1)
296       return mlist;
297
298   // Find squares where a blocking evasion or a capture of the
299   // checker piece is possible.
300   target = squares_between(checksq, ksq) | checkers;
301
302   mlist = generate_piece_moves<PAWN, MV_EVASION>(pos, mlist, us, target);
303   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
304   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
305   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
306   return  generate_piece_moves<QUEEN>(pos, mlist, us, target);
307 }
308
309
310 /// generate<MV_LEGAL> computes a complete list of legal moves in the current position
311
312 template<>
313 MoveStack* generate<MV_LEGAL>(const Position& pos, MoveStack* mlist) {
314
315   MoveStack *last, *cur = mlist;
316   Bitboard pinned = pos.pinned_pieces();
317
318   last = pos.in_check() ? generate<MV_EVASION>(pos, mlist)
319                         : generate<MV_NON_EVASION>(pos, mlist);
320
321   // Remove illegal moves from the list
322   while (cur != last)
323       if (!pos.pl_move_is_legal(cur->move, pinned))
324           cur->move = (--last)->move;
325       else
326           cur++;
327
328   return last;
329 }
330
331
332 namespace {
333
334   template<Square Delta>
335   inline Bitboard move_pawns(Bitboard p) {
336
337     return Delta == DELTA_N  ? p << 8 : Delta == DELTA_S  ? p >> 8 :
338            Delta == DELTA_NE ? p << 9 : Delta == DELTA_SE ? p >> 7 :
339            Delta == DELTA_NW ? p << 7 : Delta == DELTA_SW ? p >> 9 : p;
340   }
341
342   template<MoveType Type, Square Delta>
343   inline MoveStack* generate_pawn_captures(MoveStack* mlist, Bitboard pawns, Bitboard target) {
344
345     const Bitboard TFileABB = (Delta == DELTA_NE || Delta == DELTA_SE ? FileABB : FileHBB);
346
347     Bitboard b;
348     Square to;
349
350     // Captures in the a1-h8 (a8-h1 for black) diagonal or in the h1-a8 (h8-a1 for black)
351     b = move_pawns<Delta>(pawns) & target & ~TFileABB;
352     SERIALIZE_MOVES_D(b, -Delta);
353     return mlist;
354   }
355
356   template<MoveType Type, Square Delta>
357   inline MoveStack* generate_promotions(const Position& pos, MoveStack* mlist, Bitboard pawnsOn7, Bitboard target) {
358
359     const Bitboard TFileABB = (Delta == DELTA_NE || Delta == DELTA_SE ? FileABB : FileHBB);
360
361     Bitboard b;
362     Square to;
363
364     // Promotions and under-promotions, both captures and non-captures
365     b = move_pawns<Delta>(pawnsOn7) & target;
366
367     if (Delta != DELTA_N && Delta != DELTA_S)
368         b &= ~TFileABB;
369
370     while (b)
371     {
372         to = pop_1st_bit(&b);
373
374         if (Type == MV_CAPTURE || Type == MV_EVASION)
375             (*mlist++).move = make_promotion(to - Delta, to, QUEEN);
376
377         if (Type == MV_NON_CAPTURE || Type == MV_EVASION)
378         {
379             (*mlist++).move = make_promotion(to - Delta, to, ROOK);
380             (*mlist++).move = make_promotion(to - Delta, to, BISHOP);
381             (*mlist++).move = make_promotion(to - Delta, to, KNIGHT);
382         }
383
384         // This is the only possible under promotion that can give a check
385         // not already included in the queen-promotion.
386         if (   Type == MV_CHECK
387             && bit_is_set(pos.attacks_from<KNIGHT>(to), pos.king_square(Delta > 0 ? BLACK : WHITE)))
388             (*mlist++).move = make_promotion(to - Delta, to, KNIGHT);
389         else (void)pos; // Silence a warning under MSVC
390     }
391     return mlist;
392   }
393
394   template<Color Us, MoveType Type>
395   MoveStack* generate_pawn_moves(const Position& pos, MoveStack* mlist, Bitboard target, Square ksq) {
396
397     // Calculate our parametrized parameters at compile time, named
398     // according to the point of view of white side.
399     const Color    Them      = (Us == WHITE ? BLACK    : WHITE);
400     const Bitboard TRank7BB  = (Us == WHITE ? Rank7BB  : Rank2BB);
401     const Bitboard TRank3BB  = (Us == WHITE ? Rank3BB  : Rank6BB);
402     const Square   UP        = (Us == WHITE ? DELTA_N  : DELTA_S);
403     const Square   RIGHT_UP  = (Us == WHITE ? DELTA_NE : DELTA_SW);
404     const Square   LEFT_UP   = (Us == WHITE ? DELTA_NW : DELTA_SE);
405
406     Square to;
407     Bitboard b1, b2, dc1, dc2, pawnPushes, emptySquares;
408     Bitboard pawns = pos.pieces(PAWN, Us);
409     Bitboard pawnsOn7 = pawns & TRank7BB;
410     Bitboard enemyPieces = (Type == MV_CAPTURE ? target : pos.pieces(Them));
411
412     // Pre-calculate pawn pushes before changing emptySquares definition
413     if (Type != MV_CAPTURE)
414     {
415         emptySquares = (Type == MV_NON_CAPTURE ? target : pos.empty_squares());
416         pawnPushes = move_pawns<UP>(pawns & ~TRank7BB) & emptySquares;
417     }
418
419     if (Type == MV_EVASION)
420     {
421         emptySquares &= target; // Only blocking squares
422         enemyPieces  &= target; // Capture only the checker piece
423     }
424
425     // Promotions and underpromotions
426     if (pawnsOn7)
427     {
428         if (Type == MV_CAPTURE)
429             emptySquares = pos.empty_squares();
430
431         pawns &= ~TRank7BB;
432         mlist = generate_promotions<Type, RIGHT_UP>(pos, mlist, pawnsOn7, enemyPieces);
433         mlist = generate_promotions<Type, LEFT_UP>(pos, mlist, pawnsOn7, enemyPieces);
434         mlist = generate_promotions<Type, UP>(pos, mlist, pawnsOn7, emptySquares);
435     }
436
437     // Standard captures
438     if (Type == MV_CAPTURE || Type == MV_EVASION)
439     {
440         mlist = generate_pawn_captures<Type, RIGHT_UP>(mlist, pawns, enemyPieces);
441         mlist = generate_pawn_captures<Type, LEFT_UP>(mlist, pawns, enemyPieces);
442     }
443
444     // Single and double pawn pushes
445     if (Type != MV_CAPTURE)
446     {
447         b1 = (Type != MV_EVASION ? pawnPushes : pawnPushes & emptySquares);
448         b2 = move_pawns<UP>(pawnPushes & TRank3BB) & emptySquares;
449
450         if (Type == MV_CHECK)
451         {
452             // Consider only pawn moves which give direct checks
453             b1 &= pos.attacks_from<PAWN>(ksq, Them);
454             b2 &= pos.attacks_from<PAWN>(ksq, Them);
455
456             // Add pawn moves which gives discovered check. This is possible only
457             // if the pawn is not on the same file as the enemy king, because we
458             // don't generate captures.
459             if (pawns & target) // For CHECK type target is dc bitboard
460             {
461                 dc1 = move_pawns<UP>(pawns & target & ~file_bb(ksq)) & emptySquares;
462                 dc2 = move_pawns<UP>(dc1 & TRank3BB) & emptySquares;
463
464                 b1 |= dc1;
465                 b2 |= dc2;
466             }
467         }
468         SERIALIZE_MOVES_D(b1, -UP);
469         SERIALIZE_MOVES_D(b2, -UP -UP);
470     }
471
472     // En passant captures
473     if ((Type == MV_CAPTURE || Type == MV_EVASION) && pos.ep_square() != SQ_NONE)
474     {
475         assert(Us != WHITE || rank_of(pos.ep_square()) == RANK_6);
476         assert(Us != BLACK || rank_of(pos.ep_square()) == RANK_3);
477
478         // An en passant capture can be an evasion only if the checking piece
479         // is the double pushed pawn and so is in the target. Otherwise this
480         // is a discovery check and we are forced to do otherwise.
481         if (Type == MV_EVASION && !bit_is_set(target, pos.ep_square() - UP))
482             return mlist;
483
484         b1 = pawns & pos.attacks_from<PAWN>(pos.ep_square(), Them);
485
486         assert(b1);
487
488         while (b1)
489         {
490             to = pop_1st_bit(&b1);
491             (*mlist++).move = make_enpassant(to, pos.ep_square());
492         }
493     }
494     return mlist;
495   }
496
497   template<CastlingSide Side>
498   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist, Color us) {
499
500     CastleRight f = CastleRight((Side == KING_SIDE ? WHITE_OO : WHITE_OOO) << us);
501     Color them = flip(us);
502
503     // After castling, the rook and king's final positions are exactly the same
504     // in Chess960 as they would be in standard chess.
505     Square kfrom = pos.king_square(us);
506     Square rfrom = pos.castle_rook_square(f);
507     Square kto = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);
508     Square rto = relative_square(us, Side == KING_SIDE ? SQ_F1 : SQ_D1);
509
510     assert(!pos.in_check());
511     assert(pos.piece_on(kfrom) == make_piece(us, KING));
512     assert(pos.piece_on(rfrom) == make_piece(us, ROOK));
513
514     // Unimpeded rule: All the squares between the king's initial and final squares
515     // (including the final square), and all the squares between the rook's initial
516     // and final squares (including the final square), must be vacant except for
517     // the king and castling rook.
518     for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); s++)
519         if (  (s != kfrom && s != rfrom && !pos.square_is_empty(s))
520             ||(pos.attackers_to(s) & pos.pieces(them)))
521             return mlist;
522
523     for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); s++)
524         if (s != kfrom && s != rfrom && !pos.square_is_empty(s))
525             return mlist;
526
527     // Because we generate only legal castling moves we need to verify that
528     // when moving the castling rook we do not discover some hidden checker.
529     // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
530     if (pos.is_chess960())
531     {
532         Bitboard occ = pos.occupied_squares();
533         clear_bit(&occ, rfrom);
534         if (pos.attackers_to(kto, occ) & pos.pieces(them))
535             return mlist;
536     }
537
538     (*mlist++).move = make_castle(kfrom, rfrom);
539
540     return mlist;
541   }
542
543 } // namespace