10 int cto_fd, ctg_fd, ctb_fd;
12 unsigned int tbl2[] = {
13 0x3100d2bf, 0x3118e3de, 0x34ab1372, 0x2807a847,
14 0x1633f566, 0x2143b359, 0x26d56488, 0x3b9e6f59,
15 0x37755656, 0x3089ca7b, 0x18e92d85, 0x0cd0e9d8,
16 0x1a9e3b54, 0x3eaa902f, 0x0d9bfaae, 0x2f32b45b,
17 0x31ed6102, 0x3d3c8398, 0x146660e3, 0x0f8d4b76,
18 0x02c77a5f, 0x146c8799, 0x1c47f51f, 0x249f8f36,
19 0x24772043, 0x1fbc1e4d, 0x1e86b3fa, 0x37df36a6,
20 0x16ed30e4, 0x02c3148e, 0x216e5929, 0x0636b34e,
21 0x317f9f56, 0x15f09d70, 0x131026fb, 0x38c784b1,
22 0x29ac3305, 0x2b485dc5, 0x3c049ddc, 0x35a9fbcd,
23 0x31d5373b, 0x2b246799, 0x0a2923d3, 0x08a96e9d,
24 0x30031a9f, 0x08f525b5, 0x33611c06, 0x2409db98,
25 0x0ca4feb2, 0x1000b71e, 0x30566e32, 0x39447d31,
26 0x194e3752, 0x08233a95, 0x0f38fe36, 0x29c7cd57,
27 0x0f7b3a39, 0x328e8a16, 0x1e7d1388, 0x0fba78f5,
28 0x274c7e7c, 0x1e8be65c, 0x2fa0b0bb, 0x1eb6c371
31 signed char data[] = {
32 0x36, 0xb6, 0x0f, 0x79, 0x61, 0x1f, 0x50, 0xde, 0x61, 0xb9, 0x52, 0x24, 0xb3, 0xac, 0x6e, 0x5e, 0x0a, 0x69, 0xbd, 0x61, 0x61, 0xc5
35 void output_stats(char *result, int invert)
37 unsigned char *ptr = result;
43 printf("%u,", (ptr[0] << 16) | (ptr[1] << 8) | ptr[2]);
44 printf("%u,", (ptr[6] << 16) | (ptr[7] << 8) | ptr[8]);
45 printf("%u,", (ptr[3] << 16) | (ptr[4] << 8) | ptr[5]);
47 printf("%u,", (ptr[3] << 16) | (ptr[4] << 8) | ptr[5]);
48 printf("%u,", (ptr[6] << 16) | (ptr[7] << 8) | ptr[8]);
49 printf("%u,", (ptr[0] << 16) | (ptr[1] << 8) | ptr[2]);
58 int rat2_sum, rat2_div;
59 rat2_div = (ptr[0] << 16) | (ptr[1] << 8) | ptr[2];
60 rat2_sum = (ptr[3] << 24) | (ptr[4] << 16) | (ptr[5] << 8) | ptr[6];
65 printf("%u,%u", rat2_sum / rat2_div, rat2_div);
72 unsigned int gen_hash(signed char *ptr, unsigned len)
78 for (i = 0; i < len; ++i) {
79 signed char ch = *ptr++;
80 tmp += ((0x0f - (ch & 0x0f)) << 2) + 1;
81 hash += tbl2[tmp & 0x3f];
82 tmp += ((0xf0 - (ch & 0xf0)) >> 2) + 1;
83 hash += tbl2[tmp & 0x3f];
88 void decode_fen_board(char *str, char *board)
134 fprintf(stderr, "Unknown FEN board character '%c'\n", *str);
142 void invert_board(char *board)
147 for (y = 0; y < 4; ++y) {
148 for (x = 0; x < 8; ++x) {
149 char tmp = board[y * 8 + (x)];
150 board[y * 8 + (x)] = board[(7-y) * 8 + (x)];
151 board[(7-y) * 8 + (x)] = tmp;
156 for (y = 0; y < 8; ++y) {
157 for (x = 0; x < 8; ++x) {
158 if (board[y * 8 + x] == toupper(board[y * 8 + x])) {
159 board[y * 8 + x] = tolower(board[y * 8 + x]);
161 board[y * 8 + x] = toupper(board[y * 8 + x]);
167 int needs_flipping(char *board, char *castling_rights)
171 // never flip if either side can castle
172 if (strcmp(castling_rights, "-") != 0)
175 for (y = 0; y < 8; ++y) {
176 for (x = 0; x < 4; ++x) {
177 if (board[y * 8 + x] == 'K')
186 void flip_board(char *board, char *eps)
191 for (y = 0; y < 8; ++y) {
192 for (x = 0; x < 4; ++x) {
193 char tmp = board[y * 8 + x];
194 board[y * 8 + (x)] = board[y * 8 + (7-x)];
195 board[y * 8 + (7-x)] = tmp;
199 // flip the en passant square
200 if (strcmp(eps, "-") != 0) {
201 int epsc = eps[0] - 'a';
202 eps[0] = 'a' + (7 - epsc);
206 unsigned char position[32];
212 position[pos_len] <<= 1;
214 position[pos_len] |= 1;
216 if (--bits_left == 0) {
222 void dump_fen(char *board, int invert, int flip, char *castling_rights, char *ep_square)
225 for (y = 0; y < 8; ++y) {
227 for (x = 0; x < 8; ++x) {
228 int xx = (flip) ? (7-x) : x;
230 if (board[y * 8 + xx] == ' ') {
234 putchar('0' + space);
235 putchar(board[y * 8 + xx]);
240 putchar('0' + space);
251 printf(" %s ", castling_rights);
252 if (flip && strcmp(ep_square, "-") != 0) {
253 printf("%c%c 0 0\n", 'a' + (7 - (ep_square[0] - 'a')), ep_square[1]);
255 printf("%s 0 0\n", ep_square);
259 void encode_position(char *board, int invert, char *castling_rights, char *ep_column)
265 memset(position, 0, 32);
267 // leave some room for the header byte, which will be filled last
271 // slightly unusual ordering
272 for (x = 0; x < 8; ++x) {
273 for (y = 0; y < 8; ++y) {
274 switch (board[(7-y) * 8 + x]) {
366 if (strcmp(ep_column, "-") != 0) {
367 int epcn = ep_column[0] - 'a';
369 if ((epcn > 0 && board[3*8 + epcn - 1] == 'P') ||
370 (epcn < 7 && board[3*8 + epcn + 1] == 'P')) {
375 // really odd padding
379 // find the right number of bits
380 int right = (ep_any) ? 3 : 8;
382 // castling needs four more
383 if (strcmp(castling_rights, "-") != 0) {
389 if (bits_left > right)
390 nb = bits_left - right;
391 else if (bits_left < right)
392 nb = bits_left + 8 - right;
394 if (bits_left == 8 && strcmp(castling_rights, "-") == 0 && !ep_any)
397 for (i = 0; i < nb; ++i) {
404 int epcn = ep_column[0] - 'a';
406 put_bit(epcn & 0x04);
407 put_bit(epcn & 0x02);
408 put_bit(epcn & 0x01);
412 if (strcmp(castling_rights, "-") != 0) {
414 put_bit(strchr(castling_rights, 'K') != NULL);
415 put_bit(strchr(castling_rights, 'Q') != NULL);
416 put_bit(strchr(castling_rights, 'k') != NULL);
417 put_bit(strchr(castling_rights, 'q') != NULL);
419 put_bit(strchr(castling_rights, 'k') != NULL);
420 put_bit(strchr(castling_rights, 'q') != NULL);
421 put_bit(strchr(castling_rights, 'K') != NULL);
422 put_bit(strchr(castling_rights, 'Q') != NULL);
427 if (bits_left == 8) {
433 int i, nd = 8 - bits_left;
434 for (i = 0; i < nd; ++i)
439 // and the header byte
440 position[0] = pos_len;
442 if (strcmp(castling_rights, "-") != 0)
450 for (i = 0; i < pos_len; ++i) {
451 printf("%02x ", position[i]);
458 int search_pos(unsigned c, char *result)
461 unsigned char pagebuf[4096];
465 lseek(cto_fd, c * 4 + 16, SEEK_SET);
467 read(cto_fd, buf, 4);
468 page = htonl(*((unsigned *)buf));
472 lseek(ctg_fd, page * 4096 + 4096, SEEK_SET);
473 read(ctg_fd, pagebuf, 4096);
478 int page_end = htons(*((short *)(pagebuf + 2)));
480 while (pos < page_end) {
481 if (pagebuf[pos] != position[0] ||
482 memcmp(pagebuf + pos, position, pos_len) != 0) {
483 // no match, skip through
484 pos += pagebuf[pos] & 0x1f;
489 pos += pagebuf[pos] & 0x1f;
490 memcpy(result, pagebuf + pos, pagebuf[pos] + 33);
498 int lookup_position(char *pos, unsigned len, char *result)
500 int hash = gen_hash(position, pos_len);
503 for (n = 0; n < 0x7fffffff; n = 2 * n + 1) {
504 unsigned c = (hash & n) + n;
506 // FIXME: adjust these bounds
510 if (search_pos(c, result))
526 struct moveenc movetable[] = {
528 0x01, 'N', 2, -1, -2,
539 0x0f, 'N', 1, -1, -2,
560 0x30, 'N', 2, -2, -1,
592 0x6b, 'K', 1, 0, 2, /* short castling */
612 0x8c, 'K', 1, -1, -1,
663 0xda, 'N', 1, -2, -1,
685 0xf6, 'K', 1, 0, -2, /* long castling */
695 int find_piece(char *board, char piece, int num)
698 for (x = 0; x < 8; ++x) {
699 for (y = 0; y < 8; ++y) {
700 if (board[(7-y) * 8 + x] != piece)
707 fprintf(stderr, "Couldn't find piece '%c' number %u\n", piece, num);
711 void execute_move(char *board, char *castling_rights, int inverted, char *ep_square, int from_square, int to_square)
713 int black_ks, black_qs, white_ks, white_qs;
716 from_square = (7 - (from_square / 8)) * 8 + (from_square % 8);
717 to_square = (7 - (to_square / 8)) * 8 + (to_square % 8);
719 // compute the new castling rights
720 black_ks = (strchr(castling_rights, 'k') != NULL);
721 black_qs = (strchr(castling_rights, 'q') != NULL);
722 white_ks = (strchr(castling_rights, 'K') != NULL);
723 white_qs = (strchr(castling_rights, 'Q') != NULL);
725 if (board[from_square] == 'K') {
727 black_ks = black_qs = 0;
729 white_ks = white_qs = 0;
731 if (board[from_square] == 'R') {
733 if (from_square == 56) // h1
735 else if (from_square == 63) // h8
738 if (from_square == 56) // a1
740 else if (from_square == 63) // a8
744 if (board[to_square] == 'r') {
746 if (to_square == 0) // h1
748 else if (to_square == 7) // h8
751 if (to_square == 0) // a1
753 else if (to_square == 7) // a8
758 if ((black_ks | black_qs | white_ks | white_qs) == 0) {
759 strcpy(castling_rights, "-");
761 strcpy(castling_rights, "");
764 strcat(castling_rights, "K");
766 strcat(castling_rights, "Q");
768 strcat(castling_rights, "k");
770 strcat(castling_rights, "q");
774 if (board[from_square] == 'P' && to_square - from_square == -16) {
775 sprintf(ep_square, "%c%u", "abcdefgh"[from_square % 8], from_square / 8);
777 strcpy(ep_square, "-");
780 // is this move an en passant capture?
781 if (board[from_square] == 'P' && board[to_square] == ' ' &&
782 (to_square - from_square == -9 || to_square - from_square == -7)) {
783 board[to_square + 8] = ' ';
787 board[to_square] = board[from_square];
788 board[from_square] = ' ';
791 if (board[to_square] == 'P' && to_square < 8)
792 board[to_square] = 'Q';
794 if (board[to_square] == 'K' && to_square - from_square == 2) {
796 board[to_square - 1] = 'R';
797 board[to_square + 1] = ' ';
798 } else if (board[to_square] == 'K' && to_square - from_square == -2) {
800 board[to_square + 1] = 'R';
801 board[to_square - 2] = ' ';
809 for (y = 0; y < 8; ++y) {
810 for (x = 0; x < 8; ++x) {
811 putchar(board[y * 8 + x]);
816 printf("cr='%s' ep='%s'\n", castling_rights, ep_square);
820 void dump_move(char *board, char *castling_rights, char *ep_col, int invert, int flip, char move, char annotation)
823 char newboard[64], nkr[5], neps[3];
824 for (i = 0; i < sizeof(movetable)/sizeof(movetable[0]); ++i) {
825 int from_square, from_row, from_col;
826 int to_square, to_row, to_col;
830 if (move != movetable[i].encoding)
833 from_square = find_piece(board, movetable[i].piece, movetable[i].num);
834 from_row = from_square / 8;
835 from_col = from_square % 8;
837 to_row = (from_row + 8 + movetable[i].forward) % 8;
838 to_col = (from_col + 8 + movetable[i].right) % 8;
839 to_square = to_row * 8 + to_col;
841 // do the move, and look up the new position
842 memcpy(newboard, board, 64);
843 strcpy(nkr, castling_rights);
844 execute_move(newboard, nkr, invert, neps, from_square, to_square);
845 invert_board(newboard);
847 if (needs_flipping(newboard, nkr)) {
848 flip_board(newboard, neps);
852 encode_position(newboard, !invert, nkr, neps);
853 ret = lookup_position(position, pos_len, result);
857 invert_board(newboard);
859 dump_fen(newboard, !invert, flip, nkr, neps);
861 fprintf(stderr, "Destination move not found in book.\n");
866 // very useful for regression testing (some shell and
867 // you can walk the entire book quite easily)
869 invert_board(newboard);
870 dump_fen(newboard, !invert, flip, nkr, neps);
876 int fromcol = from_square % 8;
877 int fromrow = from_square / 8;
878 int tocol = to_square % 8;
879 int torow = to_square / 8;
882 fromrow = 7 - fromrow;
886 fromcol = 7 - fromcol;
891 "abcdefgh"[fromcol], fromrow + 1,
892 "abcdefgh"[tocol], torow + 1);
896 switch (annotation) {
918 printf(" (only move)");
921 printf(" (zugzwang)");
924 printf(" (unknown status 0x%02x)", annotation);
928 output_stats(result, invert);
932 fprintf(stderr, "ERROR: Unknown move 0x%02x\n", move);
936 void dump_info(char *board, char *castling_rights, char *ep_col, int invert, int flip, char *result)
938 int book_moves = result[0] >> 1;
943 output_stats(result, !invert);
946 for (i = 0; i < book_moves; ++i) {
947 dump_move(board, castling_rights, ep_col, invert, flip, result[i * 2 + 1], result[i * 2 + 2]);
951 int main(int argc, char **argv)
953 // encode the position
954 char board[64], result[256];
955 int invert = 0, flip;
958 ctg_fd = open("RybkaII.ctg", O_RDONLY);
959 cto_fd = open("RybkaII.cto", O_RDONLY);
960 ctb_fd = open("RybkaII.ctb", O_RDONLY);
961 decode_fen_board(argv[1], board);
963 // always from white's position
964 if (argv[2][0] == 'b') {
969 // and the white king is always in the right half
970 flip = needs_flipping(board, argv[3]);
972 flip_board(board, argv[4]);
980 for (y = 0; y < 8; ++y) {
981 for (x = 0; x < 8; ++x) {
982 putchar(board[y * 8 + x]);
989 encode_position(board, invert, argv[3], argv[4]);
990 ret = lookup_position(position, pos_len, result);
992 //fprintf(stderr, "Not found in book.\n");
996 dump_info(board, argv[3], argv[4], invert, flip, result);