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