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