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