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