Initial import of Glaurung 2.1
[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 &pos, MoveStack *mlist);
36   int generate_black_pawn_captures(const Position &pos, MoveStack *mlist);
37   int generate_white_pawn_noncaptures(const Position &pos, MoveStack *mlist);
38   int generate_black_pawn_noncaptures(const Position &pos, MoveStack *mlist);
39   int generate_knight_moves(const Position &pos, MoveStack *mlist, 
40                             Color side, Bitboard target);
41   int generate_bishop_moves(const Position &pos, MoveStack *mlist, 
42                             Color side, Bitboard target);
43   int generate_rook_moves(const Position &pos, MoveStack *mlist, 
44                           Color side, Bitboard target);
45   int generate_queen_moves(const Position &pos, MoveStack *mlist, 
46                            Color side, Bitboard target);
47   int generate_king_moves(const Position &pos, MoveStack *mlist, 
48                           Square from, Bitboard target);
49   int generate_castle_moves(const Position &pos, MoveStack *mlist, Color us);
50
51 }
52
53
54 ////
55 //// Functions
56 ////
57
58
59 /// generate_captures generates() all pseudo-legal captures and queen
60 /// promotions.  The return value is the number of moves generated.
61
62 int generate_captures(const Position &pos, MoveStack *mlist) {
63   Color us = pos.side_to_move();
64   Bitboard target = pos.pieces_of_color(opposite_color(us));
65   int n = 0;
66
67   assert(pos.is_ok());
68   assert(!pos.is_check());
69
70   if(us == WHITE)
71     n += generate_white_pawn_captures(pos, mlist);
72   else
73     n += generate_black_pawn_captures(pos, mlist);
74   n += generate_knight_moves(pos, mlist+n, us, target);
75   n += generate_bishop_moves(pos, mlist+n, us, target);
76   n += generate_rook_moves(pos, mlist+n, us, target);
77   n += generate_queen_moves(pos, mlist+n, us, target);
78   n += generate_king_moves(pos, mlist+n, pos.king_square(us), target);
79
80   return n;
81 }
82
83
84 /// generate_noncaptures() generates all pseudo-legal non-captures and 
85 /// underpromotions.  The return value is the number of moves generated.
86
87 int generate_noncaptures(const Position &pos, MoveStack *mlist) {
88   Color us = pos.side_to_move();
89   Bitboard target = pos.empty_squares();
90   int n = 0;
91
92   assert(pos.is_ok());
93   assert(!pos.is_check());
94
95   if(us == WHITE)
96     n += generate_white_pawn_noncaptures(pos, mlist);
97   else
98     n += generate_black_pawn_noncaptures(pos, mlist);
99   n += generate_knight_moves(pos, mlist+n, us, target);
100   n += generate_bishop_moves(pos, mlist+n, us, target);
101   n += generate_rook_moves(pos, mlist+n, us, target);
102   n += generate_queen_moves(pos, mlist+n, us, target);
103   n += generate_king_moves(pos, mlist+n, pos.king_square(us), target);
104   n += generate_castle_moves(pos, mlist+n, us);
105
106   return n;
107 }
108
109
110 /// generate_checks() generates all pseudo-legal non-capturing, non-promoting
111 /// checks, except castling moves (will add this later).  It returns the
112 /// number of generated moves.  
113
114 int generate_checks(const Position &pos, MoveStack *mlist, Bitboard dc) {
115   Color us, them;
116   Square ksq, from, to;
117   Bitboard empty, checkSqs, b1, b2, b3;
118   int n = 0;
119
120   assert(pos.is_ok());
121   assert(!pos.is_check());
122
123   us = pos.side_to_move();
124   them = opposite_color(us);
125
126   ksq = pos.king_square(them);
127   assert(pos.piece_on(ksq) == king_of_color(them));
128
129   dc = pos.discovered_check_candidates(us);
130   empty = pos.empty_squares();
131   
132   // Pawn moves.  This is somewhat messy, and we use separate code for white
133   // and black, because we can't shift by negative numbers in C/C++.  :-(
134
135   if(us == WHITE) {
136     // Pawn moves which give discovered check.  This is possible only if the 
137     // pawn is not on the same file as the enemy king, because we don't 
138     // generate captures.
139
140     // Find all friendly pawns not on the enemy king's file:
141     b1 = pos.pawns(us) & ~file_bb(ksq);
142
143     // Discovered checks, single pawn pushes:
144     b2 = b3 = ((b1 & dc) << 8) & ~Rank8BB & empty;
145     while(b3) {
146       to = pop_1st_bit(&b3);
147       mlist[n++].move = make_move(to - DELTA_N, to);
148     }
149
150     // Discovered checks, double pawn pushes:
151     b3 = ((b2 & Rank3BB) << 8) & empty;
152     while(b3) {
153       to = pop_1st_bit(&b3);
154       mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to);
155     }
156
157     // Direct checks.  These are possible only for pawns on neighboring files
158     // of the enemy king:
159
160     b1 &= (~dc & neighboring_files_bb(ksq));
161
162     // Direct checks, single pawn pushes:
163     b2 = (b1 << 8) & empty;
164     b3 = b2 & pos.black_pawn_attacks(ksq);
165     while(b3) {
166       to = pop_1st_bit(&b3);
167       mlist[n++].move = make_move(to - DELTA_N, to);
168     }
169
170     // Direct checks, double pawn pushes:
171     b3 = ((b2 & Rank3BB) << 8) & empty & pos.black_pawn_attacks(ksq);
172     while(b3) {
173       to = pop_1st_bit(&b3);
174       mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to);
175     }
176   }
177   else { // (us == BLACK)
178
179     // Pawn moves which give discovered check.  This is possible only if the 
180     // pawn is not on the same file as the enemy king, because we don't 
181     // generate captures.
182
183     // Find all friendly pawns not on the enemy king's file:
184     b1 = pos.pawns(us) & ~file_bb(ksq);
185
186     // Discovered checks, single pawn pushes:
187     b2 = b3 = ((b1 & dc) >> 8) & ~Rank1BB & empty;
188     while(b3) {
189       to = pop_1st_bit(&b3);
190       mlist[n++].move = make_move(to - DELTA_S, to);
191     }
192
193     // Discovered checks, double pawn pushes:
194     b3 = ((b2 & Rank6BB) >> 8) & empty;
195     while(b3) {
196       to = pop_1st_bit(&b3);
197       mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to);
198     }
199
200     // Direct checks.  These are possible only for pawns on neighboring files
201     // of the enemy king:
202
203     b1 &= (~dc & neighboring_files_bb(ksq));
204
205     // Direct checks, single pawn pushes:
206     b2 = (b1 >> 8) & empty;
207     b3 = b2 & pos.white_pawn_attacks(ksq);
208     while(b3) {
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.black_pawn_attacks(ksq);
215     while(b3) {
216       to = pop_1st_bit(&b3);
217       mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to);
218     }
219   }
220
221   // Knight moves
222   b1 = pos.knights(us);
223   if(b1) {
224     // Discovered knight checks:
225     b2 = b1 & dc;
226     while(b2) {
227       from = pop_1st_bit(&b2);
228       b3 = pos.knight_attacks(from) & empty;
229       while(b3) {
230         to = pop_1st_bit(&b3);
231         mlist[n++].move = make_move(from, to);
232       }
233     }
234     
235     // Direct knight checks:
236     b2 = b1 & ~dc;
237     checkSqs = pos.knight_attacks(ksq) & empty;
238     while(b2) {
239       from = pop_1st_bit(&b2);
240       b3 = pos.knight_attacks(from) & checkSqs;
241       while(b3) {
242         to = pop_1st_bit(&b3);
243         mlist[n++].move = make_move(from, to);
244       }
245     }
246   }
247
248   // Bishop moves
249   b1 = pos.bishops(us);
250   if(b1) {
251     // Discovered bishop checks:
252     b2 = b1 & dc;
253     while(b2) {
254       from = pop_1st_bit(&b2);
255       b3 = pos.bishop_attacks(from) & empty;
256       while(b3) {
257         to = pop_1st_bit(&b3);
258         mlist[n++].move = make_move(from, to);
259       }
260     }
261     
262     // Direct bishop checks:
263     b2 = b1 & ~dc;
264     checkSqs = pos.bishop_attacks(ksq) & empty;
265     while(b2) {
266       from = pop_1st_bit(&b2);
267       b3 = pos.bishop_attacks(from) & checkSqs;
268       while(b3) {
269         to = pop_1st_bit(&b3);
270         mlist[n++].move = make_move(from, to);
271       }
272     }
273   }
274
275   // Rook moves
276   b1 = pos.rooks(us);
277   if(b1) {
278     // Discovered rook checks:
279     b2 = b1 & dc;
280     while(b2) {
281       from = pop_1st_bit(&b2);
282       b3 = pos.rook_attacks(from) & empty;
283       while(b3) {
284         to = pop_1st_bit(&b3);
285         mlist[n++].move = make_move(from, to);
286       }
287     }
288     
289     // Direct rook checks:
290     b2 = b1 & ~dc;
291     checkSqs = pos.rook_attacks(ksq) & empty;
292     while(b2) {
293       from = pop_1st_bit(&b2);
294       b3 = pos.rook_attacks(from) & checkSqs;
295       while(b3) {
296         to = pop_1st_bit(&b3);
297         mlist[n++].move = make_move(from, to);
298       }
299     }
300   }
301
302   // Queen moves
303   b1 = pos.queens(us);
304   if(b1) {
305     // Discovered queen checks are impossible!
306
307     // Direct queen checks:
308     checkSqs = pos.queen_attacks(ksq) & empty;
309     while(b1) {
310       from = pop_1st_bit(&b1);
311       b2 = pos.queen_attacks(from) & checkSqs;
312       while(b2) {
313         to = pop_1st_bit(&b2);
314         mlist[n++].move = make_move(from, to);
315       }
316     }
317   }
318
319   // King moves
320   from = pos.king_square(us);
321   if(bit_is_set(dc, from)) {
322     b1 = pos.king_attacks(from) & empty & ~QueenPseudoAttacks[ksq];
323     while(b1) {
324       to = pop_1st_bit(&b1);
325       mlist[n++].move = make_move(from, to);
326     }
327   }
328
329   // TODO: Castling moves!
330   
331   return n;
332 }
333
334
335 /// generate_evasions() generates all check evasions when the side to move is
336 /// in check.  Unlike the other move generation functions, this one generates
337 /// only legal moves.  It returns the number of generated moves.  This
338 /// function is very ugly, and needs cleaning up some time later.  FIXME
339
340 int generate_evasions(const Position &pos, MoveStack *mlist) {
341   Color us, them;
342   Bitboard checkers = pos.checkers();
343   Bitboard pinned, b1, b2;
344   Square ksq, from, to;
345   int n = 0;
346
347   assert(pos.is_ok());
348   assert(pos.is_check());
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(pawn_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   assert(pos.is_ok());
580
581   if(pos.is_check())
582     return generate_evasions(pos, mlist);
583   else {
584     int i, n;
585     Bitboard pinned = pos.pinned_pieces(pos.side_to_move());
586
587     // Generate pseudo-legal moves:
588     n = generate_captures(pos, mlist);
589     n += generate_noncaptures(pos, mlist + n);
590
591     // Remove illegal moves from the list:
592     for(i = 0; i < n; i++) {
593       if(!pos.move_is_legal(mlist[i].move, pinned))
594         mlist[i--].move = mlist[--n].move;
595     }
596
597     return n;
598   }
599 }
600
601
602 /// generate_move_if_legal() takes a position and a (not necessarily
603 /// pseudo-legal) move and a pinned pieces bitboard as input, and tests
604 /// whether the move is legal.  If the move is legal, the move itself is
605 /// returned.  If not, the function returns MOVE_NONE.  This function must
606 /// only be used when the side to move is not in check.
607
608 Move generate_move_if_legal(const Position &pos, Move m, Bitboard pinned) {
609   Color us, them;
610   Square from, to;
611   Piece pc;
612
613   assert(pos.is_ok());
614   assert(!pos.is_check());
615   assert(move_is_ok(m));
616
617   us = pos.side_to_move();
618   them = opposite_color(us);
619   from = move_from(m);
620   pc = pos.piece_on(from);
621
622   // If the from square is not occupied by a piece belonging to the side to
623   // move, the move is obviously not legal.
624   if(color_of_piece(pc) != us )
625     return MOVE_NONE;
626
627   to = move_to(m);
628
629   // En passant moves:
630   if(move_is_ep(m)) {
631
632     // The piece must be a pawn:
633     if(type_of_piece(pc) != PAWN)
634       return MOVE_NONE;
635
636     // The destination square must be the en passant square:
637     if(to != pos.ep_square())
638       return MOVE_NONE;
639
640     assert(pos.square_is_empty(to));
641     assert(pos.piece_on(to - pawn_push(us)) == pawn_of_color(them));
642
643     // The move is pseudo-legal.  If it is legal, return it.
644     if(pos.move_is_legal(m))
645       return m;
646     else
647       return MOVE_NONE;
648   }
649
650   // Castling moves:
651   else if(move_is_short_castle(m)) {
652
653     // The piece must be a king:
654     if(type_of_piece(pc) != KING)
655       return MOVE_NONE;
656
657     // The side to move must still have the right to castle kingside:
658     if(!pos.can_castle_kingside(us))
659       return MOVE_NONE;
660
661     assert(from == pos.king_square(us));
662     assert(to == pos.initial_kr_square(us));
663     assert(pos.piece_on(to) == rook_of_color(us));
664
665     Square g1 = relative_square(us, SQ_G1);
666     Square f1 = relative_square(us, SQ_F1);
667     Square s;
668     bool illegal = false;
669
670     for(s = Min(from, g1); s <= Max(from, g1); s++)
671       if((s != from && s != to && !pos.square_is_empty(s)) ||
672          pos.square_is_attacked(s, them))
673         illegal = true;
674     for(s = Min(to, f1); s <= Max(to, f1); s++)
675       if(s != from && s != to && !pos.square_is_empty(s))
676         illegal = true;
677
678     if(!illegal)
679       return m;
680     else
681       return MOVE_NONE;
682   }
683   else if(move_is_long_castle(m)) {
684
685     // The piece must be a king:
686     if(type_of_piece(pc) != KING)
687       return MOVE_NONE;
688
689     // The side to move must still have the right to castle kingside:
690     if(!pos.can_castle_queenside(us))
691       return MOVE_NONE;
692
693     assert(from == pos.king_square(us));
694     assert(to == pos.initial_qr_square(us));
695     assert(pos.piece_on(to) == rook_of_color(us));
696
697     Square c1 = relative_square(us, SQ_C1);
698     Square d1 = relative_square(us, SQ_D1);
699     Square s;
700     bool illegal = false;
701
702     for(s = Min(from, c1); s <= Max(from, c1); s++)
703       if((s != from && s != to && !pos.square_is_empty(s)) ||
704          pos.square_is_attacked(s, them))
705         illegal = true;
706     for(s = Min(to, d1); s <= Max(to, d1); s++)
707       if(s != from && s != to && !pos.square_is_empty(s))
708         illegal = true;
709     if(square_file(to) == FILE_B &&
710        (pos.piece_on(to + DELTA_W) == rook_of_color(them) ||
711         pos.piece_on(to + DELTA_W) == queen_of_color(them)))
712       illegal = true;
713
714     if(!illegal)
715       return m;
716     else
717       return MOVE_NONE;
718   }
719
720   // Normal moves
721   else {
722
723     // The destination square cannot be occupied by a friendly piece:
724     if(pos.color_of_piece_on(to) == us)
725       return MOVE_NONE;
726
727     // Proceed according to the type of the moving piece.
728     switch(type_of_piece(pc)) {
729
730     case PAWN:
731       // Pawn moves, as usual, are somewhat messy.  
732       if(us == WHITE) {
733         // If the destination square is on the 8th rank, the move must be a
734         // promotion.
735         if(square_rank(to) == RANK_8 && !move_promotion(m))
736           return MOVE_NONE;
737         
738         // Proceed according to the square delta between the source and
739         // destionation squares.
740         switch(to - from) {
741           
742         case DELTA_NW: case DELTA_NE:
743           // Capture.  The destination square must be occupied by an enemy piece
744           // (en passant captures was handled earlier).
745           if(pos.color_of_piece_on(to) != them)
746             return MOVE_NONE;
747           break;
748
749         case DELTA_N:
750           // Pawn push.  The destination square must be empty.
751           if(!pos.square_is_empty(to))
752             return MOVE_NONE;
753           break;
754
755         case DELTA_NN:
756           // Double pawn push.  The destination square must be on the fourth
757           // rank, and both the destination square and the square between the
758           // source and destination squares must be empty.
759           if(square_rank(to) != RANK_4 || !pos.square_is_empty(to) ||
760              !pos.square_is_empty(from + DELTA_N))
761             return MOVE_NONE;
762           break;
763           
764         default:
765           return MOVE_NONE;
766         }
767       }
768       else { // (us == BLACK)
769         // If the destination square is on the 1st rank, the move must be a
770         // promotion.
771         if(square_rank(to) == RANK_1 && !move_promotion(m))
772           return MOVE_NONE;
773         
774         // Proceed according to the square delta between the source and
775         // destionation squares.
776         switch(to - from) {
777           
778         case DELTA_SW: case DELTA_SE:
779           // Capture.  The destination square must be occupied by an enemy piece
780           // (en passant captures was handled earlier).
781           if(pos.color_of_piece_on(to) != them)
782             return MOVE_NONE;
783           break;
784           
785         case DELTA_S:
786           // Pawn push.  The destination square must be empty.
787           if(!pos.square_is_empty(to))
788             return MOVE_NONE;
789           break;
790           
791         case DELTA_SS:
792           // Double pawn push.  The destination square must be on the fifth
793           // rank, and both the destination square and the square between the
794           // source and destination squares must be empty.
795           if(square_rank(to) != RANK_5 || !pos.square_is_empty(to) ||
796              !pos.square_is_empty(from + DELTA_S))
797             return MOVE_NONE;
798           break;
799           
800         default:
801           return MOVE_NONE;
802         }
803       }
804       // The move is pseudo-legal.  Return it if it is legal.
805       if(pos.move_is_legal(m))
806         return m;
807       else
808         return MOVE_NONE;
809       break;
810
811     case KNIGHT:
812       if(pos.knight_attacks_square(from, to) && pos.move_is_legal(m) &&
813          !move_promotion(m))
814         return m;
815       else
816         return MOVE_NONE;
817       break;
818       
819     case BISHOP:
820       if(pos.bishop_attacks_square(from, to) && pos.move_is_legal(m) &&
821          !move_promotion(m))
822         return m;
823       else
824         return MOVE_NONE;
825       break;
826       
827     case ROOK:
828       if(pos.rook_attacks_square(from, to) && pos.move_is_legal(m) &&
829          !move_promotion(m))
830         return m;
831       else
832         return MOVE_NONE;
833       break;
834     
835     case QUEEN:
836       if(pos.queen_attacks_square(from, to) && pos.move_is_legal(m) &&
837          !move_promotion(m))
838         return m;
839       else
840         return MOVE_NONE;
841       break;
842
843     case KING:
844       if(pos.king_attacks_square(from, to) && pos.move_is_legal(m) &&
845          !move_promotion(m))
846         return m;
847       else
848         return MOVE_NONE;
849       break;
850
851     default:
852       assert(false);
853     }
854   }
855
856   assert(false);
857   return MOVE_NONE;
858 }
859
860
861 namespace {
862
863   int generate_white_pawn_captures(const Position &pos, MoveStack *mlist) {
864     Bitboard pawns = pos.pawns(WHITE);
865     Bitboard enemyPieces = pos.pieces_of_color(BLACK);
866     Bitboard b1, b2;
867     Square sq;
868     int n = 0;
869
870     // Captures in the a1-h8 direction:
871     b1 = (pawns << 9) & ~FileABB & enemyPieces;
872
873     // Promotions:
874     b2 = b1 & Rank8BB;
875     while(b2) {
876       sq = pop_1st_bit(&b2);
877       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, QUEEN);
878     }
879
880     // Non-promotions:
881     b2 = b1 & ~Rank8BB;
882     while(b2) {
883       sq = pop_1st_bit(&b2);
884       mlist[n++].move = make_move(sq - DELTA_NE, sq);
885     }
886
887     // Captures in the h1-a8 direction:
888     b1 = (pawns << 7) & ~FileHBB & enemyPieces;
889
890     // Promotions:
891     b2 = b1 & Rank8BB;
892     while(b2) {
893       sq = pop_1st_bit(&b2);
894       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, QUEEN);
895     }
896
897     // Non-promotions:
898     b2 = b1 & ~Rank8BB;
899     while(b2) {
900       sq = pop_1st_bit(&b2);
901       mlist[n++].move = make_move(sq - DELTA_NW, sq);
902     }
903
904     // Non-capturing promotions:
905     b1 = (pawns << 8) & pos.empty_squares() & Rank8BB;
906     while(b1)  {
907       sq = pop_1st_bit(&b1);
908       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, QUEEN);
909     }
910
911     // En passant captures:
912     if(pos.ep_square() != SQ_NONE) {
913       assert(square_rank(pos.ep_square()) == RANK_6);
914       b1 = pawns & pos.black_pawn_attacks(pos.ep_square());
915       assert(b1 != EmptyBoardBB);
916       while(b1) {
917         sq = pop_1st_bit(&b1);
918         mlist[n++].move = make_ep_move(sq, pos.ep_square());
919       }
920     }
921
922     return n;
923   }
924
925
926   int generate_black_pawn_captures(const Position &pos, MoveStack *mlist) {
927     Bitboard pawns = pos.pawns(BLACK);
928     Bitboard enemyPieces = pos.pieces_of_color(WHITE);
929     Bitboard b1, b2;
930     Square sq;
931     int n = 0;
932
933     // Captures in the a8-h1 direction:
934     b1 = (pawns >> 7) & ~FileABB & enemyPieces;
935
936     // Promotions:
937     b2 = b1 & Rank1BB;
938     while(b2) {
939       sq = pop_1st_bit(&b2);
940       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, QUEEN);
941     }
942
943     // Non-promotions:
944     b2 = b1 & ~Rank1BB;
945     while(b2) {
946       sq = pop_1st_bit(&b2);
947       mlist[n++].move = make_move(sq - DELTA_SE, sq);
948     }
949
950     // Captures in the h8-a1 direction:
951     b1 = (pawns >> 9) & ~FileHBB & enemyPieces;
952
953     // Promotions:
954     b2 = b1 & Rank1BB;
955     while(b2) {
956       sq = pop_1st_bit(&b2);
957       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, QUEEN);
958     }
959
960     // Non-promotions:
961     b2 = b1 & ~Rank1BB;
962     while(b2) {
963       sq = pop_1st_bit(&b2);
964       mlist[n++].move = make_move(sq - DELTA_SW, sq);
965     }
966
967     // Non-capturing promotions:
968     b1 = (pawns >> 8) & pos.empty_squares() & Rank1BB;
969     while(b1)  {
970       sq = pop_1st_bit(&b1);
971       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, QUEEN);
972     }
973
974     // En passant captures:
975     if(pos.ep_square() != SQ_NONE) {
976       assert(square_rank(pos.ep_square()) == RANK_3);
977       b1 = pawns & pos.white_pawn_attacks(pos.ep_square());
978       assert(b1 != EmptyBoardBB);
979       while(b1) {
980         sq = pop_1st_bit(&b1);
981         mlist[n++].move = make_ep_move(sq, pos.ep_square());
982       }
983     }
984
985     return n;
986   }
987     
988
989   int generate_white_pawn_noncaptures(const Position &pos, MoveStack *mlist) {
990     Bitboard pawns = pos.pawns(WHITE);
991     Bitboard enemyPieces = pos.pieces_of_color(BLACK);
992     Bitboard emptySquares = pos.empty_squares();
993     Bitboard b1, b2;
994     Square sq;
995     int n = 0;
996
997     // Underpromotion captures in the a1-h8 direction:
998     b1 = (pawns << 9) & ~FileABB & enemyPieces & Rank8BB;
999     while(b1) {
1000       sq = pop_1st_bit(&b1);
1001       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, ROOK);
1002       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, BISHOP);
1003       mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, KNIGHT);
1004     }
1005
1006     // Underpromotion captures in the h1-a8 direction:
1007     b1 = (pawns << 7) & ~FileHBB & enemyPieces & Rank8BB;
1008     while(b1) {
1009       sq = pop_1st_bit(&b1);
1010       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, ROOK);
1011       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, BISHOP);
1012       mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, KNIGHT);
1013     }
1014
1015     // Single pawn pushes:
1016     b1 = (pawns << 8) & emptySquares;
1017     b2 = b1 & Rank8BB;
1018     while(b2) {
1019       sq = pop_1st_bit(&b2);
1020       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, ROOK);
1021       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, BISHOP);
1022       mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, KNIGHT);
1023     }
1024     b2 = b1 & ~Rank8BB;
1025     while(b2) {
1026       sq = pop_1st_bit(&b2);
1027       mlist[n++].move = make_move(sq - DELTA_N, sq);
1028     }
1029
1030     // Double pawn pushes:
1031     b2 = ((b1 & Rank3BB) << 8) & emptySquares;
1032     while(b2) {
1033       sq = pop_1st_bit(&b2);
1034       mlist[n++].move = make_move(sq - DELTA_N - DELTA_N, sq);
1035     }
1036
1037     return n;
1038   }
1039
1040
1041   int generate_black_pawn_noncaptures(const Position &pos, MoveStack *mlist) {
1042     Bitboard pawns = pos.pawns(BLACK);
1043     Bitboard enemyPieces = pos.pieces_of_color(WHITE);
1044     Bitboard emptySquares = pos.empty_squares();
1045     Bitboard b1, b2;
1046     Square sq;
1047     int n = 0;
1048
1049     // Underpromotion captures in the a8-h1 direction:
1050     b1 = (pawns >> 7) & ~FileABB & enemyPieces & Rank1BB;
1051     while(b1) {
1052       sq = pop_1st_bit(&b1);
1053       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, ROOK);
1054       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, BISHOP);
1055       mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, KNIGHT);
1056     }
1057
1058     // Underpromotion captures in the h8-a1 direction:
1059     b1 = (pawns >> 9) & ~FileHBB & enemyPieces & Rank1BB;
1060     while(b1) {
1061       sq = pop_1st_bit(&b1);
1062       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, ROOK);
1063       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, BISHOP);
1064       mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, KNIGHT);
1065     }
1066
1067     // Single pawn pushes:
1068     b1 = (pawns >> 8) & emptySquares;
1069     b2 = b1 & Rank1BB;
1070     while(b2) {
1071       sq = pop_1st_bit(&b2);
1072       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, ROOK);
1073       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, BISHOP);
1074       mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, KNIGHT);
1075     }
1076     b2 = b1 & ~Rank1BB;
1077     while(b2) {
1078       sq = pop_1st_bit(&b2);
1079       mlist[n++].move = make_move(sq - DELTA_S, sq);
1080     }
1081     
1082     // Double pawn pushes:
1083     b2 = ((b1 & Rank6BB) >> 8) & emptySquares;
1084     while(b2) {
1085       sq = pop_1st_bit(&b2);
1086       mlist[n++].move = make_move(sq - DELTA_S - DELTA_S, sq);
1087     }
1088
1089     return n;
1090   }
1091
1092   
1093   int generate_knight_moves(const Position &pos, MoveStack *mlist, 
1094                             Color side, Bitboard target) {
1095     Square from, to;
1096     Bitboard b;
1097     int i, n = 0;
1098
1099     for(i = 0; i < pos.knight_count(side); i++) {
1100       from = pos.knight_list(side, i);
1101       b = pos.knight_attacks(from) & target;
1102       while(b) {
1103         to = pop_1st_bit(&b);
1104         mlist[n++].move = make_move(from, to);
1105       }
1106     }
1107     return n;
1108   }
1109
1110
1111   int generate_bishop_moves(const Position &pos, MoveStack *mlist, 
1112                             Color side, Bitboard target) {
1113     Square from, to;
1114     Bitboard b;
1115     int i, n = 0;
1116
1117     for(i = 0; i < pos.bishop_count(side); i++) {
1118       from = pos.bishop_list(side, i);
1119       b = pos.bishop_attacks(from) & target;
1120       while(b) {
1121         to = pop_1st_bit(&b);
1122         mlist[n++].move = make_move(from, to);
1123       }
1124     }
1125     return n;
1126   }
1127
1128
1129   int generate_rook_moves(const Position &pos, MoveStack *mlist, 
1130                           Color side, Bitboard target) {
1131     Square from, to;
1132     Bitboard b;
1133     int i, n = 0;
1134
1135     for(i = 0; i < pos.rook_count(side); i++) {
1136       from = pos.rook_list(side, i);
1137       b = pos.rook_attacks(from) & target;
1138       while(b) {
1139         to = pop_1st_bit(&b);
1140         mlist[n++].move = make_move(from, to);
1141       }
1142     }
1143     return n;
1144   }
1145
1146
1147   int generate_queen_moves(const Position &pos, MoveStack *mlist, 
1148                            Color side, Bitboard target) {
1149     Square from, to;
1150     Bitboard b;
1151     int i, n = 0;
1152
1153     for(i = 0; i < pos.queen_count(side); i++) {
1154       from = pos.queen_list(side, i);
1155       b = pos.queen_attacks(from) & target;
1156       while(b) {
1157         to = pop_1st_bit(&b);
1158         mlist[n++].move = make_move(from, to);
1159       }
1160     }
1161     return n;
1162   }
1163
1164
1165   int generate_king_moves(const Position &pos, MoveStack *mlist, 
1166                           Square from, Bitboard target) {
1167     Square to;
1168     Bitboard b;
1169     int n = 0;
1170     
1171     b = pos.king_attacks(from) & target;
1172     while(b) {
1173       to = pop_1st_bit(&b);
1174       mlist[n++].move = make_move(from, to);
1175     }
1176     return n;
1177   }
1178
1179
1180   int generate_castle_moves(const Position &pos, MoveStack *mlist, Color us) {
1181     int n = 0;
1182
1183     if(pos.can_castle(us)) {
1184       Color them = opposite_color(us);
1185       Square ksq = pos.king_square(us);
1186       assert(pos.piece_on(ksq) == king_of_color(us));
1187       
1188       if(pos.can_castle_kingside(us)) {
1189         Square rsq = pos.initial_kr_square(us);
1190         Square g1 = relative_square(us, SQ_G1);
1191         Square f1 = relative_square(us, SQ_F1);
1192         Square s;
1193         bool illegal = false;
1194
1195         assert(pos.piece_on(rsq) == rook_of_color(us));
1196
1197         for(s = Min(ksq, g1); s <= Max(ksq, g1); s++)
1198           if((s != ksq && s != rsq && pos.square_is_occupied(s))
1199              || pos.square_is_attacked(s, them))
1200             illegal = true;
1201         for(s = Min(rsq, f1); s <= Max(rsq, f1); s++)
1202           if(s != ksq && s != rsq && pos.square_is_occupied(s))
1203             illegal = true;
1204
1205         if(!illegal)
1206           mlist[n++].move = make_castle_move(ksq, rsq);
1207       }
1208
1209       if(pos.can_castle_queenside(us)) {
1210         Square rsq = pos.initial_qr_square(us);
1211         Square c1 = relative_square(us, SQ_C1);
1212         Square d1 = relative_square(us, SQ_D1);
1213         Square s;
1214         bool illegal = false;
1215
1216         assert(pos.piece_on(rsq) == rook_of_color(us));
1217
1218         for(s = Min(ksq, c1); s <= Max(ksq, c1); s++)
1219           if((s != ksq && s != rsq && pos.square_is_occupied(s))
1220              || pos.square_is_attacked(s, them))
1221             illegal = true;
1222         for(s = Min(rsq, d1); s <= Max(rsq, d1); s++)
1223           if(s != ksq && s != rsq && pos.square_is_occupied(s))
1224             illegal = true;
1225         if(square_file(rsq) == FILE_B &&
1226            (pos.piece_on(relative_square(us, SQ_A1)) == rook_of_color(them) ||
1227             pos.piece_on(relative_square(us, SQ_A1)) == queen_of_color(them)))
1228            illegal = true;
1229                          
1230         if(!illegal)
1231           mlist[n++].move = make_castle_move(ksq, rsq);
1232       }
1233     }
1234
1235     return n;
1236   }
1237     
1238 }