1 /* genmove.c
2
3 GNU Chess frontend
4
5 Copyright (C) 2001-2011 Free Software Foundation, Inc.
6
7 GNU Chess is based on the two research programs
8 Cobalt by Chua Kong-Sian and Gazebo by Stuart Cracraft.
9
10 This program is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation, either version 3 of the License, or
13 (at your option) any later version.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program. If not, see <http://www.gnu.org/licenses/>.
22
23 Contact Info:
24 bug-gnu-chess@gnu.org
25 cracraft@ai.mit.edu, cracraft@stanfordalumni.org, cracraft@earthlink.net
26 */
27
28 #include <stdio.h>
29
30 #include "common.h"
31
32 static leaf *node;
33
34 #define ADDMOVE(a,b,c) \
35 do { \
36 node->move = MOVE(a,b) | (c); \
37 node++; \
38 } while (0)
39
40 #define ADDPROMOTE(a,b) \
41 do { \
42 ADDMOVE (a, b, QUEENPRM); \
43 ADDMOVE (a, b, KNIGHTPRM); \
44 ADDMOVE (a, b, ROOKPRM); \
45 ADDMOVE (a, b, BISHOPPRM); \
46 } while (0)
47
BitToMove(short f,BitBoard b)48 static inline void BitToMove (short f, BitBoard b)
49 /***************************************************************************
50 *
51 * Convert a bitboard into a list of moves. These are stored
52 * into the tree. f is the origin square.
53 *
54 ***************************************************************************/
55 {
56 int t;
57
58 while (b)
59 {
60 t = leadz (b);
61 CLEARBIT (b, t);
62 ADDMOVE (f, t, 0);
63 }
64 }
65
66
67
GenMoves(short ply)68 void GenMoves (short ply)
69 /****************************************************************************
70 *
71 * My bitboard move generator. Let's see how fast we can go!
72 * This routine generates pseudo-legal moves.
73 *
74 ****************************************************************************/
75 {
76 int side;
77 int piece, sq, t, ep;
78 BitBoard b, c, d, e, friends, notfriends, blocker, notblocker;
79 BitBoard *a;
80
81 side = board.side;
82 a = board.b[side];
83 friends = board.friends[side];
84 notfriends = ~friends;
85 blocker = board.blocker;
86 notblocker = ~blocker;
87 node = TreePtr[ply + 1];
88 ep = board.ep;
89
90 /* Knight & King */
91 for (piece = knight; piece <= king; piece += 4)
92 {
93 b = a[piece];
94 while (b)
95 {
96 sq = leadz (b);
97 CLEARBIT (b, sq);
98 BitToMove (sq, MoveArray[piece][sq] & notfriends);
99 }
100 }
101
102 /* Bishops */
103 b = a[bishop];
104 while (b)
105 {
106 sq = leadz (b);
107 CLEARBIT (b, sq);
108 d = BishopAttack(sq);
109 BitToMove (sq, d & notfriends);
110 }
111
112 /* Rooks */
113 b = a[rook];
114 while (b)
115 {
116 sq = leadz (b);
117 CLEARBIT (b, sq);
118 d = RookAttack(sq);
119 BitToMove (sq, d & notfriends);
120 }
121
122 /* Queen */
123 b = a[queen];
124 while (b)
125 {
126 sq = leadz (b);
127 CLEARBIT (b, sq);
128 d = QueenAttack(sq);
129 BitToMove (sq, d & notfriends);
130 }
131
132 /* White pawn moves */
133 e = (board.friends[1^side] | (ep > -1 ? BitPosArray[ep] : NULLBITBOARD));
134 if (side == white)
135 {
136 c = (a[pawn] >> 8) & notblocker; /* 1 square forward */
137 while (c)
138 {
139 t = leadz (c);
140 CLEARBIT (c, t);
141 if (t >= 56) /* promotion */
142 {
143 ADDPROMOTE (t-8, t);
144 }
145 else
146 ADDMOVE (t-8, t, 0);
147 }
148
149 b = a[pawn] & RankBit[1]; /* all pawns on 2nd rank */
150 c = (b >> 8) & notblocker;
151 c = (c >> 8) & notblocker; /* 2 squares forward */
152 while (c)
153 {
154 t = leadz (c);
155 CLEARBIT (c, t);
156 ADDMOVE (t-16, t, 0);
157 }
158
159 b = a[pawn] & ~FileBit[0]; /* captures to the left */
160 c = (b >> 7) & e;
161 while (c)
162 {
163 t = leadz (c);
164 CLEARBIT (c, t);
165 if (t >= 56) /* promotion */
166 {
167 ADDPROMOTE (t-7, t);
168 }
169 else if (ep == t)
170 {
171 ADDMOVE (t-7, t, ENPASSANT);
172 }
173 else
174 {
175 ADDMOVE (t-7, t, 0);
176 }
177 }
178
179 b = a[pawn] & ~FileBit[7]; /* captures to the right */
180 c = (b >> 9) & e;
181 while (c)
182 {
183 t = leadz (c);
184 CLEARBIT (c, t);
185 if (t >= 56) /* promotion */
186 {
187 ADDPROMOTE (t-9, t);
188 }
189 else if (ep == t)
190 {
191 ADDMOVE (t-9, t, ENPASSANT);
192 }
193 else
194 {
195 ADDMOVE (t-9, t, 0);
196 }
197 }
198 }
199
200
201 /* Black pawn forward moves */
202 if (side == black)
203 {
204 c = (a[pawn] << 8) & notblocker;
205 while (c)
206 {
207 t = leadz (c);
208 CLEARBIT (c, t);
209 if (t <= 7) /* promotion */
210 {
211 ADDPROMOTE (t+8, t);
212 }
213 else
214 ADDMOVE (t+8, t, 0);
215 }
216
217 b = a[pawn] & RankBit[6]; /* all pawns on 7th rank */
218 c = (b << 8) & notblocker;
219 c = (c << 8) & notblocker;
220 while (c)
221 {
222 t = leadz (c);
223 CLEARBIT (c, t);
224 ADDMOVE (t+16, t, 0);
225 }
226
227 b = a[pawn] & ~FileBit[7]; /* captures to the left */
228 c = (b << 7) & e;
229 while (c)
230 {
231 t = leadz (c);
232 CLEARBIT (c, t);
233 if (t <= 7) /* promotion */
234 {
235 ADDPROMOTE (t+7, t);
236 }
237 else if (ep == t)
238 {
239 ADDMOVE (t+7, t, ENPASSANT);
240 }
241 else
242 {
243 ADDMOVE (t+7, t, 0);
244 }
245 }
246
247 b = a[pawn] & ~FileBit[0]; /* captures to the right */
248 c = (b << 9) & e;
249 while (c)
250 {
251 t = leadz (c);
252 CLEARBIT (c, t);
253 if (t <= 7) /* promotion */
254 {
255 ADDPROMOTE (t+9, t);
256 }
257 else if (ep == t)
258 {
259 ADDMOVE (t+9, t, ENPASSANT);
260 }
261 else
262 {
263 ADDMOVE (t+9, t, 0);
264 }
265 }
266 }
267
268 /* Castling code */
269 b = board.b[side][rook];
270 if (side == white && (board.flag & WKINGCASTLE) && (b & BitPosArray[H1]) &&
271 !(FromToRay[E1][G1] & blocker) &&
272 !SqAtakd (E1, black) && !SqAtakd (F1, black) && !SqAtakd (G1, black))
273 {
274 ADDMOVE (E1, G1, CASTLING);
275 }
276 if (side == white && (board.flag & WQUEENCASTLE) && (b & BitPosArray[A1]) &&
277 !(FromToRay[E1][B1] & blocker) &&
278 !SqAtakd (E1, black) && !SqAtakd (D1, black) && !SqAtakd (C1, black))
279 {
280 ADDMOVE (E1, C1, CASTLING);
281 }
282 if (side == black && (board.flag & BKINGCASTLE) && (b & BitPosArray[H8]) &&
283 !(FromToRay[E8][G8] & blocker) &&
284 !SqAtakd (E8, white) && !SqAtakd (F8, white) && !SqAtakd (G8, white))
285 {
286 ADDMOVE (E8, G8, CASTLING);
287 }
288 if (side == black && (board.flag & BQUEENCASTLE) && (b & BitPosArray[A8]) &&
289 !(FromToRay[E8][B8] & blocker) &&
290 !SqAtakd (E8, white) && !SqAtakd (D8, white) && !SqAtakd (C8, white))
291 {
292 ADDMOVE (E8, C8, CASTLING);
293 }
294
295 /* Update tree pointers and count */
296 TreePtr[ply + 1] = node;
297 GenCnt += TreePtr[ply + 1] - TreePtr[ply];
298 }
299
300
GenNonCaptures(short ply)301 void GenNonCaptures (short ply)
302 /****************************************************************************
303 *
304 * Here I generate only non-captures. Promotions are considered
305 * as captures and are not generated.
306 *
307 ****************************************************************************/
308 {
309 int side;
310 int piece, sq, t;
311 BitBoard b, c, d, blocker, notblocker;
312 BitBoard *a;
313
314 side = board.side;
315 a = board.b[side];
316 blocker = board.blocker;
317 notblocker = ~blocker;
318 node = TreePtr[ply + 1];
319
320 /* Knight & King */
321 for (piece = knight; piece <= king; piece += 4)
322 {
323 b = a[piece];
324 while (b)
325 {
326 sq = leadz (b);
327 CLEARBIT (b, sq);
328 BitToMove (sq, MoveArray[piece][sq] & notblocker);
329 }
330 }
331
332 /* Bishops */
333 b = a[bishop];
334 while (b)
335 {
336 sq = leadz (b);
337 CLEARBIT (b, sq);
338 d = BishopAttack(sq);
339 BitToMove (sq, d & notblocker);
340 }
341
342 /* Rooks */
343 b = a[rook];
344 while (b)
345 {
346 sq = leadz (b);
347 CLEARBIT (b, sq);
348 d = RookAttack(sq);
349 BitToMove (sq, d & notblocker);
350 }
351
352 /* Queen */
353 b = a[queen];
354 while (b)
355 {
356 sq = leadz (b);
357 CLEARBIT (b, sq);
358 d = QueenAttack(sq);
359 BitToMove (sq, d & notblocker);
360 }
361
362 /* White pawn moves */
363 if (side == white)
364 {
365 c = (a[pawn] >> 8) & notblocker; /* 1 square forward */
366 while (c)
367 {
368 t = leadz (c);
369 CLEARBIT (c, t);
370 if (t < 56)
371 ADDMOVE (t-8, t, 0);
372 }
373
374 b = a[pawn] & RankBit[1]; /* all pawns on 2nd rank */
375 c = (b >> 8) & notblocker;
376 c = (c >> 8) & notblocker; /* 2 squares forward */
377 while (c)
378 {
379 t = leadz (c);
380 CLEARBIT (c, t);
381 ADDMOVE (t-16, t, 0);
382 }
383 }
384
385
386 /* Black pawn forward moves */
387 if (side == black)
388 {
389 c = (a[pawn] << 8) & notblocker;
390 while (c)
391 {
392 t = leadz (c);
393 CLEARBIT (c, t);
394 if ( t > 7)
395 ADDMOVE (t+8, t, 0);
396 }
397
398 b = a[pawn] & RankBit[6]; /* all pawns on 7th rank */
399 c = (b << 8) & notblocker;
400 c = (c << 8) & notblocker;
401 while (c)
402 {
403 t = leadz (c);
404 CLEARBIT (c, t);
405 ADDMOVE (t+16, t, 0);
406 }
407 }
408
409 /* Castling code */
410 b = board.b[side][rook];
411 if (side == white && (board.flag & WKINGCASTLE) && (b & BitPosArray[7]) &&
412 !(FromToRay[4][6] & blocker) &&
413 !SqAtakd (4, black) && !SqAtakd (5, black) && !SqAtakd (6, black))
414 {
415 ADDMOVE (4, 6, CASTLING);
416 }
417 if (side == white && (board.flag & WQUEENCASTLE) && (b & BitPosArray[0]) &&
418 !(FromToRay[4][1] & blocker) &&
419 !SqAtakd (4, black) && !SqAtakd (3, black) && !SqAtakd (2, black))
420 {
421 ADDMOVE (4, 2, CASTLING);
422 }
423 if (side == black && (board.flag & BKINGCASTLE) && (b & BitPosArray[63]) &&
424 !(FromToRay[60][62] & blocker) &&
425 !SqAtakd (60, white) && !SqAtakd (61, white) && !SqAtakd (62, white))
426 {
427 ADDMOVE (60, 62, CASTLING);
428 }
429 if (side == black && (board.flag & BQUEENCASTLE) && (b & BitPosArray[56]) &&
430 !(FromToRay[60][57] & blocker) &&
431 !SqAtakd (60, white) && !SqAtakd (59, white) && !SqAtakd (58, white))
432 {
433 ADDMOVE (60, 58, CASTLING);
434 }
435
436 /* Update tree pointers and count */
437 TreePtr[ply + 1] = node;
438 GenCnt += TreePtr[ply + 1] - TreePtr[ply];
439 }
440
441
GenCaptures(short ply)442 void GenCaptures (short ply)
443 /****************************************************************************
444 *
445 * This routine generates captures. En passant and pawn promotions
446 * are included.
447 *
448 ****************************************************************************/
449 {
450 int side;
451 int piece, sq, t, ep;
452 BitBoard b, c, enemy, blocker;
453 BitBoard *a;
454
455 side = board.side;
456 a = board.b[side];
457 enemy = board.friends[1^side];
458 blocker = board.blocker;
459 node = TreePtr[ply + 1];
460 ep = board.ep;
461
462 /* Knight & King */
463 for (piece = knight; piece <= king; piece += 4)
464 {
465 b = a[piece];
466 while (b)
467 {
468 sq = leadz (b);
469 CLEARBIT (b, sq);
470 BitToMove (sq, MoveArray[piece][sq] & enemy);
471 }
472 }
473
474 /* Bishop */
475 b = a[bishop];
476 while (b)
477 {
478 sq = leadz (b);
479 CLEARBIT (b, sq);
480 c = BishopAttack(sq);
481 BitToMove (sq, c & enemy);
482 }
483
484 /* Rook */
485 b = a[rook];
486 while (b)
487 {
488 sq = leadz (b);
489 CLEARBIT (b, sq);
490 c = RookAttack(sq);
491 BitToMove (sq, c & enemy);
492 }
493
494 /* Queen */
495 b = a[queen];
496 while (b)
497 {
498 sq = leadz (b);
499 CLEARBIT (b, sq);
500 c = QueenAttack(sq);
501 BitToMove (sq, c & enemy);
502 }
503
504 /* White pawn moves */
505 if (side == white)
506 {
507 b = a[pawn] & RankBit[6]; /* all pawns on 7 rank */
508 c = (b >> 8) & ~blocker; /* 1 square forward */
509 while (c)
510 {
511 t = leadz (c);
512 CLEARBIT (c, t);
513 ADDPROMOTE (t-8, t);
514 }
515
516 b = a[pawn] & ~FileBit[0]; /* captures to the left */
517 c = (b >> 7) & (board.friends[1^side] | (ep > -1 ? BitPosArray[ep] : ULL(0)));
518 while (c)
519 {
520 t = leadz (c);
521 CLEARBIT (c, t);
522 if (t >= 56) /* promotion */
523 {
524 ADDPROMOTE (t-7, t);
525 }
526 else if (ep == t)
527 {
528 ADDMOVE (t-7, t, ENPASSANT);
529 }
530 else
531 {
532 ADDMOVE (t-7, t, 0);
533 }
534 }
535
536 b = a[pawn] & ~FileBit[7]; /* captures to the right */
537 c = (b >> 9) & (board.friends[1^side] | (ep > -1 ? BitPosArray[ep] : ULL(0)));
538 while (c)
539 {
540 t = leadz (c);
541 CLEARBIT (c, t);
542 if (t >= 56) /* promotion */
543 {
544 ADDPROMOTE (t-9, t);
545 }
546 else if (ep == t)
547 {
548 ADDMOVE (t-9, t, ENPASSANT);
549 }
550 else
551 {
552 ADDMOVE (t-9, t, 0);
553 }
554 }
555 }
556
557 /* Black pawn forward moves */
558 if (side == black)
559 {
560 b = a[pawn] & RankBit[1]; /* all pawns on 2nd rank */
561 c = (b << 8) & ~blocker;
562 while (c)
563 {
564 t = leadz (c);
565 CLEARBIT (c, t);
566 ADDPROMOTE (t+8, t);
567 }
568
569 b = a[pawn] & ~FileBit[7]; /* captures to the left */
570 c = (b << 7) & (board.friends[1^side] | (ep > -1 ? BitPosArray[ep] : ULL(0)));
571 while (c)
572 {
573 t = leadz (c);
574 CLEARBIT (c, t);
575 if (t <= 7) /* promotion */
576 {
577 ADDPROMOTE (t+7, t);
578 }
579 else if (ep == t)
580 {
581 ADDMOVE (t+7, t, ENPASSANT);
582 }
583 else
584 {
585 ADDMOVE (t+7, t, 0);
586 }
587 }
588
589 b = a[pawn] & ~FileBit[0]; /* captures to the right */
590 c = (b << 9) & (board.friends[1^side] | (ep > -1 ? BitPosArray[ep] : ULL(0)));
591 while (c)
592 {
593 t = leadz (c);
594 CLEARBIT (c, t);
595 if (t <= 7) /* promotion */
596 {
597 ADDPROMOTE (t+9, t);
598 }
599 else if (ep == t)
600 {
601 ADDMOVE (t+9, t, ENPASSANT);
602 }
603 else
604 {
605 ADDMOVE (t+9, t, 0);
606 }
607 }
608 }
609
610
611 /* Update tree pointers and count */
612 TreePtr[ply + 1] = node;
613 GenCnt += TreePtr[ply + 1] - TreePtr[ply];
614 }
615
616
GenCheckEscapes(short ply)617 void GenCheckEscapes (short ply)
618 /**************************************************************************
619 *
620 * The king is in check, so generate only moves which get the king out
621 * of check.
622 * Caveat: The special case of an enpassant capture must be taken into
623 * account too as the captured pawn could be the checking piece.
624 *
625 **************************************************************************/
626 {
627 int side, xside;
628 int kingsq, chksq, sq, sq1, epsq, dir;
629 BitBoard checkers, b, c, p, escapes;
630 escapes = NULLBITBOARD;
631 side = board.side;
632 xside = 1 ^ side;
633 /* TreePtr[ply + 1] = TreePtr[ply]; */
634 node = TreePtr[ply + 1];
635 kingsq = board.king[side];
636 checkers = AttackTo (kingsq, xside);
637 p = board.b[side][pawn];
638
639 if (nbits (checkers) == 1)
640 {
641 /* Captures of checking pieces (except by king) */
642 chksq = leadz (checkers);
643 b = AttackTo (chksq, side);
644 b &= ~board.b[side][king];
645 while (b)
646 {
647 sq = leadz (b);
648 CLEARBIT (b, sq);
649 if (!PinnedOnKing (sq, side))
650 {
651 if (cboard[sq] == pawn && (chksq <= H1 || chksq >= A8))
652 {
653 ADDPROMOTE (sq, chksq);
654 }
655 else
656 ADDMOVE (sq, chksq, 0);
657 }
658 }
659
660 /* Maybe enpassant can help */
661 if (board.ep > -1)
662 {
663 epsq = board.ep;
664 if (epsq + (side == white ? -8 : 8) == chksq)
665 {
666 b = MoveArray[ptype[1^side]][epsq] & p;
667 while (b)
668 {
669 sq = leadz (b);
670 CLEARBIT (b, sq);
671 if (!PinnedOnKing (sq, side))
672 ADDMOVE (sq, epsq, ENPASSANT);
673 }
674 }
675 }
676
677 /* Lets block/capture the checking piece */
678 if (slider[cboard[chksq]])
679 {
680 c = FromToRay[kingsq][chksq] & NotBitPosArray[chksq];
681 while (c)
682 {
683 sq = leadz (c);
684 CLEARBIT (c, sq);
685 b = AttackTo (sq, side);
686 b &= ~(board.b[side][king] | p);
687
688 /* Add in pawn advances */
689 if (side == white && sq > H2)
690 {
691 if (BitPosArray[sq-8] & p)
692 b |= BitPosArray[sq-8];
693 if (RANK(sq) == 3 && cboard[sq-8] == empty &&
694 (BitPosArray[sq-16] & p))
695 b |= BitPosArray[sq-16];
696 }
697 if (side == black && sq < H7)
698 {
699 if (BitPosArray[sq+8] & p)
700 b |= BitPosArray[sq+8];
701 if (RANK(sq) == 4 && cboard[sq+8] == empty &&
702 (BitPosArray[sq+16] & p))
703 b |= BitPosArray[sq+16];
704 }
705 while (b)
706 {
707 sq1 = leadz (b);
708 CLEARBIT (b, sq1);
709 if (!PinnedOnKing (sq1, side))
710 {
711 if (cboard[sq1] == pawn && (sq > H7 || sq < A2))
712 {
713 ADDPROMOTE (sq1, sq);
714 }
715 else
716 ADDMOVE (sq1, sq, 0);
717 }
718 }
719 }
720 }
721 }
722
723 /* If more than one checkers, move king to get out of check */
724 if (checkers)
725 escapes = MoveArray[king][kingsq] & ~board.friends[side];
726 while (checkers)
727 {
728 chksq = leadz (checkers);
729 CLEARBIT (checkers, chksq);
730 dir = directions[chksq][kingsq];
731 if (slider[cboard[chksq]])
732 escapes &= ~Ray[chksq][dir];
733 }
734 while (escapes)
735 {
736 sq = leadz (escapes);
737 CLEARBIT (escapes, sq);
738 if (!SqAtakd (sq, xside))
739 ADDMOVE (kingsq, sq, 0);
740 }
741
742 /* Update tree pointers and count */
743 TreePtr[ply + 1] = node;
744 GenCnt += TreePtr[ply + 1] - TreePtr[ply];
745 return;
746 }
747
748
FilterIllegalMoves(short ply)749 void FilterIllegalMoves (short ply)
750 /**************************************************************************
751 *
752 * All the illegal moves in the current ply is removed.
753 *
754 **************************************************************************/
755 {
756 leaf *p;
757 int side, xside;
758 int check, sq;
759
760 side = board.side;
761 xside = 1^side;
762 sq = board.king[side];
763 for (p = TreePtr[ply]; p < TreePtr[ply+1]; p++)
764 {
765 MakeMove (side, &p->move);
766 if (cboard[TOSQ(p->move)] != king)
767 check = SqAtakd (sq, xside);
768 else
769 check = SqAtakd (TOSQ(p->move), xside);
770 UnmakeMove (xside, &p->move);
771
772 if (check) /* its an illegal move */
773 {
774 --TreePtr[ply+1];
775 *p = *TreePtr[ply+1];
776 --p;
777 GenCnt--;
778 }
779 }
780 }
781