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