1/* 2 Sjeng - a chess variants playing program 3 Copyright (C) 2000 Gian-Carlo Pascutto 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 2 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; if not, write to the Free Software 17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18 19 File: newbook.c 20 Purpose: general function concerning the binary hashed book 21 22*/ 23 24#include "sjeng.h" 25#include "protos.h" 26#include "extvars.h" 27#include <ndbm.h> 28#include <sys/stat.h> 29#include <sys/fcntl.h> 30#include <inttypes.h> 31#include <errno.h> 32#include <math.h> 33 34#define BUILDTHRESHOLD 2 35#define PLAYTHRESHOLD 3 36 37typedef struct 38{ 39 uint32_t hashkey; 40} hashkey_t; 41 42typedef struct 43{ 44 uint32_t played; 45 int32_t score; 46} posinfo_t; 47 48typedef struct 49{ 50 int32_t result; /* 0: 1-0 1:1/2 2:0-1 3:? */ 51} pgn_header_t; 52 53uint32_t kksize; 54unsigned char *keycache; 55 56uint32_t bookpos[400], booktomove[400], bookidx; 57 58int gamenum; 59 60void get_header(FILE *pgnbook, pgn_header_t *pgn_header) 61{ 62 int ch; 63 char buff[STR_BUFF]; 64 int b; 65 int terminate = FALSE; 66 67 memset(pgn_header, 0, sizeof(pgn_header_t)); 68 69 while(!terminate) 70 { 71 ch = getc(pgnbook); 72 73 if (ch == EOF) 74 break; 75 76 /* beginning of a header field */ 77 if (ch == '[') 78 { 79 b = 0; 80 memset(buff, 0, sizeof(buff)); 81 82 while(((buff[b++] = getc(pgnbook)) != ']') && (b < STR_BUFF)); 83 buff[--b] = '\0'; 84 85 /* buff now contains the field, minus the [] */ 86 /* file position is just after ] */ 87 88 //printf ("Read header: -%s-\n", buff); 89 90 if (!strncmp("Result", buff, 6)) 91 { 92 if (strstr(buff+6, "1-0")) 93 pgn_header->result = 0; 94 else if (strstr(buff+6, "1/2-1/2")) 95 pgn_header->result = 1; 96 else if (strstr(buff+6, "0-1")) 97 pgn_header->result = 2; 98 else if (strstr(buff+6, "*")) 99 pgn_header->result = 3; 100 } 101 } 102 /* space or newlines between headers */ 103 else if (ch == ' ' || ch == '\n' || ch == '\r'); 104 else /* no more headers, put back last char */ 105 { 106 //printf("End of header: -%c-\n", ch); 107 terminate = TRUE; 108 ungetc(ch, pgnbook); 109 } 110 } 111} 112 113void add_current(DBM * binbook, pgn_header_t pgn_header) 114{ 115 hashkey_t key; 116 posinfo_t posinfo; 117 posinfo_t *pst; 118 datum index; 119 datum data; 120 int win = 0, loss = 0; 121 int ret; 122 123 /* fill in the key field */ 124 key.hashkey = htonl(hash ^ ToMove); 125 126 if (keycache[key.hashkey % kksize] >= BUILDTHRESHOLD) 127 { 128 129 index.dptr = (char*) &key; 130 index.dsize = sizeof(key); 131 132 posinfo.played = htonl(2); 133 posinfo.score = 0; 134 135 data.dptr = (char*) &posinfo; 136 data.dsize = sizeof(posinfo); 137 138 ret = dbm_store(binbook, index, data, DBM_INSERT); 139 140 if (ret < 0) 141 printf("dbm_store %d\n", errno); 142 if (ret == 1) 143 { 144 data = dbm_fetch(binbook, index); 145 146 pst = (posinfo_t *) data.dptr; 147 pst->played = htonl(ntohl(pst->played)+1); 148 149 dbm_store(binbook, index, data, DBM_REPLACE); 150 } 151 } 152 else 153 keycache[key.hashkey % kksize]++; 154 155} 156 157void replay_game(FILE *pgnbook, DBM * binbook, pgn_header_t pgn_header) 158{ 159 int ch, xch; 160 char movebuff[STR_BUFF], sjmove[STR_BUFF]; 161 int ms; 162 int brackets = 0, braces = 0; 163 int gameend = FALSE; 164 move_s moves[MOVE_BUFF]; 165 int match, num_moves, i; 166 int limit = 0; 167 int ic; 168 169 /* reset board */ 170 init_game(); 171 initialize_hash(); 172 173 putchar('.'); 174 175 while (!gameend) 176 { 177 ch = getc(pgnbook); 178 179 if (ch == EOF) 180 return; 181 182 if (ch == ' ' || ch == '\n') 183 { 184 /* just skip and go on */ 185 } 186 else if (ch == '{') 187 { 188 brackets++; 189 /* we want to skip everything till we get brackets 190 * and braces back to 0 */ 191 192 while (brackets > 0 || braces > 0) 193 { 194 xch = getc(pgnbook); 195 if (xch == '}') 196 brackets--; 197 else if (xch == '{') 198 brackets++; 199 else if (xch == '[') 200 braces++; 201 else if (xch == ']') 202 braces--; 203 else if (xch == EOF) 204 break; 205 } 206 } 207 else if (ch == '[') 208 { 209 braces++; 210 while (brackets > 0 || braces > 0) 211 { 212 xch = getc(pgnbook); 213 if (xch == '}') 214 brackets--; 215 else if (xch == '{') 216 brackets++; 217 else if (xch == '[') 218 braces++; 219 else if (xch == ']') 220 braces--; 221 else if (xch == EOF) 222 break; 223 } 224 } 225 else if (ch == '*') 226 { 227 /* result string: unfinished game */ 228 /* seek next header */ 229 while (((ch = getc(pgnbook)) != '[') && !feof(pgnbook)); 230 ungetc(ch, pgnbook); 231 gameend = TRUE; 232 } 233 else if (isdigit(ch)) 234 { 235 xch = getc(pgnbook); 236 237 if (xch == EOF) 238 { 239 return; 240 } 241 /* either a move number or a result string */ 242 else if (isdigit(xch)) /* 2 digits...must be move number */ 243 { 244 while(((ch = getc(pgnbook)) != '.') && !feof(pgnbook)); 245 } 246 else if (xch != '.') 247 { 248 /* not a move numer, must be result */ 249 /* seek to next header */ 250 while (((ch = getc(pgnbook)) != '[') && !feof(pgnbook)); 251 ungetc(ch, pgnbook); 252 253 gameend = TRUE; 254 } 255 } 256 else if (isalpha(ch)) 257 { 258 /* parse one move */ 259 ms = 0; 260 movebuff[ms++] = ch; 261 262 while(movebuff[ms-1] != ' ' && movebuff[ms-1] != '\n') 263 { 264 movebuff[ms++] = getc(pgnbook); 265 } 266 movebuff[--ms] = '\0'; /* scratch last bogus char */ 267 268 /* movebuff now contains -hopefully- the move in SAN */ 269 // printf("Read move: -%s- ", &movebuff); 270 271 /* now, generate all moves from the current pos and try 272 * to get a match */ 273 match = FALSE; 274 num_moves = 0; 275 // 21-3 276 ply = 0; 277 278 gen (&moves[0]); 279 num_moves = numb_moves; 280 281 ic = in_check(); 282 283 for (i = 0; i < num_moves; i++) 284 { 285 comp_to_san(moves[i], sjmove); 286 if (!strcmp(movebuff, sjmove)) 287 { 288 /* moves matched !*/ 289 make(&moves[0], i); 290 291 match = TRUE; 292 if (check_legal(&moves[0], i, ic)) 293 { 294 break; 295 } 296 else 297 { 298 printf("Illegal move from PGN!\n"); 299 printf("Game: %d Move: %s\n", gamenum, movebuff); 300 break; 301 } 302 } 303 } 304 305 limit++; 306 307 if (match == FALSE || limit > 40) 308 { 309 if (match == FALSE) 310 printf("No move match! -%s-\n", movebuff); 311 312 /* skip junk game */ 313 while (((ch = getc(pgnbook)) != '[') && !feof(pgnbook)); 314 ungetc(ch, pgnbook); 315 gameend = TRUE; 316 } 317 else 318 { 319 add_current(binbook, pgn_header); 320 } 321 } 322 } 323} 324 325void weed_book(DBM * binbook) 326{ 327 datum data; 328 datum index; 329 posinfo_t *ps; 330 int weeds; 331 int positions; 332 333 do 334 { 335 weeds = 0; 336 positions = 0; 337 338 index = dbm_firstkey(binbook); 339 340 while (index.dptr) 341 { 342 positions++; 343 344 data = dbm_fetch(binbook, index); 345 ps = (posinfo_t *) data.dptr; 346 347 if (ps && ntohl(ps->played) < PLAYTHRESHOLD) 348 { 349 dbm_delete(binbook, index); 350 weeds++; 351 } 352 353 index = dbm_nextkey (binbook); 354 } 355 356 printf("Weeded %d moves.\n", weeds); 357 } 358 while (weeds > 0); 359 360 printf("%d unique positions.\n", positions); 361 362 printf("Done.\n"); 363} 364 365void build_book (void) 366{ 367 FILE *pgnbook; 368 DBM * binbook; 369 pgn_header_t pgn_header; 370 char bookname[FILENAME_MAX], kks[STR_BUFF]; 371 372 printf("\nName of PGN book: "); 373 rinput(bookname, STR_BUFF, stdin); 374 375 pgnbook = fopen(bookname, "r"); 376 377 if (pgnbook == NULL) 378 { 379 printf("PGN book not found!\n"); 380 exit(EXIT_FAILURE); 381 } 382 383 if (Variant == Normal) 384 binbook = dbm_open("nbook", O_CREAT|O_TRUNC|O_RDWR, 00664); 385 else if (Variant == Suicide) 386 binbook = dbm_open("sbook", O_CREAT|O_TRUNC|O_RDWR, 00664); 387 else if (Variant == Losers) 388 binbook = dbm_open("lbook", O_CREAT|O_TRUNC|O_RDWR, 00664); 389 else 390 binbook = dbm_open("zbook", O_CREAT|O_TRUNC|O_RDWR, 00664); 391 392 if (binbook == NULL) 393 { 394 printf("Error opening binbook.\n"); 395 exit(EXIT_FAILURE); 396 } 397 398 printf("\nSize of KeyCache (bytes): "); 399 rinput(kks, STR_BUFF, stdin); 400 401 kksize = atoi(kks); 402 403 printf("Freeing hash and eval cache\n"); 404 free_hash(); 405 free_ecache(); 406 407 printf("Allocating keycache\n"); 408 409 keycache = (unsigned char *) calloc(kksize, sizeof(unsigned char)); 410 411 if (keycache == NULL) 412 { 413 printf("Not enough RAM!\n"); 414 exit(EXIT_FAILURE); 415 } 416 417 printf("Building"); 418 419 gamenum = 0; 420 421 while (!feof(pgnbook)) 422 { 423 gamenum++; 424 get_header(pgnbook, &pgn_header); 425 replay_game(pgnbook, binbook, pgn_header); 426 }; 427 428 free(keycache); 429 430 printf("\nWeeding book moves.\n"); 431 weed_book(binbook); 432 433 fclose(pgnbook); 434 dbm_close(binbook); 435 436 alloc_hash(); 437 alloc_ecache(); 438} 439 440 441move_s choose_binary_book_move (void) 442{ 443 DBM * binbook; 444 hashkey_t key; 445 posinfo_t *ps; 446 datum index; 447 datum data; 448 move_s moves[MOVE_BUFF], bestmove; 449 move_s bookmoves[MOVE_BUFF]; 450 int num_bookmoves; 451 int raw; 452 int num_moves, i; 453 char output[6]; 454 int32_t scores[MOVE_BUFF], best_score = 0; 455 456 srand((unsigned)time(0)); 457 458 if (Variant == Normal) 459 binbook = dbm_open("nbook", O_RDONLY, 0); 460 else if (Variant == Suicide) 461 binbook = dbm_open("sbook", O_RDONLY, 0); 462 else if (Variant == Losers) 463 binbook = dbm_open("lbook", O_RDONLY, 0); 464 else 465 binbook = dbm_open("zbook", O_RDONLY, 0); 466 467 468 if (binbook == NULL) 469 { 470 printf("No BinBook found.\n"); 471 return dummy; 472 } 473 474 num_moves = 0; 475 raw = 0; 476 num_bookmoves = 0; 477 478 gen(&moves[0]); 479 num_moves = numb_moves; 480 481 for (i = 0; i < num_moves; i++) 482 { 483 make(&moves[0], i); 484 485 if (check_legal(&moves[0], i, TRUE)) 486 { 487 488 if (is_draw()) 489 { 490 /* ok this is fishy: we can get a draw-by-rep 491 * while still in book. let the search take over. 492 * this prevents a trick where the player simply 493 * retreats his knights and Sjeng does the same */ 494 book_ply = 50; 495 496 printf("Anti-book-rep-trick...\n"); 497 498 unmake(&moves[0], i); 499 dbm_close(binbook); 500 return dummy; 501 } 502 503 key.hashkey = htonl(hash ^ ToMove); 504 index.dptr = (char*) &key; 505 index.dsize = sizeof(key); 506 507 data = dbm_fetch(binbook, index); 508 509 if (data.dptr != NULL) 510 { 511 ps = (posinfo_t *) data.dptr; 512 513 raw++; 514 515 comp_to_coord(moves[i], output); 516 517 printf("Move %s: %u times played, %d learned\n", output, 518 (uint32_t)ntohl(ps->played), (int)ntohl(ps->score)); 519 520 if ((ntohl(ps->played) + ntohl(ps->score)) >= PLAYTHRESHOLD) 521 { 522 scores[num_bookmoves] = ntohl(ps->played) + ntohl(ps->score); 523 bookmoves[num_bookmoves] = moves[i]; 524 num_bookmoves++; 525 } 526 } 527 } 528 529 unmake(&moves[0], i); 530 } 531 532 dbm_close(binbook); 533 534 printf("Book moves: raw: %d cut : %d\n", raw, num_bookmoves); 535 536 if (!num_bookmoves) 537 return dummy; 538 539 /* find the top frequency: */ 540 for (i = 0; i < num_bookmoves; i++) { 541 if (scores[i] > best_score) { 542 best_score = scores[i]; 543 } 544 } 545 546 /* add some randomness to each frequency: */ 547 for (i = 0; i < num_bookmoves; i++) { 548 /* weed out very rare lines */ 549 if (scores[i] * 15 > best_score) 550 { 551 scores[i] += (int) ((float)(((float)(rand())/RAND_MAX)) * ((float)best_score*1.35)); 552 } 553 else 554 { 555 scores[i] = 0; 556 } 557 } 558 559 /* now pick our best move: */ 560 best_score = 0; 561 for (i = 0; i < num_bookmoves; i++) { 562 if (scores[i] > best_score) { 563 best_score = scores[i]; 564 bestmove = bookmoves[i]; 565 } 566 } 567 568 /* we need to find the hash here so learning will 569 * be correct */ 570 571 make(&bestmove, 0); 572 573 bookpos[bookidx] = hash; 574 booktomove[bookidx++] = ToMove; 575 576 unmake(&bestmove, 0); 577 578 return bestmove; 579} 580 581 582void book_learning(int result) 583{ 584 DBM * binbook; 585 hashkey_t key; 586 posinfo_t *ps; 587 datum index; 588 datum data; 589 float playinc; 590 float factor; 591 int pi; 592 int iters; 593 static const float factortable[] = {1.0f, 0.5f, 0.25f, 0.12f, 0.08f, 0.05f, 0.03f}; 594 595 if (bookidx == 0) return; 596 597 if (Variant == Normal) 598 binbook = dbm_open("nbook", O_RDWR, 0); 599 else if (Variant == Suicide) 600 binbook = dbm_open("sbook", O_RDWR, 0); 601 else if (Variant == Losers) 602 binbook = dbm_open("lbook", O_RDWR, 0); 603 else if (Variant == Crazyhouse) 604 binbook = dbm_open("zbook", O_RDWR, 0); 605 else if (Variant == Bughouse) 606 return; 607 608 if (binbook == NULL) 609 { 610 printf("No BinBook found, not learning.\n"); 611 return; 612 } 613 614 iters = 0; 615 616 while ((iters < 7) && ((bookidx - iters) > 0)) 617 { 618 iters++; 619 620 factor = factortable[iters-1]; 621 622 key.hashkey = htonl(bookpos[bookidx-iters] ^ booktomove[bookidx-iters]); 623 index.dptr = (char*) &key; 624 index.dsize = sizeof(key); 625 626 data = dbm_fetch(binbook, index); 627 628 if (data.dptr != NULL) 629 { 630 ps = (posinfo_t *) data.dptr; 631 632 playinc = 0; 633 634 if (result == WIN) 635 { 636 if (my_rating <= opp_rating) 637 playinc = 0.5f * factor; 638 else 639 playinc = 0.25f * factor; 640 } 641 else if (result == LOSS) 642 { 643 if (my_rating >= opp_rating) 644 playinc = -0.5f * factor; 645 else 646 playinc = -0.25f * factor; 647 } 648 else 649 { 650 if (my_rating >= opp_rating) 651 playinc = -0.3f * factor; 652 else 653 playinc = 0.3f * factor; 654 } 655 656 if (fabs((double)((ntohl(ps->played) + ntohl(ps->score))) * playinc) < 1.0) 657 { 658 pi = (int)(playinc * 10.0f); 659 } 660 else 661 { 662 pi = (int)((float)(ntohl(ps->played) + ntohl(ps->score))*(float)playinc); 663 } 664 665 /* don't 'overlearn' */ 666 if (abs((ps->score)+pi) < (ntohl(ps->played)*5)) 667 { 668 669 printf("Learning opening %u, played %u, old score %d, new score %d\n", 670 (uint32_t)bookpos[bookidx-iters], 671 (uint32_t)ntohl(ps->played), 672 (int32_t)ntohl(ps->score), (int32_t)ntohl(ps->score)+pi); 673 674 ps->score = htonl(ntohl(ps->score)+pi); 675 676 dbm_store(binbook, index, data, DBM_REPLACE); 677 } 678 } 679 else 680 { 681 printf("No hit in hashed book, not learning.\n"); 682 } 683 } 684 685 dbm_close(binbook); 686 687 return; 688}; 689