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 side_boards[2];                /* pieces for each side */
  60
  61 int castled[2];                                 /* WHITE or BLACK castled */
  62
  63 int material_complete[2];               /* sum of the material */
  64 int material_pawns[2];                  /* ... for pawns */
  65 int material_pieces[2];                 /* for pieces except pawns */
  66
  67 /* initial values according to Larry Kaufman */
  68 int piece_value[7] = { 0, 100, 325, 325, 500, 1000, 10000 };
  69
  70 int piece_count[2][7];                  /* count pieces of each type */
  71
  72 /* add piece to the board, update bitboard, zobrist and count */
  73 void
  74 add_piece(int square, int piece, int side)
  75 {
  76         assert(square >= 0 && square <= 63);
  77         assert(piece >= PAWN && piece <= KING);
  78         assert(side == WHITE || side == BLACK);
  79         assert(material_complete[side] == material_pieces[side] + \
  80                         material_pawns[side]);
  81
  82         square64[square] = piece;
  83
  84         SET(piece_boards[side][piece], square);                 /* update bitboard */
  85         SET(side_boards[side], square);                                 /* update bitboard */
  86         SET(complete, square);                                                  /* update bitboard */
  87         brd.hash_key ^= hash_code[side][piece][square]; /* update zobrist key */
  88
  89         if (piece == KING)
  90                 brd.kings[side] = square;
  91         else {
  92                 if (piece == PAWN) {
  93                         brd.hash_pawn_key ^= hash_code[side][PAWN][square];
  94                         material_pawns[side] += piece_value[PAWN];
  95                 } else
  96                         material_pieces[side] += piece_value[piece];
  97                 material_complete[side] += piece_value[piece];
  98         }
  99         piece_count[side][piece]++;
 100 }
 101
 102 int
 103 board_is_legal(struct board_t *b)
 104 {
 105         int i;
 106         int wk = 0;
 107         int bk = 0;
 108         int color;
 109         int n_pieces = 0;
 110
 111         for (i = 0; i < 64; i++) {
 112                 if (!square64[i]) {
 113                         /* if mailbox square isn't empty but bitboard's bit isn't set */
 114                         if (complete & BIT(i))
 115                                 return FALSE;
 116                 } else {
 117                         color = -1;
 118                         switch (square64[i]) {
 119                                 case PAWN:
 120                                         if (((PAWNS(WHITE) | PAWNS(BLACK)) & BIT(i)) == 0)
 121                                                 return FALSE;
 122                                         if (_FILE(square64[i]) == 0 || _FILE(square64[i]) == 7)
 123                                                 return FALSE;
 124                                         break;
 125                                 case KNIGHT:
 126                                         if (((KNIGHTS(WHITE) | KNIGHTS(BLACK)) & BIT(i)) == 0)
 127                                                 return FALSE;
 128                                         break;
 129                                 case BISHOP:
 130                                         if (((BISHOPS(WHITE) | BISHOPS(BLACK)) & BIT(i)) == 0)
 131                                                 return FALSE;
 132                                         break;
 133                                 case ROOK:
 134                                         if (((ROOKS(WHITE) | ROOKS(BLACK)) & BIT(i)) == 0)
 135                                                 return FALSE;
 136                                         break;
 137                                 case QUEEN:
 138                                         if (((QUEENS(WHITE) | QUEENS(BLACK)) & BIT(i)) == 0)
 139                                                 return FALSE;
 140                                         break;
 141                                 case KING:
 142                                         if (b->kings[WHITE] == i)
 143                                                 wk++;
 144                                         else if (b->kings[BLACK] == i)
 145                                                 bk++;
 146                                         break;
 147                                 default:
 148                                         return FALSE;
 149                         }
 150                         n_pieces++;
 151                 }
 152         }
 153         /* bad king count or more than 32 pieces total */
 154         if (wk != 1 || bk != 1 || n_pieces > 32)
 155                 return FALSE;
 156
 157         return TRUE;
 158 }
 159
 160 /* return board position in Forsyth-Edwards notation */
 161 char *
 162 current_fen_position(char *buf)
 163 {
 164         assert(board_is_legal(&brd));
 165
 166         char tmp[256];
 167         int i, j, p;
 168         int empty;
 169
 170         empty = 0;
 171         buf[0] = '\0';
 172
 173         for (i = 8; i > 0; i--) {
 174                 for (j = 0; j < 8; j++) {
 175                         p = square64[(i - 1) * 8 + j];
 176                         if (!p)
 177                                 empty++;
 178                         else {
 179                                 if (empty) {
 180                                         /* square is not empty, but last square is. add empty
 181                                            square count to result */
 182                                         snprintf(tmp, 2, "%d", empty);
 183                                         strcat(buf, tmp);
 184                                 }
 185                                 if (side_boards[WHITE] & BIT((i - 1) * 8 + j))
 186                                         sprintf(tmp, "%c", char_pieces[p]);
 187                                 else
 188                                         sprintf(tmp, "%c", (char)(char_pieces[p] + 'a' - 'A'));
 189                                 strcat(buf, tmp);
 190                                 empty = 0;
 191                         }
 192                 }
 193                 if (empty) {
 194                         snprintf(tmp, 2, "%d", empty);
 195                         strcat(buf, tmp);
 196                         empty = 0;
 197                 }
 198                 if (i != 1)
 199                         strcat(buf, "/");
 200         }
 201
 202         strcat(buf, !brd.wtm ? " w " : " b ");
 203
 204         if (!brd.castle_mask)
 205                 strcat(buf, "-");
 206         else {
 207                 if (brd.castle_mask & WHITE_CASTLE_KINGSIDE)
 208                         strcat(buf, "K");
 209                 if (brd.castle_mask & WHITE_CASTLE_QUEENSIDE)
 210                         strcat(buf, "Q");
 211                 if (brd.castle_mask & BLACK_CASTLE_KINGSIDE)
 212                         strcat(buf, "k");
 213                 if (brd.castle_mask & BLACK_CASTLE_QUEENSIDE)
 214                         strcat(buf, "q");
 215         }
 216
 217         strcat(buf, " ");
 218
 219         if (brd.ep == -1)
 220                 strcat(buf, "-");
 221         else
 222                 strcat(buf, char_board[brd.ep]);
 223
 224         return buf;
 225 }
 226
 227 /* remove piece from the board, update bitboard, zobrist and count */
 228 void
 229 remove_piece(int square, int piece, int side)
 230 {
 231         assert(square >= 0 && square <= 63);
 232         assert(piece >= PAWN && piece <= KING);
 233         assert(side == WHITE || side == BLACK);
 234         assert(material_complete[side] == material_pieces[side] + \
 235                         material_pawns[side]);
 236
 237         square64[square] = 0;
 238
 239         CLEAR(piece_boards[side][piece], square);               /* update bitboard */
 240         CLEAR(side_boards[side], square);                               /* update bitboard */
 241         CLEAR(complete, square);                                                /* update bitboard */
 242         brd.hash_key ^= hash_code[side][piece][square]; /* update zobrist */
 243
 244         if (piece != KING) {
 245                 if (piece == PAWN) {
 246                         brd.hash_pawn_key ^= hash_code[side][PAWN][square];
 247                         material_pawns[side] -= piece_value[PAWN];
 248                 } else
 249                         material_pieces[side] -= piece_value[piece];
 250                 material_complete[side] -= piece_value[piece];
 251         }
 252         piece_count[side][piece]--;
 253 }
 254
 255 /* how many times this position was occured */
 256 int
 257 reps()
 258 {
 259         int i, rep;
 260
 261         /* search for the same hash_key */
 262         for (i = 0, rep = 0; i < game_history.count - 1; i++)
 263                 if (game_history.board[i].hash_key == brd.hash_key)
 264                         rep++;
 265
 266         return rep;
 267 }
 268
 269 /* setup board using FEN notation */
 270 int
 271 setup_board(char *fen)
 272 {
 273         int i, j, k, m, p;
 274         int color;
 275         char ranks[8][64];
 276         char side[8];
 277         char castle[8];
 278         char ep[8];
 279
 280         if (sscanf(fen, "%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/" \
 281                         "%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/" \
 282                         "%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK]/%8[1-8pnbrqkPNBRQK] " \
 283                         "%1[bw] %[KQkq-] %[1-8a-h-]", ranks[7], ranks[6], ranks[5], \
 284                         ranks[4], ranks[3], ranks[2], ranks[1], ranks[0], side, \
 285                         castle, ep) < 11)
 286                 return FALSE;
 287
 288         ZERO_MEM(brd);
 289         ZERO_MEM(game_history);
 290         ZERO_MEM(piece_boards);
 291         ZERO_MEM(side_boards);
 292         ZERO_MEM(material_pawns);
 293         ZERO_MEM(material_pieces);
 294         ZERO_MEM(material_complete);
 295         ZERO_MEM(piece_count);
 296
 297         castled[WHITE] = castled[BLACK] = FALSE;
 298
 299         for (i = 0, j = 0; i < 8; i++, j = 0)
 300                 for (p = 0; p < strlen(ranks[i]); p++) {
 301                         if (ranks[i][p] < 'A') {                        /* empty squares */
 302                                 for (m = j, k = m; k < m + ranks[i][p] - '0'; k++, j++)
 303                                         square64[i * 8 + j] = 0;
 304                                 continue;
 305                         }
 306                         /* lowercase letter - BLACK, uppercase - WHITE */
 307                         color = ranks[i][p] > 'a'? BLACK : WHITE;
 308                         switch (ranks[i][p] - ('a' - 'A') * color) {
 309                                 case 'B':
 310                                         add_piece(i * 8 + j, BISHOP, color);
 311                                         break;
 312                                 case 'K':
 313                                         add_piece(i * 8 + j, KING, color);
 314                                         break;
 315                                 case 'N':
 316                                         add_piece(i * 8 + j, KNIGHT, color);
 317                                         break;
 318                                 case 'P':
 319                                         add_piece(i * 8 + j, PAWN, color);
 320                                         break;
 321                                 case 'Q':
 322                                         add_piece(i * 8 + j, QUEEN, color);
 323                                         break;
 324                                 case 'R':
 325                                         add_piece(i * 8 + j, ROOK, color);
 326                                         break;
 327                         }
 328                         j++;
 329                 }
 330
 331         brd.wtm = (!strcmp(side, "w")) ? WHITE : BLACK;
 332
 333         brd.ep = -1;
 334         if (strncmp(ep, "-", 1)) {
 335                 i = (ep[0] - 'a') + (ep[1] - '1') * 8;
 336                 j = i + (brd.wtm == WHITE? 8 : -8);
 337                 /* polyglot compatibility hack */
 338                 if ((BIT(j - 1) & PAWNS(brd.wtm)) || (BIT(j + 1) & PAWNS(brd.wtm)))
 339                         brd.ep = i;
 340         }
 341         assert((brd.ep >= 16 && brd.ep <= 47) || brd.ep == -1);
 342
 343         brd.castle_mask = 0;
 344
 345         if (strchr(castle, 'K'))
 346                 brd.castle_mask |= WHITE_CASTLE_KINGSIDE;
 347         if (strchr(castle, 'Q'))
 348                 brd.castle_mask |= WHITE_CASTLE_QUEENSIDE;
 349         if (strchr(castle, 'k'))
 350                 brd.castle_mask |= BLACK_CASTLE_KINGSIDE;
 351         if (strchr(castle, 'q'))
 352                 brd.castle_mask |= BLACK_CASTLE_QUEENSIDE;
 353
 354         brd.fifty_rule = 0;
 355
 356         update_boards();
 357         calc_zobrist(&brd.hash_key, &brd.hash_pawn_key);
 358
 359         assert(board_is_legal(&brd));
 360         set_engine_value(&e.hopeless_moves, 0);
 361
 362         return TRUE;
 363 }
 364
 365 /* update bitboards, normaly after making moves */
 366 void
 367 update_boards(void)
 368 {
 369         side_boards[WHITE] = PAWNS(WHITE) | KNIGHTS(WHITE) | BISHOPS(WHITE) | \
 370                                           ROOKS(WHITE) | QUEENS(WHITE) | KING(WHITE);
 371         side_boards[BLACK] = PAWNS(BLACK) | KNIGHTS(BLACK) | BISHOPS(BLACK) | \
 372                                           ROOKS(BLACK) | QUEENS(BLACK) | KING(BLACK);
 373
 374         complete = side_boards[WHITE] | side_boards[BLACK];
 375 }
 376
 377 /* simple board representation for debugging */
 378 void
 379 print_bb(uint64_t b)
 380 {
 381         int rank, file;
 382
 383         for (rank = 7; rank >= 0; rank--) {
 384                 for (file = 0; file < 8; file++)
 385                         if (b & (1ULL << (rank * 8 + file)))
 386                                 printf("* ");
 387                         else
 388                                 printf("X ");
 389                 printf("\n");
 390         }
 391         printf("\n");
 392 }
 393
 394 /* simple bitboard representation for debugging */
 395 void
 396 print_board()
 397 {
 398         int i, j, p;
 399         char pieces[] = {' ', 'P', 'N', 'B', 'R', 'Q', 'K'};
 400
 401         for (i = 7; i >= 0; i--) {
 402                 printf("%d  ", i + 1);
 403                 for (j = 0; j < 8; j++) {
 404                         p = square64[i * 8 + j];
 405                         if (p) {
 406                                 if (side_boards[BLACK] & BIT(i * 8 + j))
 407                                         printf("%c ", (char)(pieces[p] + ('a' - 'A')));
 408                                 else
 409                                         printf("%c ", pieces[p]);
 410                         } else
 411                                 printf(". ");
 412                 }
 413                 printf("\n");
 414         }
 415         printf("\n   a b c d e f g h\n");
 416 }