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