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