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