/* vim:set ts=2 sw=2: */ /* * $Id: main.c,v 1.9 1997/05/29 16:30:28 schweikh Exp $ */ #ifdef POSIX #define _POSIX_SOURCE #include /* alarm */ #include /* SIGUSR1 */ #include /* setjmp */ #endif #include /* printf */ #include /* qsort */ #include /* strrchr */ #include "alloc.h" #include "attack.h" #include "board.h" #include "chess.h" #include "config.h" #include "error.h" #include "fgetline.h" #include "init.h" #include "initlang.h" #include "movegen.h" #include "options.h" #include "shutup.h" #include "timing.h" /*@-fullinitblock@ */ /*@-type@ */ static struct { /* command line options */ unsigned first_mv_only: 1; unsigned all_moves: 1; unsigned dump_moves: 1; unsigned dump_positions: 1; unsigned test_checks: 1; unsigned skip_checks: 1; unsigned test_ismate: 1; unsigned quiet: 1; unsigned show_escapes: 1; unsigned no_timing: 1; unsigned alarm: 1; unsigned sort_distance: 1; } opt; static unsigned first_move; /* Index of first move that mates */ static signed char first_move_from = -1; /* user supplied from cmdline */ static signed char first_move_to = -1; /* -1: none supplied */ static int mate_in = 0; /* # of mvs to mate in or INPUT_ERROR */ static int n_moves_max = 0, xn_moves_max = 0; static unsigned n_first_moves; /* Number of first moves */ static int trace_move_depth = 0; /* >0 when supplied */ #ifdef POSIX static unsigned alarm_time = 0; /* argument of option */ static jmp_buf jmp_env; static volatile sig_atomic_t time_expired = 0; /* non-zero when time expired */ #define CHECK_ALARM if (time_expired) longjmp (jmp_env, 1); #else /* not POSIX */ #define CHECK_ALARM /* nothing */ #endif /* not POSIX */ /* Return values of checks() */ enum { NOT_CHECKED, SINGLE_CHECK, DOUBLE_CHECK }; /* An array to initialize newly allocated move arrays from. */ static Mlist null_move_array[MAX_MOVES] = { {0} }; typedef struct cache { int entries; /* 0 .. MOVE_CACHE_SIZE - 1 */ move_t move[MOVE_CACHE_SIZE]; /* The actual moves */ long hits[MOVE_CACHE_SIZE]; /* How often each move * occured before */ } cache; /* * Pointers to the caches of mating moves (for the attacker) * and to escape moves (for the defender). */ static cache *mating_moves = NULL; static cache *escape_moves = NULL; /*____________________________________________________________________________ * PROTOTYPES */ static void add_move_to_cache (const move_t * const, cache * const); static void allocate_move_cache (void); static int cmp_moves (const void *, const void *); static void free_move_cache (void); static bool mate (int, Mlist * const, State); static void merge_cache (move_t *, int, const cache *); static void print_notation (lbitvec); static void process_options (int, char **); static void show_move_tree (Mlist *, unsigned, unsigned char, unsigned char); static void solve_one_problem (char *); static void sort_by_answers_on_moves (move_t *, int, State *, int); static void sort_by_distance_to_king (move_t *, int, unsigned char); static void sort_move_tree (Mlist *); static void usage (void); #ifdef POSIX static void print_current_move (int); static void alarm_handler (int); static void install_signal_handlers (void); static handler_t * reliable_signal (int, handler_t *); #endif /* POSIX */ /*____________________________________________________________________________ * */ #ifdef POSIX static void alarm_handler (int signum) { ++time_expired; } static void print_current_move (int signum) /* * Print the current outermost move. Invoked on SIGUSR1. */ { Fprintf (stderr, "%d/%d\n", first_move + 1, n_first_moves); Fflush (stderr); } static void install_signal_handlers (void) { check_sys (reliable_signal (SIGUSR1, print_current_move) != SIG_ERR); check_sys (reliable_signal (SIGALRM, alarm_handler) != SIG_ERR); } /* Install a handler which remains installed */ static handler_t * reliable_signal (int sig, handler_t * handler) { struct sigaction action, old_action; action.sa_handler = handler; action.sa_flags = 0; sigemptyset (&action.sa_mask); if (sigaction (sig, &action, &old_action) < 0) return SIG_ERR; return old_action.sa_handler; } #endif /* POSIX */ static void free_list (Mlist * const p) /* * Free a part of a move list tree beginning with node p, * which should be the beginning of an Mlist array. */ { Mlist *tmp = p; /* free all leaf nodes, then free node itself. */ #if SANITY_CHECKS unsigned j = 0; if (p == 0) Printf ("OOPS: p == 0 in free_list\n"); do { if (tmp->answer != 0) free_list (tmp->answer); if (++j > 100) err_quit ("OOPS? no null move after %u elements starting with %p\n", j, (void *) p); } while ((++tmp)->mv != 0); #else /* not SANITY_CHECKS */ do { if (tmp->answer != 0) free_list (tmp->answer); /* the leaf nodes first */ } while ((++tmp)->mv != 0); #endif /* not SANITY_CHECKS */ xfree (p); /* The node itself */ } static void dump_positions (State * s) { int i, n; unsigned char *pos, *fig; pos = s->pos[0]; fig = s->fig[0]; n = s->n[0]; if (n == 0 || n > 16) err_quit ("OOPS: white n = %d", (int) n); Printf ("W: n = %d : ", (int) n); for (i = 0; i < n; ++i) Printf ("%c%s%c", pchar[code[fig[i]]], pos2string (pos[i]), i == n - 1 ? '\n' : ' '); pos = s->pos[1]; fig = s->fig[1]; n = s->n[1]; if (n == 0 || n > 16) err_quit ("OOPS: black n = %d", (int) n); Printf ("B: n = %d : ", (int) n); for (i = 0; i < n; ++i) Printf ("%c%s%c", pchar[code[fig[i]]], pos2string (pos[i]), i == n - 1 ? '\n' : ' '); } static int compare (const void *a, const void *b) /* * Compare function for qsort, returns -1 for *a < *b etc. * (Used by dump_moves). */ { if (*(unsigned *) a == *(unsigned *) b) return 0; return *(unsigned *) a < *(unsigned *) b ? -1 : 1; } static void dump_moves (State * s, const int n, const move_t * mvs) /* * Dump possible moves. Primary sort key: source, secondary: dest. * n is the size of mvs[], that is, the number of moves * or -1 for stale mate. mvs[] holds the moves as filled in * by movegen(). */ { int src, dest; int N = n, indx; unsigned char *pos; unsigned srt[MAX_MOVES]; Printf ("%d\n", (int) n); if (n < 1) { return; } if (BLACK_TO_MOVE) pos = s->pos[1]; else pos = s->pos[0]; #if 0 Printf ("mvs[%d] = ", (int) n); for (indx = 0; indx != (unsigned) n; ++indx) Printf ("%d %s%c", (int) mvs[indx].index, pos2string (mvs[indx].dest), indx == n - 1 ? '\n' : ' '); #endif do { --N; dest = mvs[N].dest; src = pos[mvs[N].index]; srt[N] = (src << 6) + dest; } while (N != 0); qsort (srt, n, sizeof *srt, compare); for (indx = 0; indx < n; ++indx) { Printf ("%s-", pos2string (srt[indx] >> 6)); Printf ("%s\n", pos2string (srt[indx] & 077)); } } __inline static void merge_cache (move_t * m, int n, const cache * c) /* * Merge the 'n' moves from the move array 'm' with the cache 'c'. * Because 'm' is processed from last to first element, the move * with the largest number of cache hits is placed at the *end* of 'm'. */ { int i; for (i = c->entries - 1; i >= 0; --i) { /* for each move in the cache, beginning with the last one */ int j; move_t mv = c->move[i]; for (j = n - 1; j >= 0; --j) { if (m[j].index == mv.index && m[j].dest == mv.dest) { /* Yes, that move is move in 'm' */ Memmove (m + j, m + j + 1, (n - j - 1) * sizeof *m); m[n - 1] = mv; #if 0 Printf ("merging move to %s\n", pos2string (mv.dest)); #endif break; } } } } __inline static void add_move_to_cache (const move_t * const m, cache * const c) { int i; #if 0 Printf ("add_move_to_cache %s\n", pos2string (m->dest)); #endif /* is the move 'm' already in the cache? */ for (i = c->entries - 1; i >= 0; --i) { if (m->index == c->move[i].index && m->dest == c->move[i].dest) { /* Yes, increment the number of hits */ ++(c->hits[i]); if (i > 0 && c->hits[i] > c->hits[i - 1]) { /* swap them to keep the hits in ascending order */ long t = c->hits[i]; c->hits[i] = c->hits[i - 1]; c->hits[i - 1] = t; } return; } } /* No, insert at the end of the list or overwrite last element */ if (c->entries < MOVE_CACHE_SIZE) { /* insert */ c->move[c->entries] = *m; ++c->entries; } else { /* overwrite */ c->move[MOVE_CACHE_SIZE - 1] = *m; } } __inline static int checks (State * s) /* * Return the number of pieces giving check to the party to move. */ { unsigned char *fig, *pos; int kpos, n, n_check = 0; if (BLACK_TO_MOVE) { kpos = s->pos[1][0]; fig = s->fig[0]; pos = s->pos[0]; if ((n = s->n[0]) == 1) return NOT_CHECKED; /* White has just a king */ do { --n; if (fig[n] == PAWN) { if (COL (pos[n]) > 0 && kpos == pos[n] + 7) return SINGLE_CHECK; /* Can't be double check */ if (COL (pos[n]) < 7 && kpos == pos[n] + 9) return SINGLE_CHECK; } else { /* Not PAWN */ if (ok[code[fig[n]]][pos[n]][kpos]) { /* If piece can attack * king */ if (fig[n] == KNIGHT) { ++n_check; } else if (dist[pos[n]][kpos] == 1) { ++n_check; } else { unsigned char *board = s->brd; int p; signed char dir = off[pos[n]][kpos]; for (p = pos[n] + dir; p != kpos; p += dir) if (board[p] != FREE) goto next_iteration_b; /* break 2 */ ++n_check; } } } next_iteration_b:; } while (n != 1); } else { kpos = s->pos[0][0]; fig = s->fig[1]; pos = s->pos[1]; if ((n = s->n[1]) == 1) return NOT_CHECKED; /* Black has just a king */ do { --n; if (fig[n] == PAWN) { if (COL (pos[n]) > 0 && kpos == pos[n] - 9) return SINGLE_CHECK; /* Can't be double check */ if (COL (pos[n]) < 7 && kpos == pos[n] - 7) return SINGLE_CHECK; } else { /* Not PAWN */ if (ok[code[fig[n]]][pos[n]][kpos]) { /* If piece can attack * king */ if (fig[n] == KNIGHT) { ++n_check; } else if (dist[pos[n]][kpos] == 1) { ++n_check; } else { unsigned char *board = s->brd; signed char dir = off[pos[n]][kpos]; int p; for (p = pos[n] + dir; p != kpos; p += dir) if (board[p] != FREE) goto next_iteration_w; /* break 2 */ ++n_check; } } } next_iteration_w:; } while (n != 1); } return n_check; } static void usage (void) { Fprintf (stderr, "\nusage: "); err_progname (); Fprintf (stderr, " [-1aCcdeIMqPt] [-A seconds] [-f move]\n" "\t[-l file] [-T depth]\n" "\n" "\t-1 exit after one solution is found\n" "\t-A stop solving after this many seconds\n" "\t-a find all possible second and further moves not just the first\n" "\t-C print only the number of checks for a position (debugging)\n" "\t-c skip tests for check, double check and stale mate\n" "\t-d sort moves by distance to king\n" "\t-e show escape move tree\n" "\t-f try this move first, e.g. e2-e4\n" "\t-I print only the result of the ismate function (debugging)\n" "\t-l load language information from this file\n" "\t-M print only the possible moves (debugging)\n" "\t-q don't print statistics\n" "\t-P print only the position (debugging)\n" "\t-t don't print timing information\n" "\t-T trace the move tree up to this depth\n" "\n" " Compile time options:\n"); #if POSIX Fprintf (stderr, " POSIX - Alarm option and SIGUSR1 to print current move\n"); #endif #if SANITY_CHECKS Fprintf (stderr, " SANITY_CHECKS - Test certain data structures for consistency\n"); #endif #if DEBUG_ALLOCATIONS Fprintf (stderr, " DEBUG_ALLOCATIONS - Print information about each (de)allocation\n"); #endif #if DEBUG_TREE Fprintf (stderr, " DEBUG_TREE - Print the move tree data in a semi binary format\n"); #endif #if HAVE_GETRUSAGE Fprintf (stderr, " HAVE_GETRUSAGE - prefer getrusage() over clock() for timing\n"); #endif } static void process_options (int argc, char **argv) /* * parse the command line switches */ { int c; opt_err = 0; while ((c = get_opt (argc, argv, "1A:aCcdef:Il:MqPtT:")) != EOF) { switch (c) { case '1': opt.first_mv_only = 1; break; case 'A': #ifdef POSIX if (sscanf (opt_arg, "%u", &alarm_time) != 1) err_quit ("invalid alarm timer value"); opt.alarm = 1; #else err_msg ("timer not supported (needs POSIX) -- option ignored"); #endif break; case 'a': opt.all_moves = 1; break; case 'C': opt.test_checks = 1; break; case 'c': opt.skip_checks = 1; break; case 'd': opt.sort_distance = 1; break; case 'e': opt.show_escapes = 1; break; case 'f': { unsigned char from_col, from_row, to_col, to_row; if (sscanf (opt_arg, "%c%c-%c%c", &from_col, &from_row, &to_col, &to_row) != 4) err_quit ("-f %s: invalid first move", opt_arg); first_move_from = from_col - 'a' + 8 * (from_row - '1'); first_move_to = to_col - 'a' + 8 * (to_row - '1'); if (first_move_from > 63 || first_move_to > 63 || first_move_from < 0 || first_move_to < 0) err_quit ("-f %s: invalid first move", opt_arg); } break; case 'I': opt.test_ismate = 1; break; case 'l': Initialize_language (opt_arg); break; case 'M': opt.dump_moves = 1; break; case 'P': opt.dump_positions = 1; break; case 'q': opt.quiet = 1; break; case 't': opt.no_timing = 1; break; case 'T': if (sscanf (opt_arg, "%d", &trace_move_depth) != 1 || trace_move_depth < 1) err_quit ("-T %s: positive trace value expected\n", opt_arg); /* A trace is wanted when trace_move_depth > 0 */ break; default: usage (); exit (EXIT_FAILURE); } } } __inline static lbitvec move_pieces (unsigned char *board, unsigned *sp, int type, int from, int d) /* * Move pieces on the board. Index i (0-15), destination d (0-63), * pointer to special information (castling ep position) sp, * type is QUEEN, not queen etc. * Returns a move (except for the bits check, double, mate, stale, * which are set in the next depth level) and adjusts *sp. */ { lbitvec mv = code[type]; /* return value */ int to; /* 0 .. 63 */ *sp &= ~SP_EP_POS; /* clear old ep position */ if (type & PAWN) { /* a pawn */ if (board[from] & WHITE) { /* white pawn */ if (from > H6) { /* it's a white pawn promotion */ to = A8 + COL (d); /* ROW (d) = 2..5 = n,b,r,q Promote right now: */ board[from] = bit[ROW (d)] | WHITE; mv |= ROW (d) << 16; } else if (COL (from) != COL (d) && board[d] == FREE) { /* en passant */ to = d; board[d - 8] = FREE; /* remove captured piece */ mv |= MV_EP | MV_CAPT; } else { /* not (promotion|ep) */ to = d; } } else { /* black pawn */ if (from < A3) { /* it's a black pawn promotion */ to = COL (d); /* ROW (d) = 2..5 = n,b,r,q Promote right now: */ board[from] = bit[ROW (d)] | BLACK; mv |= ROW (d) << 16; } else if (COL (from) != COL (d) && board[d] == FREE) { /* en passant */ to = d; board[d + 8] = FREE; /* remove captured piece */ mv |= MV_EP | MV_CAPT; } else { /* not (promotion|ep) */ to = d; } } /* black pawn */ if (dist[from][to] == 2) *sp |= to; /* set new ep position */ } else if (type == KING && dist[from][d] == 2) { /* castles, move the rook now */ switch (d) { case G1: board[H1] = FREE; board[F1] = (WHITE | ROOK); *sp &= ~(SP_O_O | SP_O_O_O); break; case C1: board[A1] = FREE; board[D1] = (WHITE | ROOK); *sp &= ~(SP_O_O | SP_O_O_O); break; case G8: board[H8] = FREE; board[F8] = (BLACK | ROOK); *sp &= ~(SP_o_o | SP_o_o_o); break; case C8: board[A8] = FREE; board[D8] = (BLACK | ROOK); *sp &= ~(SP_o_o | SP_o_o_o); break; } to = d; } else { /* no (ep|promotion|castle) */ to = d; } /* Void castling possiblities if rook moves */ if (type == ROOK) { /* don't care for BLACK or WHITE */ switch (from) { case A1: *sp &= ~SP_O_O_O; break; case H1: *sp &= ~SP_O_O; break; case A8: *sp &= ~SP_o_o_o; break; case H8: *sp &= ~SP_o_o; break; } } /* Any move to an occupied square is a capture */ if (board[to] != FREE) { mv |= MV_CAPT; } board[to] = board[from]; board[from] = FREE; return mv | from << 3 | to << 10; } static __inline void print_notation (lbitvec move) /* * Print a move in human readable form. */ { lbitvec t; int i; char s[sizeof "Pa4xb5ep+"]; /* 10, this is the longest * string */ /* encoding of move: LSB 3 bit (shift 0) piece type that moves 6 bit * (shift 3) from position 1 bit (shift 9) capture 6 bit (shift 10) to * position 3 bit (shift 16) piece type after promotion 1 bit (shift 19) * en passant 1 bit (shift 20) check 1 bit (shift 21) double check 1 bit * (shift 22) mate 1 bit (shift 23) stale mate 1 bit (shift 24) this move * allows a forced mate later on MSB Total: 25 bits used */ /* Special cases first: castling */ t = move & 0177777; if (t == ((G1 << 10) | (E1 << 3) | king)) { Sprintf (s, "O-O"); move >>= 16; } else if (t == ((C1 << 10) | (E1 << 3) | king)) { Sprintf (s, "O-O-O"); move >>= 16; } else if (t == ((C8 << 10) | (E8 << 3) | king)) { Sprintf (s, "o-o-o"); move >>= 16; } else if (t == ((G8 << 10) | (E8 << 3) | king)) { Sprintf (s, "o-o"); move >>= 16; } else { s[0] = pchar[move & 7]; /* piece type */ move >>= 3; Sprintf (s + 1, "%s", pos2string (move & 63)); move >>= 6; s[3] = move & 1 ? M.cp : M.mv; move >>= 1; Sprintf (s + 4, "%s", pos2string (move & 63)); move >>= 6; } i = 0; while (s[i]) /* advance i on \0 */ ++i; /* pawn promotion? */ if (move & 7) s[i++] = pchar[move & 7]; move >>= 3; /* en passant? */ if (move & 1) { s[i++] = 'e'; /* hardcoded characters to avoid trouble */ s[i++] = 'p'; /* with s[] being to small */ } move >>= 1; /* check? */ if (move & 1) s[i++] = M.ch; move >>= 1; /* double check? */ if (move & 1) s[i++] = M.db; move >>= 1; /* mate? */ if (move & 1) s[i++] = M.mt; move >>= 1; /* stale mate? */ if (move & 1) s[i++] = M.st; s[i++] = '\0'; Printf ("%-10s", s); } static int king_pos; /* To pass the king's position to the compare * function */ static int cmp_pos (const void *a, const void *b) { /* void pointers point to move_t */ unsigned char d_pos_a = dist[(int) ((move_t *) a)->dest][king_pos]; unsigned char d_pos_b = dist[(int) ((move_t *) b)->dest][king_pos]; if (d_pos_a < d_pos_b) return 1; else if (d_pos_a > d_pos_b) return -1; /* TODO: Distance to king is the same, compare type of piece, Q has * higher priority than R, B, N, P, K. */ return 0; } static void sort_by_distance_to_king (move_t * mvs, int nmvs, unsigned char kpos) { /* Printf ("Opponent's king on %s\n", pos2string (kpos)); */ king_pos = kpos; qsort (mvs, (size_t) nmvs, sizeof *mvs, cmp_pos); } static bool mate (int n, Mlist * const p, State st) /* * Test for a mate in n moves. Write result to *p. * Return true if mate in n moves can be forced, 0 otherwise. */ { unsigned char *pos, *fig; Mlist *m; int d, i; /* square and piece index loop counts */ int mvcnt; /* loop index that counts moves */ State save; move_t mvs[MAX_MOVES]; int n_moves; int side; unsigned mating = 0; /* # of moves that mate the opponent sooner * or later */ switch (n_moves = movegen (&st, mvs, attacks (&st))) { case MVGEN_STALE_MATE: /* side to move is stale mate */ p->mv = MV_STALE; p->answer = 0; CHECK_ALARM return 0; case MVGEN_MATE: /* side to move is mate */ p->mv = MV_MATE; p->answer = 0; CHECK_ALARM return 0; } /* default: at least one move */ /* We need to allocate a node for every possible move. */ if (n_moves > n_moves_max) n_moves_max = n_moves; m = xmalloc ((n_moves + 1) * sizeof *m); p->answer = memcpy (m, null_move_array, (n_moves + 1) * sizeof *m); /* Test if previous move has set us check or double check. */ if (opt.skip_checks == 0) { switch (checks (&st)) { case NOT_CHECKED: break; case SINGLE_CHECK: p->mv |= MV_CHECK; break; case DOUBLE_CHECK: p->mv |= MV_DOUBLE; break; default: err_quit ("checks not in {0, 1, 2}"); } } /* Okay, there is at least one move for us */ side = (st.sp & SP_BLACK2MV) == SP_BLACK2MV; /* current side to move * 0, 1 */ pos = st.pos[side]; fig = st.fig[side]; st.sp ^= SP_BLACK2MV; /* toggle side to opponent for mate/ismate */ if (n == 1) { /* We found a mating move if for any of our moves the opponent has no * escape. For n == 1 this means that we found a mate if for any of * our moves the opponent is mate immediately. */ /* possible move to escape mate sooner or later */ lbitvec escape; mvcnt = n_moves; if (n == mate_in) { n_first_moves = n_moves; /* Was there a user suggested first move ? */ if (first_move_from >= A1 && first_move_to >= A1) { int cnt; for (cnt = 0; cnt < n_moves; ++cnt) { if (pos[mvs[cnt].index] == (unsigned) first_move_from && mvs[cnt].dest == first_move_to) { move_t tmp = mvs[n_moves - 1]; /* exchange with last * move */ mvs[n_moves - 1] = mvs[cnt]; mvs[cnt] = tmp; break; } } if (cnt == n_moves) err_quit ("-f: invalid or disallowed move"); } } do { /* while (mvcnt != 0) : for all moves */ if (n == mate_in) first_move = n_moves - mvcnt; i = mvs[--mvcnt].index; /* index into fig and pos */ d = mvs[mvcnt].dest; /* destination square */ if (trace_move_depth >= mate_in) /* DEBUG */ Printf ("%*s-%s\n", 2 * mate_in, pos2string (pos[i]), pos2string (d)); save = st; /* save our own state */ /* Move pieces on board and adjust special information on * castling and en passant. */ m->mv = move_pieces (st.brd, &st.sp, fig[i], pos[i], d); /* Recalc pos[], fig[], n[], pm[] and lm[]. */ scan_board (&st); /* opponent's moves */ switch (ismate (&st, attacks (&st), &escape)) { case ISMATE_YES: /* mate */ ++mating; m->mv |= MV_MATE; if (opt.all_moves || (mate_in == 1 && !opt.first_mv_only)) { break; /* switch, you want to find all moves */ } else { goto found_mate_in_1; /* first mate is enough */ } case ISMATE_STALE_MATE: /* stale mate */ m->mv |= MV_STALE; break; case ISMATE_NO: /* Found escape */ /* If we havn't found a mating move yet, record the escape * move if recording them is wanted. */ if (mating == 0 && opt.show_escapes) { Mlist *mp = xmalloc (2 * sizeof *mp); mp->answer = NULL; mp->mv = escape; /* fill the new node */ m->answer = mp; /* link it to caller */ mp[1] = null_move_array[0]; /* sentinel */ } break; #if SANITY_CHECKS default: err_quit ("OOPS: ismate not in {-1, 0, 1}"); #endif } /* recall state */ st = save; ++m; /* point to next array element */ } while (mvcnt != 0); #if SANITY_CHECKS if (m != p->answer + n_moves) Printf ("m != p->answer + n_moves, m = %p, p->answer + %d = %p\n", (void *) m, n_moves, (void *) (p->answer + n_moves)); #endif if (mating == 0) { if (opt.show_escapes) { CHECK_ALARM return 0; } else { /* We don't want escapes recorded, free the whole array m[] */ xfree (p->answer); p->answer = NULL; CHECK_ALARM return 0; } } else { /* found at least one mating move */ /* Free all the nodes that were allocated for escapes and build a * smaller Mlist with only the mating moves then shrink (realloc) * the old list. */ int j, k; found_mate_in_1: /* if gone to this label, mating == 1 */ m = p->answer; /* reset m to first node */ for (j = k = 0; k < n_moves; ++k) { if (m[k].answer != NULL) { xfree (m[k].answer); } else if (m[k].mv & MV_MATE) { m[j].mv = m[k].mv | MV_CANMATE; m[j].answer = NULL; ++j; } /* else it was a stale mate */ } m[mating] = null_move_array[0]; p->answer = xrealloc (m, (mating + 1) * sizeof *m); CHECK_ALARM return 1; } /**************************************************************************/ } else { /* n > 1 */ move_t xmvs[MAX_MOVES]; int xn_moves; State xsave; Mlist *xm; /* We found a mating move if for any of our moves the opponent has no * escape. For n > 1 this means that we found a mate if for any of * our moves the opponent can be forced mate in n-1 moves. */ mvcnt = n_moves; if (opt.sort_distance) { sort_by_distance_to_king (mvs, n_moves, st.pos[side ^ 1][0]); } else { sort_by_answers_on_moves (mvs, n_moves, &st, side); } if (n == mate_in) { n_first_moves = n_moves; /* Was there a user suggested first move ? */ if (first_move_from >= A1 && first_move_to >= A1) { int cnt; for (cnt = 0; cnt < n_moves; ++cnt) { if (pos[mvs[cnt].index] == (unsigned) first_move_from && mvs[cnt].dest == first_move_to) { move_t tmp = mvs[n_moves - 1]; /* exchange with last * move */ mvs[n_moves - 1] = mvs[cnt]; mvs[cnt] = tmp; break; } } if (cnt == n_moves) err_quit ("-f: invalid or disallowed move"); } } if (mate_in > 2 && mate_in > n && mating_moves[n].entries != 0) merge_cache (mvs, n_moves, mating_moves + n); do { /* while (mvcnt != 0) : for all moves */ if (n == mate_in) first_move = n_first_moves - mvcnt; i = mvs[--mvcnt].index; /* index into fig and pos */ d = mvs[mvcnt].dest; /* destination square */ if (n + trace_move_depth > mate_in) Printf ("%*s-%s\n", 2 * (mate_in - n) + 2, pos2string (pos[i]), pos2string (d)); save = st; /* save our own state */ /* Move pieces on board and adjust special information on * castling and en passant. */ m->mv = move_pieces (st.brd, &st.sp, fig[i], pos[i], d); /* Recalc pos[], fig[], n[], pm[] and lm[]. */ scan_board (&st); /* Opponent's moves */ switch (xn_moves = movegen (&st, xmvs, attacks (&st))) { case MVGEN_MATE: /* premature mate */ ++mating; m->mv |= MV_MATE | MV_CANMATE; if (!opt.all_moves) { goto found_mate_in_n; } break; case MVGEN_STALE_MATE: /* stale mate */ m->mv |= MV_STALE; break; default: /* found at least one answer move */ { /* can I mate for any of these answers? */ int D, I; unsigned xmvcnt; Mlist *const xp = m; /* xp points on previous * move */ int xside = side ^ 1; /* toggle side: 0 or 1 */ unsigned char *xpos = st.pos[xside], *xfig = st.fig[xside]; if (xn_moves > xn_moves_max) xn_moves_max = xn_moves; /* Test if outer move has set us check or double check. */ if (!opt.skip_checks) { switch (checks (&st)) { case NOT_CHECKED: break; case SINGLE_CHECK: m->mv |= MV_CHECK; break; case DOUBLE_CHECK: m->mv |= MV_DOUBLE; break; default: err_quit ("checks not in {0, 1, 2}"); } } st.sp ^= SP_BLACK2MV; /* toggle side to first mover */ /* We need to allocate a node for every possible move. */ xm = xmalloc ((xn_moves + 1) * sizeof *xm); xp->answer = memcpy (xm, null_move_array, (xn_moves + 1) * sizeof *xm); xmvcnt = xn_moves; if (opt.sort_distance) { sort_by_distance_to_king (xmvs, xn_moves, st.pos[xside ^ 1][0]); } else { sort_by_answers_on_moves (xmvs, xn_moves, &st, xside); } do { /* while (xmvcnt != 0) : for all xmoves */ I = xmvs[--xmvcnt].index; /* index into fig and * pos */ D = xmvs[xmvcnt].dest; /* destination square */ if (n + trace_move_depth > mate_in) Printf ("%*s-%s\n", 2 * (mate_in - n) + 3, pos2string (xpos[I]), pos2string (D)); xsave = st; /* save opponent's state */ /* Move pieces on board and adjust special * information on castling and en passant. */ xm->mv = move_pieces (st.brd, &st.sp, xfig[I], xpos[I], D); /* Recalc pos[], fig[], n[], pm[] and lm[]. */ scan_board (&st); if (mate (n - 1, xm, st) == 0) { /* no mate */ /* The current move (of the outer loop) allows * the opponent to escape by the current move of * the inner loop. Break inner loop & continue * outer. */ if (!opt.show_escapes) { xm = xp->answer; /* reset xm */ xp->answer = 0; /* tell caller: can't mate */ free_list (xm); } goto next_outer_move; } st = xsave; /* recall opponent's (inner) state */ ++xm; /* point to next array element */ } while (xmvcnt != 0); /* None of the xn_moves inner moves was an escape, that * is, the current outer move can mate. */ #if SANITY_CHECKS if (xm != xp->answer + xn_moves) Printf ("xm != xp->answer + xn_moves, xm = %p, " "xp->answer + %d = %p\n", (void *) xm, xn_moves, (void *) (xp->answer + xn_moves)); #endif xp->mv |= MV_CANMATE; /* tell parent move */ if (mate_in > 2 && mate_in > n) add_move_to_cache (mvs + mvcnt, mating_moves + n); ++mating; if (opt.first_mv_only) { goto found_mate_in_n; } /* TODO: this still seeks all moves when -a given */ if (n != mate_in && !opt.all_moves) { goto found_mate_in_n; } } /* default: xn_moves > 0 */ } /* switch (xn_moves) */ next_outer_move: st = save; /* recall our own (outer) state */ ++m; /* point to next move */ if (n == mate_in && first_move_from >= A1 && first_move_to >= A1) { Printf ("first move %s-%s does not solve in %d\n", pos2string (first_move_from), pos2string (first_move_to), n); exit (EXIT_FAILURE); } } while (mvcnt != 0); #if SANITY_CHECKS if (m != p->answer + n_moves) Printf ("m != p->answer + n_moves, m = %p, p->answer + %d = %p\n", (void *) m, n_moves, (void *) (p->answer + n_moves)); #endif if (mating == 0) { if (!opt.show_escapes) { m = p->answer; p->answer = 0; free_list (m); } CHECK_ALARM return 0; } else { /* found at least one move that can mate * sooner or later */ /* Free all the nodes that were allocated for escapes * (!MV_CANMATE) and build a smaller Mlist with only the moves * that can mate, then shrink (realloc) the old list. */ int j, k; found_mate_in_n: /* if gone to this label, mating == 1 */ m = p->answer; /* reset m to first node */ /* countdown difficult because we need to move things near m[0] */ for (j = k = 0; k < n_moves; ++k) { if (m[k].mv & MV_CANMATE) { m[j].mv = m[k].mv; /* copy to lower index j (noop for * k==j, */ m[j].answer = m[k].answer; /* already freed for k > j) */ ++j; } else if (m[k].answer != NULL) { free_list (m[k].answer); } } m[mating] = null_move_array[0]; p->answer = xrealloc (m, (mating + 1) * sizeof *m); CHECK_ALARM return 1; } } /* if n != 1 */ } static void sort_by_answers_on_moves (move_t * mvs, int n_mvs, State * state, int side) /* * Calculate the number of answers for every move in array mvs. * As this function should only be used by the attacker, a stale * mate (which is undesirable for an attacker wanting to mate) is * treated as allowing a large number of moves instead of 0. * Side is the attacker. * Actually this function may also be used to sort opponents moves. * The rare case of a stale mate will only result in a time penalty * (the stale mating move is taken last when it should be taken first.) */ { static short result[MAX_MOVES]; static move_t xmvs[MAX_MOVES]; unsigned char *pos = state->pos[side], *fig = state->fig[side]; int n; for (n = 0; n < n_mvs; ++n) { unsigned char d = mvs[n].dest; /* destination square */ unsigned char i = mvs[n].index; /* index into fig and pos */ State st = *state; /* Make a scratch copy of the state */ /* Move pieces on board and adjust special information on castling * and en passant. */ (void) move_pieces (st.brd, &st.sp, fig[i], pos[i], d); /* Recalc pos[], fig[], n[], pm[] and lm[]. */ scan_board (&st); /* Opponent's moves */ result[n] = movegen (&st, xmvs, attacks (&st)) / 2; if (result[n] == -1) /* opponent is stale mate */ result[n] = MAX_MOVES; #if 0 Printf ("%3d %s-%s %d", n, pos2string (pos[i]), pos2string (d), result[n]); if (result[n] <= 9) { int k; for (k = 0; k < result[n]; ++k) Printf (" %s-%s", pos2string (st.pos[side ^ 1][xmvs[k].index]), pos2string (xmvs[k].dest)); } Putchar ('\n'); #endif } /* Shellsort mvs[] in descending order using result[] as key */ { int gap, a, b; unsigned char kpos = state->pos[side ^ 1][0]; /* Opponent's king * position */ for (gap = n_mvs; gap > 0; gap /= 2) for (a = gap; a < n_mvs; ++a) for (b = a - gap; b >= 0 && (result[b] < result[b + gap] ? 1 : /* Less moves. Must * swap. */ (result[b] > result[b + gap] ? 0 : /* More moves. Don't * swap. */ /* Same number of moves. Sort by distance to king */ dist[(int) mvs[b].dest][kpos] < dist[(int) mvs[b + gap].dest][kpos]) ); b -= gap) { /* swap result and associated elements in mvs[] */ short tmp = result[b]; move_t temp = mvs[b]; result[b] = result[b + gap]; mvs[b] = mvs[b + gap]; result[b + gap] = tmp; mvs[b + gap] = temp; } } #if 0 for (n = 0; n < n_mvs; ++n) Printf ("%3d %s-%s %d\n", n, pos2string (pos[mvs[n].index], pos2string (mvs[n].dest), result[n])); #endif } #if DEBUG_TREE static void show_move_tree (Mlist * p, unsigned indent, unsigned char n, unsigned char side) /* * Show the move tree starting from some node p. Debugging version. * Start numbering of moves with n. * Initial indentation indent. * The tree is traversed `depth first'. */ { unsigned j; int ind = 0; /* flag != 0: please indent */ if (n > mate_in + 1) { Printf ("OOPS: show_move for depth %u\n", (unsigned) n); return; } if (indent == 0) { /* root node */ if (p->answer == 0) { /* empty root node */ if (p->mv & MV_MATE) { Puts (M.mate); } else if (p->mv & MV_STALE) { Puts (M.stale); } else { err_msg ("empty root node in show_move_tree"); } return; } Printf ("Root node: %p, mv = ", (void *) p); if (p->mv & 7) print_notation (p->mv); else Printf ("%x ", p->mv); Printf ("answer at %p\n", (void *) (p->answer)); p = p->answer; /* start with first leaf node */ } /* Before the next move is output we either print a move number or a * blank. */ if (side == WHITE) { Printf ("%2u. ", (unsigned int) n); indent += 4; } else { /* side == BLACK */ if (indent == 0) { Printf ("1. ... "); indent = 7; } else { Putchar (' '); ++indent; } } do { if (ind) Printf ("%*s", indent, ""); if (p->mv == 0) err_quit ("OOPS: want to call print_notation(0)\n"); Printf ("{%p ", (void *) p); print_notation (p->mv); /* prints 10 characters */ Printf ("a: %p}", (void *) (p->answer)); if (p->answer != 0) { show_move_tree (p->answer, indent + 30, side == WHITE ? n : n + 1, side ^ (WHITE | BLACK)); } else { Putchar ('\n'); } ind |= 1; /* please indent the next time */ } while ((++p)->mv != 0); /* while not last move */ } #else /* not DEBUG_TREE */ static void show_move_tree (Mlist * p, unsigned indent, unsigned char n, unsigned char side) /* * Show the move tree starting from some node p. * Start numbering of moves with n. * Initial indentation indent. * The tree is traversed `depth first'. */ { int ind = 0; /* flag != 0: please indent */ #if SANITY_CHECKS if (n > mate_in + 1) { Printf ("OOPS: show_move for depth %u\n", (unsigned) n); exit (EXIT_FAILURE); } #endif if (indent == 0) { /* root node */ if (p->answer == 0) { /* empty root node */ if (p->mv & MV_MATE) { Puts (M.mate); } else if (p->mv & MV_STALE) { Puts (M.stale); } else { err_msg ("empty root node in show_move_tree"); } return; } p = p->answer; /* start with first leaf node */ } /* Before the next move is output we print either a move number or a * blank. */ if (side == WHITE) { Printf ("%2u. ", (unsigned int) n); indent += 4; } else { /* side == BLACK */ if (indent == 0) { Printf (" 1. ... "); indent = 8; } else { Putchar (' '); ++indent; } } do { if (ind != 0) Printf ("%*s", indent, ""); /* output spaces */ #if SANITY_CHECKS if (p->mv == 0) err_quit ("OOPS: attempt to call print_notation(0)\n"); #endif print_notation (p->mv); /* prints 10 characters */ if (p->answer != NULL) { show_move_tree (p->answer, indent + 10, side == WHITE ? n : n + 1, side ^ (WHITE | BLACK)); } else { Putchar ('\n'); } ind |= 1; /* please indent the next time */ } while ((++p)->mv != 0); /* while not last move */ } #endif /* not DEBUG_TREE */ static int cmp_moves (const void *a, const void *b) { /* for sort_move_tree */ /* select only piece type after move, src, dst position */ lbitvec x = ((Mlist *) a)->mv & 01776770; lbitvec y = ((Mlist *) b)->mv & 01776770; /* adjust positions to sort with the keys 1) src, 2) dst, 3) type */ x = (x >> 16) + ((x >> 7) & 0770) + ((x << 6) & 077000); y = (y >> 16) + ((y >> 7) & 0770) + ((y << 6) & 077000); if (x < y) { return -1; } else if (x > y) { return 1; } else { err_msg ("cmp_moves with equal moves: %08x\n", (unsigned long) x); return 0; } } static void sort_move_tree (Mlist * p) { /* primary key from, secondary to */ size_t num_moves = 0; if (p == NULL) { err_quit ("NULL pointer passed to sort_move_tree\n"); } /* depth first recursion */ do { ++num_moves; /* count moves for the sort that follows */ if (p->answer != NULL) { sort_move_tree (p->answer); } } while ((++p)->mv != 0); p -= num_moves; /* restore p as it was on function entry */ qsort (p, num_moves, sizeof *p, cmp_moves); } int main (int argc, char **argv) { char *input_line; /* setbuf (stdout, NULL); * unbuffered */ initialize (); set_progname (argv[0], "chess"); process_options (argc, argv); #ifdef POSIX install_signal_handlers (); #endif /* POSIX */ while ((input_line = getline ()) != NULL) { solve_one_problem (input_line); free (input_line); } return EXIT_SUCCESS; } static void solve_one_problem (char *input_line) { Mlist root[2]; State start; int has_solution; double start_time = cpu_usage (); mate_in = read_board (input_line, &start); if (mate_in == INPUT_ERROR) { return; } if (opt.dump_moves) { move_t mvs[MAX_MOVES]; int n = movegen (&start, mvs, attacks (&start)); dump_moves (&start, n, mvs); start.sp &= ~SP_EP_POS; start.sp ^= SP_BLACK2MV; n = movegen (&start, mvs, attacks (&start)); dump_moves (&start, n, mvs); return; } if (opt.dump_positions) { dump_positions (&start); return; } if (opt.test_checks) { Printf ("checks () = %u\n", (unsigned) checks (&start)); return; } if (opt.test_ismate) { lbitvec esc; switch (ismate (&start, attacks (&start), &esc)) { case ISMATE_NO: print_notation (esc); Putchar ('\n'); break; case ISMATE_STALE_MATE: Puts (M.stale); break; case ISMATE_YES: Puts (M.mate); break; default: Puts ("OOPS: ismate not in {-1, 0, 1}"); } return; } /* Okay, we have a problem to solve */ if (!opt.quiet) { draw_board (start.brd); tell_special (mate_in, &start); } Memcpy (root, null_move_array, sizeof root); allocate_move_cache (); #ifdef POSIX if (setjmp (jmp_env) == 0) { if (opt.alarm) { alarm (alarm_time); /* switch alarm on */ has_solution = mate (mate_in, root, start); alarm (0); /* switch alarm off */ } else { has_solution = mate (mate_in, root, start); } } else { Printf ("Alarm at %d/%d\n", first_move + 1, n_first_moves); Fflush (stdout); free_list (root->answer); free_move_cache (); if (alloc_free != 0) Printf ("alloc - free = %ld\n", (long) alloc_free); return; } #else /* not POSIX */ has_solution = mate (mate_in, root, start); #endif /* not POSIX */ if (has_solution) { if (opt.no_timing) { Puts (M.solution); } else { Printf ("%s %.2f %d/%d\n", M.solution, cpu_usage () - start_time, (int) first_move + 1, (int) n_first_moves); } sort_move_tree (root); show_move_tree (root, 0, 1, firstmv); free_list (root->answer); } else { /* No solution */ if (opt.no_timing) { Puts (M.no_solution); } else { Printf ("%s %.2f\n", M.no_solution, cpu_usage () - start_time); } if (opt.show_escapes) { sort_move_tree (root); show_move_tree (root, 0, 1, firstmv); free_list (root->answer); } else { Puts ("[use option -e to see escape move tree]"); } } if (!opt.quiet) { Printf ("max moves side to move = %u\n", (unsigned) n_moves_max); Printf ("max moves side to answer = %u\n", (unsigned) xn_moves_max); Printf ("max number allocations = %ld\n", (long) alloc_max); } free_move_cache (); if (alloc_free != 0) Printf ("alloc - free = %ld\n", (long) alloc_free); Fflush (stdout); } static void allocate_move_cache (void) { int i; if (mate_in > 1) { escape_moves = xmalloc ((mate_in + 1) * sizeof *escape_moves); for (i = 1; i <= mate_in; ++i) { escape_moves[i].entries = 0; } } if (mate_in > 2) { mating_moves = xmalloc (mate_in * sizeof *mating_moves); for (i = 1; i < mate_in; ++i) { mating_moves[i].entries = 0; } } } static void free_move_cache (void) { if (mate_in > 1) xfree (escape_moves); if (mate_in > 2) xfree (mating_moves); }