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))) // Only one bit set?
 250   {
 251       Square checksq = first_1(checkers);
 252
 253       assert(pos.color_of_piece_on(checksq) == them);
 254
 255       // Generate captures of the checking piece
 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       // Pieces captures
 273       b1 = (  (pos.attacks_from<KNIGHT>(checksq) & pos.pieces(KNIGHT, us))
 274             | (pos.attacks_from<BISHOP>(checksq) & pos.pieces(BISHOP, QUEEN, us))
 275             | (pos.attacks_from<ROOK>(checksq)   & pos.pieces(ROOK, QUEEN, us)) ) & ~pinned;
 276
 277       while (b1)
 278       {
 279           from = pop_1st_bit(&b1);
 280           (*mlist++).move = make_move(from, checksq);
 281       }
 282
 283       // Blocking check evasions are possible only if the checking piece is a slider
 284       if (sliderAttacks)
 285       {
 286           Bitboard blockSquares = squares_between(checksq, ksq);
 287
 288           assert((pos.occupied_squares() & blockSquares) == EmptyBoardBB);
 289
 290           if (blockSquares)
 291           {
 292               mlist = generate_piece_evasions<PAWN>(pos, mlist, us, blockSquares, pinned);
 293               mlist = generate_piece_evasions<KNIGHT>(pos, mlist, us, blockSquares, pinned);
 294               mlist = generate_piece_evasions<BISHOP>(pos, mlist, us, blockSquares, pinned);
 295               mlist = generate_piece_evasions<ROOK>(pos, mlist, us, blockSquares, pinned);
 296               mlist = generate_piece_evasions<QUEEN>(pos, mlist, us, blockSquares, pinned);
 297           }
 298       }
 299
 300       // Finally, the special case of en passant captures. An en passant
 301       // capture can only be a check evasion if the check is not a discovered
 302       // check. If pos.ep_square() is set, the last move made must have been
 303       // a double pawn push. If, furthermore, the checking piece is a pawn,
 304       // an en passant check evasion may be possible.
 305       if (pos.ep_square() != SQ_NONE && (checkers & pos.pieces(PAWN, them)))
 306       {
 307           to = pos.ep_square();
 308           b1 = pos.attacks_from<PAWN>(to, them) & pos.pieces(PAWN, us);
 309
 310           // The checking pawn cannot be a discovered (bishop) check candidate
 311           // otherwise we were in check also before last double push move.
 312           assert(!bit_is_set(pos.discovered_check_candidates(them), checksq));
 313           assert(count_1s(b1) == 1 || count_1s(b1) == 2);
 314
 315           b1 &= ~pinned;
 316           while (b1)
 317           {
 318               from = pop_1st_bit(&b1);
 319               // Move is always legal because checking pawn is not a discovered
 320               // check candidate and our capturing pawn has been already tested
 321               // against pinned pieces.
 322               (*mlist++).move = make_ep_move(from, to);
 323           }
 324       }
 325   }
 326   return mlist;
 327 }
 328
 329
 330 /// generate_moves() computes a complete list of legal or pseudo-legal moves in
 331 /// the current position. This function is not very fast, and should be used
 332 /// only in non time-critical paths.
 333
 334 MoveStack* generate_moves(const Position& pos, MoveStack* mlist, bool pseudoLegal) {
 335
 336   assert(pos.is_ok());
 337
 338   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 339
 340   if (pos.is_check())
 341       return generate_evasions(pos, mlist, pinned);
 342
 343   // Generate pseudo-legal moves
 344   MoveStack* last = generate_captures(pos, mlist);
 345   last = generate_noncaptures(pos, last);
 346   if (pseudoLegal)
 347       return last;
 348
 349   // Remove illegal moves from the list
 350   for (MoveStack* cur = mlist; cur != last; cur++)
 351       if (!pos.pl_move_is_legal(cur->move, pinned))
 352       {
 353           cur->move = (--last)->move;
 354           cur--;
 355       }
 356   return last;
 357 }
 358
 359
 360 /// move_is_legal() takes a position and a (not necessarily pseudo-legal)
 361 /// move and tests whether the move is legal. This version is not very fast
 362 /// and should be used only in non time-critical paths.
 363
 364 bool move_is_legal(const Position& pos, const Move m) {
 365
 366   MoveStack mlist[256];
 367   MoveStack* last = generate_moves(pos, mlist, true);
 368   for (MoveStack* cur = mlist; cur != last; cur++)
 369       if (cur->move == m)
 370           return pos.pl_move_is_legal(m);
 371
 372   return false;
 373 }
 374
 375
 376 /// Fast version of move_is_legal() that takes a position a move and a
 377 /// bitboard of pinned pieces as input, and tests whether the move is legal.
 378 /// This version must only be used when the side to move is not in check.
 379
 380 bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
 381
 382   assert(pos.is_ok());
 383   assert(!pos.is_check());
 384   assert(move_is_ok(m));
 385   assert(pinned == pos.pinned_pieces(pos.side_to_move()));
 386
 387   // Use a slower but simpler function for uncommon cases
 388   if (move_is_ep(m) || move_is_castle(m))
 389       return move_is_legal(pos, m);
 390
 391   Color us = pos.side_to_move();
 392   Color them = opposite_color(us);
 393   Square from = move_from(m);
 394   Square to = move_to(m);
 395   Piece pc = pos.piece_on(from);
 396
 397   // If the from square is not occupied by a piece belonging to the side to
 398   // move, the move is obviously not legal.
 399   if (color_of_piece(pc) != us)
 400       return false;
 401
 402   // The destination square cannot be occupied by a friendly piece
 403   if (pos.color_of_piece_on(to) == us)
 404       return false;
 405
 406   // Handle the special case of a pawn move
 407   if (type_of_piece(pc) == PAWN)
 408   {
 409       // Move direction must be compatible with pawn color
 410       int direction = to - from;
 411       if ((us == WHITE) != (direction > 0))
 412           return false;
 413
 414       // A pawn move is a promotion iff the destination square is
 415       // on the 8/1th rank.
 416       if ((  (square_rank(to) == RANK_8 && us == WHITE)
 417            ||(square_rank(to) == RANK_1 && us != WHITE)) != bool(move_is_promotion(m)))
 418           return false;
 419
 420       // Proceed according to the square delta between the origin and
 421       // destination squares.
 422       switch (direction)
 423       {
 424       case DELTA_NW:
 425       case DELTA_NE:
 426       case DELTA_SW:
 427       case DELTA_SE:
 428       // Capture. The destination square must be occupied by an enemy
 429       // piece (en passant captures was handled earlier).
 430           if (pos.color_of_piece_on(to) != them)
 431               return false;
 432           break;
 433
 434       case DELTA_N:
 435       case DELTA_S:
 436       // Pawn push. The destination square must be empty.
 437           if (!pos.square_is_empty(to))
 438               return false;
 439           break;
 440
 441       case DELTA_NN:
 442       // Double white pawn push. The destination square must be on the fourth
 443       // rank, and both the destination square and the square between the
 444       // source and destination squares must be empty.
 445       if (   square_rank(to) != RANK_4
 446           || !pos.square_is_empty(to)
 447           || !pos.square_is_empty(from + DELTA_N))
 448           return false;
 449           break;
 450
 451       case DELTA_SS:
 452       // Double black pawn push. The destination square must be on the fifth
 453       // rank, and both the destination square and the square between the
 454       // source and destination squares must be empty.
 455           if (   square_rank(to) != RANK_5
 456               || !pos.square_is_empty(to)
 457               || !pos.square_is_empty(from + DELTA_S))
 458               return false;
 459           break;
 460
 461       default:
 462           return false;
 463       }
 464       // The move is pseudo-legal, check if it is also legal
 465       return pos.pl_move_is_legal(m, pinned);
 466   }
 467
 468   // Luckly we can handle all the other pieces in one go
 469   return (   bit_is_set(pos.attacks_from(pc, from), to)
 470           && pos.pl_move_is_legal(m, pinned)
 471           && !move_is_promotion(m));
 472 }
 473
 474
 475 namespace {
 476
 477   template<PieceType Piece>
 478   MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 479
 480     Square from;
 481     Bitboard b;
 482     const Square* ptr = pos.piece_list_begin(us, Piece);
 483
 484     while ((from = *ptr++) != SQ_NONE)
 485     {
 486         b = pos.attacks_from<Piece>(from) & target;
 487         SERIALIZE_MOVES(b);
 488     }
 489     return mlist;
 490   }
 491
 492   template<>
 493   MoveStack* generate_piece_moves<KING>(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 494
 495     Bitboard b;
 496     Square from = pos.king_square(us);
 497
 498     b = pos.attacks_from<KING>(from) & target;
 499     SERIALIZE_MOVES(b);
 500     return mlist;
 501   }
 502
 503   template<PieceType Piece>
 504   MoveStack* generate_piece_evasions(const Position& pos, MoveStack* mlist,
 505                                      Color us, Bitboard target, Bitboard pinned) {
 506     Square from;
 507     Bitboard b;
 508     const Square* ptr = pos.piece_list_begin(us, Piece);
 509
 510     while ((from = *ptr++) != SQ_NONE)
 511     {
 512         if (pinned && bit_is_set(pinned, from))
 513             continue;
 514
 515         b = pos.attacks_from<Piece>(from) & target;
 516         SERIALIZE_MOVES(b);
 517     }
 518     return mlist;
 519   }
 520
 521   template<Color Us, SquareDelta Direction>
 522   inline Bitboard move_pawns(Bitboard p) {
 523
 524     if (Direction == DELTA_N)
 525         return Us == WHITE ? p << 8 : p >> 8;
 526     else if (Direction == DELTA_NE)
 527         return Us == WHITE ? p << 9 : p >> 7;
 528     else if (Direction == DELTA_NW)
 529         return Us == WHITE ? p << 7 : p >> 9;
 530     else
 531         return p;
 532   }
 533
 534   template<Color Us, SquareDelta Diagonal>
 535   MoveStack* generate_pawn_diagonal_captures(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion) {
 536
 537     // Calculate our parametrized parameters at compile time
 538     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 539     const Bitboard TFileABB = (Diagonal == DELTA_NE ? FileABB : FileHBB);
 540     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 541     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 542     const SquareDelta TTDELTA_NE = (Diagonal == DELTA_NE ? TDELTA_NE : TDELTA_NW);
 543
 544     Square to;
 545
 546     // Captures in the a1-h8 (a8-h1 for black) diagonal or in the h1-a8 (h8-a1 for black)
 547     Bitboard b1 = move_pawns<Us, Diagonal>(pawns) & ~TFileABB & enemyPieces;
 548
 549     // Capturing promotions
 550     if (promotion)
 551     {
 552         Bitboard b2 = b1 & TRank8BB;
 553         b1 &= ~TRank8BB;
 554         while (b2)
 555         {
 556             to = pop_1st_bit(&b2);
 557             (*mlist++).move = make_promotion_move(to - TTDELTA_NE, to, QUEEN);
 558         }
 559     }
 560
 561     // Capturing non-promotions
 562     SERIALIZE_MOVES_D(b1, -TTDELTA_NE);
 563     return mlist;
 564   }
 565
 566   template<Color Us, MoveType Type>
 567   MoveStack* generate_pawn_moves(const Position& pos, MoveStack* mlist, Bitboard dcp,
 568                                  Square ksq, Bitboard blockSquares) {
 569
 570     // Calculate our parametrized parameters at compile time
 571     const Color Them = (Us == WHITE ? BLACK : WHITE);
 572     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 573     const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB);
 574     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 575     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 576     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 577     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 578
 579     Bitboard b1, b2, dcPawns1, dcPawns2;
 580     Square to;
 581     Bitboard pawns = (Type == EVASION ? pos.pieces(PAWN, Us) & ~dcp : pos.pieces(PAWN, Us));
 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_diagonal_captures<Us, DELTA_NE>(mlist, pawns, enemyPieces, possiblePromotion);
 589         mlist = generate_pawn_diagonal_captures<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 queen promotions for evasions and captures.
 625         b1 = move_pawns<Us, DELTA_N>(pp) & TRank8BB;
 626         b1 &= (Type == EVASION ? blockSquares : pos.empty_squares());
 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         Bitboard emptySquares = pos.empty_squares();
 646         dcPawns1 = dcPawns2 = EmptyBoardBB;
 647         if (Type == CHECK && (pawns & dcp))
 648         {
 649             // Pawn moves which gives discovered check. This is possible only if the
 650             // pawn is not on the same file as the enemy king, because we don't
 651             // generate captures.
 652             dcPawns1 = move_pawns<Us, DELTA_N>(pawns & dcp & ~file_bb(ksq)) & emptySquares & ~TRank8BB;
 653             dcPawns2 = move_pawns<Us, DELTA_N>(dcPawns1 & TRank3BB) & emptySquares;
 654         }
 655
 656         // Single pawn pushes
 657         b1 = move_pawns<Us, DELTA_N>(pawns) & emptySquares & ~TRank8BB;
 658         b2 = (Type == CHECK ? (b1 & pos.attacks_from<PAWN>(ksq, Them)) | dcPawns1 :
 659              (Type == EVASION ? b1 & blockSquares : b1));
 660         SERIALIZE_MOVES_D(b2, -TDELTA_N);
 661
 662         // Double pawn pushes
 663         b1 = move_pawns<Us, DELTA_N>(b1 & TRank3BB) & emptySquares;
 664         b2 = (Type == CHECK ? (b1 & pos.attacks_from<PAWN>(ksq, Them)) | dcPawns2 :
 665              (Type == EVASION ? b1 & blockSquares : b1));
 666         SERIALIZE_MOVES_D(b2, -TDELTA_N -TDELTA_N);
 667     }
 668     else if (pos.ep_square() != SQ_NONE) // En passant captures
 669     {
 670         assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6);
 671         assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3);
 672
 673         b1 = pawns & pos.attacks_from<PAWN>(pos.ep_square(), Them);
 674         assert(b1 != EmptyBoardBB);
 675
 676         while (b1)
 677         {
 678             to = pop_1st_bit(&b1);
 679             (*mlist++).move = make_ep_move(to, pos.ep_square());
 680         }
 681     }
 682     return mlist;
 683   }
 684
 685   template<PieceType Piece>
 686   MoveStack* generate_discovered_checks(const Position& pos, Square from, MoveStack* mlist) {
 687
 688     assert(Piece != QUEEN);
 689
 690     Bitboard b = pos.attacks_from<Piece>(from) & pos.empty_squares();
 691     if (Piece == KING)
 692     {
 693         Square ksq = pos.king_square(opposite_color(pos.side_to_move()));
 694         b &= ~QueenPseudoAttacks[ksq];
 695     }
 696     SERIALIZE_MOVES(b);
 697     return mlist;
 698   }
 699
 700   template<PieceType Piece>
 701   MoveStack* generate_direct_checks(const Position& pos, MoveStack* mlist, Color us,
 702                                    Bitboard dc, Square ksq) {
 703     assert(Piece != KING);
 704
 705     Square from;
 706     Bitboard checkSqs;
 707     const Square* ptr = pos.piece_list_begin(us, Piece);
 708
 709     if ((from = *ptr++) == SQ_NONE)
 710         return mlist;
 711
 712     checkSqs = pos.attacks_from<Piece>(ksq) & pos.empty_squares();
 713
 714     do
 715     {
 716         if (   (Piece == QUEEN  && !(QueenPseudoAttacks[from]  & checkSqs))
 717             || (Piece == ROOK   && !(RookPseudoAttacks[from]   & checkSqs))
 718             || (Piece == BISHOP && !(BishopPseudoAttacks[from] & checkSqs)))
 719             continue;
 720
 721         if (dc && bit_is_set(dc, from))
 722             continue;
 723
 724         Bitboard bb = pos.attacks_from<Piece>(from) & checkSqs;
 725         SERIALIZE_MOVES(bb);
 726
 727     } while ((from = *ptr++) != SQ_NONE);
 728
 729     return mlist;
 730   }
 731
 732   template<CastlingSide Side>
 733   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist) {
 734
 735     Color us = pos.side_to_move();
 736
 737     if (  (Side == KING_SIDE && pos.can_castle_kingside(us))
 738         ||(Side == QUEEN_SIDE && pos.can_castle_queenside(us)))
 739     {
 740         Color them = opposite_color(us);
 741         Square ksq = pos.king_square(us);
 742
 743         assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING));
 744
 745         Square rsq = (Side == KING_SIDE ? pos.initial_kr_square(us) : pos.initial_qr_square(us));
 746         Square s1 = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);
 747         Square s2 = relative_square(us, Side == KING_SIDE ? SQ_F1 : SQ_D1);
 748         Square s;
 749         bool illegal = false;
 750
 751         assert(pos.piece_on(rsq) == piece_of_color_and_type(us, ROOK));
 752
 753         // It is a bit complicated to correctly handle Chess960
 754         for (s = Min(ksq, s1); s <= Max(ksq, s1); s++)
 755             if (  (s != ksq && s != rsq && pos.square_is_occupied(s))
 756                 ||(pos.attackers_to(s) & pos.pieces_of_color(them)))
 757                 illegal = true;
 758
 759         for (s = Min(rsq, s2); s <= Max(rsq, s2); s++)
 760             if (s != ksq && s != rsq && pos.square_is_occupied(s))
 761                 illegal = true;
 762
 763         if (   Side == QUEEN_SIDE
 764             && square_file(rsq) == FILE_B
 765             && (   pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, ROOK)
 766                 || pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, QUEEN)))
 767             illegal = true;
 768
 769         if (!illegal)
 770             (*mlist++).move = make_castle_move(ksq, rsq);
 771     }
 772     return mlist;
 773   }
 774 }