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

   1 /*
   2   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
   3   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
   4   Copyright (C) 2008-2009 Marco Costalba
   5
   6   Stockfish is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   Stockfish is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20
  21 ////
  22 //// Includes
  23 ////
  24
  25 #include <cassert>
  26
  27 #include "bitcount.h"
  28 #include "movegen.h"
  29
  30 // Simple macro to wrap a very common while loop, no facny, no flexibility,
  31 // hardcoded list name 'mlist' and from square 'from'.
  32 #define SERIALIZE_MOVES(b) while (b) (*mlist++).move = make_move(from, pop_1st_bit(&b))
  33
  34 // Version used for pawns, where the 'from' square is given as a delta from the 'to' square
  35 #define SERIALIZE_MOVES_D(b, d) while (b) { to = pop_1st_bit(&b); (*mlist++).move = make_move(to + (d), to); }
  36
  37 ////
  38 //// Local definitions
  39 ////
  40
  41 namespace {
  42
  43   enum CastlingSide {
  44     KING_SIDE,
  45     QUEEN_SIDE
  46   };
  47
  48   enum MoveType {
  49     CAPTURE,
  50     NON_CAPTURE
  51   };
  52
  53   // Functions
  54   bool castling_is_check(const Position&, CastlingSide);
  55
  56   // Helper templates
  57   template<CastlingSide Side>
  58   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist);
  59
  60   template<Color Us>
  61   MoveStack* generate_pawn_blocking_evasions(const Position&, Bitboard, Bitboard, MoveStack*);
  62
  63   template<Color Us>
  64   MoveStack* generate_pawn_captures(const Position& pos, MoveStack* mlist);
  65
  66   template<Color Us, SquareDelta Diagonal>
  67   MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion);
  68
  69   template<Color Us>
  70   MoveStack* generate_pawn_noncaptures(const Position& pos, MoveStack* mlist);
  71
  72   template<Color Us>
  73   MoveStack* generate_pawn_checks(const Position&, Bitboard, Square, MoveStack*);
  74
  75   template<Color Us, SquareDelta Direction>
  76   inline Bitboard move_pawns(Bitboard p) {
  77
  78     if (Direction == DELTA_N)
  79         return Us == WHITE ? p << 8 : p >> 8;
  80     else if (Direction == DELTA_NE)
  81         return Us == WHITE ? p << 9 : p >> 7;
  82     else if (Direction == DELTA_NW)
  83         return Us == WHITE ? p << 7 : p >> 9;
  84     else
  85         return p;
  86   }
  87
  88   // Template generate_piece_checks() with specializations
  89   template<PieceType>
  90   MoveStack* generate_piece_checks(const Position&, MoveStack*, Color, Bitboard, Square);
  91
  92   template<>
  93   inline MoveStack* generate_piece_checks<PAWN>(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) {
  94
  95     return (us == WHITE ? generate_pawn_checks<WHITE>(p, dc, ksq, m)
  96                         : generate_pawn_checks<BLACK>(p, dc, ksq, m));
  97   }
  98
  99   // Template generate_piece_moves() with specializations and overloads
 100   template<PieceType>
 101   MoveStack* generate_piece_moves(const Position&, MoveStack*, Color us, Bitboard);
 102
 103   template<>
 104   MoveStack* generate_piece_moves<KING>(const Position&, MoveStack*, Color, Bitboard);
 105
 106   template<PieceType Piece, MoveType Type>
 107   inline MoveStack* generate_piece_moves(const Position& p, MoveStack* m, Color us) {
 108
 109       assert(Piece == PAWN);
 110
 111       if (Type == CAPTURE)
 112           return (us == WHITE ? generate_pawn_captures<WHITE>(p, m)
 113                               : generate_pawn_captures<BLACK>(p, m));
 114       else
 115           return (us == WHITE ? generate_pawn_noncaptures<WHITE>(p, m)
 116                               : generate_pawn_noncaptures<BLACK>(p, m));
 117   }
 118
 119   template<PieceType>
 120   MoveStack* generate_piece_moves(const Position&, MoveStack*, Color us, Bitboard, Bitboard);
 121
 122   template<>
 123   inline MoveStack* generate_piece_moves<PAWN>(const Position& p, MoveStack* m,
 124                                                Color us, Bitboard t, Bitboard pnd) {
 125
 126     return (us == WHITE ? generate_pawn_blocking_evasions<WHITE>(p, pnd, t, m)
 127                         : generate_pawn_blocking_evasions<BLACK>(p, pnd, t, m));
 128   }
 129 }
 130
 131
 132 ////
 133 //// Functions
 134 ////
 135
 136
 137 /// generate_captures generates() all pseudo-legal captures and queen
 138 /// promotions. Returns a pointer to the end of the move list.
 139
 140 MoveStack* generate_captures(const Position& pos, MoveStack* mlist) {
 141
 142   assert(pos.is_ok());
 143   assert(!pos.is_check());
 144
 145   Color us = pos.side_to_move();
 146   Bitboard target = pos.pieces_of_color(opposite_color(us));
 147
 148   mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
 149   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
 150   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
 151   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
 152   mlist = generate_piece_moves<PAWN, CAPTURE>(pos, mlist, us);
 153   return  generate_piece_moves<KING>(pos, mlist, us, target);
 154 }
 155
 156
 157 /// generate_noncaptures() generates all pseudo-legal non-captures and
 158 /// underpromotions. Returns a pointer to the end of the move list.
 159
 160 MoveStack* generate_noncaptures(const Position& pos, MoveStack* mlist) {
 161
 162   assert(pos.is_ok());
 163   assert(!pos.is_check());
 164
 165   Color us = pos.side_to_move();
 166   Bitboard target = pos.empty_squares();
 167
 168   mlist = generate_piece_moves<PAWN, NON_CAPTURE>(pos, mlist, us);
 169   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
 170   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
 171   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
 172   mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
 173   mlist = generate_piece_moves<KING>(pos, mlist, us, target);
 174   mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
 175   return  generate_castle_moves<QUEEN_SIDE>(pos, mlist);
 176 }
 177
 178
 179 /// generate_non_capture_checks() generates all pseudo-legal non-capturing,
 180 /// non-promoting checks. Returns a pointer to the end of the move list.
 181
 182 MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) {
 183
 184   assert(pos.is_ok());
 185   assert(!pos.is_check());
 186
 187   Color us = pos.side_to_move();
 188   Square ksq = pos.king_square(opposite_color(us));
 189
 190   assert(pos.piece_on(ksq) == piece_of_color_and_type(opposite_color(us), KING));
 191
 192   // Pieces moves
 193   mlist = generate_piece_checks<PAWN>(pos, mlist, us, dc, ksq);
 194   mlist = generate_piece_checks<KNIGHT>(pos, mlist, us, dc, ksq);
 195   mlist = generate_piece_checks<BISHOP>(pos, mlist, us, dc, ksq);
 196   mlist = generate_piece_checks<ROOK>(pos, mlist, us, dc, ksq);
 197   mlist = generate_piece_checks<QUEEN>(pos, mlist, us, dc, ksq);
 198   mlist = generate_piece_checks<KING>(pos, mlist, us, dc, ksq);
 199
 200   // Castling moves that give check. Very rare but nice to have!
 201   if (   pos.can_castle_queenside(us)
 202       && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_D)
 203       && castling_is_check(pos, QUEEN_SIDE))
 204       mlist = generate_castle_moves<QUEEN_SIDE>(pos, mlist);
 205
 206   if (   pos.can_castle_kingside(us)
 207       && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_F)
 208       && castling_is_check(pos, KING_SIDE))
 209       mlist = generate_castle_moves<KING_SIDE>(pos, mlist);
 210
 211   return mlist;
 212 }
 213
 214
 215 /// generate_evasions() generates all check evasions when the side to move is
 216 /// in check. Unlike the other move generation functions, this one generates
 217 /// only legal moves. Returns a pointer to the end of the move list.
 218
 219 MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) {
 220
 221   assert(pos.is_ok());
 222   assert(pos.is_check());
 223
 224   Square from, to;
 225   Color us = pos.side_to_move();
 226   Color them = opposite_color(us);
 227   Square ksq = pos.king_square(us);
 228
 229   assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING));
 230
 231   // The bitboard of occupied pieces without our king
 232   Bitboard b_noKing = pos.occupied_squares();
 233   clear_bit(&b_noKing, ksq);
 234
 235   // Find squares attacked by slider checkers, we will
 236   // remove them from king evasions set so to avoid a couple
 237   // of cycles in the slow king evasions legality check loop
 238   // and to be able to use attackers_to().
 239   Bitboard checkers = pos.checkers();
 240   Bitboard checkersAttacks = EmptyBoardBB;
 241   Bitboard b = checkers & pos.pieces(BISHOP, QUEEN);
 242   while (b)
 243   {
 244       from = pop_1st_bit(&b);
 245       checkersAttacks |= bishop_attacks_bb(from, b_noKing);
 246   }
 247
 248   b = checkers & pos.pieces(ROOK, QUEEN);
 249   while (b)
 250   {
 251       from = pop_1st_bit(&b);
 252       checkersAttacks |= rook_attacks_bb(from, b_noKing);
 253   }
 254
 255   // Generate evasions for king
 256   Bitboard b1 = pos.piece_attacks<KING>(ksq) & ~pos.pieces_of_color(us) & ~checkersAttacks;
 257   while (b1)
 258   {
 259       to = pop_1st_bit(&b1);
 260       // Note that we can use attackers_to() only because we
 261       // have already removed slider checkers.
 262       if (!pos.attackers_to(to, them))
 263           (*mlist++).move = make_move(ksq, to);
 264   }
 265
 266   // Generate evasions for other pieces only if not double check. We use a
 267   // simple bit twiddling hack here rather than calling count_1s in order to
 268   // save some time (we know that pos.checkers() has at most two nonzero bits).
 269   if (!(checkers & (checkers - 1))) // Only one bit set?
 270   {
 271       Square checksq = first_1(checkers);
 272
 273       assert(pos.color_of_piece_on(checksq) == them);
 274
 275       // Generate captures of the checking piece
 276
 277       // Pawn captures
 278       b1 = pos.pawn_attacks(checksq, them) & pos.pieces(PAWN, us) & ~pinned;
 279       while (b1)
 280       {
 281           from = pop_1st_bit(&b1);
 282           if (relative_rank(us, checksq) == RANK_8)
 283           {
 284               (*mlist++).move = make_promotion_move(from, checksq, QUEEN);
 285               (*mlist++).move = make_promotion_move(from, checksq, ROOK);
 286               (*mlist++).move = make_promotion_move(from, checksq, BISHOP);
 287               (*mlist++).move = make_promotion_move(from, checksq, KNIGHT);
 288           } else
 289               (*mlist++).move = make_move(from, checksq);
 290       }
 291
 292       // Pieces captures
 293       b1 = (  (pos.piece_attacks<KNIGHT>(checksq) & pos.pieces(KNIGHT, us))
 294             | (pos.piece_attacks<BISHOP>(checksq) & pos.pieces(BISHOP, QUEEN, us))
 295             | (pos.piece_attacks<ROOK>(checksq)   & pos.pieces(ROOK, QUEEN, us)) ) & ~pinned;
 296
 297       while (b1)
 298       {
 299           from = pop_1st_bit(&b1);
 300           (*mlist++).move = make_move(from, checksq);
 301       }
 302
 303       // Blocking check evasions are possible only if the checking piece is
 304       // a slider.
 305       if (checkers & (pos.pieces(BISHOP) | pos.pieces(ROOK) | pos.pieces(QUEEN)))
 306       {
 307           Bitboard blockSquares = squares_between(checksq, ksq);
 308
 309           assert((pos.occupied_squares() & blockSquares) == EmptyBoardBB);
 310
 311           if (blockSquares != EmptyBoardBB)
 312           {
 313               mlist = generate_piece_moves<PAWN>(pos, mlist, us, blockSquares, pinned);
 314               mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, blockSquares, pinned);
 315               mlist = generate_piece_moves<BISHOP>(pos, mlist, us, blockSquares, pinned);
 316               mlist = generate_piece_moves<ROOK>(pos, mlist, us, blockSquares, pinned);
 317               mlist = generate_piece_moves<QUEEN>(pos, mlist, us, blockSquares, pinned);
 318           }
 319       }
 320
 321       // Finally, the special case of en passant captures. An en passant
 322       // capture can only be a check evasion if the check is not a discovered
 323       // check. If pos.ep_square() is set, the last move made must have been
 324       // a double pawn push. If, furthermore, the checking piece is a pawn,
 325       // an en passant check evasion may be possible.
 326       if (pos.ep_square() != SQ_NONE && (checkers & pos.pieces(PAWN, them)))
 327       {
 328           to = pos.ep_square();
 329           b1 = pos.pawn_attacks(to, them) & pos.pieces(PAWN, us);
 330
 331           // The checking pawn cannot be a discovered (bishop) check candidate
 332           // otherwise we were in check also before last double push move.
 333           assert(!bit_is_set(pos.discovered_check_candidates(them), checksq));
 334           assert(count_1s(b1) == 1 || count_1s(b1) == 2);
 335
 336           b1 &= ~pinned;
 337           while (b1)
 338           {
 339               from = pop_1st_bit(&b1);
 340               // Move is always legal because checking pawn is not a discovered
 341               // check candidate and our capturing pawn has been already tested
 342               // against pinned pieces.
 343               (*mlist++).move = make_ep_move(from, to);
 344           }
 345       }
 346   }
 347   return mlist;
 348 }
 349
 350
 351 /// generate_legal_moves() computes a complete list of legal moves in the
 352 /// current position. This function is not very fast, and should be used
 353 /// only in situations where performance is unimportant. It wouldn't be
 354 /// very hard to write an efficient legal move generator, but for the moment
 355 /// we don't need it.
 356
 357 MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist) {
 358
 359   assert(pos.is_ok());
 360
 361   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 362
 363   if (pos.is_check())
 364       return generate_evasions(pos, mlist, pinned);
 365
 366   // Generate pseudo-legal moves
 367   MoveStack* last = generate_captures(pos, mlist);
 368   last = generate_noncaptures(pos, last);
 369
 370   // Remove illegal moves from the list
 371   for (MoveStack* cur = mlist; cur != last; cur++)
 372       if (!pos.pl_move_is_legal(cur->move, pinned))
 373       {
 374           cur->move = (--last)->move;
 375           cur--;
 376       }
 377   return last;
 378 }
 379
 380
 381 /// move_is_legal() takes a position and a (not necessarily pseudo-legal)
 382 /// move and a pinned pieces bitboard as input, and tests whether
 383 /// the move is legal.  If the move is legal, the move itself is
 384 /// returned. If not, the function returns false.  This function must
 385 /// only be used when the side to move is not in check.
 386
 387 bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) {
 388
 389   assert(pos.is_ok());
 390   assert(!pos.is_check());
 391   assert(move_is_ok(m));
 392   assert(pinned == pos.pinned_pieces(pos.side_to_move()));
 393
 394   Color us = pos.side_to_move();
 395   Square from = move_from(m);
 396   Piece pc = pos.piece_on(from);
 397
 398   // If the from square is not occupied by a piece belonging to the side to
 399   // move, the move is obviously not legal.
 400   if (color_of_piece(pc) != us)
 401       return false;
 402
 403   Color them = opposite_color(us);
 404   Square to = move_to(m);
 405
 406   // En passant moves
 407   if (move_is_ep(m))
 408   {
 409       // The piece must be a pawn and destination square must be the
 410       // en passant square.
 411       if (   type_of_piece(pc) != PAWN
 412           || to != pos.ep_square())
 413           return false;
 414
 415       assert(pos.square_is_empty(to));
 416       assert(pos.piece_on(to - pawn_push(us)) == piece_of_color_and_type(them, PAWN));
 417
 418       // The move is pseudo-legal, check if it is also legal
 419       return pos.pl_move_is_legal(m, pinned);
 420   }
 421
 422   // Castling moves
 423   if (move_is_short_castle(m))
 424   {
 425       // The piece must be a king and side to move must still have
 426       // the right to castle kingside.
 427       if (   type_of_piece(pc) != KING
 428           ||!pos.can_castle_kingside(us))
 429           return false;
 430
 431       assert(from == pos.king_square(us));
 432       assert(to == pos.initial_kr_square(us));
 433       assert(pos.piece_on(to) == piece_of_color_and_type(us, ROOK));
 434
 435       Square g1 = relative_square(us, SQ_G1);
 436       Square f1 = relative_square(us, SQ_F1);
 437       Square s;
 438       bool illegal = false;
 439
 440       // Check if any of the squares between king and rook
 441       // is occupied or under attack.
 442       for (s = Min(from, g1); s <= Max(from, g1); s++)
 443           if (  (s != from && s != to && !pos.square_is_empty(s))
 444               || pos.attackers_to(s, them))
 445               illegal = true;
 446
 447       // Check if any of the squares between king and rook
 448       // is occupied.
 449       for (s = Min(to, f1); s <= Max(to, f1); s++)
 450           if (s != from && s != to && !pos.square_is_empty(s))
 451               illegal = true;
 452
 453       return !illegal;
 454   }
 455
 456   if (move_is_long_castle(m))
 457   {
 458       // The piece must be a king and side to move must still have
 459       // the right to castle kingside.
 460       if (   type_of_piece(pc) != KING
 461           ||!pos.can_castle_queenside(us))
 462           return false;
 463
 464       assert(from == pos.king_square(us));
 465       assert(to == pos.initial_qr_square(us));
 466       assert(pos.piece_on(to) == piece_of_color_and_type(us, ROOK));
 467
 468       Square c1 = relative_square(us, SQ_C1);
 469       Square d1 = relative_square(us, SQ_D1);
 470       Square s;
 471       bool illegal = false;
 472
 473       for (s = Min(from, c1); s <= Max(from, c1); s++)
 474           if(  (s != from && s != to && !pos.square_is_empty(s))
 475              || pos.attackers_to(s, them))
 476               illegal = true;
 477
 478       for (s = Min(to, d1); s <= Max(to, d1); s++)
 479           if(s != from && s != to && !pos.square_is_empty(s))
 480               illegal = true;
 481
 482       if (   square_file(to) == FILE_B
 483           && (   pos.piece_on(to + DELTA_W) == piece_of_color_and_type(them, ROOK)
 484               || pos.piece_on(to + DELTA_W) == piece_of_color_and_type(them, QUEEN)))
 485           illegal = true;
 486
 487       return !illegal;
 488   }
 489
 490   // Normal moves
 491
 492   // The destination square cannot be occupied by a friendly piece
 493   if (pos.color_of_piece_on(to) == us)
 494       return false;
 495
 496   // Proceed according to the type of the moving piece.
 497   if (type_of_piece(pc) == PAWN)
 498   {
 499       // Move direction must be compatible with pawn color
 500       int direction = to - from;
 501       if ((us == WHITE) != (direction > 0))
 502           return false;
 503
 504       // If the destination square is on the 8/1th rank, the move must
 505       // be a promotion.
 506       if (   (  (square_rank(to) == RANK_8 && us == WHITE)
 507               ||(square_rank(to) == RANK_1 && us != WHITE))
 508            && !move_is_promotion(m))
 509           return false;
 510
 511       // Proceed according to the square delta between the source and
 512       // destionation squares.
 513       switch (direction)
 514       {
 515       case DELTA_NW:
 516       case DELTA_NE:
 517       case DELTA_SW:
 518       case DELTA_SE:
 519       // Capture. The destination square must be occupied by an enemy
 520       // piece (en passant captures was handled earlier).
 521           if (pos.color_of_piece_on(to) != them)
 522               return false;
 523           break;
 524
 525       case DELTA_N:
 526       case DELTA_S:
 527       // Pawn push. The destination square must be empty.
 528           if (!pos.square_is_empty(to))
 529               return false;
 530           break;
 531
 532       case DELTA_NN:
 533       // Double white pawn push. The destination square must be on the fourth
 534       // rank, and both the destination square and the square between the
 535       // source and destination squares must be empty.
 536       if (   square_rank(to) != RANK_4
 537           || !pos.square_is_empty(to)
 538           || !pos.square_is_empty(from + DELTA_N))
 539           return false;
 540           break;
 541
 542       case DELTA_SS:
 543       // Double black pawn push. The destination square must be on the fifth
 544       // rank, and both the destination square and the square between the
 545       // source and destination squares must be empty.
 546           if (   square_rank(to) != RANK_5
 547               || !pos.square_is_empty(to)
 548               || !pos.square_is_empty(from + DELTA_S))
 549               return false;
 550           break;
 551
 552       default:
 553           return false;
 554       }
 555       // The move is pseudo-legal, check if it is also legal
 556       return pos.pl_move_is_legal(m, pinned);
 557   }
 558
 559   // Luckly we can handle all the other pieces in one go
 560   return (   pos.piece_attacks_square(pos.piece_on(from), from, to)
 561           && pos.pl_move_is_legal(m, pinned)
 562           && !move_is_promotion(m));
 563 }
 564
 565
 566 /// Another version of move_is_legal(), which takes only a position and a move
 567 /// as input. This function does not require that the side to move is not in
 568 /// check. It is not optimized for speed, and is only used for verifying move
 569 /// legality when building a PV from the transposition table.
 570
 571 bool move_is_legal(const Position& pos, const Move m) {
 572
 573   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 574   if (!pos.is_check())
 575       return move_is_legal(pos, m, pinned);
 576   else
 577   {
 578       Position p(pos);
 579       MoveStack mlist[64];
 580       MoveStack* last = generate_evasions(p, mlist, pinned);
 581       for (MoveStack* cur = mlist; cur != last; cur++)
 582           if (cur->move == m)
 583               return true;
 584
 585       return false;
 586   }
 587 }
 588
 589
 590 namespace {
 591
 592   template<PieceType Piece>
 593   MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 594
 595     Square from;
 596     Bitboard b;
 597
 598     for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++)
 599     {
 600         from = pos.piece_list(us, Piece, i);
 601         b = pos.piece_attacks<Piece>(from) & target;
 602         SERIALIZE_MOVES(b);
 603     }
 604     return mlist;
 605   }
 606
 607   template<PieceType Piece>
 608   MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist,
 609                                   Color us, Bitboard target, Bitboard pinned) {
 610     Square from;
 611     Bitboard b;
 612
 613     for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++)
 614     {
 615         from = pos.piece_list(us, Piece, i);
 616         if (pinned && bit_is_set(pinned, from))
 617             continue;
 618
 619         b = pos.piece_attacks<Piece>(from) & target;
 620         SERIALIZE_MOVES(b);
 621     }
 622     return mlist;
 623   }
 624
 625   template<>
 626   MoveStack* generate_piece_moves<KING>(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 627
 628     Bitboard b;
 629     Square from = pos.king_square(us);
 630
 631     b = pos.piece_attacks<KING>(from) & target;
 632     SERIALIZE_MOVES(b);
 633     return mlist;
 634   }
 635
 636   template<Color Us, SquareDelta Diagonal>
 637   MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion) {
 638
 639     // Calculate our parametrized parameters at compile time
 640     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 641     const Bitboard TFileABB = (Diagonal == DELTA_NE ? FileABB : FileHBB);
 642     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 643     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 644     const SquareDelta TTDELTA_NE = (Diagonal == DELTA_NE ? TDELTA_NE : TDELTA_NW);
 645
 646     Square to;
 647
 648     // Captures in the a1-h8 (a8-h1 for black) diagonal or in the h1-a8 (h8-a1 for black)
 649     Bitboard b1 = move_pawns<Us, Diagonal>(pawns) & ~TFileABB & enemyPieces;
 650
 651     // Capturing promotions
 652     if (promotion)
 653     {
 654         Bitboard b2 = b1 & TRank8BB;
 655         b1 &= ~TRank8BB;
 656         while (b2)
 657         {
 658             to = pop_1st_bit(&b2);
 659             (*mlist++).move = make_promotion_move(to - TTDELTA_NE, to, QUEEN);
 660         }
 661     }
 662
 663     // Capturing non-promotions
 664     SERIALIZE_MOVES_D(b1, -TTDELTA_NE);
 665     return mlist;
 666   }
 667
 668   template<Color Us>
 669   MoveStack* generate_pawn_captures(const Position& pos, MoveStack* mlist) {
 670
 671     // Calculate our parametrized parameters at compile time
 672     const Color Them = (Us == WHITE ? BLACK : WHITE);
 673     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 674     const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB);
 675     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 676
 677     Square to;
 678     Bitboard pawns = pos.pieces(PAWN, Us);
 679     Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us));
 680     bool possiblePromotion = (pawns & TRank7BB);
 681
 682     // Standard captures and capturing promotions in both directions
 683     mlist = generate_pawn_captures_diagonal<Us, DELTA_NE>(mlist, pawns, enemyPieces, possiblePromotion);
 684     mlist = generate_pawn_captures_diagonal<Us, DELTA_NW>(mlist, pawns, enemyPieces, possiblePromotion);
 685
 686     // Non-capturing promotions
 687     if (possiblePromotion)
 688     {
 689         Bitboard b1 = move_pawns<Us, DELTA_N>(pawns) & pos.empty_squares() & TRank8BB;
 690         while (b1)
 691         {
 692             to = pop_1st_bit(&b1);
 693             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN);
 694         }
 695     }
 696
 697     // En passant captures
 698     if (pos.ep_square() != SQ_NONE)
 699     {
 700         assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6);
 701         assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3);
 702
 703         Bitboard b1 = pawns & pos.pawn_attacks(pos.ep_square(), Them);
 704         assert(b1 != EmptyBoardBB);
 705
 706         while (b1)
 707         {
 708             to = pop_1st_bit(&b1);
 709             (*mlist++).move = make_ep_move(to, pos.ep_square());
 710         }
 711     }
 712     return mlist;
 713   }
 714
 715   template<Color Us>
 716   MoveStack* generate_pawn_noncaptures(const Position& pos, MoveStack* mlist) {
 717
 718     // Calculate our parametrized parameters at compile time
 719     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 720     const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB);
 721     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 722     const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE);
 723     const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW);
 724     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 725
 726     Bitboard b1, b2;
 727     Square to;
 728     Bitboard pawns = pos.pieces(PAWN, Us);
 729     Bitboard emptySquares = pos.empty_squares();
 730
 731     if (pawns & TRank7BB) // There is some promotion candidate ?
 732     {
 733          Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us));
 734
 735         // Underpromotion captures in the a1-h8 (a8-h1 for black) direction
 736         b1 = move_pawns<Us, DELTA_NE>(pawns) & ~FileABB & enemyPieces & TRank8BB;
 737         while (b1)
 738         {
 739             to = pop_1st_bit(&b1);
 740             (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, ROOK);
 741             (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, BISHOP);
 742             (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, KNIGHT);
 743         }
 744
 745         // Underpromotion captures in the h1-a8 (h8-a1 for black) direction
 746         b1 = move_pawns<Us, DELTA_NW>(pawns) & ~FileHBB & enemyPieces & TRank8BB;
 747         while (b1)
 748         {
 749             to = pop_1st_bit(&b1);
 750             (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, ROOK);
 751             (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, BISHOP);
 752             (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, KNIGHT);
 753         }
 754
 755         // Underpromotion pawn pushes
 756         b1 = move_pawns<Us, DELTA_N>(pawns) & emptySquares & TRank8BB;
 757         while (b1)
 758         {
 759             to = pop_1st_bit(&b1);
 760             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK);
 761             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, BISHOP);
 762             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, KNIGHT);
 763         }
 764     }
 765
 766     // Single pawn pushes
 767     b2 = b1 = move_pawns<Us, DELTA_N>(pawns) & emptySquares & ~TRank8BB;
 768     SERIALIZE_MOVES_D(b2, -TDELTA_N);
 769
 770     // Double pawn pushes
 771     b2 = move_pawns<Us, DELTA_N>(b1 & TRank3BB) & emptySquares;
 772     SERIALIZE_MOVES_D(b2, -TDELTA_N -TDELTA_N);
 773     return mlist;
 774   }
 775
 776
 777   template<Color Us>
 778   MoveStack* generate_pawn_checks(const Position& pos, Bitboard dc, Square ksq, MoveStack* mlist)
 779   {
 780     // Calculate our parametrized parameters at compile time
 781     const Color Them = (Us == WHITE ? BLACK : WHITE);
 782     const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
 783     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 784     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 785     const SquareDelta TDELTA_S = (Us == WHITE ? DELTA_S : DELTA_N);
 786
 787     Square to;
 788     Bitboard b1, b2, b3;
 789     Bitboard pawns = pos.pieces(PAWN, Us);
 790
 791     if (dc & pawns)
 792     {
 793          Bitboard empty = pos.empty_squares();
 794
 795         // Pawn moves which gives discovered check. This is possible only if the
 796         // pawn is not on the same file as the enemy king, because we don't
 797         // generate captures.
 798         b1 = pawns & ~file_bb(ksq);
 799
 800         // Discovered checks, single pawn pushes, no promotions
 801         b2 = b3 = move_pawns<Us, DELTA_N>(b1 & dc) & empty & ~TRank8BB;
 802         SERIALIZE_MOVES_D(b3, -TDELTA_N);
 803
 804         // Discovered checks, double pawn pushes
 805         b3 = move_pawns<Us, DELTA_N>(b2 & TRank3BB) & empty;
 806         SERIALIZE_MOVES_D(b3, -TDELTA_N -TDELTA_N);
 807     }
 808
 809     // Direct checks. These are possible only for pawns on neighboring files
 810     // and in the two ranks that, after the push, are in front of the enemy king.
 811     b1 = pawns & neighboring_files_bb(ksq) & ~dc;
 812
 813     // We can get false positives if (ksq + x) is not in [0,63] range but
 814     // is not a problem, they will be filtered out later.
 815     b2 = b1 & (rank_bb(ksq + 2 * TDELTA_S) | rank_bb(ksq + 3 * TDELTA_S));
 816     if (!b2)
 817         return mlist;
 818
 819     // Direct checks, single pawn pushes
 820     Bitboard empty = pos.empty_squares();
 821     b2 = move_pawns<Us, DELTA_N>(b1) & empty;
 822     b3 = b2 & pos.pawn_attacks(ksq, Them);
 823     SERIALIZE_MOVES_D(b3, -TDELTA_N);
 824
 825     // Direct checks, double pawn pushes
 826     b3 =  move_pawns<Us, DELTA_N>(b2 & TRank3BB) & empty & pos.pawn_attacks(ksq, Them);
 827     SERIALIZE_MOVES_D(b3, -TDELTA_N -TDELTA_N);
 828     return mlist;
 829   }
 830
 831   template<PieceType Piece>
 832   MoveStack* generate_piece_checks(const Position& pos, MoveStack* mlist, Color us,
 833                                    Bitboard dc, Square ksq) {
 834
 835     Bitboard target = pos.pieces(Piece, us);
 836
 837     // Discovered checks
 838     Bitboard b = target & dc;
 839     while (b)
 840     {
 841         Square from = pop_1st_bit(&b);
 842         Bitboard bb = pos.piece_attacks<Piece>(from) & pos.empty_squares();
 843         if (Piece == KING)
 844             bb &= ~QueenPseudoAttacks[ksq];
 845
 846         SERIALIZE_MOVES(bb);
 847     }
 848
 849     // Direct checks
 850     b = target & ~dc;
 851     if (Piece != KING || b)
 852     {
 853         Bitboard checkSqs = pos.piece_attacks<Piece>(ksq) & pos.empty_squares();
 854         if (!checkSqs)
 855             return mlist;
 856
 857         while (b)
 858         {
 859             Square from = pop_1st_bit(&b);
 860             if (   (Piece == QUEEN  && !(QueenPseudoAttacks[from]  & checkSqs))
 861                 || (Piece == ROOK   && !(RookPseudoAttacks[from]   & checkSqs))
 862                 || (Piece == BISHOP && !(BishopPseudoAttacks[from] & checkSqs)))
 863                 continue;
 864
 865             Bitboard bb = pos.piece_attacks<Piece>(from) & checkSqs;
 866             SERIALIZE_MOVES(bb);
 867         }
 868     }
 869     return mlist;
 870   }
 871
 872   template<Color Us>
 873   MoveStack* generate_pawn_blocking_evasions(const Position& pos, Bitboard pinned,
 874                                              Bitboard blockSquares, MoveStack* mlist) {
 875
 876     // Calculate our parametrized parameters at compile time
 877     const Rank TRANK_8 = (Us == WHITE ? RANK_8 : RANK_1);
 878     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
 879     const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S);
 880
 881     Square to;
 882
 883     // Find non-pinned pawns and push them one square
 884     Bitboard b1 = move_pawns<Us, DELTA_N>(pos.pieces(PAWN, Us) & ~pinned);
 885
 886     // We don't have to AND with empty squares here,
 887     // because the blocking squares will always be empty.
 888     Bitboard b2 = b1 & blockSquares;
 889     while (b2)
 890     {
 891         to = pop_1st_bit(&b2);
 892
 893         assert(pos.piece_on(to) == EMPTY);
 894
 895         if (square_rank(to) == TRANK_8)
 896         {
 897             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN);
 898             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK);
 899             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, BISHOP);
 900             (*mlist++).move = make_promotion_move(to - TDELTA_N, to, KNIGHT);
 901         } else
 902             (*mlist++).move = make_move(to - TDELTA_N, to);
 903     }
 904
 905     // Double pawn pushes
 906     b2 = b1 & pos.empty_squares() & TRank3BB;
 907     b2 = move_pawns<Us, DELTA_N>(b2) & blockSquares;
 908     while (b2)
 909     {
 910         to = pop_1st_bit(&b2);
 911
 912         assert(pos.piece_on(to) == EMPTY);
 913         assert(Us != WHITE || square_rank(to) == RANK_4);
 914         assert(Us != BLACK || square_rank(to) == RANK_5);
 915
 916         (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to);
 917     }
 918     return mlist;
 919   }
 920
 921   template<CastlingSide Side>
 922   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist) {
 923
 924     Color us = pos.side_to_move();
 925
 926     if (  (Side == KING_SIDE && pos.can_castle_kingside(us))
 927         ||(Side == QUEEN_SIDE && pos.can_castle_queenside(us)))
 928     {
 929         Color them = opposite_color(us);
 930         Square ksq = pos.king_square(us);
 931
 932         assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING));
 933
 934         Square rsq = (Side == KING_SIDE ? pos.initial_kr_square(us) : pos.initial_qr_square(us));
 935         Square s1 = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);
 936         Square s2 = relative_square(us, Side == KING_SIDE ? SQ_F1 : SQ_D1);
 937         Square s;
 938         bool illegal = false;
 939
 940         assert(pos.piece_on(rsq) == piece_of_color_and_type(us, ROOK));
 941
 942         // It is a bit complicated to correctly handle Chess960
 943         for (s = Min(ksq, s1); s <= Max(ksq, s1); s++)
 944             if (  (s != ksq && s != rsq && pos.square_is_occupied(s))
 945                 || pos.attackers_to(s, them))
 946                 illegal = true;
 947
 948         for (s = Min(rsq, s2); s <= Max(rsq, s2); s++)
 949             if (s != ksq && s != rsq && pos.square_is_occupied(s))
 950                 illegal = true;
 951
 952         if (   Side == QUEEN_SIDE
 953             && square_file(rsq) == FILE_B
 954             && (   pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, ROOK)
 955                 || pos.piece_on(relative_square(us, SQ_A1)) == piece_of_color_and_type(them, QUEEN)))
 956             illegal = true;
 957
 958         if (!illegal)
 959             (*mlist++).move = make_castle_move(ksq, rsq);
 960     }
 961     return mlist;
 962   }
 963
 964   bool castling_is_check(const Position& pos, CastlingSide side) {
 965
 966     // After castling opponent king is attacked by the castled rook?
 967     File rookFile = (side == QUEEN_SIDE ? FILE_D : FILE_F);
 968     Color us = pos.side_to_move();
 969     Square ksq = pos.king_square(us);
 970     Bitboard occ = pos.occupied_squares();
 971
 972     clear_bit(&occ, ksq); // Remove our king from the board
 973     Square rsq = make_square(rookFile, square_rank(ksq));
 974     return bit_is_set(rook_attacks_bb(rsq, occ), pos.king_square(opposite_color(us)));
 975   }
 976 }