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_knight_moves(const Position&, MoveStack*, Color side, Bitboard t);
  40   int generate_bishop_moves(const Position&, MoveStack*, Color side, Bitboard t);
  41   int generate_rook_moves(const Position&, MoveStack*, Color side, Bitboard t);
  42   int generate_queen_moves(const Position&, MoveStack*, Color side, Bitboard t);
  43   int generate_king_moves(const Position&, MoveStack*, Square from, Bitboard t);
  44   int generate_castle_moves(const Position&, MoveStack*, Color us);
  45
  46 }
  47
  48
  49 ////
  50 //// Functions
  51 ////
  52
  53
  54 /// generate_captures generates() all pseudo-legal captures and queen
  55 /// promotions.  The return value is the number of moves generated.
  56
  57 int generate_captures(const Position& pos, MoveStack* mlist) {
  58
  59   assert(pos.is_ok());
  60   assert(!pos.is_check());
  61
  62   Color us = pos.side_to_move();
  63   Bitboard target = pos.pieces_of_color(opposite_color(us));
  64   int n;
  65
  66   if (us == WHITE)
  67       n = generate_white_pawn_captures(pos, mlist);
  68   else
  69       n = generate_black_pawn_captures(pos, mlist);
  70
  71   n += generate_knight_moves(pos, mlist+n, us, target);
  72   n += generate_bishop_moves(pos, mlist+n, us, target);
  73   n += generate_rook_moves(pos, mlist+n, us, target);
  74   n += generate_queen_moves(pos, mlist+n, us, target);
  75   n += generate_king_moves(pos, mlist+n, pos.king_square(us), target);
  76   return n;
  77 }
  78
  79
  80 /// generate_noncaptures() generates all pseudo-legal non-captures and
  81 /// underpromotions.  The return value is the number of moves generated.
  82
  83 int generate_noncaptures(const Position& pos, MoveStack *mlist) {
  84
  85   assert(pos.is_ok());
  86   assert(!pos.is_check());
  87
  88   Color us = pos.side_to_move();
  89   Bitboard target = pos.empty_squares();
  90   int n;
  91
  92   if (us == WHITE)
  93       n = generate_white_pawn_noncaptures(pos, mlist);
  94   else
  95       n = generate_black_pawn_noncaptures(pos, mlist);
  96
  97   n += generate_knight_moves(pos, mlist+n, us, target);
  98   n += generate_bishop_moves(pos, mlist+n, us, target);
  99   n += generate_rook_moves(pos, mlist+n, us, target);
 100   n += generate_queen_moves(pos, mlist+n, us, target);
 101   n += generate_king_moves(pos, mlist+n, pos.king_square(us), target);
 102   n += generate_castle_moves(pos, mlist+n, us);
 103   return n;
 104 }
 105
 106
 107 /// generate_checks() generates all pseudo-legal non-capturing, non-promoting
 108 /// checks, except castling moves (will add this later).  It returns the
 109 /// number of generated moves.
 110
 111 int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) {
 112
 113   assert(pos.is_ok());
 114   assert(!pos.is_check());
 115
 116   Color us, them;
 117   Square ksq, from, to;
 118   Bitboard empty, checkSqs, b1, b2, b3;
 119   int n = 0;
 120
 121   us = pos.side_to_move();
 122   them = opposite_color(us);
 123
 124   ksq = pos.king_square(them);
 125   assert(pos.piece_on(ksq) == king_of_color(them));
 126
 127   dc = pos.discovered_check_candidates(us);
 128   empty = pos.empty_squares();
 129
 130   // Pawn moves.  This is somewhat messy, and we use separate code for white
 131   // and black, because we can't shift by negative numbers in C/C++.  :-(
 132
 133   if (us == WHITE)
 134   {
 135     // Pawn moves which give discovered check.  This is possible only if the
 136     // pawn is not on the same file as the enemy king, because we don't
 137     // generate captures.
 138
 139     // Find all friendly pawns not on the enemy king's file:
 140     b1 = pos.pawns(us) & ~file_bb(ksq);
 141
 142     // Discovered checks, single pawn pushes:
 143     b2 = b3 = ((b1 & dc) << 8) & ~Rank8BB & empty;
 144     while(b3) {
 145       to = pop_1st_bit(&b3);
 146       mlist[n++].move = make_move(to - DELTA_N, to);
 147     }
 148
 149     // Discovered checks, double pawn pushes:
 150     b3 = ((b2 & Rank3BB) << 8) & empty;
 151     while(b3) {
 152       to = pop_1st_bit(&b3);
 153       mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to);
 154     }
 155
 156     // Direct checks.  These are possible only for pawns on neighboring files
 157     // of the enemy king:
 158
 159     b1 &= (~dc & neighboring_files_bb(ksq));
 160
 161     // Direct checks, single pawn pushes:
 162     b2 = (b1 << 8) & empty;
 163     b3 = b2 & pos.black_pawn_attacks(ksq);
 164     while(b3) {
 165       to = pop_1st_bit(&b3);
 166       mlist[n++].move = make_move(to - DELTA_N, to);
 167     }
 168
 169     // Direct checks, double pawn pushes:
 170     b3 = ((b2 & Rank3BB) << 8) & empty & pos.black_pawn_attacks(ksq);
 171     while(b3) {
 172       to = pop_1st_bit(&b3);
 173       mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to);
 174     }
 175   }
 176   else { // (us == BLACK)
 177
 178     // Pawn moves which give discovered check.  This is possible only if the
 179     // pawn is not on the same file as the enemy king, because we don't
 180     // generate captures.
 181
 182     // Find all friendly pawns not on the enemy king's file:
 183     b1 = pos.pawns(us) & ~file_bb(ksq);
 184
 185     // Discovered checks, single pawn pushes:
 186     b2 = b3 = ((b1 & dc) >> 8) & ~Rank1BB & empty;
 187     while(b3) {
 188       to = pop_1st_bit(&b3);
 189       mlist[n++].move = make_move(to - DELTA_S, to);
 190     }
 191
 192     // Discovered checks, double pawn pushes:
 193     b3 = ((b2 & Rank6BB) >> 8) & empty;
 194     while(b3) {
 195       to = pop_1st_bit(&b3);
 196       mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to);
 197     }
 198
 199     // Direct checks.  These are possible only for pawns on neighboring files
 200     // of the enemy king:
 201
 202     b1 &= (~dc & neighboring_files_bb(ksq));
 203
 204     // Direct checks, single pawn pushes:
 205     b2 = (b1 >> 8) & empty;
 206     b3 = b2 & pos.white_pawn_attacks(ksq);
 207     while(b3) {
 208       to = pop_1st_bit(&b3);
 209       mlist[n++].move = make_move(to - DELTA_S, to);
 210     }
 211
 212     // Direct checks, double pawn pushes:
 213     b3 = ((b2 & Rank6BB) >> 8) & empty & pos.black_pawn_attacks(ksq);
 214     while(b3) {
 215       to = pop_1st_bit(&b3);
 216       mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to);
 217     }
 218   }
 219
 220   // Knight moves
 221   b1 = pos.knights(us);
 222   if(b1) {
 223     // Discovered knight checks:
 224     b2 = b1 & dc;
 225     while(b2) {
 226       from = pop_1st_bit(&b2);
 227       b3 = pos.knight_attacks(from) & empty;
 228       while(b3) {
 229         to = pop_1st_bit(&b3);
 230         mlist[n++].move = make_move(from, to);
 231       }
 232     }
 233
 234     // Direct knight checks:
 235     b2 = b1 & ~dc;
 236     checkSqs = pos.knight_attacks(ksq) & empty;
 237     while(b2) {
 238       from = pop_1st_bit(&b2);
 239       b3 = pos.knight_attacks(from) & checkSqs;
 240       while(b3) {
 241         to = pop_1st_bit(&b3);
 242         mlist[n++].move = make_move(from, to);
 243       }
 244     }
 245   }
 246
 247   // Bishop moves
 248   b1 = pos.bishops(us);
 249   if(b1) {
 250     // Discovered bishop checks:
 251     b2 = b1 & dc;
 252     while(b2) {
 253       from = pop_1st_bit(&b2);
 254       b3 = pos.bishop_attacks(from) & empty;
 255       while(b3) {
 256         to = pop_1st_bit(&b3);
 257         mlist[n++].move = make_move(from, to);
 258       }
 259     }
 260
 261     // Direct bishop checks:
 262     b2 = b1 & ~dc;
 263     checkSqs = pos.bishop_attacks(ksq) & empty;
 264     while(b2) {
 265       from = pop_1st_bit(&b2);
 266       b3 = pos.bishop_attacks(from) & checkSqs;
 267       while(b3) {
 268         to = pop_1st_bit(&b3);
 269         mlist[n++].move = make_move(from, to);
 270       }
 271     }
 272   }
 273
 274   // Rook moves
 275   b1 = pos.rooks(us);
 276   if(b1) {
 277     // Discovered rook checks:
 278     b2 = b1 & dc;
 279     while(b2) {
 280       from = pop_1st_bit(&b2);
 281       b3 = pos.rook_attacks(from) & empty;
 282       while(b3) {
 283         to = pop_1st_bit(&b3);
 284         mlist[n++].move = make_move(from, to);
 285       }
 286     }
 287
 288     // Direct rook checks:
 289     b2 = b1 & ~dc;
 290     checkSqs = pos.rook_attacks(ksq) & empty;
 291     while(b2) {
 292       from = pop_1st_bit(&b2);
 293       b3 = pos.rook_attacks(from) & checkSqs;
 294       while(b3) {
 295         to = pop_1st_bit(&b3);
 296         mlist[n++].move = make_move(from, to);
 297       }
 298     }
 299   }
 300
 301   // Queen moves
 302   b1 = pos.queens(us);
 303   if(b1) {
 304     // Discovered queen checks are impossible!
 305
 306     // Direct queen checks:
 307     checkSqs = pos.queen_attacks(ksq) & empty;
 308     while(b1) {
 309       from = pop_1st_bit(&b1);
 310       b2 = pos.queen_attacks(from) & checkSqs;
 311       while(b2) {
 312         to = pop_1st_bit(&b2);
 313         mlist[n++].move = make_move(from, to);
 314       }
 315     }
 316   }
 317
 318   // King moves
 319   from = pos.king_square(us);
 320   if(bit_is_set(dc, from)) {
 321     b1 = pos.king_attacks(from) & empty & ~QueenPseudoAttacks[ksq];
 322     while(b1) {
 323       to = pop_1st_bit(&b1);
 324       mlist[n++].move = make_move(from, to);
 325     }
 326   }
 327
 328   // TODO: Castling moves!
 329
 330   return n;
 331 }
 332
 333
 334 /// generate_evasions() generates all check evasions when the side to move is
 335 /// in check.  Unlike the other move generation functions, this one generates
 336 /// only legal moves.  It returns the number of generated moves.  This
 337 /// function is very ugly, and needs cleaning up some time later.  FIXME
 338
 339 int generate_evasions(const Position &pos, MoveStack *mlist) {
 340
 341   assert(pos.is_ok());
 342   assert(pos.is_check());
 343
 344   Color us, them;
 345   Bitboard checkers = pos.checkers();
 346   Bitboard pinned, b1, b2;
 347   Square ksq, from, to;
 348   int n = 0;
 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
 580   assert(pos.is_ok());
 581
 582   if (pos.is_check())
 583       return generate_evasions(pos, mlist);
 584
 585   // Generate pseudo-legal moves:
 586   int n = generate_captures(pos, mlist);
 587   n += generate_noncaptures(pos, mlist + n);
 588
 589   Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
 590
 591   // Remove illegal moves from the list:
 592   for (int i = 0; i < n; i++)
 593       if (!pos.move_is_legal(mlist[i].move, pinned))
 594           mlist[i--].move = mlist[--n].move;
 595
 596   return n;
 597 }
 598
 599
 600 /// generate_move_if_legal() takes a position and a (not necessarily
 601 /// pseudo-legal) move and a pinned pieces bitboard as input, and tests
 602 /// whether the move is legal.  If the move is legal, the move itself is
 603 /// returned.  If not, the function returns MOVE_NONE.  This function must
 604 /// only be used when the side to move is not in check.
 605
 606 Move generate_move_if_legal(const Position &pos, Move m, Bitboard pinned) {
 607
 608   assert(pos.is_ok());
 609   assert(!pos.is_check());
 610   assert(move_is_ok(m));
 611
 612   Color us = pos.side_to_move();
 613   Color them = opposite_color(us);
 614   Square from = move_from(m);
 615   Piece pc = pos.piece_on(from);
 616
 617   // If the from square is not occupied by a piece belonging to the side to
 618   // move, the move is obviously not legal.
 619   if (color_of_piece(pc) != us)
 620       return MOVE_NONE;
 621
 622   Square to = move_to(m);
 623
 624   // En passant moves
 625   if (move_is_ep(m))
 626   {
 627       // The piece must be a pawn and destination square must be the
 628       // en passant square.
 629       if (   type_of_piece(pc) != PAWN
 630           || to != pos.ep_square())
 631           return MOVE_NONE;
 632
 633       assert(pos.square_is_empty(to));
 634       assert(pos.piece_on(to - pawn_push(us)) == pawn_of_color(them));
 635
 636       // The move is pseudo-legal.  If it is legal, return it.
 637       return (pos.move_is_legal(m) ? m : MOVE_NONE);
 638   }
 639
 640   // Castling moves
 641   if (move_is_short_castle(m))
 642   {
 643       // The piece must be a king and side to move must still have
 644       // the right to castle kingside.
 645       if (   type_of_piece(pc) != KING
 646           ||!pos.can_castle_kingside(us))
 647           return MOVE_NONE;
 648
 649       assert(from == pos.king_square(us));
 650       assert(to == pos.initial_kr_square(us));
 651       assert(pos.piece_on(to) == rook_of_color(us));
 652
 653       Square g1 = relative_square(us, SQ_G1);
 654       Square f1 = relative_square(us, SQ_F1);
 655       Square s;
 656       bool illegal = false;
 657
 658       // Check if any of the squares between king and rook
 659       // is occupied or under attack.
 660       for (s = Min(from, g1); s <= Max(from, g1); s++)
 661           if (  (s != from && s != to && !pos.square_is_empty(s))
 662               || pos.square_is_attacked(s, them))
 663               illegal = true;
 664
 665       // Check if any of the squares between king and rook
 666       // is occupied.
 667       for (s = Min(to, f1); s <= Max(to, f1); s++)
 668           if (s != from && s != to && !pos.square_is_empty(s))
 669               illegal = true;
 670
 671       return (!illegal ? m : MOVE_NONE);
 672   }
 673
 674   if (move_is_long_castle(m))
 675   {
 676       // The piece must be a king and side to move must still have
 677       // the right to castle kingside.
 678       if (   type_of_piece(pc) != KING
 679           ||!pos.can_castle_queenside(us))
 680           return MOVE_NONE;
 681
 682       assert(from == pos.king_square(us));
 683       assert(to == pos.initial_qr_square(us));
 684       assert(pos.piece_on(to) == rook_of_color(us));
 685
 686       Square c1 = relative_square(us, SQ_C1);
 687       Square d1 = relative_square(us, SQ_D1);
 688       Square s;
 689       bool illegal = false;
 690
 691       for (s = Min(from, c1); s <= Max(from, c1); s++)
 692           if(  (s != from && s != to && !pos.square_is_empty(s))
 693              || pos.square_is_attacked(s, them))
 694               illegal = true;
 695
 696       for (s = Min(to, d1); s <= Max(to, d1); s++)
 697           if(s != from && s != to && !pos.square_is_empty(s))
 698               illegal = true;
 699
 700       if (   square_file(to) == FILE_B
 701           && (   pos.piece_on(to + DELTA_W) == rook_of_color(them)
 702               || pos.piece_on(to + DELTA_W) == queen_of_color(them)))
 703           illegal = true;
 704
 705       return (!illegal ? m : MOVE_NONE);
 706   }
 707
 708   // Normal moves
 709
 710   // The destination square cannot be occupied by a friendly piece
 711   if (pos.color_of_piece_on(to) == us)
 712       return MOVE_NONE;
 713
 714   // Proceed according to the type of the moving piece.
 715   switch(type_of_piece(pc)) {
 716
 717   case PAWN:
 718       // Pawn moves, as usual, are somewhat messy.
 719       if (us == WHITE)
 720       {
 721           // If the destination square is on the 8th rank, the move must
 722           //  be a promotion.
 723           if (square_rank(to) == RANK_8 && !move_promotion(m))
 724               return MOVE_NONE;
 725
 726           // Proceed according to the square delta between the source and
 727           // destionation squares.
 728           switch (to - from)
 729           {
 730           case DELTA_NW:
 731           case DELTA_NE:
 732           // Capture. The destination square must be occupied by an enemy
 733           // piece (en passant captures was handled earlier).
 734               if (pos.color_of_piece_on(to) != them)
 735                   return MOVE_NONE;
 736               break;
 737
 738           case DELTA_N:
 739           // Pawn push. The destination square must be empty.
 740               if (!pos.square_is_empty(to))
 741                   return MOVE_NONE;
 742               break;
 743
 744           case DELTA_NN:
 745           // Double pawn push.  The destination square must be on the fourth
 746           // rank, and both the destination square and the square between the
 747           // source and destination squares must be empty.
 748           if (   square_rank(to) != RANK_4
 749               || !pos.square_is_empty(to)
 750               || !pos.square_is_empty(from + DELTA_N))
 751               return MOVE_NONE;
 752               break;
 753
 754           default:
 755               return MOVE_NONE;
 756         }
 757       }
 758       else // (us == BLACK)
 759       {
 760           // If the destination square is on the 1th rank, the move must
 761           //  be a promotion.
 762           if (square_rank(to) == RANK_1 && !move_promotion(m))
 763               return MOVE_NONE;
 764
 765           // Proceed according to the square delta between the source and
 766           // destionation squares.
 767           switch (to - from)
 768           {
 769           case DELTA_SW:
 770           case DELTA_SE:
 771           // Capture. The destination square must be occupied by an enemy
 772           // piece (en passant captures was handled earlier).
 773               if (pos.color_of_piece_on(to) != them)
 774                   return MOVE_NONE;
 775               break;
 776
 777           case DELTA_S:
 778           // Pawn push. The destination square must be empty.
 779               if (!pos.square_is_empty(to))
 780                   return MOVE_NONE;
 781               break;
 782
 783           case DELTA_SS:
 784           // Double pawn push.  The destination square must be on the fifth
 785           // rank, and both the destination square and the square between the
 786           // source and destination squares must be empty.
 787               if (   square_rank(to) != RANK_5
 788                   || !pos.square_is_empty(to)
 789                   || !pos.square_is_empty(from + DELTA_S))
 790                   return MOVE_NONE;
 791               break;
 792
 793           default:
 794               return MOVE_NONE;
 795           }
 796       }
 797       // The move is pseudo-legal.  Return it if it is legal.
 798       return (pos.move_is_legal(m) ? m : MOVE_NONE);
 799       break;
 800
 801       case KNIGHT:
 802           return (   pos.knight_attacks_square(from, to)
 803                   && pos.move_is_legal(m)
 804                   && !move_promotion(m) ? m : MOVE_NONE);
 805           break;
 806
 807       case BISHOP:
 808           return (   pos.bishop_attacks_square(from, to)
 809                   && pos.move_is_legal(m)
 810                   && !move_promotion(m) ? m : MOVE_NONE);
 811           break;
 812
 813       case ROOK:
 814           return (   pos.rook_attacks_square(from, to)
 815                   && pos.move_is_legal(m)
 816                   && !move_promotion(m) ? m : MOVE_NONE);
 817           break;
 818
 819       case QUEEN:
 820           return (   pos.queen_attacks_square(from, to)
 821                   && pos.move_is_legal(m)
 822                   && !move_promotion(m) ? m : MOVE_NONE);
 823           break;
 824
 825       case KING:
 826           return (   pos.king_attacks_square(from, to)
 827                   && pos.move_is_legal(m)
 828                   && !move_promotion(m) ? m : MOVE_NONE);
 829           break;
 830
 831       default:
 832           assert(false);
 833     }
 834     assert(false);
 835     return MOVE_NONE;
 836 }
 837
 838
 839 namespace {
 840
 841   int generate_white_pawn_captures(const Position &pos, MoveStack *mlist) {
 842     Bitboard pawns = pos.pawns(WHITE);
 843     Bitboard enemyPieces = pos.pieces_of_color(BLACK);
 844     Bitboard b1, b2;
 845     Square sq;
 846     int n = 0;
 847
 848     // Captures in the a1-h8 direction:
 849     b1 = (pawns << 9) & ~FileABB & enemyPieces;
 850
 851     // Promotions:
 852     b2 = b1 & Rank8BB;
 853     while(b2) {
 854       sq = pop_1st_bit(&b2);
 855       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, QUEEN);
 856     }
 857
 858     // Non-promotions:
 859     b2 = b1 & ~Rank8BB;
 860     while(b2) {
 861       sq = pop_1st_bit(&b2);
 862       mlist[n++].move = make_move(sq - DELTA_NE, sq);
 863     }
 864
 865     // Captures in the h1-a8 direction:
 866     b1 = (pawns << 7) & ~FileHBB & enemyPieces;
 867
 868     // Promotions:
 869     b2 = b1 & Rank8BB;
 870     while(b2) {
 871       sq = pop_1st_bit(&b2);
 872       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, QUEEN);
 873     }
 874
 875     // Non-promotions:
 876     b2 = b1 & ~Rank8BB;
 877     while(b2) {
 878       sq = pop_1st_bit(&b2);
 879       mlist[n++].move = make_move(sq - DELTA_NW, sq);
 880     }
 881
 882     // Non-capturing promotions:
 883     b1 = (pawns << 8) & pos.empty_squares() & Rank8BB;
 884     while(b1)  {
 885       sq = pop_1st_bit(&b1);
 886       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, QUEEN);
 887     }
 888
 889     // En passant captures:
 890     if(pos.ep_square() != SQ_NONE) {
 891       assert(square_rank(pos.ep_square()) == RANK_6);
 892       b1 = pawns & pos.black_pawn_attacks(pos.ep_square());
 893       assert(b1 != EmptyBoardBB);
 894       while(b1) {
 895         sq = pop_1st_bit(&b1);
 896         mlist[n++].move = make_ep_move(sq, pos.ep_square());
 897       }
 898     }
 899
 900     return n;
 901   }
 902
 903
 904   int generate_black_pawn_captures(const Position &pos, MoveStack *mlist) {
 905     Bitboard pawns = pos.pawns(BLACK);
 906     Bitboard enemyPieces = pos.pieces_of_color(WHITE);
 907     Bitboard b1, b2;
 908     Square sq;
 909     int n = 0;
 910
 911     // Captures in the a8-h1 direction:
 912     b1 = (pawns >> 7) & ~FileABB & enemyPieces;
 913
 914     // Promotions:
 915     b2 = b1 & Rank1BB;
 916     while(b2) {
 917       sq = pop_1st_bit(&b2);
 918       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, QUEEN);
 919     }
 920
 921     // Non-promotions:
 922     b2 = b1 & ~Rank1BB;
 923     while(b2) {
 924       sq = pop_1st_bit(&b2);
 925       mlist[n++].move = make_move(sq - DELTA_SE, sq);
 926     }
 927
 928     // Captures in the h8-a1 direction:
 929     b1 = (pawns >> 9) & ~FileHBB & enemyPieces;
 930
 931     // Promotions:
 932     b2 = b1 & Rank1BB;
 933     while(b2) {
 934       sq = pop_1st_bit(&b2);
 935       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, QUEEN);
 936     }
 937
 938     // Non-promotions:
 939     b2 = b1 & ~Rank1BB;
 940     while(b2) {
 941       sq = pop_1st_bit(&b2);
 942       mlist[n++].move = make_move(sq - DELTA_SW, sq);
 943     }
 944
 945     // Non-capturing promotions:
 946     b1 = (pawns >> 8) & pos.empty_squares() & Rank1BB;
 947     while(b1)  {
 948       sq = pop_1st_bit(&b1);
 949       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, QUEEN);
 950     }
 951
 952     // En passant captures:
 953     if(pos.ep_square() != SQ_NONE) {
 954       assert(square_rank(pos.ep_square()) == RANK_3);
 955       b1 = pawns & pos.white_pawn_attacks(pos.ep_square());
 956       assert(b1 != EmptyBoardBB);
 957       while(b1) {
 958         sq = pop_1st_bit(&b1);
 959         mlist[n++].move = make_ep_move(sq, pos.ep_square());
 960       }
 961     }
 962
 963     return n;
 964   }
 965
 966
 967   int generate_white_pawn_noncaptures(const Position &pos, MoveStack *mlist) {
 968     Bitboard pawns = pos.pawns(WHITE);
 969     Bitboard enemyPieces = pos.pieces_of_color(BLACK);
 970     Bitboard emptySquares = pos.empty_squares();
 971     Bitboard b1, b2;
 972     Square sq;
 973     int n = 0;
 974
 975     // Underpromotion captures in the a1-h8 direction:
 976     b1 = (pawns << 9) & ~FileABB & enemyPieces & Rank8BB;
 977     while(b1) {
 978       sq = pop_1st_bit(&b1);
 979       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, ROOK);
 980       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, BISHOP);
 981       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, KNIGHT);
 982     }
 983
 984     // Underpromotion captures in the h1-a8 direction:
 985     b1 = (pawns << 7) & ~FileHBB & enemyPieces & Rank8BB;
 986     while(b1) {
 987       sq = pop_1st_bit(&b1);
 988       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, ROOK);
 989       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, BISHOP);
 990       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, KNIGHT);
 991     }
 992
 993     // Single pawn pushes:
 994     b1 = (pawns << 8) & emptySquares;
 995     b2 = b1 & Rank8BB;
 996     while(b2) {
 997       sq = pop_1st_bit(&b2);
 998       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, ROOK);
 999       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, BISHOP);
1000       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, KNIGHT);
1001     }
1002     b2 = b1 & ~Rank8BB;
1003     while(b2) {
1004       sq = pop_1st_bit(&b2);
1005       mlist[n++].move = make_move(sq - DELTA_N, sq);
1006     }
1007
1008     // Double pawn pushes:
1009     b2 = ((b1 & Rank3BB) << 8) & emptySquares;
1010     while(b2) {
1011       sq = pop_1st_bit(&b2);
1012       mlist[n++].move = make_move(sq - DELTA_N - DELTA_N, sq);
1013     }
1014
1015     return n;
1016   }
1017
1018
1019   int generate_black_pawn_noncaptures(const Position &pos, MoveStack *mlist) {
1020     Bitboard pawns = pos.pawns(BLACK);
1021     Bitboard enemyPieces = pos.pieces_of_color(WHITE);
1022     Bitboard emptySquares = pos.empty_squares();
1023     Bitboard b1, b2;
1024     Square sq;
1025     int n = 0;
1026
1027     // Underpromotion captures in the a8-h1 direction:
1028     b1 = (pawns >> 7) & ~FileABB & enemyPieces & Rank1BB;
1029     while(b1) {
1030       sq = pop_1st_bit(&b1);
1031       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, ROOK);
1032       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, BISHOP);
1033       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, KNIGHT);
1034     }
1035
1036     // Underpromotion captures in the h8-a1 direction:
1037     b1 = (pawns >> 9) & ~FileHBB & enemyPieces & Rank1BB;
1038     while(b1) {
1039       sq = pop_1st_bit(&b1);
1040       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, ROOK);
1041       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, BISHOP);
1042       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, KNIGHT);
1043     }
1044
1045     // Single pawn pushes:
1046     b1 = (pawns >> 8) & emptySquares;
1047     b2 = b1 & Rank1BB;
1048     while(b2) {
1049       sq = pop_1st_bit(&b2);
1050       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, ROOK);
1051       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, BISHOP);
1052       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, KNIGHT);
1053     }
1054     b2 = b1 & ~Rank1BB;
1055     while(b2) {
1056       sq = pop_1st_bit(&b2);
1057       mlist[n++].move = make_move(sq - DELTA_S, sq);
1058     }
1059
1060     // Double pawn pushes:
1061     b2 = ((b1 & Rank6BB) >> 8) & emptySquares;
1062     while(b2) {
1063       sq = pop_1st_bit(&b2);
1064       mlist[n++].move = make_move(sq - DELTA_S - DELTA_S, sq);
1065     }
1066
1067     return n;
1068   }
1069
1070
1071   int generate_knight_moves(const Position &pos, MoveStack *mlist,
1072                             Color side, Bitboard target) {
1073     Square from, to;
1074     Bitboard b;
1075     int i, n = 0;
1076
1077     for(i = 0; i < pos.knight_count(side); i++) {
1078       from = pos.knight_list(side, i);
1079       b = pos.knight_attacks(from) & target;
1080       while(b) {
1081         to = pop_1st_bit(&b);
1082         mlist[n++].move = make_move(from, to);
1083       }
1084     }
1085     return n;
1086   }
1087
1088
1089   int generate_bishop_moves(const Position &pos, MoveStack *mlist,
1090                             Color side, Bitboard target) {
1091     Square from, to;
1092     Bitboard b;
1093     int i, n = 0;
1094
1095     for(i = 0; i < pos.bishop_count(side); i++) {
1096       from = pos.bishop_list(side, i);
1097       b = pos.bishop_attacks(from) & target;
1098       while(b) {
1099         to = pop_1st_bit(&b);
1100         mlist[n++].move = make_move(from, to);
1101       }
1102     }
1103     return n;
1104   }
1105
1106
1107   int generate_rook_moves(const Position &pos, MoveStack *mlist,
1108                           Color side, Bitboard target) {
1109     Square from, to;
1110     Bitboard b;
1111     int i, n = 0;
1112
1113     for(i = 0; i < pos.rook_count(side); i++) {
1114       from = pos.rook_list(side, i);
1115       b = pos.rook_attacks(from) & target;
1116       while(b) {
1117         to = pop_1st_bit(&b);
1118         mlist[n++].move = make_move(from, to);
1119       }
1120     }
1121     return n;
1122   }
1123
1124
1125   int generate_queen_moves(const Position &pos, MoveStack *mlist,
1126                            Color side, Bitboard target) {
1127     Square from, to;
1128     Bitboard b;
1129     int i, n = 0;
1130
1131     for(i = 0; i < pos.queen_count(side); i++) {
1132       from = pos.queen_list(side, i);
1133       b = pos.queen_attacks(from) & target;
1134       while(b) {
1135         to = pop_1st_bit(&b);
1136         mlist[n++].move = make_move(from, to);
1137       }
1138     }
1139     return n;
1140   }
1141
1142
1143   int generate_king_moves(const Position &pos, MoveStack *mlist,
1144                           Square from, Bitboard target) {
1145     Square to;
1146     Bitboard b;
1147     int n = 0;
1148
1149     b = pos.king_attacks(from) & target;
1150     while(b) {
1151       to = pop_1st_bit(&b);
1152       mlist[n++].move = make_move(from, to);
1153     }
1154     return n;
1155   }
1156
1157
1158   int generate_castle_moves(const Position &pos, MoveStack *mlist, Color us) {
1159     int n = 0;
1160
1161     if(pos.can_castle(us)) {
1162       Color them = opposite_color(us);
1163       Square ksq = pos.king_square(us);
1164       assert(pos.piece_on(ksq) == king_of_color(us));
1165
1166       if(pos.can_castle_kingside(us)) {
1167         Square rsq = pos.initial_kr_square(us);
1168         Square g1 = relative_square(us, SQ_G1);
1169         Square f1 = relative_square(us, SQ_F1);
1170         Square s;
1171         bool illegal = false;
1172
1173         assert(pos.piece_on(rsq) == rook_of_color(us));
1174
1175         for(s = Min(ksq, g1); s <= Max(ksq, g1); s++)
1176           if((s != ksq && s != rsq && pos.square_is_occupied(s))
1177              || pos.square_is_attacked(s, them))
1178             illegal = true;
1179         for(s = Min(rsq, f1); s <= Max(rsq, f1); s++)
1180           if(s != ksq && s != rsq && pos.square_is_occupied(s))
1181             illegal = true;
1182
1183         if(!illegal)
1184           mlist[n++].move = make_castle_move(ksq, rsq);
1185       }
1186
1187       if(pos.can_castle_queenside(us)) {
1188         Square rsq = pos.initial_qr_square(us);
1189         Square c1 = relative_square(us, SQ_C1);
1190         Square d1 = relative_square(us, SQ_D1);
1191         Square s;
1192         bool illegal = false;
1193
1194         assert(pos.piece_on(rsq) == rook_of_color(us));
1195
1196         for(s = Min(ksq, c1); s <= Max(ksq, c1); s++)
1197           if((s != ksq && s != rsq && pos.square_is_occupied(s))
1198              || pos.square_is_attacked(s, them))
1199             illegal = true;
1200         for(s = Min(rsq, d1); s <= Max(rsq, d1); s++)
1201           if(s != ksq && s != rsq && pos.square_is_occupied(s))
1202             illegal = true;
1203         if(square_file(rsq) == FILE_B &&
1204            (pos.piece_on(relative_square(us, SQ_A1)) == rook_of_color(them) ||
1205             pos.piece_on(relative_square(us, SQ_A1)) == queen_of_color(them)))
1206            illegal = true;
1207
1208         if(!illegal)
1209           mlist[n++].move = make_castle_move(ksq, rsq);
1210       }
1211     }
1212
1213     return n;
1214   }
1215
1216 }