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