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-2012 Marco Costalba, Joona Kiiski, Tord Romstad
   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 #include <algorithm>
  21 #include <cassert>
  22
  23 #include "bitcount.h"
  24 #include "movegen.h"
  25 #include "position.h"
  26
  27 /// Simple macro to wrap a very common while loop, no facny, no flexibility,
  28 /// hardcoded names 'mlist' and 'from'.
  29 #define SERIALIZE_MOVES(b) while (b) (*mlist++).move = make_move(from, pop_1st_bit(&b))
  30
  31 /// Version used for pawns, where the 'from' square is given as a delta from the 'to' square
  32 #define SERIALIZE_MOVES_D(b, d) while (b) { to = pop_1st_bit(&b); (*mlist++).move = make_move(to + (d), to); }
  33
  34 namespace {
  35
  36   enum CastlingSide { KING_SIDE, QUEEN_SIDE };
  37
  38   template<CastlingSide Side>
  39   MoveStack* generate_castle_moves(const Position& pos, MoveStack* mlist, Color us) {
  40
  41     const CastleRight CR[] = { Side ? WHITE_OOO : WHITE_OO,
  42                                Side ? BLACK_OOO : BLACK_OO };
  43
  44     if (!pos.can_castle(CR[us]))
  45         return mlist;
  46
  47     // After castling, the rook and king final positions are the same in Chess960
  48     // as they would be in standard chess.
  49     Square kfrom = pos.king_square(us);
  50     Square rfrom = pos.castle_rook_square(CR[us]);
  51     Square kto = relative_square(us, Side == KING_SIDE ? SQ_G1 : SQ_C1);
  52     Square rto = relative_square(us, Side == KING_SIDE ? SQ_F1 : SQ_D1);
  53     Bitboard enemies = pos.pieces(flip(us));
  54
  55     assert(!pos.in_check());
  56     assert(pos.piece_on(kfrom) == make_piece(us, KING));
  57     assert(pos.piece_on(rfrom) == make_piece(us, ROOK));
  58
  59     // Unimpeded rule: All the squares between the king's initial and final squares
  60     // (including the final square), and all the squares between the rook's initial
  61     // and final squares (including the final square), must be vacant except for
  62     // the king and castling rook.
  63     for (Square s = std::min(rfrom, rto), e = std::max(rfrom, rto); s <= e; s++)
  64         if (s != kfrom && s != rfrom && !pos.square_is_empty(s))
  65             return mlist;
  66
  67     for (Square s = std::min(kfrom, kto), e = std::max(kfrom, kto); s <= e; s++)
  68         if (  (s != kfrom && s != rfrom && !pos.square_is_empty(s))
  69             ||(pos.attackers_to(s) & enemies))
  70             return mlist;
  71
  72     // Because we generate only legal castling moves we need to verify that
  73     // when moving the castling rook we do not discover some hidden checker.
  74     // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
  75     if (pos.is_chess960())
  76     {
  77         Bitboard occ = pos.occupied_squares();
  78         clear_bit(&occ, rfrom);
  79         if (pos.attackers_to(kto, occ) & enemies)
  80             return mlist;
  81     }
  82
  83     (*mlist++).move = make_castle(kfrom, rfrom);
  84
  85     return mlist;
  86   }
  87
  88
  89   template<Square Delta>
  90   inline Bitboard move_pawns(Bitboard p) {
  91
  92     return Delta == DELTA_N  ? p << 8 : Delta == DELTA_S  ? p >> 8 :
  93            Delta == DELTA_NE ? p << 9 : Delta == DELTA_SE ? p >> 7 :
  94            Delta == DELTA_NW ? p << 7 : Delta == DELTA_SW ? p >> 9 : p;
  95   }
  96
  97
  98   template<Square Delta>
  99   inline MoveStack* generate_pawn_captures(MoveStack* mlist, Bitboard pawns, Bitboard target) {
 100
 101     const Bitboard TFileABB = (   Delta == DELTA_NE
 102                                || Delta == DELTA_SE ? FileABB : FileHBB);
 103     Bitboard b;
 104     Square to;
 105
 106     b = move_pawns<Delta>(pawns) & target & ~TFileABB;
 107     SERIALIZE_MOVES_D(b, -Delta);
 108     return mlist;
 109   }
 110
 111
 112   template<MoveType Type, Square Delta>
 113   inline MoveStack* generate_promotions(MoveStack* mlist, Bitboard pawnsOn7, Bitboard target, Square ksq) {
 114
 115     const Bitboard TFileABB = (   Delta == DELTA_NE
 116                                || Delta == DELTA_SE ? FileABB : FileHBB);
 117     Bitboard b;
 118     Square to;
 119
 120     b = move_pawns<Delta>(pawnsOn7) & target;
 121
 122     if (Delta != DELTA_N && Delta != DELTA_S)
 123         b &= ~TFileABB;
 124
 125     while (b)
 126     {
 127         to = pop_1st_bit(&b);
 128
 129         if (Type == MV_CAPTURE || Type == MV_EVASION || Type == MV_NON_EVASION)
 130             (*mlist++).move = make_promotion(to - Delta, to, QUEEN);
 131
 132         if (Type == MV_NON_CAPTURE || Type == MV_EVASION || Type == MV_NON_EVASION)
 133         {
 134             (*mlist++).move = make_promotion(to - Delta, to, ROOK);
 135             (*mlist++).move = make_promotion(to - Delta, to, BISHOP);
 136             (*mlist++).move = make_promotion(to - Delta, to, KNIGHT);
 137         }
 138
 139         // Knight-promotion is the only one that can give a check (direct or
 140         // discovered) not already included in the queen-promotion.
 141         if (   Type == MV_NON_CAPTURE_CHECK
 142             && bit_is_set(StepAttacksBB[W_KNIGHT][to], ksq))
 143                 (*mlist++).move = make_promotion(to - Delta, to, KNIGHT);
 144         else
 145             (void)ksq; // Silence a warning under MSVC
 146     }
 147     return mlist;
 148   }
 149
 150
 151   template<Color Us, MoveType Type>
 152   MoveStack* generate_pawn_moves(const Position& pos, MoveStack* mlist, Bitboard target, Square ksq) {
 153
 154     // Calculate our parametrized parameters at compile time, named according to
 155     // the point of view of white side.
 156     const Color    Them     = (Us == WHITE ? BLACK    : WHITE);
 157     const Bitboard TRank7BB = (Us == WHITE ? Rank7BB  : Rank2BB);
 158     const Bitboard TRank3BB = (Us == WHITE ? Rank3BB  : Rank6BB);
 159     const Square   UP       = (Us == WHITE ? DELTA_N  : DELTA_S);
 160     const Square   RIGHT    = (Us == WHITE ? DELTA_NE : DELTA_SW);
 161     const Square   LEFT     = (Us == WHITE ? DELTA_NW : DELTA_SE);
 162
 163     Square to;
 164     Bitboard b1, b2, dc1, dc2, emptySquares;
 165
 166     Bitboard pawns       = pos.pieces(PAWN, Us);
 167     Bitboard pawnsOn7    = pawns &  TRank7BB;
 168     Bitboard pawnsNotOn7 = pawns & ~TRank7BB;
 169
 170     Bitboard enemies = (Type == MV_EVASION ? pos.pieces(Them) & target:
 171                         Type == MV_CAPTURE ? target : pos.pieces(Them));
 172
 173     // Single and double pawn pushes, no promotions
 174     if (Type != MV_CAPTURE)
 175     {
 176         emptySquares = (Type == MV_NON_CAPTURE ? target : pos.empty_squares());
 177
 178         b1 = move_pawns<UP>(pawnsNotOn7)   & emptySquares;
 179         b2 = move_pawns<UP>(b1 & TRank3BB) & emptySquares;
 180
 181         if (Type == MV_EVASION) // Consider only blocking squares
 182         {
 183             b1 &= target;
 184             b2 &= target;
 185         }
 186
 187         if (Type == MV_NON_CAPTURE_CHECK)
 188         {
 189             // Consider only direct checks
 190             b1 &= pos.attacks_from<PAWN>(ksq, Them);
 191             b2 &= pos.attacks_from<PAWN>(ksq, Them);
 192
 193             // Add pawn pushes which give discovered check. This is possible only
 194             // if the pawn is not on the same file as the enemy king, because we
 195             // don't generate captures. Note that a possible discovery check
 196             // promotion has been already generated among captures.
 197             if (pawnsNotOn7 & target) // Target is dc bitboard
 198             {
 199                 dc1 = move_pawns<UP>(pawnsNotOn7 & target) & emptySquares & ~file_bb(ksq);
 200                 dc2 = move_pawns<UP>(dc1 & TRank3BB) & emptySquares;
 201
 202                 b1 |= dc1;
 203                 b2 |= dc2;
 204             }
 205         }
 206
 207         SERIALIZE_MOVES_D(b1, -UP);
 208         SERIALIZE_MOVES_D(b2, -UP -UP);
 209     }
 210
 211     // Promotions and underpromotions
 212     if (pawnsOn7)
 213     {
 214         if (Type == MV_CAPTURE)
 215             emptySquares = pos.empty_squares();
 216
 217         if (Type == MV_EVASION)
 218             emptySquares &= target;
 219
 220         mlist = generate_promotions<Type, RIGHT>(mlist, pawnsOn7, enemies, ksq);
 221         mlist = generate_promotions<Type, LEFT>(mlist, pawnsOn7, enemies, ksq);
 222         mlist = generate_promotions<Type, UP>(mlist, pawnsOn7, emptySquares, ksq);
 223     }
 224
 225     // Standard and en-passant captures
 226     if (Type == MV_CAPTURE || Type == MV_EVASION || Type == MV_NON_EVASION)
 227     {
 228         mlist = generate_pawn_captures<RIGHT>(mlist, pawnsNotOn7, enemies);
 229         mlist = generate_pawn_captures<LEFT >(mlist, pawnsNotOn7, enemies);
 230
 231         if (pos.ep_square() != SQ_NONE)
 232         {
 233             assert(rank_of(pos.ep_square()) == (Us == WHITE ? RANK_6 : RANK_3));
 234
 235             // An en passant capture can be an evasion only if the checking piece
 236             // is the double pushed pawn and so is in the target. Otherwise this
 237             // is a discovery check and we are forced to do otherwise.
 238             if (Type == MV_EVASION && !bit_is_set(target, pos.ep_square() - UP))
 239                 return mlist;
 240
 241             b1 = pawnsNotOn7 & pos.attacks_from<PAWN>(pos.ep_square(), Them);
 242
 243             assert(b1);
 244
 245             while (b1)
 246                 (*mlist++).move = make_enpassant(pop_1st_bit(&b1), pos.ep_square());
 247         }
 248     }
 249
 250     return mlist;
 251   }
 252
 253
 254   template<PieceType Pt>
 255   inline MoveStack* generate_direct_checks(const Position& pos, MoveStack* mlist, Color us,
 256                                            Bitboard dc, Square ksq) {
 257     assert(Pt != KING && Pt != PAWN);
 258
 259     Bitboard checkSqs, b;
 260     Square from;
 261     const Square* pl = pos.piece_list(us, Pt);
 262
 263     if ((from = *pl++) == SQ_NONE)
 264         return mlist;
 265
 266     checkSqs = pos.attacks_from<Pt>(ksq) & pos.empty_squares();
 267
 268     do
 269     {
 270         if (   (Pt == QUEEN  && !(QueenPseudoAttacks[from]  & checkSqs))
 271             || (Pt == ROOK   && !(RookPseudoAttacks[from]   & checkSqs))
 272             || (Pt == BISHOP && !(BishopPseudoAttacks[from] & checkSqs)))
 273             continue;
 274
 275         if (dc && bit_is_set(dc, from))
 276             continue;
 277
 278         b = pos.attacks_from<Pt>(from) & checkSqs;
 279         SERIALIZE_MOVES(b);
 280
 281     } while ((from = *pl++) != SQ_NONE);
 282
 283     return mlist;
 284   }
 285
 286
 287   template<>
 288   FORCE_INLINE MoveStack* generate_direct_checks<PAWN>(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) {
 289
 290     return (us == WHITE ? generate_pawn_moves<WHITE, MV_NON_CAPTURE_CHECK>(p, m, dc, ksq)
 291                         : generate_pawn_moves<BLACK, MV_NON_CAPTURE_CHECK>(p, m, dc, ksq));
 292   }
 293
 294
 295   template<PieceType Pt, MoveType Type>
 296   FORCE_INLINE MoveStack* generate_piece_moves(const Position& p, MoveStack* m, Color us, Bitboard t) {
 297
 298     assert(Pt == PAWN);
 299     return (us == WHITE ? generate_pawn_moves<WHITE, Type>(p, m, t, SQ_NONE)
 300                         : generate_pawn_moves<BLACK, Type>(p, m, t, SQ_NONE));
 301   }
 302
 303
 304   template<PieceType Pt>
 305   FORCE_INLINE MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 306
 307     Bitboard b;
 308     Square from;
 309     const Square* pl = pos.piece_list(us, Pt);
 310
 311     if (*pl != SQ_NONE)
 312     {
 313         do {
 314             from = *pl;
 315             b = pos.attacks_from<Pt>(from) & target;
 316             SERIALIZE_MOVES(b);
 317         } while (*++pl != SQ_NONE);
 318     }
 319     return mlist;
 320   }
 321
 322
 323   template<>
 324   FORCE_INLINE MoveStack* generate_piece_moves<KING>(const Position& pos, MoveStack* mlist, Color us, Bitboard target) {
 325
 326     Bitboard b;
 327     Square from = pos.king_square(us);
 328
 329     b = pos.attacks_from<KING>(from) & target;
 330     SERIALIZE_MOVES(b);
 331     return mlist;
 332   }
 333
 334 } // namespace
 335
 336
 337 /// generate<MV_CAPTURE> generates all pseudo-legal captures and queen
 338 /// promotions. Returns a pointer to the end of the move list.
 339 ///
 340 /// generate<MV_NON_CAPTURE> generates all pseudo-legal non-captures and
 341 /// underpromotions. Returns a pointer to the end of the move list.
 342 ///
 343 /// generate<MV_NON_EVASION> generates all pseudo-legal captures and
 344 /// non-captures. Returns a pointer to the end of the move list.
 345
 346 template<MoveType Type>
 347 MoveStack* generate(const Position& pos, MoveStack* mlist) {
 348
 349   assert(Type == MV_CAPTURE || Type == MV_NON_CAPTURE || Type == MV_NON_EVASION);
 350   assert(!pos.in_check());
 351
 352   Color us = pos.side_to_move();
 353   Bitboard target;
 354
 355   if (Type == MV_CAPTURE)
 356       target = pos.pieces(flip(us));
 357
 358   else if (Type == MV_NON_CAPTURE)
 359       target = pos.empty_squares();
 360
 361   else if (Type == MV_NON_EVASION)
 362       target = pos.pieces(flip(us)) | pos.empty_squares();
 363
 364   mlist = generate_piece_moves<PAWN, Type>(pos, mlist, us, target);
 365   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
 366   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
 367   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
 368   mlist = generate_piece_moves<QUEEN>(pos, mlist, us, target);
 369   mlist = generate_piece_moves<KING>(pos, mlist, us, target);
 370
 371   if (Type != MV_CAPTURE && pos.can_castle(us))
 372   {
 373       mlist = generate_castle_moves<KING_SIDE>(pos, mlist, us);
 374       mlist = generate_castle_moves<QUEEN_SIDE>(pos, mlist, us);
 375   }
 376
 377   return mlist;
 378 }
 379
 380 // Explicit template instantiations
 381 template MoveStack* generate<MV_CAPTURE>(const Position& pos, MoveStack* mlist);
 382 template MoveStack* generate<MV_NON_CAPTURE>(const Position& pos, MoveStack* mlist);
 383 template MoveStack* generate<MV_NON_EVASION>(const Position& pos, MoveStack* mlist);
 384
 385
 386 /// generate<MV_NON_CAPTURE_CHECK> generates all pseudo-legal non-captures and knight
 387 /// underpromotions that give check. Returns a pointer to the end of the move list.
 388 template<>
 389 MoveStack* generate<MV_NON_CAPTURE_CHECK>(const Position& pos, MoveStack* mlist) {
 390
 391   assert(!pos.in_check());
 392
 393   Bitboard b, dc;
 394   Square from;
 395   PieceType pt;
 396   Color us = pos.side_to_move();
 397   Square ksq = pos.king_square(flip(us));
 398
 399   assert(pos.piece_on(ksq) == make_piece(flip(us), KING));
 400
 401   // Discovered non-capture checks
 402   b = dc = pos.discovered_check_candidates();
 403
 404   while (b)
 405   {
 406      from = pop_1st_bit(&b);
 407      pt = type_of(pos.piece_on(from));
 408
 409      if (pt == PAWN)
 410          continue; // Will be generated togheter with direct checks
 411
 412      b = pos.attacks_from(Piece(pt), from) & pos.empty_squares();
 413
 414      if (pt == KING)
 415          b &= ~QueenPseudoAttacks[ksq];
 416
 417      SERIALIZE_MOVES(b);
 418   }
 419
 420   // Direct non-capture checks
 421   mlist = generate_direct_checks<PAWN>(pos, mlist, us, dc, ksq);
 422   mlist = generate_direct_checks<KNIGHT>(pos, mlist, us, dc, ksq);
 423   mlist = generate_direct_checks<BISHOP>(pos, mlist, us, dc, ksq);
 424   mlist = generate_direct_checks<ROOK>(pos, mlist, us, dc, ksq);
 425   return  generate_direct_checks<QUEEN>(pos, mlist, us, dc, ksq);
 426 }
 427
 428
 429 /// generate<MV_EVASION> generates all pseudo-legal check evasions when the side
 430 /// to move is in check. Returns a pointer to the end of the move list.
 431 template<>
 432 MoveStack* generate<MV_EVASION>(const Position& pos, MoveStack* mlist) {
 433
 434   assert(pos.in_check());
 435
 436   Bitboard b, target;
 437   Square from, checksq;
 438   int checkersCnt = 0;
 439   Color us = pos.side_to_move();
 440   Square ksq = pos.king_square(us);
 441   Bitboard checkers = pos.checkers();
 442   Bitboard sliderAttacks = 0;
 443
 444   assert(pos.piece_on(ksq) == make_piece(us, KING));
 445   assert(checkers);
 446
 447   // Find squares attacked by slider checkers, we will remove
 448   // them from the king evasions set so to early skip known
 449   // illegal moves and avoid an useless legality check later.
 450   b = checkers;
 451   do
 452   {
 453       checkersCnt++;
 454       checksq = pop_1st_bit(&b);
 455
 456       assert(color_of(pos.piece_on(checksq)) == flip(us));
 457
 458       switch (type_of(pos.piece_on(checksq)))
 459       {
 460       case BISHOP: sliderAttacks |= BishopPseudoAttacks[checksq]; break;
 461       case ROOK:   sliderAttacks |= RookPseudoAttacks[checksq];   break;
 462       case QUEEN:
 463           // If queen and king are far we can safely remove all the squares attacked
 464           // in the other direction becuase are not reachable by the king anyway.
 465           if (squares_between(ksq, checksq) || (RookPseudoAttacks[checksq] & (1ULL << ksq)))
 466               sliderAttacks |= QueenPseudoAttacks[checksq];
 467
 468           // Otherwise, if king and queen are adjacent and on a diagonal line, we need to
 469           // use real rook attacks to check if king is safe to move in the other direction.
 470           // For example: king in B2, queen in A1 a knight in B1, and we can safely move to C1.
 471           else
 472               sliderAttacks |= BishopPseudoAttacks[checksq] | pos.attacks_from<ROOK>(checksq);
 473
 474       default:
 475           break;
 476       }
 477   } while (b);
 478
 479   // Generate evasions for king, capture and non capture moves
 480   b = pos.attacks_from<KING>(ksq) & ~pos.pieces(us) & ~sliderAttacks;
 481   from = ksq;
 482   SERIALIZE_MOVES(b);
 483
 484   // Generate evasions for other pieces only if not double check
 485   if (checkersCnt > 1)
 486       return mlist;
 487
 488   // Find squares where a blocking evasion or a capture of the
 489   // checker piece is possible.
 490   target = squares_between(checksq, ksq) | checkers;
 491
 492   mlist = generate_piece_moves<PAWN, MV_EVASION>(pos, mlist, us, target);
 493   mlist = generate_piece_moves<KNIGHT>(pos, mlist, us, target);
 494   mlist = generate_piece_moves<BISHOP>(pos, mlist, us, target);
 495   mlist = generate_piece_moves<ROOK>(pos, mlist, us, target);
 496   return  generate_piece_moves<QUEEN>(pos, mlist, us, target);
 497 }
 498
 499
 500 /// generate<MV_LEGAL> generates all legal moves in the current position
 501
 502 template<>
 503 MoveStack* generate<MV_LEGAL>(const Position& pos, MoveStack* mlist) {
 504
 505   MoveStack *last, *cur = mlist;
 506   Bitboard pinned = pos.pinned_pieces();
 507
 508   last = pos.in_check() ? generate<MV_EVASION>(pos, mlist)
 509                         : generate<MV_NON_EVASION>(pos, mlist);
 510
 511   // Remove illegal moves from the list
 512   while (cur != last)
 513       if (!pos.pl_move_is_legal(cur->move, pinned))
 514           cur->move = (--last)->move;
 515       else
 516           cur++;
 517
 518   return last;
 519 }