git.sesse.net Git - stockfish/blob - src/movegen.cpp

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