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