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