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