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