/*----------------------------------------------------------------------+ | | | mscp.c - Marcel's Simple Chess Program | | | +----------------------------------------------------------------------+ | | Author: Marcel van Kervinck | Creation: 11-Jun-1998 | Last update: 14-Dec-2003 | Description: Simple chess playing program | +----------------------------------------------------------------------+ | Copyright (C)1998-2003 Marcel van Kervinck | | This program is distributed under the GNU General Public License. | | See file COPYING or http://bitpit.net/mscp/ for details. | +----------------------------------------------------------------------*/ char mscp_c_rcsid[] = "@(#)$Id: mscp.c,v 1.18 2003/12/14 15:12:12 marcelk Exp $"; #include #include #include #include #include #include #include #include typedef unsigned char byte; #define INF 32000 #define MAX(a,b) ((a)>(b) ? (a) : (b)) #define MIN(a,b) ((a)<(b) ? (a) : (b)) #define xisspace(c) isspace((int)(c)) /* Prevent warnings on crappy Solaris */ #define xisalpha(c) isalpha((int)(c)) /*----------------------------------------------------------------------+ | data structures | +----------------------------------------------------------------------*/ enum { /* 64 squares */ A1, A2, A3, A4, A5, A6, A7, A8, B1, B2, B3, B4, B5, B6, B7, B8, C1, C2, C3, C4, C5, C6, C7, C8, D1, D2, D3, D4, D5, D6, D7, D8, E1, E2, E3, E4, E5, E6, E7, E8, F1, F2, F3, F4, F5, F6, F7, F8, G1, G2, G3, G4, G5, G6, G7, G8, H1, H2, H3, H4, H5, H6, H7, H8, CASTLE, /* Castling rights */ EP, /* En-passant square */ LAST /* Ply number of last capture or pawn push */ }; static byte board[64+3]; /* Board state */ static int ply; /* Number of half-moves made in game and search */ #define WTM (~ply & 1) /* White-to-move predicate */ static byte castle[64]; /* Which pieces may participate in castling */ #define CASTLE_WHITE_KING 1 #define CASTLE_WHITE_QUEEN 2 #define CASTLE_BLACK_KING 4 #define CASTLE_BLACK_QUEEN 8 static int computer[2]; /* Which side is played by the computer */ static int xboard_mode; /* XBoard protocol, surpresses prompt */ static unsigned long nodes; /* Node counter */ struct side { /* Attacks */ byte attack[64]; int king; byte pawns[10]; }; static struct side white, black, *friend, *enemy; static unsigned short history[64*64]; /* History-move heuristic counters */ static signed char undo_stack[6*1024], *undo_sp; /* Move undo administration */ static unsigned long hash_stack[1024]; /* History of hashes, for repetition */ static int maxdepth = 4; /* Maximum search depth */ /* Constants for static move ordering (pre-scores) */ #define PRESCORE_EQUAL (10U<<9) #define PRESCORE_HASHMOVE (3U<<14) #define PRESCORE_KILLERMOVE (2U<<14) #define PRESCORE_COUNTERMOVE (1U<<14) static const int prescore_piece_value[] = { 0, 0, 9<<9, 5<<9, 3<<9, 3<<9, 1<<9, 0, 9<<9, 5<<9, 3<<9, 3<<9, 1<<9, }; struct move { short move; unsigned short prescore; }; static struct move move_stack[1024], *move_sp; /* History of moves */ static int piece_square[12][64]; /* Position evaluation tables */ static unsigned long zobrist[12][64]; /* Hash-key construction */ /* * CORE is the number of entries in the opening book or transposition table. * It must be power of two. MSCP is very simple and optimized for 4 ply, * so I don't want to waste space on a large table. This also makes MSCP * fit well on 8bit machines. */ #define CORE (2048) static long booksize; /* Number of opening book entries */ /* Transposition table and opening book share the same memory */ static union { struct tt { /* Transposition table entry */ unsigned short hash; /* - Identifies position */ short move; /* - Best recorded move */ short score; /* - Score */ char flag; /* - How to interpret score */ char depth; /* - Remaining search depth */ } tt[CORE]; struct bk { /* Opening book entry */ unsigned long hash; /* - Identifies position */ short move; /* - Move for this position */ unsigned short count; /* - Frequency */ } bk[CORE]; } core; #define TTABLE (core.tt) #define BOOK (core.bk) /*----------------------------------------------------------------------+ | chess defines | +----------------------------------------------------------------------*/ enum { EMPTY, WHITE_KING, WHITE_QUEEN, WHITE_ROOK, WHITE_BISHOP, WHITE_KNIGHT, WHITE_PAWN, BLACK_KING, BLACK_QUEEN, BLACK_ROOK, BLACK_BISHOP, BLACK_KNIGHT, BLACK_PAWN }; #define PIECE_COLOR(pc) ((pc) < BLACK_KING) /* White or black */ #define DIR_N (+1) /* Offset to step one square up (north) */ #define DIR_E (+8) /* Offset to step one square right (east) */ enum { FILE_A, FILE_B, FILE_C, FILE_D, FILE_E, FILE_F, FILE_G, FILE_H }; enum { RANK_1, RANK_2, RANK_3, RANK_4, RANK_5, RANK_6, RANK_7, RANK_8 }; #define RANK2CHAR(r) ('1'+(r)) /* rank to text */ #define CHAR2RANK(c) ((c)-'1') /* text to rank */ #define FILE2CHAR(f) ('a'+(f)) /* file to text */ #define CHAR2FILE(c) ((c)-'a') /* text to file */ #define PIECE2CHAR(p) ("-KQRBNPkqrbnp"[p]) /* piece to text */ #define F(square) ((square) >> 3) /* file */ #define R(square) ((square) & 7) /* rank */ #define SQ(f,r) (((f) << 3) | (r)) /* compose square */ #define FLIP(square) ((square)^7) /* flip board */ #define MOVE(fr,to) (((fr) << 6) | (to)) /* compose move */ #define FR(move) (((move) & 07700) >> 6) /* from square */ #define TO(move) ((move) & 00077) /* target square */ #define SPECIAL (1<<12) /* for special moves */ struct command { char *name; void (*cmd)(char*); char *help; }; /* attacks */ #define ATKB_NORTH 0 #define ATKB_NORTHEAST 1 #define ATKB_EAST 2 #define ATKB_SOUTHEAST 3 #define ATKB_SOUTH 4 #define ATKB_SOUTHWEST 5 #define ATKB_WEST 6 #define ATKB_NORTHWEST 7 #define ATK_NORTH (1 << ATKB_NORTH) #define ATK_NORTHEAST (1 << ATKB_NORTHEAST) #define ATK_EAST (1 << ATKB_EAST) #define ATK_SOUTHEAST (1 << ATKB_SOUTHEAST) #define ATK_SOUTH (1 << ATKB_SOUTH) #define ATK_SOUTHWEST (1 << ATKB_SOUTHWEST) #define ATK_WEST (1 << ATKB_WEST) #define ATK_NORTHWEST (1 << ATKB_NORTHWEST) #define ATK_ORTHOGONAL ( ATK_NORTH | ATK_SOUTH | \ ATK_WEST | ATK_EAST ) #define ATK_DIAGONAL ( ATK_NORTHEAST | ATK_NORTHWEST | \ ATK_SOUTHEAST | ATK_SOUTHWEST ) #define ATK_SLIDER ( ATK_ORTHOGONAL | ATK_DIAGONAL ) static signed char king_step[129]; /* Offsets for king moves */ static signed char knight_jump[129]; /* Offsets for knight jumps */ /* 8 bits per square representing which directions a king can walk to */ static const byte king_dirs[64] = { 7, 31, 31, 31, 31, 31, 31, 28, 199, 255, 255, 255, 255, 255, 255, 124, 199, 255, 255, 255, 255, 255, 255, 124, 199, 255, 255, 255, 255, 255, 255, 124, 199, 255, 255, 255, 255, 255, 255, 124, 199, 255, 255, 255, 255, 255, 255, 124, 199, 255, 255, 255, 255, 255, 255, 124, 193, 241, 241, 241, 241, 241, 241, 112, }; /* 8 bits per square representing which directions a knight can jump to */ static const byte knight_dirs[64] = { 6, 14, 46, 46, 46, 46, 44, 40, 7, 15, 63, 63, 63, 63, 60, 56, 71, 207, 255, 255, 255, 255, 252, 184, 71, 207, 255, 255, 255, 255, 252, 184, 71, 207, 255, 255, 255, 255, 252, 184, 71, 207, 255, 255, 255, 255, 252, 184, 67, 195, 243, 243, 243, 243, 240, 176, 65, 193, 209, 209, 209, 209, 208, 144, }; /*----------------------------------------------------------------------+ | simple random generator | +----------------------------------------------------------------------*/ static long rnd_seed = 1; static long rnd(void) { long r = rnd_seed; r = 16807 * (r % 127773L) - 2836 * (r / 127773L); if (r < 0) r += 0x7fffffffL; return rnd_seed = r; } /*----------------------------------------------------------------------+ | I/O functions | +----------------------------------------------------------------------*/ static void print_square(int square) { putchar(FILE2CHAR(F(square))); putchar(RANK2CHAR(R(square))); } static void print_move_long(int move) { print_square(FR(move)); print_square(TO(move)); if (move >= SPECIAL) { if ((board[FR(move)] == WHITE_PAWN && R(TO(move)) == RANK_8) || (board[FR(move)] == BLACK_PAWN && R(TO(move)) == RANK_1)) { putchar('='); putchar("QRBN"[move >> 13]); } } } static void print_board(void) { int file, rank; for (rank=RANK_8; rank>=RANK_1; rank--) { printf("%d ", 1+rank); for (file=FILE_A; file<=FILE_H; file++) { putchar(' '); putchar(PIECE2CHAR(board[SQ(file,rank)])); } putchar('\n'); } printf(" a b c d e f g h\n%d. %s to move. %s%s%s%s ", 1+ply/2, WTM ? "White" : "Black", board[CASTLE] & CASTLE_WHITE_KING ? "K" : "", board[CASTLE] & CASTLE_WHITE_QUEEN ? "Q" : "", board[CASTLE] & CASTLE_BLACK_KING ? "k" : "", board[CASTLE] & CASTLE_BLACK_QUEEN ? "q" : "" ); if (board[EP]) print_square(board[EP]); putchar('\n'); } static int readline(char *line, int size, FILE *fp) { int c; int pos = 0; for (;;) { errno = 0; c = fgetc(fp); if (c == EOF) { if (!errno) return -1; printf("error: %s\n", strerror(errno)); errno = 0; continue; } if (c == '\n') { break; } if (pos < size-1) { line[pos++] = c; } } line[pos] = 0; return pos; } /*----------------------------------------------------------------------+ | transposition tables | +----------------------------------------------------------------------*/ /* Compute 32-bit Zobrist hash key. Normally 32 bits this is too small, but for MSCP's small searches it is OK */ static unsigned long compute_hash(void) { unsigned long hash = 0; int sq; for (sq=0; sq<64; sq++) { if (board[sq] != EMPTY) { hash ^= zobrist[board[sq]-1][sq]; } } return hash ^ WTM; } /*----------------------------------------------------------------------+ | position | +----------------------------------------------------------------------*/ static void reset(void) { move_sp = move_stack; undo_sp = undo_stack; hash_stack[ply] = compute_hash(); } static void setup_board(char *fen) { int file=FILE_A, rank=RANK_8; while (xisspace(*fen)) fen++; memset(board, 0, sizeof board); while (rank>RANK_1 || file<=FILE_H) { int piece = EMPTY; int count = 1; switch (*fen) { case 'K': piece = WHITE_KING; break; case 'Q': piece = WHITE_QUEEN; break; case 'R': piece = WHITE_ROOK; break; case 'B': piece = WHITE_BISHOP; break; case 'N': piece = WHITE_KNIGHT; break; case 'P': piece = WHITE_PAWN; break; case 'k': piece = BLACK_KING; break; case 'r': piece = BLACK_ROOK; break; case 'q': piece = BLACK_QUEEN; break; case 'b': piece = BLACK_BISHOP; break; case 'n': piece = BLACK_KNIGHT; break; case 'p': piece = BLACK_PAWN; break; case '/': rank -= 1; file = FILE_A; fen++; continue; case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': count = *fen - '0'; break; default: puts("fen error\n"); return; } do { board[SQ(file,rank)] = piece; file++; } while (--count); fen++; } ply = (fen[1] == 'b'); board[LAST] = ply; fen += 2; while (*fen) { switch (*fen) { case 'K': board[CASTLE] |= CASTLE_WHITE_KING; break; case 'Q': board[CASTLE] |= CASTLE_WHITE_QUEEN; break; case 'k': board[CASTLE] |= CASTLE_BLACK_KING; break; case 'q': board[CASTLE] |= CASTLE_BLACK_QUEEN; break; case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': board[EP] = SQ(CHAR2FILE(*fen),WTM?RANK_5:RANK_4); break; default: break; } fen++; } reset(); print_board(); } /*----------------------------------------------------------------------+ | attack tables | +----------------------------------------------------------------------*/ static void atk_slide(int sq, byte dirs, struct side *s) { byte dir = 0; int to; dirs &= king_dirs[sq]; do { dir -= dirs; dir &= dirs; to = sq; do { to += king_step[dir]; s->attack[to] += 1; if (board[to] != EMPTY) break; } while (dir & king_dirs[to]); } while (dirs -= dir); } static void compute_attacks(void) { int sq, to, pc; byte dir, dirs; memset(&white, 0, sizeof white); memset(&black, 0, sizeof black); friend = WTM ? &white : &black; enemy = WTM ? &black : &white; for (sq=0; sq<64; sq++) { pc = board[sq]; if (pc == EMPTY) continue; switch (pc) { case WHITE_KING: dir = 0; white.king = sq; dirs = king_dirs[sq]; do { dir -= dirs; dir &= dirs; to = sq + king_step[dir]; white.attack[to] += 1; } while (dirs -= dir); break; case BLACK_KING: dir = 0; black.king = sq; dirs = king_dirs[sq]; do { dir -= dirs; dir &= dirs; to = sq + king_step[dir]; black.attack[to] += 1; } while (dirs -= dir); break; case WHITE_QUEEN: atk_slide(sq, ATK_SLIDER, &white); break; case BLACK_QUEEN: atk_slide(sq, ATK_SLIDER, &black); break; case WHITE_ROOK: atk_slide(sq, ATK_ORTHOGONAL, &white); break; case BLACK_ROOK: atk_slide(sq, ATK_ORTHOGONAL, &black); break; case WHITE_BISHOP: atk_slide(sq, ATK_DIAGONAL, &white); break; case BLACK_BISHOP: atk_slide(sq, ATK_DIAGONAL, &black); break; case WHITE_KNIGHT: dir = 0; dirs = knight_dirs[sq]; do { dir -= dirs; dir &= dirs; to = sq + knight_jump[dir]; white.attack[to] += 1; } while (dirs -= dir); break; case BLACK_KNIGHT: dir = 0; dirs = knight_dirs[sq]; do { dir -= dirs; dir &= dirs; to = sq + knight_jump[dir]; black.attack[to] += 1; } while (dirs -= dir); break; case WHITE_PAWN: white.pawns[1+F(sq)] += 1; if (F(sq) != FILE_H) { white.attack[sq + DIR_N + DIR_E] += 1; } if (F(sq) != FILE_A) { white.attack[sq + DIR_N - DIR_E] += 1; } break; case BLACK_PAWN: black.pawns[1+F(sq)] += 1; if (F(sq) != FILE_H) { black.attack[sq - DIR_N + DIR_E] += 1; } if (F(sq) != FILE_A) { black.attack[sq - DIR_N - DIR_E] += 1; } break; } } } /*----------------------------------------------------------------------+ | make/unmake move | +----------------------------------------------------------------------*/ static void unmake_move(void) { int sq; for (;;) { sq = *--undo_sp; if (sq < 0) break; /* Found sentinel */ board[sq] = *--undo_sp; } ply--; } static void make_move(int move) { int fr; int to; int sq; *undo_sp++ = -1; /* Place sentinel */ if (board[EP]) { /* Clear en-passant info */ *undo_sp++ = board[EP]; *undo_sp++ = EP; board[EP] = 0; } to = TO(move); fr = FR(move); if (move & SPECIAL) { /* Special moves first */ switch (R(fr)) { case RANK_8: /* Black castles */ unmake_move(); if (to == G8) { make_move(MOVE(H8,F8)); } else { make_move(MOVE(A8,D8)); } break; case RANK_7: if (board[fr] == BLACK_PAWN) { /* Set en-passant flag */ *undo_sp++ = 0; *undo_sp++ = EP; board[EP] = to; } else { /* White promotes */ *undo_sp++ = board[fr]; *undo_sp++ = fr; board[fr] = WHITE_QUEEN + (move>>13); } break; case RANK_5: /* White captures en-passant */ case RANK_4: /* Black captures en-passant */ sq = SQ(F(to),R(fr)); *undo_sp++ = board[sq]; *undo_sp++ = sq; board[sq] = EMPTY; break; case RANK_2: if (board[fr] == WHITE_PAWN) { /* Set en-passant flag */ *undo_sp++ = 0; *undo_sp++ = EP; board[EP] = to; } else { /* Black promotes */ *undo_sp++ = board[fr]; *undo_sp++ = fr; board[fr] = BLACK_QUEEN + (move>>13); } break; case RANK_1: /* White castles */ unmake_move(); if (to == G1) { make_move(MOVE(H1,F1)); } else { make_move(MOVE(A1,D1)); } break; default: break; } } ply++; if (board[to]!=EMPTY || board[fr]==WHITE_PAWN || board[fr]==BLACK_PAWN ) { *undo_sp++ = board[LAST]; *undo_sp++ = LAST; board[LAST] = ply; } *undo_sp++ = board[to]; *undo_sp++ = to; *undo_sp++ = board[fr]; *undo_sp++ = fr; board[to] = board[fr]; board[fr] = EMPTY; if (board[CASTLE] & (castle[fr] | castle[to])) { *undo_sp++ = board[CASTLE]; *undo_sp++ = CASTLE; board[CASTLE] &= ~(castle[fr] | castle[to]); } } /*----------------------------------------------------------------------+ | move generator | +----------------------------------------------------------------------*/ /* XXX Dirty hack. Used to signal normal move generation or generation of good captures only */ static unsigned short caps; static int push_move(int fr, int to) { unsigned short prescore = PRESCORE_EQUAL; int move; /* what do we capture */ if (board[to] != EMPTY) { prescore += (1<<9) + prescore_piece_value[board[to]]; } /* does the destination square look safe? */ if (WTM) { if (black.attack[to] != 0) { /* defended */ prescore -= prescore_piece_value[board[fr]]; } } else { if (white.attack[to] != 0) { /* defended */ prescore -= prescore_piece_value[board[fr]]; } } if (prescore >= caps) { move = MOVE(fr, to); move_sp->move = move; move_sp->prescore = prescore | history[move]; move_sp++; return 1; } return 0; } static void push_special_move(int fr, int to) { int move; move = MOVE(fr, to); move_sp->prescore = PRESCORE_EQUAL | history[move]; move_sp->move = move | SPECIAL; move_sp++; } static void push_pawn_move(int fr, int to) { if ((R(to) == RANK_8) || (R(to) == RANK_1)) { push_special_move(fr, to); /* queen promotion */ push_special_move(fr, to); /* rook promotion */ move_sp[-1].move += 1<<13; push_special_move(fr, to); /* bishop promotion */ move_sp[-1].move += 2<<13; push_special_move(fr, to); /* knight promotion */ move_sp[-1].move += 3<<13; } else { push_move(fr, to); } } static void gen_slides(int fr, byte dirs) { int vector; int to; byte dir = 0; dirs &= king_dirs[fr]; do { dir -= dirs; dir &= dirs; vector = king_step[dir]; to = fr; do { to += vector; if (board[to] != EMPTY) { if (PIECE_COLOR(board[to]) != WTM) { push_move(fr, to); } break; } push_move(fr, to); } while (dir & king_dirs[to]); } while (dirs -= dir); } static int cmp_move(const void *ap, const void *bp) { const struct move *a = ap; const struct move *b = bp; if (a->prescore < b->prescore) return -1; if (a->prescore > b->prescore) return 1; return a->move - b->move; /* this makes qsort deterministic */ } static int test_illegal(int move) { make_move(move); compute_attacks(); unmake_move(); return friend->attack[enemy->king] != 0; } static void generate_moves(unsigned treshold) { int fr, to; int pc; byte dir, dirs; caps = treshold; for (fr=0; fr<64; fr++) { pc = board[fr]; if (!pc || PIECE_COLOR(pc) != WTM) continue; /* * generate moves for this piece */ switch (pc) { case WHITE_KING: case BLACK_KING: dir = 0; dirs = king_dirs[fr]; do { dir -= dirs; dir &= dirs; to = fr+king_step[dir]; if (board[to] != EMPTY && PIECE_COLOR(board[to]) == WTM) continue; push_move(fr, to); } while (dirs -= dir); break; case WHITE_QUEEN: case BLACK_QUEEN: gen_slides(fr, ATK_SLIDER); break; case WHITE_ROOK: case BLACK_ROOK: gen_slides(fr, ATK_ORTHOGONAL); break; case WHITE_BISHOP: case BLACK_BISHOP: gen_slides(fr, ATK_DIAGONAL); break; case WHITE_KNIGHT: case BLACK_KNIGHT: dir = 0; dirs = knight_dirs[fr]; do { dir -= dirs; dir &= dirs; to = fr+knight_jump[dir]; if (board[to] != EMPTY && PIECE_COLOR(board[to]) == WTM) continue; push_move(fr, to); } while (dirs -= dir); break; case WHITE_PAWN: if (F(fr) != FILE_H) { to = fr + DIR_N + DIR_E; if (board[to] >= BLACK_KING) { push_pawn_move(fr, to); } } if (F(fr) != FILE_A) { to = fr + DIR_N - DIR_E; if (board[to] >= BLACK_KING) { push_pawn_move(fr, to); } } to = fr + DIR_N; if (board[to] != EMPTY) { break; } push_pawn_move(fr, to); if (R(fr) == RANK_2) { to += DIR_N; if (board[to] == EMPTY) { if (push_move(fr, to)) if (black.attack[to-DIR_N]) { move_sp[-1].move |= SPECIAL; } } } break; case BLACK_PAWN: if (F(fr) != FILE_H) { to = fr - DIR_N + DIR_E; if (board[to] && board[to] < BLACK_KING) { push_pawn_move(fr, to); } } if (F(fr) != FILE_A) { to = fr - DIR_N - DIR_E; if (board[to] && board[to] < BLACK_KING) { push_pawn_move(fr, to); } } to = fr - DIR_N; if (board[to] != EMPTY) { break; } push_pawn_move(fr, to); if (R(fr) == RANK_7) { to -= DIR_N; if (board[to] == EMPTY) { if (push_move(fr, to)) if (white.attack[to+DIR_N]) { move_sp[-1].move |= SPECIAL; } } } break; } } /* * generate castling moves */ if (board[CASTLE] && !enemy->attack[friend->king]) { if (WTM && (board[CASTLE] & CASTLE_WHITE_KING) && !board[F1] && !board[G1] && !enemy->attack[F1]) { push_special_move(E1, G1); } if (WTM && (board[CASTLE] & CASTLE_WHITE_QUEEN) && !board[D1] && !board[C1] && !board[B1] && !enemy->attack[D1]) { push_special_move(E1, C1); } if (!WTM && (board[CASTLE] & CASTLE_BLACK_KING) && !board[F8] && !board[G8] && !enemy->attack[F8]) { push_special_move(E8, G8); } if (!WTM && (board[CASTLE] & CASTLE_BLACK_QUEEN) && !board[D8] && !board[C8] && !board[B8] && !enemy->attack[D8]) { push_special_move(E8, C8); } } /* * generate en-passant captures */ if (board[EP]) { int ep = board[EP]; if (WTM) { if (F(ep) != FILE_A && board[ep-DIR_E] == WHITE_PAWN) { if (push_move(ep-DIR_E, ep+DIR_N)) move_sp[-1].move |= SPECIAL; } if (F(ep) != FILE_H && board[ep+DIR_E] == WHITE_PAWN) { if (push_move(ep+DIR_E, ep+DIR_N)) move_sp[-1].move |= SPECIAL; } } else { if (F(ep) != FILE_A && board[ep-DIR_E] == BLACK_PAWN) { if (push_move(ep-DIR_E, ep-DIR_N)) move_sp[-1].move |= SPECIAL; } if (F(ep) != FILE_H && board[ep+DIR_E] == BLACK_PAWN) { if (push_move(ep+DIR_E, ep-DIR_N)) move_sp[-1].move |= SPECIAL; } } } } static void print_move_san(int move) { int fr, to; int filex = 0, rankx = 0; struct move *moves; fr = FR(move); to = TO(move); if ((move==(MOVE(E1,C1)|SPECIAL)) || (move==(MOVE(E8,C8)|SPECIAL))) { fputs("O-O-O", stdout); goto check; } if ((move==(MOVE(E1,G1)|SPECIAL)) || (move==(MOVE(E8,G8)|SPECIAL))) { fputs("O-O", stdout); goto check; } if ((board[fr]==WHITE_PAWN) || (board[fr] == BLACK_PAWN)) { /* * pawn moves are a bit special */ if (F(fr) != F(to)) { printf("%cx", FILE2CHAR(F(fr))); } print_square(to); /* * promote to piece (=Q, =R, =B, =N) */ if (move > 4095 && (R(to)==RANK_1 || R(to)==RANK_8)) { putchar('='); putchar("QRBN"[move>>13]); } goto check; } /* * piece identifier (K, Q, R, B, N) */ putchar(toupper(PIECE2CHAR(board[fr]))); /* * disambiguate: consider moves of identical pieces to the same square */ moves = move_sp; generate_moves(0); while (move_sp > moves) { move_sp--; if (to != TO(move_sp->move) /* same destination */ || move == move_sp->move /* different move */ || board[fr] != board[FR(move_sp->move)] /* same piece */ || test_illegal(move_sp->move)) { continue; } rankx |= (R(fr) == R(FR(move_sp->move))) + 1; filex |= F(fr) == F(FR(move_sp->move)); } if (rankx != filex) putchar(FILE2CHAR(F(fr))); if (filex) putchar(RANK2CHAR(R(fr))); /* * capture sign */ if (board[to] != EMPTY) putchar('x'); /* * to-square */ print_square(to); /* * check ('+') or checkmate ('#') */ check: make_move(move); compute_attacks(); if (enemy->attack[friend->king]) { /* in check, is mate? */ int sign = '#'; moves = move_sp; generate_moves(0); while (move_sp > moves) { move_sp--; if (!test_illegal(move_sp->move)) { sign = '+'; move_sp = moves; /* break */ } } putchar(sign); } unmake_move(); } /*----------------------------------------------------------------------+ | move parser | +----------------------------------------------------------------------*/ static int parse_move(char *line, int *num) { int move, matches; int n = 0; struct move *m; char *piece = NULL; char *fr_file = NULL; char *fr_rank = NULL; char *to_file = NULL; char *to_rank = NULL; char *prom_piece = NULL; char *s; while (xisspace(line[n])) /* skip white space */ n++; if (!strncmp(line+n, "o-o-o", 5) || !strncmp(line+n, "O-O-O", 5) || !strncmp(line+n, "0-0-0", 5)) { piece = "K"; fr_file = "e"; to_file = "c"; n+=5; } else if (!strncmp(line+n, "o-o", 3) || !strncmp(line+n, "O-O", 3) || !strncmp(line+n, "0-0", 3)) { piece = "K"; fr_file = "e"; to_file = "g"; n+=3; } else { s = strchr("KQRBNP", line[n]); if (s && *s) { piece = s; n++; } /* first square */ s = strchr("abcdefgh", line[n]); if (s && *s) { to_file = s; n++; } s = strchr("12345678", line[n]); if (s && *s) { to_rank = s; n++; } if (line[n] == '-' || line[n] == 'x') { n++; } s = strchr("abcdefgh", line[n]); if (s && *s) { fr_file = to_file; fr_rank = to_rank; to_file = s; to_rank = NULL; n++; } s = strchr("12345678", line[n]); if (s && *s) { to_rank = s; n++; } if (line[n] == '=') { n++; } s = strchr("QRBNqrbn", line[n]); if (s && *s) { prom_piece = s; n++; } } while (line[n] == '+' || line[n] == '#' || line[n] == '!' || line[n] == '?') { n++; } *num = n; if (!piece && !fr_file && !fr_rank && !to_file && !to_rank && !prom_piece) return 0; move = 0; matches = 0; m = move_sp; compute_attacks(); generate_moves(0); while (move_sp > m) { int fr, to; move_sp--; fr = FR(move_sp->move); to = TO(move_sp->move); /* does this move match? */ if ((piece && *piece != toupper(PIECE2CHAR(board[fr]))) || (to_file && *to_file != FILE2CHAR(F(to))) || (to_rank && *to_rank != RANK2CHAR(R(to))) || (fr_file && *fr_file != FILE2CHAR(F(fr))) || (fr_rank && *fr_rank != RANK2CHAR(R(fr))) || (prom_piece && (toupper(*prom_piece) != "QRBN"[(move_sp->move)>>13]))) { continue; } /* if so, is it legal? */ if (test_illegal(move_sp->move)) { continue; } /* probably.. */ /* do we already have a match? */ if (move) { int old_is_p, new_is_p; if (piece) { puts("ambiguous!"); print_board(); puts(line); move_sp = m; return 0; } /* if this move is a pawn move and the previously found isn't, we accept it */ old_is_p = (board[FR(move)]==WHITE_PAWN) || (board[FR(move)]==BLACK_PAWN); new_is_p = (board[fr]==WHITE_PAWN) || (board[fr]==BLACK_PAWN); if (new_is_p && !old_is_p) { move = move_sp->move; matches = 1; } else if (old_is_p && !new_is_p) { } else if (!old_is_p && !new_is_p) { matches++; } else if (old_is_p && new_is_p) { puts("ambiguous!"); print_board(); puts(line); move_sp = m; return 0; } } else { move = move_sp->move; matches = 1; } } if (matches <= 1) return move; puts("ambiguous!"); print_board(); puts(line); return 0; } /*----------------------------------------------------------------------+ | opening book | +----------------------------------------------------------------------*/ static int cmp_bk(const void *ap, const void *bp) { const struct bk *a = ap; const struct bk *b = bp; if (a->hash < b->hash) return -1; if (a->hash > b->hash) return 1; return (int)a->move - (int)b->move; } static void compact_book(void) { long b = 0, c = 0; qsort(BOOK, booksize, sizeof(BOOK[0]), cmp_bk); while (b= 0) { s = line; for (;;) { move = parse_move(s, &num); if (!move) break; s += num; if (booksize < CORE) { BOOK[booksize].hash = compute_hash(); BOOK[booksize].move = move; BOOK[booksize].count = 1; booksize++; if (booksize >= CORE) compact_book(); } make_move(move); } while (ply>0) unmake_move(); /* @@@ wrong */ } fclose(fp); compact_book(); } static int book_move(void) { int move = 0, sum = 0; long x = 0, y, m; char *seperator = "book:"; unsigned long hash; if (!booksize) return 0; y = booksize; hash = compute_hash(); while (y-x > 1) { /* inv: BOOK[x].hash <= hash < BOOK[y].hash */ m = (x + y) / 2; if (hash < BOOK[m].hash) { y=m; } else { x=m; } } while (BOOK[x].hash == hash) { printf("%s (%d)", seperator, BOOK[x].count); seperator = ","; print_move_san(BOOK[x].move); compute_hash(); sum += BOOK[x].count; if (rnd()%sum < BOOK[x].count) { move = BOOK[x].move; } if (!x--) break; } putchar('\n'); return move; } /*----------------------------------------------------------------------+ | evaluator | +----------------------------------------------------------------------*/ static int center[64] = { 0, 2, 3, 4, 4, 3, 2, 0, 2, 3, 4, 5, 5, 4, 3, 2, 3, 4, 5, 7, 7, 5, 4, 3, 4, 5, 7, 10, 10, 7, 5, 4, 4, 5, 7, 10, 10, 7, 5, 4, 3, 4, 5, 7, 7, 5, 4, 3, 2, 3, 4, 5, 5, 4, 3, 2, 0, 2, 3, 4, 4, 3, 2, 0, }; static int pawn_advance[64] = { 0, 0, 2, 3, 5, 30, 50, 0, 0, 0, 2, 3, 5, 30, 50, 0, 0, 0, 2, 3, 5, 30, 50, 0, 0, -5, 2, 8, 8, 30, 50, 0, 0, -5, 2, 8, 8, 30, 50, 0, 0, 0, 2, 3, 5, 30, 50, 0, 0, 0, 2, 3, 5, 30, 50, 0, 0, 0, 2, 3, 5, 30, 50, 0, }; #define DIFF(a,b) ((a)>(b) ? (a)-(b) : (b)-(a)) #define TAXI(a,b) (DIFF(F(a),F(b)) + DIFF(R(a),R(b))) static void compute_piece_square_tables(void) { int pc, sq; int score = 0; int file; compute_attacks(); /* so we know where the king and pawns are */ for (sq=0; sq<64; sq++) { file = 1+F(sq); for (pc=1; pc<13; pc++) { switch (pc) { case WHITE_KNIGHT: score = 300; score += center[sq]; score -= TAXI(black.king, sq); break; case BLACK_KNIGHT: score = -300; score -= center[sq]; score += TAXI(white.king, sq); break; case WHITE_BISHOP: score = +300; break; case BLACK_BISHOP: score = -300; break; case WHITE_ROOK: score = +500; score += DIFF(F(black.king), F(sq)); break; case BLACK_ROOK: score = -500; score -= DIFF(F(white.king), F(sq)); break; case WHITE_QUEEN: score = +900; score += center[sq]; break; case BLACK_QUEEN: score = -900; score -= center[sq]; break; case WHITE_KING: score = +400; score += center[sq]; break; case BLACK_KING: score = -400; score -= center[sq]; break; case WHITE_PAWN: score = +100; score += pawn_advance[sq]; if (!black.pawns[file]) { score += pawn_advance[sq]; } break; case BLACK_PAWN: score = -100; score -= pawn_advance[FLIP(sq)]; if (!white.pawns[file]) { score -= pawn_advance[FLIP(sq)]; } break; } piece_square[pc-1][sq] = score; } } piece_square[WHITE_KING-1][G1] += 100; piece_square[BLACK_KING-1][G8] -= 100; } static int white_control[64] = { 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 3, 3, 2, 2, 1, 1, 2, 5, 6, 3, 2, 2, 1, 1, 2, 5, 6, 3, 2, 2, 1, 1, 2, 2, 3, 3, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, }; static int evaluate(void) { int sq; int score = 0; int white_has, black_has; /* * stage 1: material+piece_square tables */ for (sq=0; sq<64; sq++) { int file; if (board[sq] == EMPTY) continue; score += piece_square[board[sq]-1][sq]; file = F(sq)+1; switch (board[sq]) { case WHITE_PAWN: { int missing; if (white.pawns[file] > 1) { score -= 15; } missing = !white.pawns[file-1] + !white.pawns[file+1] + !black.pawns[file]; score -= missing * missing * 5; break; } case BLACK_PAWN: { int missing; if (black.pawns[file] > 1) { score += 15; } missing = !black.pawns[file-1] + !black.pawns[file+1] + !white.pawns[file]; score += missing * missing * 5; break; } case WHITE_ROOK: if (!white.pawns[file]) { score += 10; if (!black.pawns[file]) { score += 10; } } break; case BLACK_ROOK: if (!black.pawns[file]) { score -= 10; if (!white.pawns[file]) { score -= 10; } } break; default: break; } } /* * stage 2: board control */ white_has = 0; black_has = 0; for (sq=0; sq<64; sq++) { if (white.attack[sq] > black.attack[sq]) { white_has += white_control[sq]; } if (white.attack[sq] < black.attack[sq]) { black_has += white_control[FLIP(sq)]; } } score += (white_has - black_has); /* some noise to randomize play */ score += (hash_stack[ply] ^ rnd_seed) % 17 - 8; return WTM ? score : -score; } /*----------------------------------------------------------------------+ | search | +----------------------------------------------------------------------*/ static int qsearch(int alpha, int beta) { int best_score; int score; struct move *moves; nodes++; hash_stack[ply] = compute_hash(); best_score = evaluate(); if (best_score >= beta) { return best_score; } moves = move_sp; generate_moves(PRESCORE_EQUAL + (1<<9)); qsort(moves, move_sp - moves, sizeof(*moves), cmp_move); while (move_sp > moves) { int move; move_sp--; move = move_sp->move; make_move(move); compute_attacks(); if (friend->attack[enemy->king]) { unmake_move(); continue; } score = - qsearch(-beta, -alpha); unmake_move(); if (score <= best_score) { continue; } best_score = score; if (score <= alpha) { continue; } alpha = score; if (score < beta) { continue; } move_sp = moves; /* fail high: skip remaining moves */ } return best_score; } static int search(int depth, int alpha, int beta) { int best_score = -INF; int best_move = 0; int score; struct move *moves; int incheck = 0; struct tt *tt; int oldalpha = alpha; int oldbeta = beta; int i, count=0; nodes++; /* test for draw by repetition */ hash_stack[ply] = compute_hash(); for (i=ply-4; i>=board[LAST]; i-=2) { if (hash_stack[i] == hash_stack[ply]) count++; if (count>=2) return 0; } /* * check transposition table */ tt = &TTABLE[ ((hash_stack[ply]>>16) & (CORE-1)) ]; if (tt->hash == (hash_stack[ply] & 0xffffU)) { if (tt->depth >= depth) { if (tt->flag >= 0) alpha = MAX(alpha, tt->score); if (tt->flag <= 0) beta = MIN(beta, tt->score); if (alpha >= beta) return tt->score; } best_move = tt->move & 07777; } history[best_move] |= PRESCORE_HASHMOVE; incheck = enemy->attack[friend->king]; /* * generate moves */ moves = move_sp; generate_moves(0); history[best_move] &= 0x3fff; best_move = 0; qsort(moves, move_sp - moves, sizeof(*moves), cmp_move); /* * loop over all moves */ while (move_sp > moves) { int newdepth; int move; move_sp--; move = move_sp->move; make_move(move); compute_attacks(); if (friend->attack[enemy->king]) { unmake_move(); continue; } newdepth = incheck ? depth : depth-1; if (newdepth <= 0) { score = -qsearch(-beta, -alpha); } else { score = -search(newdepth, -beta, -alpha); } if (score < -29000) score++; /* adjust for mate-in-n */ unmake_move(); if (score <= best_score) continue; best_score = score; best_move = move; if (score <= alpha) continue; alpha = score; if (score < beta) continue; move_sp = moves; /* fail high: skip remaining moves */ } if (best_score == -INF) { /* deal with mate and stalemate */ if (incheck) { best_score = -30000; } else { best_score = 0; } } history[best_move & 07777] += depth*depth; if (history[best_move & 07777] > 511) { int m; for (m=0; m>= 4; /* scaling */ } } tt->hash = hash_stack[ply] & 0xffffU; tt->move = best_move; tt->score = best_score; tt->depth = depth; tt->flag = (oldalpha < best_score) - (best_score < oldbeta); return best_score; } /* squeeze: compacts a long into a short */ static unsigned short squeeze(unsigned long n) { const unsigned long mask = ~0U<<11; unsigned short s; for (s=0; n&mask; n>>=1, s-=mask) /* SKIP */; return s | n; } static int root_search(int maxdepth) { int depth; int score, best_score; int move = 0; int alpha, beta; unsigned long node; struct move *m; nodes = 0; compute_piece_square_tables(); generate_moves(0); qsort(move_stack, move_sp-move_stack, sizeof(struct move), cmp_move); alpha = -INF; beta = +INF; puts(" nodes ply score move"); for (depth = 1; depth <= maxdepth; depth++) { m = move_stack; best_score = INT_MIN; node = nodes; while (m < move_sp) { make_move(m->move); compute_attacks(); if (friend->attack[enemy->king] != 0) { /* illegal? */ unmake_move(); *m = *--move_sp; /* drop this move */ continue; } hash_stack[ply] = compute_hash(); if (depth-1 > 0) { score = -search(depth-1, -beta, -alpha); } else { score = -qsearch(-beta, -alpha); } unmake_move(); if (score>=beta || (score<=alpha && m==move_stack)) { alpha = -INF; beta = +INF; continue; /* re-search this move */ } m->prescore = ~squeeze(nodes-node); node = nodes; if (score > best_score) { struct move tmp; best_score = score; alpha = score; beta = score + 1; move = m->move; tmp = *move_stack; /* swap with top of list */ *move_stack = *m; *m = tmp; } m++; /* continue with next move */ } if (move_sp-move_stack <= 1) { break; /* just one move to play */ } printf(" %5lu %3d %+1.2f ", nodes, depth, best_score / 100.0); print_move_san(move); puts(""); /* sort remaining moves in descending order of subtree size */ qsort(move_stack+1, move_sp-move_stack-1, sizeof(*m), cmp_move); alpha = best_score - 33; /* aspiration window */ beta = best_score + 33; } move_sp = move_stack; return move; } /*----------------------------------------------------------------------+ | commands | +----------------------------------------------------------------------*/ static void cmd_bd(char *dummy /* @unused */) { print_board(); } static void cmd_book(char *dummy) { int move; printf("%ld moves in book\n", booksize); move = book_move(); if (move) { print_move_san(move); puts(" selected"); } } static void cmd_list_moves(char *dummy) { struct move *m; int nmoves = 0; puts("moves are:"); compute_attacks(); m = move_sp; generate_moves(0); qsort(m, move_sp - m, sizeof(*m), cmp_move); while (move_sp > m) { --move_sp; if (test_illegal(move_sp->move)) continue; print_move_san(move_sp->move); putchar('\n'); nmoves++; } printf("%d move%s\n", nmoves, nmoves==1 ? "" : "s"); } static void cmd_default(char *s) { int move, dummy; move = parse_move(s, &dummy); if (move) { make_move(move); hash_stack[ply] = compute_hash(); print_board(); } else { printf("no such move or command: %s\n", s); } } static void cmd_undo(char *dummy) { if (undo_sp > undo_stack) { unmake_move(); computer[0] = 0; computer[1] = 0; } else { puts("cannot undo move"); } } static void cmd_both(char *dummy) { computer[0] = 1; computer[1] = 1; } static void cmd_white(char *dummy) { computer[0] = 0; computer[1] = 1; ply = 0; reset(); } static void cmd_black(char *dummy) { computer[0] = 1; computer[1] = 0; ply = 1; reset(); } static void cmd_force(char *dummy) { computer[0] = 0; computer[1] = 0; } static void cmd_go(char *dummy) { computer[!WTM] = 1; computer[WTM] = 0; } static void cmd_test(char *s) { int d = maxdepth; sscanf(s, "%*s%d", &d); root_search(d); } static void cmd_set_depth(char *s) { if (1==sscanf(s, "%*s%d", &maxdepth)) { maxdepth = MAX(1, MIN(maxdepth, 8)); } printf("maximum search depth is %d plies\n", maxdepth); } static void cmd_new(char *dummy) { setup_board("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -"); load_book("book.txt"); computer[0] = 0; computer[1] = 1; rnd_seed = time(NULL); } static void cmd_xboard(char *dummy) { xboard_mode = 1; } static void cmd_fen(char *s) { while (xisalpha(*s)) s++; setup_board(s); } static void cmd_quit(char *dummy) { exit(0); } struct command mscp_commands[]; /* forward declaration */ static void cmd_help(char *dummy) { struct command *c; puts("commands are:"); c = mscp_commands; do { printf("%-8s - %s\n", c->name ? c->name : "", c->help); } while (c++->name != NULL); } struct command mscp_commands[] = { { "help", cmd_help, "show this list of commands" }, { "bd", cmd_bd, "display board" }, { "ls", cmd_list_moves, "list moves" }, { "new", cmd_new, "new game" }, { "go", cmd_go, "computer starts playing" }, { "test", cmd_test, "search (depth)" }, { "quit", cmd_quit, "leave chess program" }, { "sd", cmd_set_depth, "set maximum search depth (plies)" }, { "both", cmd_both, "computer plays both sides" }, { "force", cmd_force, "computer plays neither side" }, { "white", cmd_white, "set computer to play white" }, { "black", cmd_black, "set computer to play black" }, { "book", cmd_book, "lookup current position in book" }, { "undo", cmd_undo, "undo move" }, { "quit", cmd_quit, "leave chess program" }, { "xboard", cmd_xboard, "switch to xboard mode" }, { "fen", cmd_fen, "setup new position" }, { NULL, cmd_default, "enter moves in algebraic notation" }, }; /*----------------------------------------------------------------------+ | main | +----------------------------------------------------------------------*/ static void catch_sigint(int s) { signal(s, catch_sigint); } static char startup_message[] = "\n" "This is MSCP 1.4 (Marcel's Simple Chess Program)\n" "\n" "Copyright (C)1998-2003 Marcel van Kervinck\n" "This program is distributed under the GNU General Public License.\n" "(See file COPYING or http://combinational.com/mscp/ for details.)\n" "\n" "Type 'help' for a list of commands\n"; int main(void) { int i; int cmd; char line[128]; char name[128]; int move; puts(startup_message); signal(SIGINT, catch_sigint); for (i=0; i ", stdout); } fflush(stdout); if (readline(line, sizeof(line), stdin) < 0) { break; } if (1 != sscanf(line, "%s", name)) continue; for (cmd=0; mscp_commands[cmd].name != NULL; cmd++) { if (0==strcmp(mscp_commands[cmd].name, name)) { break; } } mscp_commands[cmd].cmd(line); while (computer[!WTM]) { move = book_move(); if (!move) { booksize = 0; memset(&core, 0, sizeof(core)); memset(history, 0, sizeof(history)); move = root_search(maxdepth); } if (!move || ply >= 1000) { printf("game over: "); compute_attacks(); if (!move && enemy->attack[friend->king] != 0) { puts(WTM ? "0-1" : "1-0"); } else { puts("1/2-1/2"); } computer[0] = computer[1] = 0; break; } printf("%d. ... ", 1+ply/2); print_move_long(move); putc('\n', stdout); make_move(move); hash_stack[ply] = compute_hash(); print_board(); } } return 0; } /*----------------------------------------------------------------------+ | | +----------------------------------------------------------------------*/