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