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