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