git.sesse.net Git - stockfish/blob - 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-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   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
  21 ////
  22 //// Includes
  23 ////
  24
  25 #include <cassert>
  26
  27 #include "bitcount.h"
  28 #include "movegen.h"
  29
  30 // Simple macro to wrap a very common while loop, no facny, no flexibility,
  31 // hardcoded list name 'mlist' and from square 'from'.
  32 #define SERIALIZE_MOVES(b) while (b) (*mlist++).move = make_move(from, pop_1st_bit(&b))
  33
  34 // Version used for pawns, where the 'from' square is given as a delta from the 'to' square
  35 #define SERIALIZE_MOVES_D(b, d) while (b) { to = pop_1st_bit(&b); (*mlist++).move = make_move(to + (d), to); }
  36
  37 ////
  38 //// Local definitions
  39 ////
  40
  41 namespace {
  42
  43   enum CastlingSide {
  44     KING_SIDE,
  45     QUEEN_SIDE
  46   };
  47
  48   enum MoveType {
  49     CAPTURE,
  50     NON_CAPTURE,
  51     CHECK,
  52     EVASION
  53   };
  54
  55   // Functions
  56   bool castling_is_check(const Position&, CastlingSide);
  57
  58   // Helper templates
  59   template<CastlingSide Side>
  60   MoveStack* generate_castle_moves(const Position&, MoveStack*);
  61
  62   template<Color Us, SquareDelta Diagonal>
  63   MoveStack* generate_pawn_captures_diagonal(MoveStack*, Bitboard, Bitboard, bool);
  64
  65   template<Color Us, MoveType Type>
  66   MoveStack* generate_pawn_moves(const Position&, MoveStack*, Bitboard = EmptyBoardBB,
  67                                  Square = SQ_NONE, Bitboard = EmptyBoardBB);
  68
  69   template<Color Us, SquareDelta Direction>
  70   inline Bitboard move_pawns(Bitboard p) {
  71
  72     if (Direction == DELTA_N)
  73         return Us == WHITE ? p << 8 : p >> 8;
  74     else if (Direction == DELTA_NE)
  75         return Us == WHITE ? p << 9 : p >> 7;
  76     else if (Direction == DELTA_NW)
  77         return Us == WHITE ? p << 7 : p >> 9;
  78     else
  79         return p;
  80   }
  81
  82   // Template generate_piece_checks() with specializations
  83   template<PieceType>
  84   MoveStack* generate_piece_checks(const Position&, MoveStack*, Color, Bitboard, Square);
  85
  86   template<>
  87   inline MoveStack* generate_piece_checks<PAWN>(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) {
  88
  89     return (us == WHITE ? generate_pawn_moves<WHITE, CHECK>(p, m, dc, ksq)
  90                         : generate_pawn_moves<BLACK, CHECK>(p, m, dc, ksq));
  91   }
  92
  93   // Template generate_piece_moves() with specializations and overloads
  94   template<PieceType>
  95   MoveStack* generate_piece_moves(const Position&, MoveStack*, Color, Bitboard);
  96
  97   template<>
  98   MoveStack* generate_piece_moves<KING>(const Position&, MoveStack*, Color, Bitboard);
  99
 100   template<PieceType Piece, MoveType Type>
 101   inline MoveStack* generate_piece_moves(const Position& p, MoveStack* m, Color us) {
 102
 103     assert(Piece == PAWN);
 104     assert(Type == CAPTURE || Type == NON_CAPTURE);
 105
 106     return (us == WHITE ? generate_pawn_moves<WHITE, Type>(p, m)
 107                         : generate_pawn_moves<BLACK, Type>(p, m));
 108   }
 109
 110   template<PieceType>
 111   MoveStack* generate_piece_moves(const Position&, MoveStack*, Color, Bitboard, Bitboard);
 112
 113   template<>
 114   inline MoveStack* generate_piece_moves<PAWN>(const Position& p, MoveStack* m,
 115                                                Color us, Bitboard t, Bitboard pnd) {
 116
 117     return (us == WHITE ? generate_pawn_moves<WHITE, EVASION>(p, m, pnd, SQ_NONE, t)
 118                         : generate_pawn_moves<BLACK, EVASION>(p, m, pnd, SQ_NONE, t));
 119   }
 120 }
 121
 122
 123 ////
 124 //// Functions
 125 ////
 126
 127
 128 /// generate_captures() generates all pseudo-legal captures and queen
 129 /// promotions. Returns a pointer to the end of the move list.
 130
 131 MoveStack* generate_captures(const Position& pos, MoveStack* mlist) {
 132
 133   assert(pos.is_ok());
 134   assert(!pos.is_check());
 135
 136   Color us = pos.side_to_move();
 137   Bitboard target = pos.pieces_of_color(opposite_color(us));
 138
 139   mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
 140   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
 141   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
 142   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
 143   mlist = generate_piece_moves<PAWN, CAPTURE>(pos, mlist, us);
 144   return  generate_piece_moves<KING>(pos, mlist, us, target);
 145 }
 146
 147
 148 /// generate_noncaptures() generates all pseudo-legal non-captures and
 149 /// underpromotions. Returns a pointer to the end of the move list.
 150
 151 MoveStack* generate_noncaptures(const Position& pos, MoveStack* mlist) {
 152
 153   assert(pos.is_ok());
 154   assert(!pos.is_check());
 155
 156   Color us = pos.side_to_move();
 157   Bitboard target = pos.empty_squares();
 158
 159   mlist = generate_piece_moves<PAWN, NON_CAPTURE>(pos, mlist, us);
 160   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
 161   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
 162   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
 163   mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
 164   mlist = generate_piece_moves<KING>(pos, mlist, us, target);
 165   mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
 166   return  generate_castle_moves<QUEEN_SIDE>(pos, mlist);
 167 }
 168
 169
 170 /// generate_non_capture_checks() generates all pseudo-legal non-captures and
 171 /// underpromotions that give check. Returns a pointer to the end of the move list.
 172
 173 MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) {
 174
 175   assert(pos.is_ok());
 176   assert(!pos.is_check());
 177
 178   Color us = pos.side_to_move();
 179   Square ksq = pos.king_square(opposite_color(us));
 180
 181   assert(pos.piece_on(ksq) == piece_of_color_and_type(opposite_color(us), KING));
 182
 183   // Pieces moves
 184   mlist = generate_piece_checks<PAWN>(pos, mlist, us, dc, ksq);
 185   mlist = generate_piece_checks<KNIGHT>(pos, mlist, us, dc, ksq);
 186   mlist = generate_piece_checks<BISHOP>(pos, mlist, us, dc, ksq);
 187   mlist = generate_piece_checks<ROOK>(pos, mlist, us, dc, ksq);
 188   mlist = generate_piece_checks<QUEEN>(pos, mlist, us, dc, ksq);
 189   mlist = generate_piece_checks<KING>(pos, mlist, us, dc, ksq);
 190
 191   // Castling moves that give check. Very rare but nice to have!
 192   if (   pos.can_castle_queenside(us)
 193       && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_D)
 194       && castling_is_check(pos, QUEEN_SIDE))
 195       mlist = generate_castle_moves<QUEEN_SIDE>(pos, mlist);
 196
 197   if (   pos.can_castle_kingside(us)
 198       && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_F)
 199       && castling_is_check(pos, KING_SIDE))
 200       mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
 201
 202   return mlist;
 203 }
 204
 205
 206 /// generate_evasions() generates all check evasions when the side to move is
 207 /// in check. Unlike the other move generation functions, this one generates
 208 /// only legal moves. Returns a pointer to the end of the move list.
 209
 210 MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) {
 211
 212   assert(pos.is_ok());
 213   assert(pos.is_check());
 214
 215   Square from, to;
 216   Color us = pos.side_to_move();
 217   Color them = opposite_color(us);
 218   Square ksq = pos.king_square(us);
 219   Bitboard sliderAttacks = EmptyBoardBB;
 220   Bitboard checkers = pos.checkers();
 221
 222   assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING));
 223
 224   // The bitboard of occupied pieces without our king
 225   Bitboard b_noKing = pos.occupied_squares();
 226   clear_bit(&b_noKing, ksq);
 227
 228   // Find squares attacked by slider checkers, we will remove
 229   // them from the king evasions set so to avoid a couple
 230   // of cycles in the slow king evasions legality check loop
 231   // and to be able to use attackers_to().
 232   Bitboard b = checkers & pos.pieces(BISHOP, QUEEN);
 233   while (b)
 234   {
 235       from = pop_1st_bit(&b);
 236       sliderAttacks |= bishop_attacks_bb(from, b_noKing);
 237   }
 238
 239   b = checkers & pos.pieces(ROOK, QUEEN);
 240   while (b)
 241   {
 242       from = pop_1st_bit(&b);
 243       sliderAttacks |= rook_attacks_bb(from, b_noKing);
 244   }
 245
 246   // Generate evasions for king, capture and non capture moves
 247   Bitboard enemy = pos.pieces_of_color(them);
 248   Bitboard b1 = pos.attacks_from<KING>(ksq) & ~pos.pieces_of_color(us) & ~sliderAttacks;
 249   while (b1)
 250   {
 251       // Note that we can use attackers_to() only because we have already
 252       // removed from b1 the squares attacked by slider checkers.
 253       to = pop_1st_bit(&b1);
 254       if (!(pos.attackers_to(to) & enemy))
 255           (*mlist++).move = make_move(ksq, to);
 256   }
 257
 258   // Generate evasions for other pieces only if not double check. We use a
 259   // simple bit twiddling hack here rather than calling count_1s in order to
 260   // save some time (we know that pos.checkers() has at most two nonzero bits).
 261   if (!(checkers & (checkers - 1))) // Only one bit set?
 262   {
 263       Square checksq = first_1(checkers);
 264
 265       assert(pos.color_of_piece_on(checksq) == them);
 266
 267       // Generate captures of the checking piece
 268
 269       // Pawn captures
 270       b1 = pos.attacks_from<PAWN>(checksq, them) & pos.pieces(PAWN, us) & ~pinned;
 271       while (b1)
 272       {
 273           from = pop_1st_bit(&b1);
 274           if (relative_rank(us, checksq) == RANK_8)
 275           {
 276               (*mlist++).move = make_promotion_move(from, checksq, QUEEN);
 277               (*mlist++).move = make_promotion_move(from, checksq, ROOK);
 278               (*mlist++).move = make_promotion_move(from, checksq, BISHOP);
 279               (*mlist++).move = make_promotion_move(from, checksq, KNIGHT);
 280           } else
 281               (*mlist++).move = make_move(from, checksq);
 282       }
 283
 284       // Pieces captures
 285       b1 = (  (pos.attacks_from<KNIGHT>(checksq) & pos.pieces(KNIGHT, us))
 286             | (pos.attacks_from<BISHOP>(checksq) & pos.pieces(BISHOP, QUEEN, us))
 287             | (pos.attacks_from<ROOK>(checksq)   & pos.pieces(ROOK, QUEEN, us)) ) & ~pinned;
 288
 289       while (b1)
 290       {
 291           from = pop_1st_bit(&b1);
 292           (*mlist++).move = make_move(from, checksq);
 293       }
 294
 295       // Blocking check evasions are possible only if the checking piece is a slider
 296       if (sliderAttacks)
 297       {
 298           Bitboard blockSquares = squares_between(checksq, ksq);
 299
 300           assert((pos.occupied_squares() & blockSquares) == EmptyBoardBB);
 301
 302           if (blockSquares)
 303           {
 304               mlist = generate_piece_moves<PAWN>(pos, mlist, us, blockSquares, pinned);
 305               mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, blockSquares, pinned);
 306               mlist = generate_piece_moves<BISHOP>(pos, mlist, us, blockSquares, pinned);
 307               mlist = generate_piece_moves<ROOK>(pos, mlist, us, blockSquares, pinned);
 308               mlist = generate_piece_moves<QUEEN>(pos, mlist, us, blockSquares, pinned);
 309           }
 310       }
 311
 312       // Finally, the special case of en passant captures. An en passant
 313       // capture can only be a check evasion if the check is not a discovered
 314       // check. If pos.ep_square() is set, the last move made must have been
 315       // a double pawn push. If, furthermore, the checking piece is a pawn,
 316       // an en passant check evasion may be possible.
 317       if (pos.ep_square() != SQ_NONE && (checkers & pos.pieces(PAWN, them)))
 318       {
 319           to = pos.ep_square();
 320           b1 = pos.attacks_from<PAWN>(to, them) & pos.pieces(PAWN, us);
 321
 322           // The checking pawn cannot be a discovered (bishop) check candidate
 323           // otherwise we were in check also before last double push move.
 324           assert(!bit_is_set(pos.discovered_check_candidates(them), checksq));
 325           assert(count_1s(b1) == 1 || count_1s(b1) == 2);
 326
 327           b1 &= ~pinned;
 328           while (b1)
 329           {
 330               from = pop_1st_bit(&b1);
 331               // Move is always legal because checking pawn is not a discovered
 332               // check candidate and our capturing pawn has been already tested
 333               // against pinned pieces.
 334               (*mlist++).move = make_ep_move(from, to);
 335           }
 336       }
 337   }
 338   return mlist;
 339 }
 340
 341
 342 /// generate_moves() computes a complete list of legal or pseudo-legal moves in
 343 /// the current position. This function is not very fast, and should be used
 344 /// only in non time-critical paths.
 345
 346 MoveStack* generate_moves(const Position& pos, MoveStack* mlist, bool pseudoLegal) {
 347
 348   assert(pos.is_ok());
 349
 350   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 351
 352   if (pos.is_check())
 353       return generate_evasions(pos, mlist, pinned);
 354
 355   // Generate pseudo-legal moves
 356   MoveStack* last = generate_captures(pos, mlist);
 357   last = generate_noncaptures(pos, last);
 358   if (pseudoLegal)
 359       return last;
 360
 361   // Remove illegal moves from the list
 362   for (MoveStack* cur = mlist; cur != last; cur++)
 363       if (!pos.pl_move_is_legal(cur->move, pinned))
 364       {
 365           cur->move = (--last)->move;
 366           cur--;
 367       }
 368   return last;
 369 }
 370
 371
 372 /// move_is_legal() takes a position and a (not necessarily pseudo-legal)
 373 /// move and tests whether the move is legal. This version is not very fast
 374 /// and should be used only in non time-critical paths.
 375
 376 bool move_is_legal(const Position& pos, const Move m) {
 377
 378   MoveStack mlist[256];
 379   MoveStack* last = generate_moves(pos, mlist, true);
 380   for (MoveStack* cur = mlist; cur != last; cur++)
 381       if (cur->move == m)
 382           return pos.pl_move_is_legal(m);
 383
 384   return false;
 385 }
 386
 387
 388 /// Fast version of move_is_legal() that takes a position a move and a
 389 /// bitboard of pinned pieces as input, and tests whether the move is legal.
 390 /// This version must only be used when the side to move is not in check.
 391
 392 bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
 393
 394   assert(pos.is_ok());
 395   assert(!pos.is_check());
 396   assert(move_is_ok(m));
 397   assert(pinned == pos.pinned_pieces(pos.side_to_move()));
 398
 399   // Use a slower but simpler function for uncommon cases
 400   if (move_is_ep(m) || move_is_castle(m))
 401       return move_is_legal(pos, m);
 402
 403   Color us = pos.side_to_move();
 404   Color them = opposite_color(us);
 405   Square from = move_from(m);
 406   Square to = move_to(m);
 407   Piece pc = pos.piece_on(from);
 408
 409   // If the from square is not occupied by a piece belonging to the side to
 410   // move, the move is obviously not legal.
 411   if (color_of_piece(pc) != us)
 412       return false;
 413
 414   // The destination square cannot be occupied by a friendly piece
 415   if (pos.color_of_piece_on(to) == us)
 416       return false;
 417
 418   // Handle the special case of a pawn move
 419   if (type_of_piece(pc) == PAWN)
 420   {
 421       // Move direction must be compatible with pawn color
 422       int direction = to - from;
 423       if ((us == WHITE) != (direction > 0))
 424           return false;
 425
 426       // A pawn move is a promotion iff the destination square is
 427       // on the 8/1th rank.
 428       if ((  (square_rank(to) == RANK_8 && us == WHITE)
 429            ||(square_rank(to) == RANK_1 && us != WHITE)) != bool(move_is_promotion(m)))
 430           return false;
 431
 432       // Proceed according to the square delta between the origin and
 433       // destination squares.
 434       switch (direction)
 435       {
 436       case DELTA_NW:
 437       case DELTA_NE:
 438       case DELTA_SW:
 439       case DELTA_SE:
 440       // Capture. The destination square must be occupied by an enemy
 441       // piece (en passant captures was handled earlier).
 442           if (pos.color_of_piece_on(to) != them)
 443               return false;
 444           break;
 445
 446       case DELTA_N:
 447       case DELTA_S:
 448       // Pawn push. The destination square must be empty.
 449           if (!pos.square_is_empty(to))
 450               return false;
 451           break;
 452
 453       case DELTA_NN:
 454       // Double white pawn push. The destination square must be on the fourth
 455       // rank, and both the destination square and the square between the
 456       // source and destination squares must be empty.
 457       if (   square_rank(to) != RANK_4
 458           || !pos.square_is_empty(to)
 459           || !pos.square_is_empty(from + DELTA_N))
 460           return false;
 461           break;
 462
 463       case DELTA_SS:
 464       // Double black pawn push. The destination square must be on the fifth
 465       // rank, and both the destination square and the square between the
 466       // source and destination squares must be empty.
 467           if (   square_rank(to) != RANK_5
 468               || !pos.square_is_empty(to)
 469               || !pos.square_is_empty(from + DELTA_S))
 470               return false;
 471           break;
 472
 473       default:
 474           return false;
 475       }
 476       // The move is pseudo-legal, check if it is also legal
 477       return pos.pl_move_is_legal(m, pinned);
 478   }
 479
 480   // Luckly we can handle all the other pieces in one go
 481   return (   bit_is_set(pos.attacks_from(pc, from), to)
 482           && pos.pl_move_is_legal(m, pinned)
 483           && !move_is_promotion(m));
 484 }
 485
 486
 487 namespace {
 488
 489   template<PieceType Piece>
 490   MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 491
 492     Square from;
 493     Bitboard b;
 494
 495     for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++)
 496     {
 497         from = pos.piece_list(us, Piece, i);
 498         b = pos.attacks_from<Piece>(from) & target;
 499         SERIALIZE_MOVES(b);
 500     }
 501     return mlist;
 502   }
 503
 504   template<>
 505   MoveStack* generate_piece_moves<KING>(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 506
 507     Bitboard b;
 508     Square from = pos.king_square(us);
 509
 510     b = pos.attacks_from<KING>(from) & target;
 511     SERIALIZE_MOVES(b);
 512     return mlist;
 513   }
 514
 515   template<PieceType Piece>
 516   MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist,
 517                                   Color us, Bitboard target, Bitboard pinned) {
 518     Square from;
 519     Bitboard b;
 520
 521     for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++)
 522     {
 523         from = pos.piece_list(us, Piece, i);
 524         if (pinned && bit_is_set(pinned, from))
 525             continue;
 526
 527         b = pos.attacks_from<Piece>(from) & target;
 528         SERIALIZE_MOVES(b);
 529     }
 530     return mlist;
 531   }
 532
 533   template<Color Us, SquareDelta Diagonal>
 534   MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion) {
 535
 536     // Calculate our parametrized parameters at compile time
 537     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 538     const Bitboard TFileABB = (Diagonal == DELTA_NE ? FileABB : FileHBB);
 539     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 540     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 541     const SquareDelta TTDELTA_NE = (Diagonal == DELTA_NE ? TDELTA_NE : TDELTA_NW);
 542
 543     Square to;
 544
 545     // Captures in the a1-h8 (a8-h1 for black) diagonal or in the h1-a8 (h8-a1 for black)
 546     Bitboard b1 = move_pawns<Us, Diagonal>(pawns) & ~TFileABB & enemyPieces;
 547
 548     // Capturing promotions
 549     if (promotion)
 550     {
 551         Bitboard b2 = b1 & TRank8BB;
 552         b1 &= ~TRank8BB;
 553         while (b2)
 554         {
 555             to = pop_1st_bit(&b2);
 556             (*mlist++).move = make_promotion_move(to - TTDELTA_NE, to, QUEEN);
 557         }
 558     }
 559
 560     // Capturing non-promotions
 561     SERIALIZE_MOVES_D(b1, -TTDELTA_NE);
 562     return mlist;
 563   }
 564
 565   template<Color Us, MoveType Type>
 566   MoveStack* generate_pawn_moves(const Position& pos, MoveStack* mlist, Bitboard dcp,
 567                                  Square ksq, Bitboard blockSquares) {
 568
 569     // Calculate our parametrized parameters at compile time
 570     const Color Them = (Us == WHITE ? BLACK : WHITE);
 571     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 572     const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB);
 573     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 574     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 575     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 576     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 577
 578     Bitboard b1, b2, dcPawns1, dcPawns2;
 579     Square to;
 580     Bitboard pawns = (Type != EVASION ? pos.pieces(PAWN, Us) : pos.pieces(PAWN, Us) & ~dcp);
 581     Bitboard emptySquares = pos.empty_squares();
 582     bool possiblePromotion = (pawns & TRank7BB);
 583
 584     if (Type == CAPTURE)
 585     {
 586         // Standard captures and capturing promotions in both directions
 587         Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us));
 588         mlist = generate_pawn_captures_diagonal<Us, DELTA_NE>(mlist, pawns, enemyPieces, possiblePromotion);
 589         mlist = generate_pawn_captures_diagonal<Us, DELTA_NW>(mlist, pawns, enemyPieces, possiblePromotion);
 590     }
 591
 592     if (possiblePromotion)
 593     {
 594         // When generating checks consider under-promotion moves (both captures
 595         // and non captures) only if can give a discovery check. Note that dcp
 596         // is dc bitboard or pinned bitboard when Type == EVASION.
 597         Bitboard pp = (Type == CHECK ? pawns & dcp : pawns);
 598
 599         if (Type != EVASION && Type != CAPTURE)
 600         {
 601             Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us));
 602
 603             // Underpromotion captures in the a1-h8 (a8-h1 for black) direction
 604             b1 = move_pawns<Us, DELTA_NE>(pp) & ~FileABB & enemyPieces & TRank8BB;
 605             while (b1)
 606             {
 607                 to = pop_1st_bit(&b1);
 608                 (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, ROOK);
 609                 (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, BISHOP);
 610                 (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, KNIGHT);
 611             }
 612
 613             // Underpromotion captures in the h1-a8 (h8-a1 for black) direction
 614             b1 = move_pawns<Us, DELTA_NW>(pp) & ~FileHBB & enemyPieces & TRank8BB;
 615             while (b1)
 616             {
 617                 to = pop_1st_bit(&b1);
 618                 (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, ROOK);
 619                 (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, BISHOP);
 620                 (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, KNIGHT);
 621             }
 622         }
 623
 624         // Underpromotion pawn pushes. Also promotion for evasions and captures.
 625         b1 = move_pawns<Us, DELTA_N>(pp) & TRank8BB;
 626         b1 &= (Type == EVASION ? blockSquares : emptySquares);
 627
 628         while (b1)
 629         {
 630             to = pop_1st_bit(&b1);
 631             if (Type == EVASION || Type == CAPTURE)
 632                 (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN);
 633
 634             if (Type != CAPTURE)
 635             {
 636                 (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK);
 637                 (*mlist++).move = make_promotion_move(to - TDELTA_N, to, BISHOP);
 638                 (*mlist++).move = make_promotion_move(to - TDELTA_N, to, KNIGHT);
 639             }
 640         }
 641     }
 642
 643     if (Type == CAPTURE)
 644     {
 645         // En passant captures
 646         if (pos.ep_square() != SQ_NONE)
 647         {
 648             assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6);
 649             assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3);
 650
 651             Bitboard b1 = pawns & pos.attacks_from<PAWN>(pos.ep_square(), Them);
 652             assert(b1 != EmptyBoardBB);
 653
 654             while (b1)
 655             {
 656                 to = pop_1st_bit(&b1);
 657                 (*mlist++).move = make_ep_move(to, pos.ep_square());
 658             }
 659         }
 660         return mlist;
 661     }
 662
 663     dcPawns1 = dcPawns2 = EmptyBoardBB;
 664     if (Type == CHECK && (pawns & dcp))
 665     {
 666         // Pawn moves which gives discovered check. This is possible only if the
 667         // pawn is not on the same file as the enemy king, because we don't
 668         // generate captures.
 669         dcPawns1 = move_pawns<Us, DELTA_N>(pawns & dcp & ~file_bb(ksq)) & emptySquares & ~TRank8BB;
 670         dcPawns2 = move_pawns<Us, DELTA_N>(dcPawns1 & TRank3BB) & emptySquares;
 671     }
 672
 673     // Single pawn pushes
 674     b1 = move_pawns<Us, DELTA_N>(pawns) & emptySquares & ~TRank8BB;
 675     b2 = (Type == CHECK ? (b1 & pos.attacks_from<PAWN>(ksq, Them)) | dcPawns1 :
 676          (Type == EVASION ? b1 & blockSquares : b1));
 677     SERIALIZE_MOVES_D(b2, -TDELTA_N);
 678
 679     // Double pawn pushes
 680     b1 = move_pawns<Us, DELTA_N>(b1 & TRank3BB) & emptySquares;
 681     b2 = (Type == CHECK ? (b1 & pos.attacks_from<PAWN>(ksq, Them)) | dcPawns2 :
 682          (Type == EVASION ? b1 & blockSquares : b1));
 683     SERIALIZE_MOVES_D(b2, -TDELTA_N -TDELTA_N);
 684     return mlist;
 685   }
 686
 687   template<PieceType Piece>
 688   MoveStack* generate_piece_checks(const Position& pos, MoveStack* mlist, Color us,
 689                                    Bitboard dc, Square ksq) {
 690
 691     Bitboard target = pos.pieces(Piece, us);
 692
 693     // Discovered non-capture checks
 694     Bitboard b = target & dc;
 695
 696     assert(Piece != QUEEN || !b);
 697
 698     while (b)
 699     {
 700         Square from = pop_1st_bit(&b);
 701         Bitboard bb = pos.attacks_from<Piece>(from) & pos.empty_squares();
 702         if (Piece == KING)
 703             bb &= ~QueenPseudoAttacks[ksq];
 704
 705         SERIALIZE_MOVES(bb);
 706     }
 707
 708     // Direct non-capture checks
 709     b = target & ~dc;
 710     Bitboard checkSqs = pos.attacks_from<Piece>(ksq) & pos.empty_squares();
 711     if (Piece == KING || !checkSqs)
 712         return mlist;
 713
 714     while (b)
 715     {
 716         Square from = pop_1st_bit(&b);
 717         if (   (Piece == QUEEN  && !(QueenPseudoAttacks[from]  & checkSqs))
 718             || (Piece == ROOK   && !(RookPseudoAttacks[from]   & checkSqs))
 719             || (Piece == BISHOP && !(BishopPseudoAttacks[from] & checkSqs)))
 720             continue;
 721
 722         Bitboard bb = pos.attacks_from<Piece>(from) & checkSqs;
 723         SERIALIZE_MOVES(bb);
 724     }
 725     return mlist;
 726   }
 727
 728   template<CastlingSide Side>
 729   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist) {
 730
 731     Color us = pos.side_to_move();
 732
 733     if (  (Side == KING_SIDE && pos.can_castle_kingside(us))
 734         ||(Side == QUEEN_SIDE && pos.can_castle_queenside(us)))
 735     {
 736         Color them = opposite_color(us);
 737         Square ksq = pos.king_square(us);
 738
 739         assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING));
 740
 741         Square rsq = (Side == KING_SIDE ? pos.initial_kr_square(us) : pos.initial_qr_square(us));
 742         Square s1 = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);
 743         Square s2 = relative_square(us, Side == KING_SIDE ? SQ_F1 : SQ_D1);
 744         Square s;
 745         bool illegal = false;
 746
 747         assert(pos.piece_on(rsq) == piece_of_color_and_type(us, ROOK));
 748
 749         // It is a bit complicated to correctly handle Chess960
 750         for (s = Min(ksq, s1); s <= Max(ksq, s1); s++)
 751             if (  (s != ksq && s != rsq && pos.square_is_occupied(s))
 752                 ||(pos.attackers_to(s) & pos.pieces_of_color(them)))
 753                 illegal = true;
 754
 755         for (s = Min(rsq, s2); s <= Max(rsq, s2); s++)
 756             if (s != ksq && s != rsq && pos.square_is_occupied(s))
 757                 illegal = true;
 758
 759         if (   Side == QUEEN_SIDE
 760             && square_file(rsq) == FILE_B
 761             && (   pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, ROOK)
 762                 || pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, QUEEN)))
 763             illegal = true;
 764
 765         if (!illegal)
 766             (*mlist++).move = make_castle_move(ksq, rsq);
 767     }
 768     return mlist;
 769   }
 770
 771   bool castling_is_check(const Position& pos, CastlingSide side) {
 772
 773     // After castling opponent king is attacked by the castled rook?
 774     File rookFile = (side == QUEEN_SIDE ? FILE_D : FILE_F);
 775     Color us = pos.side_to_move();
 776     Square ksq = pos.king_square(us);
 777     Bitboard occ = pos.occupied_squares();
 778
 779     clear_bit(&occ, ksq); // Remove our king from the board
 780     Square rsq = make_square(rookFile, square_rank(ksq));
 781     return bit_is_set(rook_attacks_bb(rsq, occ), pos.king_square(opposite_color(us)));
 782   }
 783 }