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