board.c

   1 /*
   2  *      This program is free software; you can redistribute it and/or modify
   3  *      it under the terms of the GNU General Public License as published by
   4  *      the Free Software Foundation; either version 2 of the License, or
   5  *      (at your option) any later version.
   6  *
   7  *      This program is distributed in the hope that it will be useful,
   8  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  *      GNU General Public License for more details.
  11  *
  12  *      You should have received a copy of the GNU General Public License
  13  *      along with this program; if not, write to the Free Software
  14  *      Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  15  */
  16 #include "common.h"
  17 #include "board.h"
  18 #include "engine.h"
  19
  20 const char *char_board[64] = {
  21         "a1", "b1", "c1", "d1", "e1", "f1", "g1", "h1",
  22         "a2", "b2", "c2", "d2", "e2", "f2", "g2", "h2",
  23         "a3", "b3", "c3", "d3", "e3", "f3", "g3", "h3",
  24         "a4", "b4", "c4", "d4", "e4", "f4", "g4", "h4",
  25         "a5", "b5", "c5", "d5", "e5", "f5", "g5", "h5",
  26         "a6", "b6", "c6", "d6", "e6", "f6", "g6", "h6",
  27         "a7", "b7", "c7", "d7", "e7", "f7", "g7", "h7",
  28         "a8", "b8", "c8", "d8", "e8", "f8", "g8", "h8" };
  29
  30 const char char_pieces[7] = {' ', 'P', 'N', 'B', 'R', 'Q', 'K'};
  31
  32 /* helper data */
  33 int lzArray[65536];
  34 int bitcount[65536];
  35
  36 uint64_t isolated_mask[8];              /* masks adjacent files */
  37 uint64_t passer_mask[2][64];    /* masks passed pawn way */
  38 uint64_t pawn_moves[2][64];             /* pawn capture moves */
  39 uint64_t piece_moves[7][64];    /* all piece moves */
  40 uint64_t forward_ray[2][64];    /* masks squares infront of a pawn */
  41 uint64_t king_shield[2][64];    /* example: for king on G1 - F2,g2,h2 */
  42
  43 int distance[64][64];                   /* distance from 2 squares */
  44
  45 /* bitboard mask for files */
  46 const uint64_t file_bit[8] = {
  47         0x0101010101010101ULL, 0x0202020202020202ULL,
  48         0x0404040404040404ULL, 0x0808080808080808ULL,
  49         0x1010101010101010ULL, 0x2020202020202020ULL,
  50         0x4040404040404040ULL, 0x8080808080808080ULL
  51 };
  52
  53 uint64_t complete;                                      /* complete bitboard for both sides */
  54 int square64[64];                                       /* regular board */
  55 struct board_t brd;                                     /* board parameters */
  56 struct game_history_t game_history;     /* takeback buffer */
  57
  58 uint64_t piece_boards[2][7];    /* bitboard for each type of piece */
  59 uint64_t r_pieces[2];                   /* pieces except kings */
  60 uint64_t side_boards[2];                /* pieces for each side */
  61
  62 int castled[2];                                 /* WHITE or BLACK castled */
  63
  64 int material_complete[2];               /* sum of the material */
  65 int material_pawns[2];                  /* ... for pawns */
  66 int material_pieces[2];                 /* for pieces except pawns */
  67
  68 /* initial values according to Larry Kaufman */
  69 int piece_value[7] = { 0, 100, 325, 325, 500, 975 };
  70
  71 int piece_count[2][7];                  /* count pieces of each type */
  72
  73 /* add piece to the board, update bitboard, zobrist and count */
  74 void
  75 add_piece(int square, int piece, int side)
  76 {
  77         assert(square >= 0 && square <= 63);
  78         assert(piece >= PAWN && piece <= KING);
  79         assert(side == WHITE || side == BLACK);
  80         assert(material_complete[side] == material_pieces[side] + \
  81                         material_pawns[side]);
  82
  83         square64[square] = piece;
  84
  85         SET(piece_boards[side][piece], square);                 /* update bitboard */
  86         brd.hash_key ^= hash_code[side][piece][square]; /* update zobrist key */
  87
  88         if (piece == KING)
  89                 brd.kings[side] = square;
  90         else {
  91                 if (piece == PAWN) {
  92                         brd.hash_pawn_key ^= hash_code[side][PAWN][square];
  93                         material_pawns[side] += piece_value[PAWN];
  94                 } else
  95                         material_pieces[side] += piece_value[piece];
  96                 material_complete[side] += piece_value[piece];
  97         }
  98         piece_count[side][piece]++;
  99 }
 100
 101 int
 102 board_is_legal(struct board_t *b)
 103 {
 104         int i;
 105         int wk = 0;
 106         int bk = 0;
 107         int color;
 108         int n_pieces = 0;
 109
 110         for (i = 0; i < 64; i++) {
 111                 if (!square64[i]) {
 112                         /* if mailbox square isn't empty but bitboard's bit isn't set */
 113                         if (complete & BIT(i))
 114                                 return FALSE;
 115                 } else {
 116                         color = -1;
 117                         switch (square64[i]) {
 118                                 case PAWN:
 119                                         if (((PAWNS(WHITE) | PAWNS(BLACK)) & BIT(i)) == 0)
 120                                                 return FALSE;
 121                                         if (_FILE(square64[i]) == 0 || _FILE(square64[i]) == 7)
 122                                                 return FALSE;
 123                                         break;
 124                                 case KNIGHT:
 125                                         if (((KNIGHTS(WHITE) | KNIGHTS(BLACK)) & BIT(i)) == 0)
 126                                                 return FALSE;
 127                                         break;
 128                                 case BISHOP:
 129                                         if (((BISHOPS(WHITE) | BISHOPS(BLACK)) & BIT(i)) == 0)
 130                                                 return FALSE;
 131                                         break;
 132                                 case ROOK:
 133                                         if (((ROOKS(WHITE) | ROOKS(BLACK)) & BIT(i)) == 0)
 134                                                 return FALSE;
 135                                         break;
 136                                 case QUEEN:
 137                                         if (((QUEENS(WHITE) | QUEENS(BLACK)) & BIT(i)) == 0)
 138                                                 return FALSE;
 139                                         break;
 140                                 case KING:
 141                                         if (b->kings[WHITE] == i)
 142                                                 wk++;
 143                                         else if (b->kings[BLACK] == i)
 144                                                 bk++;
 145                                         break;
 146                                 default:
 147                                         return FALSE;
 148                         }
 149                         n_pieces++;
 150                 }
 151         }
 152         /* bad king count or more than 32 pieces total */
 153         if (wk != 1 || bk != 1 || n_pieces > 32)
 154                 return FALSE;
 155
 156         return TRUE;
 157 }
 158
 159 /* return board position in Forsyth-Edwards notation */
 160 char *
 161 current_fen_position(char *buf)
 162 {
 163         assert(board_is_legal(&brd));
 164
 165         char tmp[256];
 166         int i, j, p;
 167         int empty;
 168
 169         empty = 0;
 170         buf[0] = '\0';
 171
 172         for (i = 8; i > 0; i--) {
 173                 for (j = 0; j < 8; j++) {
 174                         p = square64[(i - 1) * 8 + j];
 175                         if (!p)
 176                                 empty++;
 177                         else {
 178                                 if (empty) {
 179                                         /* square is not empty, but last square is. add empty
 180                                            square count to result */
 181                                         snprintf(tmp, 2, "%d", empty);
 182                                         strcat(buf, tmp);
 183                                 }
 184                                 if (side_boards[WHITE] & BIT((i - 1) * 8 + j))
 185                                         sprintf(tmp, "%c", char_pieces[p]);
 186                                 else
 187                                         sprintf(tmp, "%c", (char)(char_pieces[p] + 'a' - 'A'));
 188                                 strcat(buf, tmp);
 189                                 empty = 0;
 190                         }
 191                 }
 192                 if (empty) {
 193                         snprintf(tmp, 2, "%d", empty);
 194                         strcat(buf, tmp);
 195                         empty = 0;
 196                 }
 197                 if (i != 1)
 198                         strcat(buf, "/");
 199         }
 200
 201         strcat(buf, !brd.wtm ? " w " : " b ");
 202
 203         if (!brd.castle_mask)
 204                 strcat(buf, "-");
 205         else {
 206                 if (brd.castle_mask & WHITE_CASTLE_KINGSIDE)
 207                         strcat(buf, "K");
 208                 if (brd.castle_mask & WHITE_CASTLE_QUEENSIDE)
 209                         strcat(buf, "Q");
 210                 if (brd.castle_mask & BLACK_CASTLE_KINGSIDE)
 211                         strcat(buf, "k");
 212                 if (brd.castle_mask & BLACK_CASTLE_QUEENSIDE)
 213                         strcat(buf, "q");
 214         }
 215
 216         strcat(buf, " ");
 217
 218         if (brd.ep == -1)
 219                 strcat(buf, "-");
 220         else
 221                 strcat(buf, char_board[brd.ep]);
 222
 223         return buf;
 224 }
 225
 226 /* remove piece from the board, update bitboard, zobrist and count */
 227 void
 228 remove_piece(int square, int piece, int side)
 229 {
 230         assert(square >= 0 && square <= 63);
 231         assert(piece >= PAWN && piece <= KING);
 232         assert(side == WHITE || side == BLACK);
 233         assert(material_complete[side] == material_pieces[side] + \
 234                         material_pawns[side]);
 235
 236         square64[square] = 0;
 237
 238         CLEAR(piece_boards[side][piece], square);               /* update bitboard */
 239         brd.hash_key ^= hash_code[side][piece][square]; /* update zobrist */
 240
 241         if (piece != KING) {
 242                 if (piece == PAWN) {
 243                         brd.hash_pawn_key ^= hash_code[side][PAWN][square];
 244                         material_pawns[side] -= piece_value[PAWN];
 245                 } else
 246                         material_pieces[side] -= piece_value[piece];
 247                 material_complete[side] -= piece_value[piece];
 248         }
 249         piece_count[side][piece]--;
 250 }
 251
 252 /* how many times this position was occured */
 253 int
 254 reps()
 255 {
 256         int i, rep;
 257
 258         /* search for the same hash_key */
 259         for (i = 0, rep = 0; i < game_history.count - 1; i++)
 260                 if (game_history.board[i].hash_key == brd.hash_key)
 261                         rep++;
 262
 263         return rep;
 264 }
 265
 266 /* setup board using FEN notation */
 267 int
 268 setup_board(char *fen)
 269 {
 270         int i, j, k, m, p;
 271         int color;
 272         char ranks[8][64];
 273         char side[8];
 274         char castle[8];
 275         char ep[8];
 276
 277         if (sscanf(fen, "%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/" \
 278                         "%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/" \
 279                         "%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK] " \
 280                         "%1[bw] %[KQkq-] %[1-8a-h-]", ranks[7], ranks[6], ranks[5], \
 281                         ranks[4], ranks[3], ranks[2], ranks[1], ranks[0], side, \
 282                         castle, ep) < 11)
 283                 return FALSE;
 284
 285         ZERO_MEM(brd);
 286         ZERO_MEM(game_history);
 287         ZERO_MEM(piece_boards);
 288         ZERO_MEM(r_pieces);
 289         ZERO_MEM(side_boards);
 290         ZERO_MEM(material_pawns);
 291         ZERO_MEM(material_pieces);
 292         ZERO_MEM(material_complete);
 293         ZERO_MEM(piece_count);
 294
 295         castled[WHITE] = castled[BLACK] = FALSE;
 296
 297         for (i = 0, j = 0; i < 8; i++, j = 0)
 298                 for (p = 0; p < strlen(ranks[i]); p++) {
 299                         if (ranks[i][p] < 'A') {                        /* empty squares */
 300                                 for (m = j, k = m; k < m + ranks[i][p] - '0'; k++, j++)
 301                                         square64[i * 8 + j] = 0;
 302                                 continue;
 303                         }
 304                         /* lowercase letter - BLACK, uppercase - WHITE */
 305                         color = ranks[i][p] > 'a'? BLACK : WHITE;
 306                         switch (ranks[i][p] - ('a' - 'A') * color) {
 307                                 case 'B':
 308                                         add_piece(i * 8 + j, BISHOP, color);
 309                                         break;
 310                                 case 'K':
 311                                         add_piece(i * 8 + j, KING, color);
 312                                         break;
 313                                 case 'N':
 314                                         add_piece(i * 8 + j, KNIGHT, color);
 315                                         break;
 316                                 case 'P':
 317                                         add_piece(i * 8 + j, PAWN, color);
 318                                         break;
 319                                 case 'Q':
 320                                         add_piece(i * 8 + j, QUEEN, color);
 321                                         break;
 322                                 case 'R':
 323                                         add_piece(i * 8 + j, ROOK, color);
 324                                         break;
 325                         }
 326                         j++;
 327                 }
 328
 329         brd.wtm = (!strcmp(side, "w")) ? WHITE : BLACK;
 330
 331         brd.ep = -1;
 332         if (strncmp(ep, "-", 1)) {
 333                 i = (ep[0] - 'a') + (ep[1] - '1') * 8;
 334                 j = i + (brd.wtm == WHITE? 8 : -8);
 335                 /* polyglot compatibility hack */
 336                 if ((BIT(j - 1) & PAWNS(brd.wtm)) || (BIT(j + 1) & PAWNS(brd.wtm)))
 337                         brd.ep = i;
 338         }
 339         assert((brd.ep >= 16 && brd.ep <= 47) || brd.ep == -1);
 340
 341         brd.castle_mask = 0;
 342
 343         if (strchr(castle, 'K'))
 344                 brd.castle_mask |= WHITE_CASTLE_KINGSIDE;
 345         if (strchr(castle, 'Q'))
 346                 brd.castle_mask |= WHITE_CASTLE_QUEENSIDE;
 347         if (strchr(castle, 'k'))
 348                 brd.castle_mask |= BLACK_CASTLE_KINGSIDE;
 349         if (strchr(castle, 'q'))
 350                 brd.castle_mask |= BLACK_CASTLE_QUEENSIDE;
 351
 352         brd.fifty_rule = 0;
 353
 354         update_boards();
 355         calc_zobrist(&brd.hash_key, &brd.hash_pawn_key);
 356
 357         assert(board_is_legal(&brd));
 358         set_engine_value(&e.hopeless_moves, 0);
 359
 360         return TRUE;
 361 }
 362
 363 /* update bitboards, normaly after making moves */
 364 void
 365 update_boards(void)
 366 {
 367         r_pieces[WHITE] = PAWNS(WHITE) | KNIGHTS(WHITE) | BISHOPS(WHITE) | \
 368                                           ROOKS(WHITE) | QUEENS(WHITE);
 369         r_pieces[BLACK] = PAWNS(BLACK) | KNIGHTS(BLACK) | BISHOPS(BLACK) | \
 370                                           ROOKS(BLACK) | QUEENS(BLACK);
 371
 372         side_boards[WHITE] = r_pieces[WHITE] | KING(WHITE);
 373         side_boards[BLACK] = r_pieces[BLACK] | KING(BLACK);
 374
 375         complete = side_boards[WHITE] | side_boards[BLACK];
 376 }
 377
 378 /* simple board representation for debugging */
 379 void
 380 print_bb(uint64_t b)
 381 {
 382         int rank, file;
 383
 384         for (rank = 7; rank >= 0; rank--) {
 385                 for (file = 0; file < 8; file++)
 386                         if (b & (1ULL << (rank * 8 + file)))
 387                                 printf("* ");
 388                         else
 389                                 printf("X ");
 390                 printf("\n");
 391         }
 392         printf("\n");
 393 }
 394
 395 /* simple bitboard representation for debugging */
 396 void
 397 print_board()
 398 {
 399         int i, j, p;
 400         char pieces[] = {' ', 'P', 'N', 'B', 'R', 'Q', 'K'};
 401
 402         for (i = 7; i >= 0; i--) {
 403                 printf("%d      ", i + 1);
 404                 for (j = 0; j < 8; j++) {
 405                         p = square64[i * 8 + j];
 406                         if (p) {
 407                                 if (side_boards[BLACK] & BIT(i * 8 + j))
 408                                         printf("%c ", (char)(pieces[p] + ('a' - 'A')));
 409                                 else
 410                                         printf("%c ", pieces[p]);
 411                         } else
 412                                 printf(". ");
 413                 }
 414                 printf("\n");
 415         }
 416         printf("\n       a b c d e f g h\n");
 417 }