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