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, bsf) while (b) (*mlist++).move = make_move(from, pop_1st_bit<bsf>(&b))
  33
  34 ////
  35 //// Local definitions
  36 ////
  37
  38 namespace {
  39
  40   enum CastlingSide {
  41     KING_SIDE,
  42     QUEEN_SIDE
  43   };
  44
  45   enum MoveType {
  46     CAPTURE,
  47     NON_CAPTURE
  48   };
  49
  50   // Functions
  51   bool castling_is_check(const Position&, CastlingSide);
  52
  53   // Helper templates
  54   template<CastlingSide Side>
  55   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist);
  56
  57   template<Color Us>
  58   MoveStack* generate_pawn_blocking_evasions(const Position&, Bitboard, Bitboard, MoveStack*);
  59
  60   template<Color Us>
  61   MoveStack* generate_pawn_captures(const Position& pos, MoveStack* mlist);
  62
  63   template<Color Us, SquareDelta Diagonal>
  64   MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces);
  65
  66   template<Color Us>
  67   MoveStack* generate_pawn_noncaptures(const Position& pos, MoveStack* mlist);
  68
  69   template<Color Us>
  70   MoveStack* generate_pawn_checks(const Position&, Bitboard, Square, MoveStack*);
  71
  72   template<Color Us, SquareDelta Direction>
  73   inline Bitboard move_pawns(Bitboard p) {
  74
  75     if (Direction == DELTA_N)
  76         return Us == WHITE ? p << 8 : p >> 8;
  77     else if (Direction == DELTA_NE)
  78         return Us == WHITE ? p << 9 : p >> 7;
  79     else if (Direction == DELTA_NW)
  80         return Us == WHITE ? p << 7 : p >> 9;
  81     else
  82         return p;
  83   }
  84
  85   // Template generate_piece_checks() with specializations
  86   template<PieceType, bool HasBSF>
  87   MoveStack* generate_piece_checks(const Position&, MoveStack*, Color, Bitboard, Square);
  88
  89   template<>
  90   inline MoveStack* generate_piece_checks<PAWN, false>(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) {
  91
  92     return (us == WHITE ? generate_pawn_checks<WHITE>(p, dc, ksq, m)
  93                         : generate_pawn_checks<BLACK>(p, dc, ksq, m));
  94   }
  95
  96   // Template generate_piece_moves() with specializations and overloads
  97   template<PieceType, bool HasBSF>
  98   MoveStack* generate_piece_moves(const Position&, MoveStack*, Color us, Bitboard);
  99
 100   template<>
 101   MoveStack* generate_piece_moves<KING, false>(const Position&, MoveStack*, Color, Bitboard);
 102
 103   template<PieceType Piece, MoveType Type>
 104   inline MoveStack* generate_piece_moves(const Position& p, MoveStack* m, Color us) {
 105
 106       assert(Piece == PAWN);
 107
 108       if (Type == CAPTURE)
 109           return (us == WHITE ? generate_pawn_captures<WHITE>(p, m)
 110                               : generate_pawn_captures<BLACK>(p, m));
 111       else
 112           return (us == WHITE ? generate_pawn_noncaptures<WHITE>(p, m)
 113                               : generate_pawn_noncaptures<BLACK>(p, m));
 114   }
 115
 116   template<PieceType, bool HasBSF>
 117   MoveStack* generate_piece_moves(const Position&, MoveStack*, Color us, Bitboard, Bitboard);
 118
 119   template<>
 120   inline MoveStack* generate_piece_moves<PAWN, false>(const Position& p, MoveStack* m,
 121                                                       Color us, Bitboard t, Bitboard pnd) {
 122
 123     return (us == WHITE ? generate_pawn_blocking_evasions<WHITE>(p, pnd, t, m)
 124                         : generate_pawn_blocking_evasions<BLACK>(p, pnd, t, m));
 125   }
 126 }
 127
 128
 129 ////
 130 //// Functions
 131 ////
 132
 133
 134 /// generate_captures generates() all pseudo-legal captures and queen
 135 /// promotions.  The return value is the number of moves generated.
 136 template<bool HasBSF>
 137 int generate_captures(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.pieces_of_color(opposite_color(us));
 144   MoveStack* mlist_start = mlist;
 145
 146   mlist = generate_piece_moves<QUEEN,  HasBSF>(pos, mlist, us, target);
 147   mlist = generate_piece_moves<ROOK,   HasBSF>(pos, mlist, us, target);
 148   mlist = generate_piece_moves<BISHOP, HasBSF>(pos, mlist, us, target);
 149   mlist = generate_piece_moves<KNIGHT, HasBSF>(pos, mlist, us, target);
 150   mlist = generate_piece_moves<PAWN, CAPTURE>(pos, mlist, us);
 151   mlist = generate_piece_moves<KING, false>(pos, mlist, us, target);
 152   return int(mlist - mlist_start);
 153 }
 154
 155 int generate_captures(const Position& pos, MoveStack* mlist) {
 156
 157     return CpuHasPOPCNT ? generate_captures<true>(pos, mlist)
 158                         : generate_captures<false>(pos, mlist);
 159 }
 160
 161
 162 /// generate_noncaptures() generates all pseudo-legal non-captures and
 163 /// underpromotions. The return value is the number of moves generated.
 164 template<bool HasBSF>
 165 int generate_noncaptures(const Position& pos, MoveStack* mlist) {
 166
 167   assert(pos.is_ok());
 168   assert(!pos.is_check());
 169
 170   Color us = pos.side_to_move();
 171   Bitboard target = pos.empty_squares();
 172   MoveStack* mlist_start = mlist;
 173
 174   mlist = generate_piece_moves<PAWN, NON_CAPTURE>(pos, mlist, us);
 175   mlist = generate_piece_moves<KNIGHT, HasBSF>(pos, mlist, us, target);
 176   mlist = generate_piece_moves<BISHOP, HasBSF>(pos, mlist, us, target);
 177   mlist = generate_piece_moves<ROOK,   HasBSF>(pos, mlist, us, target);
 178   mlist = generate_piece_moves<QUEEN,  HasBSF>(pos, mlist, us, target);
 179   mlist = generate_piece_moves<KING,   false>(pos, mlist, us, target);
 180   mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
 181   mlist = generate_castle_moves<QUEEN_SIDE>(pos, mlist);
 182   return int(mlist - mlist_start);
 183 }
 184
 185 int generate_noncaptures(const Position& pos, MoveStack* mlist) {
 186
 187     return CpuHasPOPCNT ? generate_noncaptures<true>(pos, mlist)
 188                         : generate_noncaptures<false>(pos, mlist);
 189 }
 190
 191
 192 /// generate_non_capture_checks() generates all pseudo-legal non-capturing,
 193 /// non-promoting checks. It returns the number of generated moves.
 194 template<bool HasBSF>
 195 int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) {
 196
 197   assert(pos.is_ok());
 198   assert(!pos.is_check());
 199
 200   Color us = pos.side_to_move();
 201   Square ksq = pos.king_square(opposite_color(us));
 202   MoveStack* mlist_start = mlist;
 203
 204   assert(pos.piece_on(ksq) == piece_of_color_and_type(opposite_color(us), KING));
 205
 206   // Pieces moves
 207   mlist = generate_piece_checks<PAWN, false>(pos, mlist, us, dc, ksq);
 208   mlist = generate_piece_checks<KNIGHT, HasBSF>(pos, mlist, us, dc, ksq);
 209   mlist = generate_piece_checks<BISHOP, HasBSF>(pos, mlist, us, dc, ksq);
 210   mlist = generate_piece_checks<ROOK,   HasBSF>(pos, mlist, us, dc, ksq);
 211   mlist = generate_piece_checks<QUEEN,  HasBSF>(pos, mlist, us, dc, ksq);
 212   mlist = generate_piece_checks<KING, false>(pos, mlist, us, dc, ksq);
 213
 214   // Castling moves that give check. Very rare but nice to have!
 215   if (   pos.can_castle_queenside(us)
 216       && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_D)
 217       && castling_is_check(pos, QUEEN_SIDE))
 218       mlist = generate_castle_moves<QUEEN_SIDE>(pos, mlist);
 219
 220   if (   pos.can_castle_kingside(us)
 221       && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_F)
 222       && castling_is_check(pos, KING_SIDE))
 223       mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
 224
 225   return int(mlist - mlist_start);
 226 }
 227
 228 int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) {
 229
 230     return CpuHasPOPCNT ? generate_non_capture_checks<true>(pos, mlist, dc)
 231                         : generate_non_capture_checks<false>(pos, mlist, dc);
 232 }
 233
 234
 235 /// generate_evasions() generates all check evasions when the side to move is
 236 /// in check. Unlike the other move generation functions, this one generates
 237 /// only legal moves. It returns the number of generated moves.
 238 template<bool HasBSF>
 239 int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) {
 240
 241   assert(pos.is_ok());
 242   assert(pos.is_check());
 243
 244   Square from, to;
 245   Color us = pos.side_to_move();
 246   Color them = opposite_color(us);
 247   Square ksq = pos.king_square(us);
 248   MoveStack* mlist_start = mlist;
 249
 250   assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING));
 251
 252   // The bitboard of occupied pieces without our king
 253   Bitboard b_noKing = pos.occupied_squares();
 254   clear_bit(&b_noKing, ksq);
 255
 256   // Find squares attacked by slider checkers, we will
 257   // remove them from king evasions set so to avoid a couple
 258   // of cycles in the slow king evasions legality check loop
 259   // and to be able to use square_is_attacked().
 260   Bitboard checkers = pos.checkers();
 261   Bitboard checkersAttacks = EmptyBoardBB;
 262   Bitboard b = checkers & (pos.queens() | pos.bishops());
 263   while (b)
 264   {
 265       from = pop_1st_bit(&b);
 266       checkersAttacks |= bishop_attacks_bb(from, b_noKing);
 267   }
 268
 269   b = checkers & (pos.queens() | pos.rooks());
 270   while (b)
 271   {
 272       from = pop_1st_bit(&b);
 273       checkersAttacks |= rook_attacks_bb(from, b_noKing);
 274   }
 275
 276   // Generate evasions for king
 277   Bitboard b1 = pos.piece_attacks<KING>(ksq) & ~pos.pieces_of_color(us) & ~checkersAttacks;
 278   while (b1)
 279   {
 280       to = pop_1st_bit(&b1);
 281       // Note that we can use square_is_attacked() only because we
 282       // have already removed slider checkers.
 283       if (!pos.square_is_attacked(to, them))
 284           (*mlist++).move = make_move(ksq, to);
 285   }
 286
 287   // Generate evasions for other pieces only if not double check. We use a
 288   // simple bit twiddling hack here rather than calling count_1s in order to
 289   // save some time (we know that pos.checkers() has at most two nonzero bits).
 290   if (!(checkers & (checkers - 1))) // Only one bit set?
 291   {
 292       Square checksq = first_1(checkers);
 293
 294       assert(pos.color_of_piece_on(checksq) == them);
 295
 296       // Generate captures of the checking piece
 297
 298       // Pawn captures
 299       b1 = pos.pawn_attacks(them, checksq) & pos.pawns(us) & ~pinned;
 300       while (b1)
 301       {
 302           from = pop_1st_bit(&b1);
 303           if (relative_rank(us, checksq) == RANK_8)
 304           {
 305               (*mlist++).move = make_promotion_move(from, checksq, QUEEN);
 306               (*mlist++).move = make_promotion_move(from, checksq, ROOK);
 307               (*mlist++).move = make_promotion_move(from, checksq, BISHOP);
 308               (*mlist++).move = make_promotion_move(from, checksq, KNIGHT);
 309           } else
 310               (*mlist++).move = make_move(from, checksq);
 311       }
 312
 313       // Pieces captures
 314       b1 = (  (pos.piece_attacks<KNIGHT>(checksq) & pos.knights(us))
 315             | (pos.piece_attacks<BISHOP>(checksq) & pos.bishops_and_queens(us))
 316             | (pos.piece_attacks<ROOK>(checksq)   & pos.rooks_and_queens(us)) ) & ~pinned;
 317
 318       while (b1)
 319       {
 320           from = pop_1st_bit(&b1);
 321           (*mlist++).move = make_move(from, checksq);
 322       }
 323
 324       // Blocking check evasions are possible only if the checking piece is
 325       // a slider.
 326       if (checkers & pos.sliders())
 327       {
 328           Bitboard blockSquares = squares_between(checksq, ksq);
 329
 330           assert((pos.occupied_squares() & blockSquares) == EmptyBoardBB);
 331
 332           if (blockSquares != EmptyBoardBB)
 333           {
 334               mlist = generate_piece_moves<PAWN, false>(pos, mlist, us, blockSquares, pinned);
 335               mlist = generate_piece_moves<KNIGHT, HasBSF>(pos, mlist, us, blockSquares, pinned);
 336               mlist = generate_piece_moves<BISHOP, HasBSF>(pos, mlist, us, blockSquares, pinned);
 337               mlist = generate_piece_moves<ROOK,   HasBSF>(pos, mlist, us, blockSquares, pinned);
 338               mlist = generate_piece_moves<QUEEN,  HasBSF>(pos, mlist, us, blockSquares, pinned);
 339           }
 340       }
 341
 342       // Finally, the special case of en passant captures. An en passant
 343       // capture can only be a check evasion if the check is not a discovered
 344       // check. If pos.ep_square() is set, the last move made must have been
 345       // a double pawn push. If, furthermore, the checking piece is a pawn,
 346       // an en passant check evasion may be possible.
 347       if (pos.ep_square() != SQ_NONE && (checkers & pos.pawns(them)))
 348       {
 349           to = pos.ep_square();
 350           b1 = pos.pawn_attacks(them, to) & pos.pawns(us);
 351
 352           // The checking pawn cannot be a discovered (bishop) check candidate
 353           // otherwise we were in check also before last double push move.
 354           assert(!bit_is_set(pos.discovered_check_candidates(them), checksq));
 355           assert(count_1s(b1) == 1 || count_1s(b1) == 2);
 356
 357           b1 &= ~pinned;
 358           while (b1)
 359           {
 360               from = pop_1st_bit(&b1);
 361               // Move is always legal because checking pawn is not a discovered
 362               // check candidate and our capturing pawn has been already tested
 363               // against pinned pieces.
 364               (*mlist++).move = make_ep_move(from, to);
 365           }
 366       }
 367   }
 368   return int(mlist - mlist_start);
 369 }
 370
 371 int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) {
 372
 373     return CpuHasPOPCNT ? generate_evasions<true>(pos, mlist, pinned)
 374                         : generate_evasions<false>(pos, mlist, pinned);
 375 }
 376
 377
 378 /// generate_legal_moves() computes a complete list of legal moves in the
 379 /// current position. This function is not very fast, and should be used
 380 /// only in situations where performance is unimportant. It wouldn't be
 381 /// very hard to write an efficient legal move generator, but for the moment
 382 /// we don't need it.
 383
 384 int generate_legal_moves(const Position& pos, MoveStack* mlist) {
 385
 386   assert(pos.is_ok());
 387
 388   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 389
 390   if (pos.is_check())
 391       return generate_evasions(pos, mlist, pinned);
 392
 393   // Generate pseudo-legal moves
 394   int n = generate_captures(pos, mlist);
 395   n += generate_noncaptures(pos, mlist + n);
 396
 397   // Remove illegal moves from the list
 398   for (int i = 0; i < n; i++)
 399       if (!pos.pl_move_is_legal(mlist[i].move, pinned))
 400           mlist[i--].move = mlist[--n].move;
 401
 402   return n;
 403 }
 404
 405
 406 /// move_is_legal() takes a position and a (not necessarily pseudo-legal)
 407 /// move and a pinned pieces bitboard as input, and tests whether
 408 /// the move is legal.  If the move is legal, the move itself is
 409 /// returned. If not, the function returns false.  This function must
 410 /// only be used when the side to move is not in check.
 411
 412 bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
 413
 414   assert(pos.is_ok());
 415   assert(!pos.is_check());
 416   assert(move_is_ok(m));
 417   assert(pinned == pos.pinned_pieces(pos.side_to_move()));
 418
 419   Color us = pos.side_to_move();
 420   Color them = opposite_color(us);
 421   Square from = move_from(m);
 422   Piece pc = pos.piece_on(from);
 423
 424   // If the from square is not occupied by a piece belonging to the side to
 425   // move, the move is obviously not legal.
 426   if (color_of_piece(pc) != us)
 427       return false;
 428
 429   Square to = move_to(m);
 430
 431   // En passant moves
 432   if (move_is_ep(m))
 433   {
 434       // The piece must be a pawn and destination square must be the
 435       // en passant square.
 436       if (   type_of_piece(pc) != PAWN
 437           || to != pos.ep_square())
 438           return false;
 439
 440       assert(pos.square_is_empty(to));
 441       assert(pos.piece_on(to - pawn_push(us)) == piece_of_color_and_type(them, PAWN));
 442
 443       // The move is pseudo-legal, check if it is also legal
 444       return pos.pl_move_is_legal(m, pinned);
 445   }
 446
 447   // Castling moves
 448   if (move_is_short_castle(m))
 449   {
 450       // The piece must be a king and side to move must still have
 451       // the right to castle kingside.
 452       if (   type_of_piece(pc) != KING
 453           ||!pos.can_castle_kingside(us))
 454           return false;
 455
 456       assert(from == pos.king_square(us));
 457       assert(to == pos.initial_kr_square(us));
 458       assert(pos.piece_on(to) == piece_of_color_and_type(us, ROOK));
 459
 460       Square g1 = relative_square(us, SQ_G1);
 461       Square f1 = relative_square(us, SQ_F1);
 462       Square s;
 463       bool illegal = false;
 464
 465       // Check if any of the squares between king and rook
 466       // is occupied or under attack.
 467       for (s = Min(from, g1); s <= Max(from, g1); s++)
 468           if (  (s != from && s != to && !pos.square_is_empty(s))
 469               || pos.square_is_attacked(s, them))
 470               illegal = true;
 471
 472       // Check if any of the squares between king and rook
 473       // is occupied.
 474       for (s = Min(to, f1); s <= Max(to, f1); s++)
 475           if (s != from && s != to && !pos.square_is_empty(s))
 476               illegal = true;
 477
 478       return !illegal;
 479   }
 480
 481   if (move_is_long_castle(m))
 482   {
 483       // The piece must be a king and side to move must still have
 484       // the right to castle kingside.
 485       if (   type_of_piece(pc) != KING
 486           ||!pos.can_castle_queenside(us))
 487           return false;
 488
 489       assert(from == pos.king_square(us));
 490       assert(to == pos.initial_qr_square(us));
 491       assert(pos.piece_on(to) == piece_of_color_and_type(us, ROOK));
 492
 493       Square c1 = relative_square(us, SQ_C1);
 494       Square d1 = relative_square(us, SQ_D1);
 495       Square s;
 496       bool illegal = false;
 497
 498       for (s = Min(from, c1); s <= Max(from, c1); s++)
 499           if(  (s != from && s != to && !pos.square_is_empty(s))
 500              || pos.square_is_attacked(s, them))
 501               illegal = true;
 502
 503       for (s = Min(to, d1); s <= Max(to, d1); s++)
 504           if(s != from && s != to && !pos.square_is_empty(s))
 505               illegal = true;
 506
 507       if (   square_file(to) == FILE_B
 508           && (   pos.piece_on(to + DELTA_W) == piece_of_color_and_type(them, ROOK)
 509               || pos.piece_on(to + DELTA_W) == piece_of_color_and_type(them, QUEEN)))
 510           illegal = true;
 511
 512       return !illegal;
 513   }
 514
 515   // Normal moves
 516
 517   // The destination square cannot be occupied by a friendly piece
 518   if (pos.color_of_piece_on(to) == us)
 519       return false;
 520
 521   // Proceed according to the type of the moving piece.
 522   if (type_of_piece(pc) == PAWN)
 523   {
 524       // Move direction must be compatible with pawn color
 525       int direction = to - from;
 526       if ((us == WHITE) != (direction > 0))
 527           return false;
 528
 529       // If the destination square is on the 8/1th rank, the move must
 530       // be a promotion.
 531       if (   (  (square_rank(to) == RANK_8 && us == WHITE)
 532               ||(square_rank(to) == RANK_1 && us != WHITE))
 533            && !move_promotion(m))
 534           return false;
 535
 536       // Proceed according to the square delta between the source and
 537       // destionation squares.
 538       switch (direction)
 539       {
 540       case DELTA_NW:
 541       case DELTA_NE:
 542       case DELTA_SW:
 543       case DELTA_SE:
 544       // Capture. The destination square must be occupied by an enemy
 545       // piece (en passant captures was handled earlier).
 546           if (pos.color_of_piece_on(to) != them)
 547               return false;
 548           break;
 549
 550       case DELTA_N:
 551       case DELTA_S:
 552       // Pawn push. The destination square must be empty.
 553           if (!pos.square_is_empty(to))
 554               return false;
 555           break;
 556
 557       case DELTA_NN:
 558       // Double white pawn push. The destination square must be on the fourth
 559       // rank, and both the destination square and the square between the
 560       // source and destination squares must be empty.
 561       if (   square_rank(to) != RANK_4
 562           || !pos.square_is_empty(to)
 563           || !pos.square_is_empty(from + DELTA_N))
 564           return false;
 565           break;
 566
 567       case DELTA_SS:
 568       // Double black pawn push. The destination square must be on the fifth
 569       // rank, and both the destination square and the square between the
 570       // source and destination squares must be empty.
 571           if (   square_rank(to) != RANK_5
 572               || !pos.square_is_empty(to)
 573               || !pos.square_is_empty(from + DELTA_S))
 574               return false;
 575           break;
 576
 577       default:
 578           return false;
 579       }
 580       // The move is pseudo-legal, check if it is also legal
 581       return pos.pl_move_is_legal(m, pinned);
 582   }
 583
 584   // Luckly we can handle all the other pieces in one go
 585   return (   pos.piece_attacks_square(pos.piece_on(from), from, to)
 586           && pos.pl_move_is_legal(m, pinned)
 587           && !move_promotion(m));
 588 }
 589
 590
 591 namespace {
 592
 593   template<PieceType Piece, bool HasBSF>
 594   MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 595
 596     Square from;
 597     Bitboard b;
 598
 599     for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++)
 600     {
 601         from = pos.piece_list(us, Piece, i);
 602         b = pos.piece_attacks<Piece>(from) & target;
 603         SERIALIZE_MOVES(b, HasBSF);
 604     }
 605     return mlist;
 606   }
 607
 608   template<PieceType Piece, bool HasBSF>
 609   MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist,
 610                                   Color us, Bitboard target, Bitboard pinned) {
 611     Square from;
 612     Bitboard b;
 613
 614     for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++)
 615     {
 616         from = pos.piece_list(us, Piece, i);
 617         if (pinned && bit_is_set(pinned, from))
 618             continue;
 619
 620         b = pos.piece_attacks<Piece>(from) & target;
 621         SERIALIZE_MOVES(b, HasBSF);
 622     }
 623     return mlist;
 624   }
 625
 626   template<>
 627   MoveStack* generate_piece_moves<KING, false>(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 628
 629     Bitboard b;
 630     Square from = pos.king_square(us);
 631
 632     b = pos.piece_attacks<KING>(from) & target;
 633     SERIALIZE_MOVES(b, false);
 634     return mlist;
 635   }
 636
 637   template<Color Us, SquareDelta Diagonal>
 638   MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces) {
 639
 640     // Calculate our parametrized parameters at compile time
 641     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 642     const Bitboard TFileABB = (Diagonal == DELTA_NE ? FileABB : FileHBB);
 643     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 644     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 645     const SquareDelta TTDELTA_NE = (Diagonal == DELTA_NE ? TDELTA_NE : TDELTA_NW);
 646
 647     Square to;
 648
 649     // Captures in the a1-h8 (a8-h1 for black) diagonal or in the h1-a8 (h8-a1 for black)
 650     Bitboard b1 = move_pawns<Us, Diagonal>(pawns) & ~TFileABB & enemyPieces;
 651
 652     // Capturing promotions
 653     Bitboard b2 = b1 & TRank8BB;
 654     while (b2)
 655     {
 656         to = pop_1st_bit(&b2);
 657         (*mlist++).move = make_promotion_move(to - TTDELTA_NE, to, QUEEN);
 658     }
 659
 660     // Capturing non-promotions
 661     b2 = b1 & ~TRank8BB;
 662     while (b2)
 663     {
 664         to = pop_1st_bit(&b2);
 665         (*mlist++).move = make_move(to - TTDELTA_NE, to);
 666     }
 667     return mlist;
 668   }
 669
 670   template<Color Us>
 671   MoveStack* generate_pawn_captures(const Position& pos, MoveStack* mlist) {
 672
 673     // Calculate our parametrized parameters at compile time
 674     const Color Them = (Us == WHITE ? BLACK : WHITE);
 675     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 676     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 677
 678     Square to;
 679     Bitboard pawns = pos.pawns(Us);
 680     Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us));
 681
 682     // Standard captures and capturing promotions in both directions
 683     mlist = generate_pawn_captures_diagonal<Us, DELTA_NE>(mlist, pawns, enemyPieces);
 684     mlist = generate_pawn_captures_diagonal<Us, DELTA_NW>(mlist, pawns, enemyPieces);
 685
 686     // Non-capturing promotions
 687     Bitboard b1 = move_pawns<Us, DELTA_N>(pawns) & pos.empty_squares() & TRank8BB;
 688     while (b1)
 689     {
 690         to = pop_1st_bit(&b1);
 691         (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN);
 692     }
 693
 694     // En passant captures
 695     if (pos.ep_square() != SQ_NONE)
 696     {
 697         assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6);
 698         assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3);
 699
 700         b1 = pawns & pos.pawn_attacks(Them, pos.ep_square());
 701         assert(b1 != EmptyBoardBB);
 702
 703         while (b1)
 704         {
 705             to = pop_1st_bit(&b1);
 706             (*mlist++).move = make_ep_move(to, pos.ep_square());
 707         }
 708     }
 709     return mlist;
 710   }
 711
 712   template<Color Us>
 713   MoveStack* generate_pawn_noncaptures(const Position& pos, MoveStack* mlist) {
 714
 715     // Calculate our parametrized parameters at compile time
 716     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 717     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 718     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 719     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 720     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 721
 722     Bitboard b1, b2;
 723     Square to;
 724     Bitboard pawns = pos.pawns(Us);
 725     Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us));
 726     Bitboard emptySquares = pos.empty_squares();
 727
 728     // Underpromotion captures in the a1-h8 (a8-h1 for black) direction
 729     b1 = move_pawns<Us, DELTA_NE>(pawns) & ~FileABB & enemyPieces & TRank8BB;
 730     while (b1)
 731     {
 732         to = pop_1st_bit(&b1);
 733         (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, ROOK);
 734         (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, BISHOP);
 735         (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, KNIGHT);
 736     }
 737
 738     // Underpromotion captures in the h1-a8 (h8-a1 for black) direction
 739     b1 = move_pawns<Us, DELTA_NW>(pawns) & ~FileHBB & enemyPieces & TRank8BB;
 740     while (b1)
 741     {
 742         to = pop_1st_bit(&b1);
 743         (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, ROOK);
 744         (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, BISHOP);
 745         (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, KNIGHT);
 746     }
 747
 748     // Single pawn pushes
 749     b1 = move_pawns<Us, DELTA_N>(pawns) & emptySquares;
 750     b2 = b1 & TRank8BB;
 751     while (b2)
 752     {
 753         to = pop_1st_bit(&b2);
 754         (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK);
 755         (*mlist++).move = make_promotion_move(to - TDELTA_N, to, BISHOP);
 756         (*mlist++).move = make_promotion_move(to - TDELTA_N, to, KNIGHT);
 757     }
 758     b2 = b1 & ~TRank8BB;
 759     while (b2)
 760     {
 761         to = pop_1st_bit(&b2);
 762         (*mlist++).move = make_move(to - TDELTA_N, to);
 763     }
 764
 765     // Double pawn pushes
 766     b2 = move_pawns<Us, DELTA_N>(b1 & TRank3BB) & emptySquares;
 767     while (b2)
 768     {
 769         to = pop_1st_bit(&b2);
 770         (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to);
 771     }
 772     return mlist;
 773   }
 774
 775
 776   template<Color Us>
 777   MoveStack* generate_pawn_checks(const Position& pos, Bitboard dc, Square ksq, MoveStack* mlist)
 778   {
 779     // Calculate our parametrized parameters at compile time
 780     const Color Them = (Us == WHITE ? BLACK : WHITE);
 781     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 782     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 783     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 784     const SquareDelta TDELTA_S = (Us == WHITE ? DELTA_S : DELTA_N);
 785
 786     Bitboard b1, b2, b3;
 787     Bitboard pawns = pos.pawns(Us);
 788
 789     if (dc & pawns)
 790     {
 791          Bitboard empty = pos.empty_squares();
 792
 793         // Pawn moves which gives discovered check. This is possible only if the
 794         // pawn is not on the same file as the enemy king, because we don't
 795         // generate captures.
 796         b1 = pawns & ~file_bb(ksq);
 797
 798         // Discovered checks, single pawn pushes, no promotions
 799         b2 = b3 = move_pawns<Us, DELTA_N>(b1 & dc) & empty & ~TRank8BB;
 800         while (b3)
 801         {
 802             Square to = pop_1st_bit(&b3);
 803             (*mlist++).move = make_move(to - TDELTA_N, to);
 804         }
 805
 806         // Discovered checks, double pawn pushes
 807         b3 = move_pawns<Us, DELTA_N>(b2 & TRank3BB) & empty;
 808         while (b3)
 809         {
 810             Square to = pop_1st_bit(&b3);
 811             (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to);
 812         }
 813     }
 814
 815     // Direct checks. These are possible only for pawns on neighboring files
 816     // and in the two ranks that, after the push, are in front of the enemy king.
 817     b1 = pawns & neighboring_files_bb(ksq) & ~dc;
 818     b2 = rank_bb(ksq + 2 * TDELTA_S) | rank_bb(ksq + 3 * TDELTA_S);
 819     b1 &= b2;
 820     if (!b1)
 821         return mlist;
 822
 823     // Direct checks, single pawn pushes
 824     Bitboard empty = pos.empty_squares();
 825     b2 = move_pawns<Us, DELTA_N>(b1) & empty;
 826     b3 = b2 & pos.pawn_attacks(Them, ksq);
 827     while (b3)
 828     {
 829         Square to = pop_1st_bit(&b3);
 830         (*mlist++).move = make_move(to - TDELTA_N, to);
 831     }
 832
 833     // Direct checks, double pawn pushes
 834     b3 =  move_pawns<Us, DELTA_N>(b2 & TRank3BB) & empty & pos.pawn_attacks(Them, ksq);
 835     while (b3)
 836     {
 837         Square to = pop_1st_bit(&b3);
 838         (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to);
 839     }
 840     return mlist;
 841   }
 842
 843   template<PieceType Piece, bool HasBSF>
 844   MoveStack* generate_piece_checks(const Position& pos, MoveStack* mlist, Color us,
 845                                    Bitboard dc, Square ksq) {
 846
 847     Bitboard target = pos.pieces_of_color_and_type(us, Piece);
 848
 849     // Discovered checks
 850     Bitboard b = target & dc;
 851     while (b)
 852     {
 853         Square from = pop_1st_bit(&b);
 854         Bitboard bb = pos.piece_attacks<Piece>(from) & pos.empty_squares();
 855         if (Piece == KING)
 856             bb &= ~QueenPseudoAttacks[ksq];
 857
 858         SERIALIZE_MOVES(bb, HasBSF);
 859     }
 860
 861     // Direct checks
 862     b = target & ~dc;
 863     if (Piece != KING || b)
 864     {
 865         Bitboard checkSqs = pos.piece_attacks<Piece>(ksq) & pos.empty_squares();
 866         if (!checkSqs)
 867             return mlist;
 868
 869         while (b)
 870         {
 871             Square from = pop_1st_bit(&b);
 872             if (   (Piece == QUEEN  && !(QueenPseudoAttacks[from]  & checkSqs))
 873                 || (Piece == ROOK   && !(RookPseudoAttacks[from]   & checkSqs))
 874                 || (Piece == BISHOP && !(BishopPseudoAttacks[from] & checkSqs)))
 875                 continue;
 876
 877             Bitboard bb = pos.piece_attacks<Piece>(from) & checkSqs;
 878             SERIALIZE_MOVES(bb, HasBSF);
 879         }
 880     }
 881     return mlist;
 882   }
 883
 884   template<Color Us>
 885   MoveStack* generate_pawn_blocking_evasions(const Position& pos, Bitboard pinned,
 886                                              Bitboard blockSquares, MoveStack* mlist) {
 887
 888     // Calculate our parametrized parameters at compile time
 889     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 890     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 891     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 892
 893     Square to;
 894
 895     // Find non-pinned pawns and push them one square
 896     Bitboard b1 = move_pawns<Us, DELTA_N>(pos.pawns(Us) & ~pinned);
 897
 898     // We don't have to AND with empty squares here,
 899     // because the blocking squares will always be empty.
 900     Bitboard b2 = b1 & blockSquares;
 901     while (b2)
 902     {
 903         to = pop_1st_bit(&b2);
 904
 905         assert(pos.piece_on(to) == EMPTY);
 906
 907         if (square_rank(to) == TRank8BB)
 908         {
 909             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN);
 910             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK);
 911             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, BISHOP);
 912             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, KNIGHT);
 913         } else
 914             (*mlist++).move = make_move(to - TDELTA_N, to);
 915     }
 916
 917     // Double pawn pushes
 918     b2 = b1 & pos.empty_squares() & TRank3BB;
 919     b2 = move_pawns<Us, DELTA_N>(b2) & blockSquares;
 920     while (b2)
 921     {
 922         to = pop_1st_bit(&b2);
 923
 924         assert(pos.piece_on(to) == EMPTY);
 925         assert(Us != WHITE || square_rank(to) == RANK_4);
 926         assert(Us != BLACK || square_rank(to) == RANK_5);
 927
 928         (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to);
 929     }
 930     return mlist;
 931   }
 932
 933   template<CastlingSide Side>
 934   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist) {
 935
 936     Color us = pos.side_to_move();
 937
 938     if (  (Side == KING_SIDE && pos.can_castle_kingside(us))
 939         ||(Side == QUEEN_SIDE && pos.can_castle_queenside(us)))
 940     {
 941         Color them = opposite_color(us);
 942         Square ksq = pos.king_square(us);
 943
 944         assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING));
 945
 946         Square rsq = (Side == KING_SIDE ? pos.initial_kr_square(us) : pos.initial_qr_square(us));
 947         Square s1 = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);
 948         Square s2 = relative_square(us, Side == KING_SIDE ? SQ_F1 : SQ_D1);
 949         Square s;
 950         bool illegal = false;
 951
 952         assert(pos.piece_on(rsq) == piece_of_color_and_type(us, ROOK));
 953
 954         // It is a bit complicated to correctly handle Chess960
 955         for (s = Min(ksq, s1); s <= Max(ksq, s1); s++)
 956             if (  (s != ksq && s != rsq && pos.square_is_occupied(s))
 957                 || pos.square_is_attacked(s, them))
 958                 illegal = true;
 959
 960         for (s = Min(rsq, s2); s <= Max(rsq, s2); s++)
 961             if (s != ksq && s != rsq && pos.square_is_occupied(s))
 962                 illegal = true;
 963
 964         if (   Side == QUEEN_SIDE
 965             && square_file(rsq) == FILE_B
 966             && (   pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, ROOK)
 967                 || pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, QUEEN)))
 968             illegal = true;
 969
 970         if (!illegal)
 971             (*mlist++).move = make_castle_move(ksq, rsq);
 972     }
 973     return mlist;
 974   }
 975
 976   bool castling_is_check(const Position& pos, CastlingSide side) {
 977
 978     // After castling opponent king is attacked by the castled rook?
 979     File rookFile = (side == QUEEN_SIDE ? FILE_D : FILE_F);
 980     Color us = pos.side_to_move();
 981     Square ksq = pos.king_square(us);
 982     Bitboard occ = pos.occupied_squares();
 983
 984     clear_bit(&occ, ksq); // Remove our king from the board
 985     Square rsq = make_square(rookFile, square_rank(ksq));
 986     return bit_is_set(rook_attacks_bb(rsq, occ), pos.king_square(opposite_color(us)));
 987   }
 988 }