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