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