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