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