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