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