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