/* vi: set tabstop=4 shiftwidth=4: */ /* * $Id: movegen.c,v 1.4 1997/01/03 15:33:09 schweikh Exp $ */ #include /* memset */ #include /* printf (debugging) */ #include "chess.h" #include "init.h" #include "movegen.h" #define ADDMOVE(indx, destination) \ do { moves[nmoves].index = (char) (indx); \ moves[nmoves++].dest = (char) (destination); \ } while (0) /* Kluge to avoid swallowed semicolon */ static int nmoves; /* number of moves, signed because -1 = stale * mate */ __inline static unsigned wgettrapped (State * s) /* * Return a mask of white's trapped pieces. */ { int piece; /* 0 .. 63 */ int kpos; /* 0 .. 63 */ int i; /* 0 .. 15 */ int j; /* 0 .. 63 */ int dir; /* -9 .. 9 */ unsigned trap_msk; unsigned char *board; /* If opponent has not one of QRB, no piece can be trapped */ if (s->lm[1] == 0) return 0; kpos = s->pos[0][0]; board = s->brd; trap_msk = 0; for (i = s->n[0] - 1; i != 0; --i) { /* for all white non-kings */ piece = s->pos[0][i]; dir = trap[kpos][piece]; /* offset from king to piece */ if (!dir) continue; /* king and piece do not align */ if (!attacked[piece]) continue; /* a piece that is not attacked can not be * trapped */ /* no trap if there's any piece between kpos and piece */ for (j = kpos + dir; j != piece; j += dir) if (board[j] != FREE) goto next_i; /* break inner loop and continue outer */ /* Okay, no other piece inbetween. Look what is coming behind piece. * If piece is on border, we stop seeking when an edge is hit * (because our king must be on the same border, look for Q|R). If * piece is not on border, we stop when the border is reached. */ if (border[piece]) { do { piece += dir; if (board[piece] == FREE) continue; if (board[piece] & WHITE) break; /* piece of my own color: no trap */ if (board[piece] & (QUEEN | ROOK)) trap_msk |= bit[i]; break; /* while */ } while (border[piece] != 1); } else { /* piece not on border, seek while not border */ if (diag[dir & 15]) { do { piece += dir; if (board[piece] == FREE) continue; if (board[piece] & WHITE) break; /* piece of my own color: no trap */ if (board[piece] & (QUEEN | BISHOP)) trap_msk |= bit[i]; break; /* while */ } while (!border[piece]); } else { /* the four straight directions */ do { piece += dir; if (board[piece] == FREE) continue; if (board[piece] & WHITE) break; /* piece of my own color: no trap */ if (board[piece] & (QUEEN | ROOK)) trap_msk |= bit[i]; break; /* while */ } while (!border[piece]); } } next_i:; } return trap_msk; } __inline static unsigned bgettrapped (State * s) /* * Return a mask of black's trapped pieces. */ { int piece; /* 0 .. 63 */ int kpos; /* 0 .. 63 */ int i; /* 0 .. 15 */ int j; /* 0 .. 63 */ int dir; /* -9 .. 9 */ unsigned trap_msk; unsigned char *board; /* If opponent has not one of QRB, no piece can be trapped */ if (s->lm[0] == 0) return 0; kpos = s->pos[1][0]; board = s->brd; trap_msk = 0; for (i = s->n[1] - 1; i != 0; --i) { /* for all black non-kings */ piece = s->pos[1][i]; dir = trap[kpos][piece]; /* offset from king to piece */ if (!dir) continue; /* king and piece do not align */ if (!attacked[piece]) continue; /* a piece that is not attacked can not be * trapped */ /* no trap if there's any piece between kpos and piece */ for (j = kpos + dir; j != piece; j += dir) if (board[j] != FREE) goto next_i; /* break inner loop and continue outer */ /* Okay, no other piece inbetween. Look what is coming behind piece. * If piece is on border, we stop seeking when an edge is hit * (because our king must be on the same border, look for Q|R). If * piece is not on border, we stop when the border is reached. */ if (border[piece]) { do { piece += dir; if (board[piece] == FREE) continue; if (board[piece] & BLACK) break; /* piece of my own color: no trap */ if (board[piece] & (QUEEN | ROOK)) trap_msk |= bit[i]; break; /* while */ } while (border[piece] != 1); } else { /* piece not on border, seek while not border */ if (diag[dir & 15]) { do { piece += dir; if (board[piece] == FREE) continue; if (board[piece] & BLACK) break; /* piece of my own color: no trap */ if (board[piece] & (QUEEN | BISHOP)) trap_msk |= bit[i]; break; /* while */ } while (!border[piece]); } else { /* the four straight directions */ do { piece += dir; if (board[piece] == FREE) continue; if (board[piece] & BLACK) break; /* piece of my own color: no trap */ if (board[piece] & (QUEEN | ROOK)) trap_msk |= bit[i]; break; /* while */ } while (!border[piece]); } } next_i:; } return trap_msk; } __inline static int * destset (unsigned char board[64], int kpos, int checkpos, int *n) /* * Return a (pointer to a) set of destination positions for moves. * The number of elements is placed into *n. */ { static int set[7]; /* maximum is 7 positions */ int count = 0; /* 0 .. 7 */ if (IS_QRB (board[checkpos]) && dist[checkpos][kpos] > 1) { /* set consists of more than one element: kpos + dir ... checkpos */ int dir; /* -9 .. 9 */ int pos; /* 0 .. 63 */ dir = off[checkpos][kpos]; /* dir from checkpos to king */ for (pos = checkpos; pos != kpos; pos += dir) set[count++] = pos; *n = count; return set; } else { /* n or p or dist == 1 */ /* set consists of only one element: checkpos */ set[0] = checkpos; *n = 1; return set; } } __inline static bool wep_ok (int myp, int epp, int kpos, unsigned char *board) /* * Return true if en passant is not forbidden because of * 'K pP q' or 'r pP K' or * 'K Pp q' or 'r Pp K' on row 4 (actual row on board: 5). */ { if (ROW (kpos) != 4 || COL (myp) == 0 || COL (myp) == 7 || COL (epp) == 0 || COL (epp) == 7) return 1; /* ep ok if any piece other than the opponent's ep pawn between kpos and * my pawn. */ if (kpos < myp) { if (myp > epp) { /* canonicalize K Pp to K pP */ --myp; ++epp; } if (myp - kpos > 1) { /* if more than one square apart */ for (++kpos; kpos < myp; ++kpos) if (board[kpos] != FREE) return 1; } /* if opponent's Q or R follow after P, it's forbidden */ for (;;) { ++epp; if (board[epp] == (BLACK | QUEEN) || board[epp] == (BLACK | ROOK)) return 0; if (board[epp] != FREE || COL (epp) == 7) return 1; } } else { /* kpos > myp, 'q Pp K' */ if (myp < epp) { /* canonicalize pP K to Pp K */ ++myp; --epp; } if (kpos - myp > 1) { /* if more than one square apart */ for (--kpos; kpos > myp; --kpos) if (board[kpos] != FREE) return 1; } /* if opponent's Q or R follow after P, it's forbidden */ for (;;) { --epp; if (board[epp] == (BLACK | QUEEN) || board[epp] == (BLACK | ROOK)) return 0; if (board[epp] != FREE || COL (epp) == 0) return 1; } } } __inline static bool bep_ok (int myp, int epp, int kpos, unsigned char *board) /* * Return true if en passant is not forbidden because of * 'k pP Q' or 'R pP k' or * 'k Pp Q' or 'R Pp k' on row 3. */ { if (ROW (kpos) != 3 || COL (myp) == 0 || COL (myp) == 7 || COL (epp) == 0 || COL (epp) == 7) return 1; /* ep ok if any piece other than the opponent's ep pawn between kpos and * my pawn. */ if (kpos < myp) { if (myp > epp) { /* canonicalize k Pp to k pP */ --myp; ++epp; } if (myp - kpos > 1) { /* if more than one square apart */ for (++kpos; kpos < myp; ++kpos) if (board[kpos] != FREE) return 1; } /* if opponent's Q or R follow after P, it's forbidden */ for (;;) { ++epp; if (board[epp] == (WHITE | QUEEN) || board[epp] == (WHITE | ROOK)) return 0; if (board[epp] != FREE || COL (epp) == 7) return 1; } } else { /* kpos > myp, 'Q Pp k' */ if (myp < epp) { /* canonicalize pP k to Pp k */ ++myp; --epp; } if (kpos - myp > 1) { /* if more than one square apart */ for (--kpos; kpos > myp; --kpos) if (board[kpos] != FREE) return 1; } /* if opponent's Q or R follow after P, it's forbidden */ for (;;) { --epp; if (board[epp] == (WHITE | QUEEN) || board[epp] == (WHITE | ROOK)) return 0; if (board[epp] != FREE || COL (epp) == 0) return 1; } } } int movegen (State * s, move_t * moves, const int pos_giving_check) /* * Generate moves: fills array 'moves[]', * 'pos_giving_check' has the position of a checking piece or -1. * We have a double check when attacks[king position] == 2. * Returns the number of moves (that is the * number of elements in 'moves[]'), 0 = mate, -1 = stale mate. */ { unsigned char *ppos, *pdir, *board = s->brd; int current, start; unsigned t; unsigned char *pos, *fig; int j; int i; nmoves = 0; /* reset the move count */ if (BLACK_TO_MOVE) { pos = s->pos[1]; fig = s->fig[1]; if (pos_giving_check >= A1) { /* white shouts "check!" */ int *set; /* Two ways to handle check: 1) move king out of check 2) move * another untrapped piece on one of the squares in the direction * from our king up to the square of the checker. */ /* 1) Find all moves out of check (includes king capturing) */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !IS_BLACK (board[current])) ADDMOVE (0, current); if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); if (attacked[start] > 1) { /* start = kpos, double check */ /* we _must_ move our king, other moves impossible, return */ return nmoves; } /* okay, single check */ /* the king's moves are done now, if it's the only piece, return */ if (s->n[1] == 1) return nmoves; /* 2) move another untrapped piece on one of the squares in the * direction from our king up to the square of the checker. */ /* okay, there are some other pieces on the board. We are only * interested in moves that either - capture the piece we are * checked by. These are the only moves if checked by P or N - or * will block check These are only possible if checked by Q, R or * B. That means the possible destinations are a small set of * squares with one element for P, N or adjacent Q, R or B - and * with more for non-adjacent Q, R or B. */ t = bgettrapped (s); set = destset (board, start, pos_giving_check, &j); /* find all moves to any position in set[] */ do { /* set[j] */ --j; for (i = s->n[1] - 1; i != 0; --i) { /* Can fig[i] move to position set[j]? Skip trapped * pieces and pieces that can't reach position set[j]. */ if (bit[i] & t) continue; /* trapped */ if (fig[i] != PAWN && !ok[code[fig[i]]][pos[i]][set[j]]) continue; /* can't reach set[j] */ if (fig[i] == PAWN) { if (pos[i] == set[j] + 8 && board[set[j]] == FREE) /* single advance */ ADDMOVE (i, set[j]); if (pos[i] == set[j] + 16 && pos[i] >= A7 && board[pos[i] - 8] == FREE && board[set[j]] == FREE) /* 2 steps from home */ ADDMOVE (i, set[j]); if (COL (pos[i]) != 0) { if (set[j] == pos[i] - 9 && board[set[j]] != FREE) /* capture to a - g */ ADDMOVE (i, set[j]); if (set[j] == pos[i] - 1 && set[j] == (s->sp & SP_EP_POS)) /* ep to a - g */ ADDMOVE (i, pos[i] - 9); } if (COL (pos[i]) != 7) { if (set[j] == pos[i] - 7 && board[set[j]] != FREE) /* capture to b - h */ ADDMOVE (i, set[j]); if (set[j] == pos[i] + 1 && set[j] == (s->sp & SP_EP_POS)) /* ep to b - h */ ADDMOVE (i, pos[i] - 7); } } else { /* not pawn, i.e. n,b,r,q */ start = pos[i]; ppos = nextpos[code[fig[i]]][start]; pdir = nextdir[code[fig[i]]][start]; current = ppos[start]; do { if (current == set[j]) { ADDMOVE (i, current); /* We can't get a 2nd time at the same s[j] * so goto next iteration by breaking the * inner loop and continuing the outer */ goto b_next_i; } if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); } b_next_i:; } } while (j != 0); } else { /* our king is not checked */ /* King may move to any non-attacked square that is not occupied * by some piece of his color and may castle */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !(board[current] & BLACK)) ADDMOVE (0, current); current = pdir[current]; /* king has only range 1, so * pdir */ } while (current != start); if (CAN_o_o) ADDMOVE (0, G8); if (CAN_o_o_o) ADDMOVE (0, C8); /* so much for the king ... */ if (s->n[1] == 1) /* stale mate if there are no other pieces */ return nmoves ? nmoves : MVGEN_STALE_MATE; t = bgettrapped (s); for (j = s->n[1] - 1; j != 0; --j) { /* black non kings */ int p; /* 0 .. 63 */ switch (fig[j]) { case KNIGHT: /* if a knight is trapped, it can't move at all */ if (t & bit[j]) break; /* switch */ start = pos[j]; ppos = nextpos[knight][start]; pdir = nextdir[knight][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) ADDMOVE (j, current); current = pdir[current]; /* knight has only range * 1 */ } while (current != start); break; case ROOK: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a rook is trapped it can only move if the trap * direction is not diagonal */ if (diag[dir & 15]) break; /* switch */ /* all moves away from the king (+dir) */ p = pos[j]; do { p += dir; ADDMOVE (j, p); } while (board[p] == FREE); /* all moves towards the king (-dir) */ p = pos[j] - dir; while (board[p] == FREE) { ADDMOVE (j, p); p -= dir; } break; /* switch */ } start = pos[j]; ppos = nextpos[rook][start]; pdir = nextdir[rook][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) ADDMOVE (j, current); if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case BISHOP: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a bishop is trapped it can only move if the * trap direction is diagonal */ if (!diag[dir & 15]) break; /* switch */ /* all moves away from the king (+dir) */ p = pos[j]; do { p += dir; ADDMOVE (j, p); } while (board[p] == FREE); /* all moves towards the king (-dir) */ p = pos[j] - dir; while (board[p] == FREE) { ADDMOVE (j, p); p -= dir; } break; /* switch */ } start = pos[j]; ppos = nextpos[bishop][start]; pdir = nextdir[bishop][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) ADDMOVE (j, current); if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case QUEEN: if (t & bit[j]) { int dir = trap[pos[0]][pos[j]]; /* all moves away from the king (+dir) */ p = pos[j]; do { p += dir; ADDMOVE (j, p); } while (board[p] == FREE); /* all moves towards the king (-dir) */ p = pos[j] - dir; while (board[p] == FREE) { ADDMOVE (j, p); p -= dir; } break; /* switch */ } start = pos[j]; ppos = nextpos[queen][start]; pdir = nextdir[queen][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) ADDMOVE (j, current); if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case PAWN: /* Pawn promotions are expanded when the move generation * for all other moves is done. */ if (t & bit[j]) { /* trapped pawn, no check */ int dir = trap[pos[0]][pos[j]]; if (dir == 1 || dir == -1 || dir == 7 || dir == 9) { /* horizontal trap or backward diag: no moves */ break; /* switch */ } else if (!(dir & 1)) { /* 8 or -8 */ /* vertical trap: advance */ p = pos[j]; if (board[p - 8] == FREE) { /* single step */ ADDMOVE (j, p - 8); if (p > H6 && board[p - 16] == FREE) ADDMOVE (j, p - 16); /* double step */ } } else { /* Diagonal forward trap, dir == -7 or -9. Move * if attacked square is opponent's piece. It * can't be ours, 'cos then it were no trap! */ p = pos[j]; if (board[p + dir] != FREE) ADDMOVE (j, p + dir); } break; /* switch */ } /* not trapped */ p = pos[j]; if (board[p - 8] == FREE) { /* single step */ ADDMOVE (j, p - 8); if (p >= A7) { /* still home */ if (board[p - 16] == FREE) ADDMOVE (j, p - 16); /* double step */ } } if (COL (p) > 0) { if (IS_WHITE (board[p - 9]) || ((s->sp & SP_EP_POS) == p - 1 && bep_ok (p, p - 1, pos[0], board))) /* capture or ep to a - g */ ADDMOVE (j, p - 9); } if (COL (p) < 7) { if (IS_WHITE (board[p - 7]) || ((s->sp & SP_EP_POS) == p + 1 && bep_ok (p, p + 1, pos[0], board))) /* capture or ep to b - h */ ADDMOVE (j, p - 7); } } } } /* not checked */ /* Pawn promotions? */ t = s->pm[1]; if (t != 0) { /* if there is at least one pawn on the board */ int move; /* Is any piece on a destination square <= H1 a pawn? */ for (move = 0; move < nmoves; ++move) { if ((moves[move].dest <= H1) && (fig[moves[move].index] == PAWN)) { ADDMOVE (moves[move].index, moves[move].dest + 24); ADDMOVE (moves[move].index, moves[move].dest + 32); ADDMOVE (moves[move].index, moves[move].dest + 40); moves[move].dest += 16; /* Make that a 'backward' * move */ } } } } else { /********************** WHITE TO MOVE ************************/ pos = s->pos[0]; fig = s->fig[0]; if (pos_giving_check >= A1) { /* black shouts "check!" */ int *set; /* Two ways to handle check: 1) move king out of check 2) move * another untrapped piece on one of the squares in the direction * from our king up to the square of the checker. */ /* 1) Find all moves out of check (includes king capturing) */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !IS_WHITE (board[current])) ADDMOVE (0, current); if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); if (attacked[start] > 1) { /* start = kpos, double check */ /* we _must_ move our king, other moves impossible, return */ return nmoves; } /* okay, single check */ /* the king's moves are done now, if it's the only piece, return */ if (s->n[0] == 1) return nmoves; /* 2) move another untrapped piece on one of the squares in the * direction from our king up to the square of the checker. */ /* okay, there are some other pieces on the board. We are only * interested in moves that either - capture the piece we are * checked by. These are the only moves if checked by P or N - or * will block check These are only possible if checked by Q, R or * B. That means the possible destinations are a small set of * squares with one element for P, N or adjacent Q, R or B - and * with more for non-adjacent Q, R or B. */ t = wgettrapped (s); set = destset (board, start, pos_giving_check, &j); /* find all moves to any position in set[] */ do { /* set[j] */ --j; for (i = s->n[0] - 1; i != 0; --i) { /* Can fig[i] move to position set[j]? Skip trapped * pieces and pieces that can't reach position set[j]. */ if (bit[i] & t) continue; /* trapped */ if (fig[i] != PAWN && !ok[code[fig[i]]][pos[i]][set[j]]) continue; /* can't reach set[j] */ if (fig[i] == PAWN) { if (pos[i] == set[j] - 8 && board[set[j]] == FREE) /* single advance */ ADDMOVE (i, set[j]); if (pos[i] == set[j] - 16 && pos[i] <= H2 && board[pos[i] + 8] == FREE && board[set[j]] == FREE) /* 2 steps from home */ ADDMOVE (i, set[j]); if (COL (pos[i]) != 0) { if (set[j] == pos[i] + 7 && board[set[j]] != FREE) /* capture to a - g */ ADDMOVE (i, set[j]); if (set[j] == pos[i] - 1 && set[j] == (s->sp & SP_EP_POS)) /* ep to a - g */ ADDMOVE (i, pos[i] + 7); } if (COL (pos[i]) != 7) { if (set[j] == pos[i] + 9 && board[set[j]] != FREE) /* capture to b - h */ ADDMOVE (i, set[j]); if (set[j] == pos[i] + 1 && set[j] == (s->sp & SP_EP_POS)) /* ep to b - h */ ADDMOVE (i, pos[i] + 9); } } else { /* not pawn, i.e. n,b,r,q */ start = pos[i]; ppos = nextpos[code[fig[i]]][start]; pdir = nextdir[code[fig[i]]][start]; current = ppos[start]; do { if (current == set[j]) { ADDMOVE (i, current); /* We can't get a 2nd time at the same s[j] * so goto next iteration by breaking the * inner loop and continuing the outer */ goto w_next_i; } if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); } w_next_i:; } } while (j != 0); } else { /* our king is not checked */ /* King may move to any non-attacked square that is not occupied * by some piece of his color and may castle */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !(board[current] & WHITE)) ADDMOVE (0, current); current = pdir[current]; /* king has only range 1, so * pdir */ } while (current != start); if (CAN_O_O) ADDMOVE (0, G1); if (CAN_O_O_O) ADDMOVE (0, C1); /* so much for the king ... */ if (s->n[0] == 1) /* stale mate if there are no other pieces */ return nmoves ? nmoves : MVGEN_STALE_MATE; t = wgettrapped (s); for (j = s->n[0] - 1; j != 0; --j) { /* white non kings */ int p; /* 0 .. 63 */ switch (fig[j]) { case KNIGHT: /* if a knight is trapped, it can't move at all */ if (t & bit[j]) break; /* switch */ start = pos[j]; ppos = nextpos[knight][start]; pdir = nextdir[knight][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) ADDMOVE (j, current); current = pdir[current]; /* knight has only range * 1 */ } while (current != start); break; case ROOK: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a rook is trapped it can only move if the trap * direction is not diagonal */ if (diag[dir & 15]) break; /* switch */ /* all moves away from the king (+dir) */ p = pos[j]; do { p += dir; ADDMOVE (j, p); } while (board[p] == FREE); /* all moves towards the king (-dir) */ p = pos[j] - dir; while (board[p] == FREE) { ADDMOVE (j, p); p -= dir; } break; /* switch */ } start = pos[j]; ppos = nextpos[rook][start]; pdir = nextdir[rook][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) ADDMOVE (j, current); if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case BISHOP: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a bishop is trapped it can only move if the * trap direction is diagonal */ if (!diag[dir & 15]) break; /* switch */ /* all moves away from the king (+dir) */ p = pos[j]; do { p += dir; ADDMOVE (j, p); } while (board[p] == FREE); /* all moves towards the king (-dir) */ p = pos[j] - dir; while (board[p] == FREE) { ADDMOVE (j, p); p -= dir; } break; /* switch */ } start = pos[j]; ppos = nextpos[bishop][start]; pdir = nextdir[bishop][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) ADDMOVE (j, current); if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case QUEEN: if (t & bit[j]) { int dir = trap[pos[0]][pos[j]]; /* all moves away from the king (+dir) */ p = pos[j]; do { p += dir; ADDMOVE (j, p); } while (board[p] == FREE); /* all moves towards the king (-dir) */ p = pos[j] - dir; while (board[p] == FREE) { ADDMOVE (j, p); p -= dir; } break; /* switch */ } start = pos[j]; ppos = nextpos[queen][start]; pdir = nextdir[queen][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) ADDMOVE (j, current); if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case PAWN: /* Pawn promotions are expanded when the move generation * for all other moves is done. */ if (t & bit[j]) { /* trapped pawn, no check */ int dir = trap[pos[0]][pos[j]]; if (dir == 1 || dir == -1 || dir == -7 || dir == -9) { /* horizontal trap or backward diag: no moves */ break; /* switch */ } else if (!(dir & 1)) { /* 8 or -8 */ /* vertical trap: advance */ p = pos[j]; if (board[p + 8] == FREE) { /* single step */ ADDMOVE (j, p + 8); if (p < H3 && board[p + 16] == FREE) ADDMOVE (j, p + 16); /* double step */ } } else { /* Diagonal forward trap, dir == 7 or 9. Move if * attacked square is opponent's piece. It can't * be ours, 'cos then it were no trap! */ p = pos[j]; if (board[p + dir] != FREE) ADDMOVE (j, p + dir); } break; /* switch */ } /* not trapped */ p = pos[j]; if (board[p + 8] == FREE) { /* single step */ ADDMOVE (j, p + 8); if (p <= H2) { /* still home */ if (board[p + 16] == FREE) ADDMOVE (j, p + 16); } } if (COL (p) > 0) { if (IS_BLACK (board[p + 7]) || ((s->sp & SP_EP_POS) == p - 1 && wep_ok (p, p - 1, pos[0], board))) /* capture or ep to a - g */ ADDMOVE (j, p + 7); } if (COL (p) < 7) { if (IS_BLACK (board[p + 9]) || ((s->sp & SP_EP_POS) == p + 1 && wep_ok (p, p + 1, pos[0], board))) /* capture or ep to b - h */ ADDMOVE (j, p + 9); } } } } /* not checked */ /* Pawn promotions? */ t = s->pm[0]; if (t != 0) { /* if there is at least one pawn on the board */ int move; /* Is any piece on a destination square >= A8 a pawn? */ for (move = 0; move < nmoves; ++move) { if ((moves[move].dest >= A8) && (fig[moves[move].index] == PAWN)) { ADDMOVE (moves[move].index, moves[move].dest - 24); ADDMOVE (moves[move].index, moves[move].dest - 32); ADDMOVE (moves[move].index, moves[move].dest - 40); moves[move].dest -= 16; /* Make that a 'backward' * move */ } } } } if (nmoves > 0) return nmoves; return pos_giving_check >= A1 ? MVGEN_MATE : MVGEN_STALE_MATE; /* stale mate if not checked */ } __inline static lbitvec move2bits (unsigned char board[64], int type, int from, int d) /* * Return a bitwise encoded move composed from knowledge of the board, * the type of piece that moves, its from and destination squares. * (Note that d IS the actual destination for pawn promotions, this * function is only called by ismate() where it is not of importance * what piece type the pawn is promoted to, so we use queens.) */ { lbitvec mv = type; /* return value, to be completed */ if (type == pawn) { /* A pawn of either colour */ if (board[from] & WHITE) { /* White pawn */ if (from > H6) { /* It's a white pawn promotion */ mv |= queen << 16; } else if (COL (from) != COL (d) && board[d] == FREE) { /* En Passant */ mv |= MV_EP | MV_CAPT; } } else { /* Black pawn */ if (from < A3) { /* It's a black pawn promotion */ mv |= queen << 16; } else if (COL (from) != COL (d) && board[d] == FREE) { /* En Passant */ mv |= MV_EP | MV_CAPT; } } /* Black pawn */ } /* Any move to an occupied square is a capture */ if (board[d] != FREE) { mv |= MV_CAPT; } return mv |= from << 3 | d << 10; } int ismate (State * s, const int pos_giving_check, lbitvec * esc) /* * Test if side to move is mate and return as soon as a move is found. * Returns ISMATE_YES for mate, ISMATE_STALE_MATE for stale mate and ISMATE_NO * when escape possible. * In the last case, the escape move is written to '*esc'. * Parameter 'pos_giving_check' has the position of a checking piece or -1. * This function is nearly the same as 'movegen'. */ { unsigned char *ppos, *pdir, *board = s->brd; int current, start; unsigned t; unsigned char *pos, *fig; int j; int i; if (BLACK_TO_MOVE) { pos = s->pos[1]; fig = s->fig[1]; if (pos_giving_check >= A1) { /* white shouts "check!" */ int *set; /* Two ways to handle check: 1) move king out of check 2) move * another untrapped piece on one of the squares in the direction * from our king up to the square of the checker. */ /* 1) Find all moves out of check (includes king capturing) */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !IS_BLACK (board[current])) { *esc = move2bits (board, king, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); if (attacked[start] > 1) { /* start = kpos, double check */ /* we _must_ move our king, other moves impossible, return */ return ISMATE_YES; /* we're mate */ } /* okay, single check */ /* the king's moves are done now, if it's the only piece, return */ if (s->n[1] == 1) return ISMATE_YES; /* we're mate */ /* 2) move another untrapped piece on one of the squares in the * direction from our king up to the square of the checker. */ /* okay, there are some other pieces on the board. We are only * interested in moves that either - capture the piece we are * checked by. These are the only moves if checked by P or N - or * will block check These are only possible if checked by Q, R or * B. That means the possible destinations are a small set of * squares with one element for P, N or adjacent Q, R or B - and * with more for non-adjacent Q, R or B. */ t = bgettrapped (s); set = destset (board, start, pos_giving_check, &j); /* find all moves to any position in set[] */ do { /* set[j] */ --j; for (i = s->n[1] - 1; i != 0; --i) { /* Can fig[i] move to position set[j]? Skip trapped * pieces and pieces that can't reach position set[j]. */ if (bit[i] & t) continue; /* trapped */ if (fig[i] != PAWN && !ok[code[fig[i]]][pos[i]][set[j]]) continue; /* can't reach set[j] */ if (fig[i] == PAWN) { if (pos[i] == set[j] + 8 && board[set[j]] == FREE) { /* single advance */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } if (pos[i] == set[j] + 16 && pos[i] >= A7 && board[pos[i] - 8] == FREE && board[set[j]] == FREE) { /* 2 steps from home */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } /* A capturing pawn must capture the checking piece */ if (COL (pos[i]) != 0) { if (set[j] == pos[i] - 9 && board[set[j]] != FREE) { /* capture to a - g */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } if (set[j] == pos[i] - 1 && set[j] == (s->sp & SP_EP_POS)) { /* ep to a - g */ *esc = move2bits (board, pawn, pos[i], pos[i] - 9); return ISMATE_NO; } } if (COL (pos[i]) != 7) { if (set[j] == pos[i] - 7 && board[set[j]] != FREE) { /* capture to b - h */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } if (set[j] == pos[i] + 1 && set[j] == (s->sp & SP_EP_POS)) { /* ep to b - h */ *esc = move2bits (board, pawn, pos[i], pos[i] - 7); return ISMATE_NO; } } } else { /* not pawn, i.e. n,b,r,q */ start = pos[i]; ppos = nextpos[code[fig[i]]][start]; pdir = nextdir[code[fig[i]]][start]; current = ppos[start]; do { if (current == set[j]) { *esc = move2bits (board, code[fig[i]], start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); } } } while (j != 0); } else { /* our king is not checked */ /* King may move to any non-attacked square that is not occupied * by some piece of his color and may castle */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !(board[current] & BLACK)) { *esc = move2bits (board, king, start, current); return ISMATE_NO; } current = pdir[current]; /* king has only range 1, so * pdir */ } while (current != start); /* We do not need to check for castling, because if it were * allowed then another king move is also possible and we have * returned already ... * * So much for the king ... */ if (s->n[1] == 1) /* stale mate if there are no other pieces */ return ISMATE_STALE_MATE; t = bgettrapped (s); for (j = s->n[1] - 1; j != 0; --j) { /* black non kings */ int p; /* 0 .. 63 */ switch (fig[j]) { case KNIGHT: /* if a knight is trapped, it can't move at all */ if (t & bit[j]) break; /* switch */ start = pos[j]; ppos = nextpos[knight][start]; pdir = nextdir[knight][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) { *esc = move2bits (board, knight, start, current); return ISMATE_NO; } current = pdir[current]; /* knight has only range * 1 */ } while (current != start); break; case ROOK: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a rook is trapped it can only move if the trap * direction is not diagonal */ if (diag[dir & 15]) break; /* switch */ /* A move away from the king (+dir) */ p = pos[j]; *esc = move2bits (board, rook, p, p + dir); return ISMATE_NO; } start = pos[j]; ppos = nextpos[rook][start]; pdir = nextdir[rook][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) { *esc = move2bits (board, rook, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case BISHOP: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a bishop is trapped it can only move if the * trap direction is diagonal */ if (!diag[dir & 15]) break; /* switch */ /* A move away from the king (+dir) */ p = pos[j]; *esc = move2bits (board, bishop, p, p + dir); return ISMATE_NO; } start = pos[j]; ppos = nextpos[bishop][start]; pdir = nextdir[bishop][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) { *esc = move2bits (board, bishop, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case QUEEN: if (t & bit[j]) { int dir = trap[pos[0]][pos[j]]; /* A move away from the king (+dir) */ p = pos[j]; *esc = move2bits (board, queen, p, p + dir); return ISMATE_NO; } start = pos[j]; ppos = nextpos[queen][start]; pdir = nextdir[queen][start]; current = ppos[start]; do { if (!(board[current] & BLACK)) { *esc = move2bits (board, queen, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case PAWN: if (t & bit[j]) { /* trapped pawn, no check */ int dir = trap[pos[0]][pos[j]]; if (dir == 1 || dir == -1 || dir == 7 || dir == 9) { /* horizontal trap or backward diag: no moves */ break; /* switch */ } else if (!(dir & 1)) { /* 8 or -8 */ /* vertical trap: advance */ p = pos[j]; if (board[p - 8] == FREE) { /* single step */ *esc = move2bits (board, pawn, p, p - 8); return ISMATE_NO; } } else { /* Diagonal forward trap, dir == -7 or -9. Move * if attacked square is opponent's piece. It * can't be ours, 'cos then it were no trap! */ p = pos[j]; if (board[p + dir] != FREE) { *esc = move2bits (board, pawn, p, p + dir); return ISMATE_NO; } } break; /* switch */ } /* not trapped */ p = pos[j]; if (board[p - 8] == FREE) { /* single step */ *esc = move2bits (board, pawn, p, p - 8); return ISMATE_NO; } if (COL (p) > 0) { if (IS_WHITE (board[p - 9]) || ((s->sp & SP_EP_POS) == p - 1 && bep_ok (p, p - 1, pos[0], board))) { /* capture or ep to a - g */ *esc = move2bits (board, pawn, p, p - 9); return ISMATE_NO; } } if (COL (p) < 7) { if (IS_WHITE (board[p - 7]) || ((s->sp & SP_EP_POS) == p + 1 && bep_ok (p, p + 1, pos[0], board))) { /* capture or ep to b - h */ *esc = move2bits (board, pawn, p, p - 7); return ISMATE_NO; } } } } } /* not checked */ } else { /* white to move */ pos = s->pos[0]; fig = s->fig[0]; if (pos_giving_check >= A1) { /* black shouts "check!" */ int *set; /* Two ways to handle check: 1) move king out of check 2) move * another untrapped piece on one of the squares in the direction * from our king up to the square of the checker. */ /* 1) Find all moves out of check (includes king capturing) */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !IS_WHITE (board[current])) { *esc = move2bits (board, king, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); if (attacked[start] > 1) { /* start = kpos, double check */ /* we _must_ move our king, other moves impossible, return */ return ISMATE_YES; /* we're mate */ } /* okay, single check */ /* the king's moves are done now, if it's the only piece, return */ if (s->n[0] == 1) return ISMATE_YES; /* we're mate */ /* 2) move another untrapped piece on one of the squares in the * direction from our king up to the square of the checker. */ /* okay, there are some other pieces on the board. We are only * interested in moves that either - capture the piece we are * checked by. These are the only moves if checked by P or N - or * will block check These are only possible if checked by Q, R or * B. That means the possible destinations are a small set of * squares with one element for P, N or adjacent Q, R or B - and * with more for non-adjacent Q, R or B. */ t = wgettrapped (s); set = destset (board, start, pos_giving_check, &j); /* find all moves to any position in set[] */ do { /* set[j] */ --j; for (i = s->n[0] - 1; i != 0; --i) { /* Can fig[i] move to position set[j]? Skip trapped * pieces and pieces that can't reach position set[j]. */ if (bit[i] & t) continue; /* trapped */ if (fig[i] != PAWN && !ok[code[fig[i]]][pos[i]][set[j]]) continue; /* can't reach set[j] */ if (fig[i] == PAWN) { if (pos[i] == set[j] - 8 && board[set[j]] == FREE) { /* single advance */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } if (pos[i] == set[j] - 16 && pos[i] <= H2 && board[pos[i] - 8] == FREE && board[set[j]] == FREE) { /* 2 steps from home */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } /* A capturing pawn must capture the checking piece */ if (COL (pos[i]) != 0) { if (set[j] == pos[i] + 7 && board[set[j]] != FREE) { /* capture to a - g */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } if (set[j] == pos[i] - 1 && set[j] == (s->sp & SP_EP_POS)) { /* ep to a - g */ *esc = move2bits (board, pawn, pos[i], pos[i] + 7); return ISMATE_NO; } } if (COL (pos[i]) != 7) { if (set[j] == pos[i] + 9 && board[set[j]] != FREE) { /* capture to b - h */ *esc = move2bits (board, pawn, pos[i], set[j]); return ISMATE_NO; } if (set[j] == pos[i] + 1 && set[j] == (s->sp & SP_EP_POS)) { /* ep to b - h */ *esc = move2bits (board, pawn, pos[i], pos[i] + 9); return ISMATE_NO; } } } else { /* not pawn, i.e. n,b,r,q */ start = pos[i]; ppos = nextpos[code[fig[i]]][start]; pdir = nextdir[code[fig[i]]][start]; current = ppos[start]; do { if (current == set[j]) { *esc = move2bits (board, code[fig[i]], start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else /* not free */ current = pdir[current]; } while (current != start); } } } while (j != 0); } else { /* our king is not checked */ /* King may move to any non-attacked square that is not occupied * by some piece of his color and may castle */ start = pos[0]; ppos = nextpos[king][start]; pdir = nextdir[king][start]; current = ppos[start]; do { if (!attacked[current] && !(board[current] & WHITE)) { *esc = move2bits (board, king, start, current); return ISMATE_NO; } current = pdir[current]; /* king has only range 1, so * pdir */ } while (current != start); /* We do not need to check for castling, because if it were * allowed then another king move is also possible and we have * returned already ... * * So much for the king ... */ if (s->n[0] == 1) /* stale mate if there are no other pieces */ return ISMATE_STALE_MATE; t = wgettrapped (s); for (j = s->n[0] - 1; j != 0; --j) { /* white non kings */ int p; /* 0 .. 63 */ switch (fig[j]) { case KNIGHT: /* if a knight is trapped, it can't move at all */ if (t & bit[j]) break; /* switch */ start = pos[j]; ppos = nextpos[knight][start]; pdir = nextdir[knight][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) { *esc = move2bits (board, knight, start, current); return ISMATE_NO; } current = pdir[current]; /* knight has only range * 1 */ } while (current != start); break; case ROOK: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a rook is trapped it can only move if the trap * direction is not diagonal */ if (diag[dir & 15]) break; /* switch */ /* A move away from the king (+dir) */ p = pos[j]; *esc = move2bits (board, rook, p, p + dir); return ISMATE_NO; } start = pos[j]; ppos = nextpos[rook][start]; pdir = nextdir[rook][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) { *esc = move2bits (board, rook, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case BISHOP: if (t & bit[j]) { int dir; dir = trap[pos[0]][pos[j]]; /* if a bishop is trapped it can only move if the * trap direction is diagonal */ if (!diag[dir & 15]) break; /* switch */ /* A move away from the king (+dir) */ p = pos[j]; *esc = move2bits (board, knight, p, p + dir); return ISMATE_NO; } start = pos[j]; ppos = nextpos[bishop][start]; pdir = nextdir[bishop][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) { *esc = move2bits (board, bishop, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case QUEEN: if (t & bit[j]) { int dir = trap[pos[0]][pos[j]]; /* A move away from the king (+dir) */ p = pos[j]; *esc = move2bits (board, knight, p, p + dir); return ISMATE_NO; } start = pos[j]; ppos = nextpos[queen][start]; pdir = nextdir[queen][start]; current = ppos[start]; do { if (!(board[current] & WHITE)) { *esc = move2bits (board, queen, start, current); return ISMATE_NO; } if (board[current] == FREE) current = ppos[current]; else current = pdir[current]; } while (current != start); break; case PAWN: if (t & bit[j]) { /* trapped pawn, no check */ int dir = trap[pos[0]][pos[j]]; if (dir == 1 || dir == -1 || dir == -7 || dir == -9) { /* horizontal trap or backward diag: no moves */ break; /* switch */ } else if (!(dir & 1)) { /* 8 or -8 */ /* vertical trap: advance */ p = pos[j]; if (board[p + 8] == FREE) { /* single step */ *esc = move2bits (board, pawn, p, p + 8); return ISMATE_NO; } } else { /* Diagonal forward trap, dir == 7 or 9. Move if * attacked square is opponent's piece. It can't * be ours, 'cos then it were no trap! */ p = pos[j]; if (board[p + dir] != FREE) { *esc = move2bits (board, pawn, p, p + dir); return ISMATE_NO; } } break; /* switch */ } /* not trapped */ p = pos[j]; if (board[p + 8] == FREE) { /* single step */ *esc = move2bits (board, pawn, p, p + 8); return ISMATE_NO; } if (COL (p) > 0) { if (IS_BLACK (board[p + 7]) || ((s->sp & SP_EP_POS) == p - 1 && wep_ok (p, p - 1, pos[0], board))) { /* capture or ep to a - g */ *esc = move2bits (board, pawn, p, p + 7); return ISMATE_NO; } } if (COL (p) < 7) { if (IS_BLACK (board[p + 9]) || ((s->sp & SP_EP_POS) == p + 1 && wep_ok (p, p + 1, pos[0], board))) { /* capture or ep to b - h */ *esc = move2bits (board, pawn, p, p + 9); return ISMATE_NO; } } } } } /* not checked */ } /* if more than an immobile unchecked king, still no moves: stale mate */ return pos_giving_check >= A1 ? ISMATE_YES : ISMATE_STALE_MATE; }