book.cpp

   1 /***************************************************************************
   2                           main.cpp  -  description
   3                              -------------------
   4     begin                : Mer Oct 19 2005
   5     copyright            : (C) 2005 by Maurizio Monge
   6     email                : monge@linuz.sns.it
   7  ***************************************************************************/
   8
   9 /***************************************************************************
  10  *                                                                         *
  11  *   This program is free software; you can redistribute it and/or modify  *
  12  *   it under the terms of the GNU General Public License as published by  *
  13  *   the Free Software Foundation; either version 2 of the License, or     *
  14  *   (at your option) any later version.                                   *
  15  *                                                                         *
  16  ***************************************************************************/
  17
  18 #include "engine.h"
  19 #include "utils.h"
  20
  21 /* each move in the book will be stored in 24 bits */
  22 struct PACKED ComprMove
  23 {
  24     unsigned int move : 14;
  25     unsigned int stat : 10;
  26 };
  27
  28 /* MoveMark and MoveStat are for the book creation */
  29 struct PACKED MoveMark
  30 {
  31     uint16_t move;
  32     uint32_t stat;
  33 };
  34
  35 class MoveStat
  36 {
  37 private:
  38     MoveMark mv_first;
  39     uint16_t oth_size;
  40     MoveMark *mv_oth;
  41
  42 public:
  43     int num;
  44     unsigned int tot;
  45
  46     MoveMark& operator[](int i) {
  47         if(i==0)
  48             return mv_first;
  49         if(i > oth_size)
  50         {
  51             oth_size = i;
  52             mv_oth = (MoveMark*)realloc(mv_oth, oth_size*sizeof(MoveMark));
  53         }
  54         return mv_oth[i-1];
  55     }
  56
  57     MoveStat()
  58         : oth_size(0)
  59         , mv_oth(NULL)
  60         , num(0)
  61         , tot(0)
  62     {
  63     }
  64
  65     ~MoveStat()
  66     {
  67         if(mv_oth)
  68             free(mv_oth);
  69     }
  70
  71     void insert(uint32_t m, unsigned int w )
  72     {
  73         for(int i=0;i<num; i++)
  74         if((*this)[i].move == m)
  75         {
  76             (*this)[i].stat += w;
  77             tot += w;
  78             return;
  79         }
  80
  81         (*this)[num].move = m;
  82         (*this)[num].stat = w;
  83         tot += w;
  84         num++;
  85     }
  86
  87     static int sort_mv_marks(const void *a, const void *b)
  88     {
  89         return ((MoveMark*)b)->stat - ((MoveMark*)a)->stat;
  90     }
  91
  92     void sort_moves()
  93     {
  94         for(int i=0;i<num-1;i++)
  95         if(mv_oth[i].stat > mv_first.stat)
  96             SWITCH(mv_oth[i], mv_first);
  97         qsort(mv_oth, num-1, sizeof(MoveMark), sort_mv_marks);
  98     }
  99 };
 100
 101 typedef std::map< HashKey, MoveStat> BkEntryMap;
 102
 103
 104 /* an entry in the book */
 105 struct PACKED BookEntry
 106 {
 107     HashKey key;
 108     /* the offset you have to add to find the right branch of the binary tree */
 109     uint32_t right_off;
 110     /* the number of moves */
 111     uint8_t num;
 112     ComprMove mv[1];
 113 };
 114
 115 /* special flags for marking the leaf nodes or those with only 1 child */
 116 #define NO_RIGHT ((uint32_t)-1)
 117 #define LEAF ((uint32_t)-2)
 118
 119 /* the size of the entry in a book with x alternatives */
 120 #define ENTRY_SIZE(x) (sizeof(BookEntry) + ((x)-1)*sizeof(ComprMove))
 121
 122 static uint32_t calc_book_range_size(BkEntryMap::iterator begin, BkEntryMap::iterator end)
 123 {
 124     uint32_t sz = 0;
 125     for(;begin!=end;++begin)
 126         sz += ENTRY_SIZE(begin->second.num);
 127     return sz;
 128 }
 129
 130 static int write_book_range(FILE* f, BkEntryMap::iterator begin, BkEntryMap::iterator end)
 131 {
 132     if(begin == end)
 133         return 0;
 134
 135     int num = 0;
 136     BkEntryMap::iterator mid = begin;
 137     while(mid != end)
 138     {
 139         ++num;
 140         ++mid;
 141     }
 142
 143     mid = begin;
 144     for(int i=0;i<num/2;i++)
 145         mid++;
 146
 147     const HashKey& hk = mid->first;
 148     MoveStat& m = mid->second;
 149     uint32_t besz = ENTRY_SIZE(m.num);
 150     uint32_t lsize = calc_book_range_size(begin, mid);
 151     BkEntryMap::iterator tmpit = mid;
 152     BookEntry b;
 153     b.key = hk;
 154     b.num = m.num;
 155     if(++tmpit == end)
 156         b.right_off = lsize ? NO_RIGHT : LEAF;
 157     else
 158         b.right_off = lsize;
 159     b.mv[0].move = m[0].move;
 160     b.mv[0].stat = m[0].stat;
 161     fwrite(&b, 1, sizeof(BookEntry), f);
 162
 163     for(int i=1;i<m.num;i++)
 164     {
 165         ComprMove c = { m[i].move, m[i].stat };
 166         fwrite(&c, 1, sizeof(ComprMove), f);
 167     }
 168
 169
 170     uint32_t truels = write_book_range(f, begin, mid);
 171     if(truels != lsize)
 172         fprintf(stderr, "Error! %d %d\n", truels, lsize);
 173     ++mid;
 174
 175     return besz + lsize + write_book_range(f, mid, end);
 176 }
 177
 178 void Engine::create_book(int argc, char *argv[])
 179 {
 180     int n=0;
 181     BkEntryMap b;
 182     FILE* f = fopen(argv[0],"r");
 183     if(!f)
 184         output("Error, could not open \"%s\" for reading.\n", argv[0]);
 185
 186     while(load_pgn(f))
 187     {
 188         if(++n % 1000 == 0)
 189             output("(%d games processed)\n", n);
 190
 191         for(int i=mv_done_num-1; i>=0; i--)
 192         {
 193             board.undo_move(mv_done[i], save_buf[--save_buf_num]);
 194
 195             if(i>v_book_creation_max_depth)
 196                 continue;
 197
 198             MoveStat& ms = b[board.hash];
 199
 200             unsigned int weight = v_book_creation_weigh_draw;
 201             if(status == _01)
 202                 weight = board.color_to_move == BLACK ? v_book_creation_weigh_win : v_book_creation_weigh_lose;
 203             else if(status == _10)
 204                 weight = board.color_to_move == WHITE ? v_book_creation_weigh_win : v_book_creation_weigh_lose;
 205
 206             ms.insert( board.compress_move(mv_done[i]), weight );
 207         }
 208     }
 209     fclose(f);
 210
 211
 212     /* adjust the entries */
 213     output("(preprocessing the tree)\n");
 214
 215     for(BkEntryMap::iterator it = b.begin(); it != b.end(); )
 216     {
 217         MoveStat& ms = it->second;
 218
 219         /* discard moves played too few times in games */
 220         if(ms.tot < (unsigned int)v_book_creation_min_games)
 221         {
 222             b.erase(it++);
 223             continue;
 224         }
 225         ++it;
 226
 227         /* remove very rare moves) */
 228         for(int i=0;i<ms.num;i++)
 229         {
 230             if(ms[i].stat*1000 < ms.tot*v_book_creation_min_probability)
 231             {
 232                 ms.tot -= ms[i].stat;
 233                 ms[i] = ms[ms.num-1];
 234                 i--;
 235                 ms.num--;
 236             }
 237         }
 238
 239         /* renormalize the alternatives up to 1024 */
 240         int prev_tot = 0;
 241         for(int i=0;i<ms.num;i++)
 242         {
 243             int st = ms[i].stat;
 244             ms[i].stat = ((prev_tot+st)*1024)/ms.tot
 245                         - (prev_tot*1024)/ms.tot;
 246             prev_tot += st;
 247         }
 248
 249         /* sort them so the program will give a nicer output :) */
 250         ms.sort_moves();
 251     }
 252
 253     FILE *bf = fopen("ratta.book","w");
 254     output("(writing the book)\n");
 255     uint32_t sz = write_book_range(bf, b.begin(), b.end());
 256     printf("Book size is %u\n",sz);
 257     fclose(bf);
 258
 259     st_computer_color = 0;
 260 }
 261
 262 bool Engine::open_book(const char *f)
 263 {
 264     close_book();
 265
 266 //     book_mmap = map_file( f, &book_size);
 267 //     if(!book_mmap)
 268 //     {
 269 //         output("Error, could not open and mmap the book file \"%s\".\n", f);
 270 //         return false;
 271 //     }
 272 //     else
 273 //     {
 274 //         output("Book file \"%s\" opened and mapped, good!\n", f);
 275 //         return true;
 276 //     }
 277
 278     FILE *file = fopen(f, "r");
 279     if(!file)
 280     {
 281         output("Error, could not open and mmap the book file \"%s\" (%s).\n", f, strerror(errno));
 282         return false;
 283     }
 284     else
 285     {
 286         fseek(file, 0, SEEK_END);
 287         book_size = ftell(file);
 288         fseek(file, 0, SEEK_SET);
 289         book_mmap = malloc(book_size);
 290         fread(book_mmap, book_size, 1, file);
 291         fclose(file);
 292
 293         output("Book file \"%s\" opened and mapped, good!\n", f);
 294         return true;
 295     }
 296 }
 297
 298 void Engine::close_book()
 299 {
 300 //     if(book_mmap)
 301 //         unmap_file(book_mmap, book_size);
 302     if(book_mmap)
 303         free(book_mmap);
 304     book_mmap = NULL;
 305 }
 306
 307 Move Engine::probe_book(Board *brd)
 308 {
 309     uint32_t delta = 0;
 310
 311     if(!book_mmap || mv_done_num>50)
 312         return Move::None();
 313
 314     /* walk the in-memory mapped binary search tree */
 315     while(1)
 316     {
 317         BookEntry *b = (BookEntry*)((long)book_mmap+delta);
 318
 319         /* book entry found */
 320         if(b->key == brd->hash)
 321         {
 322             /* print the (e4 64%, d4 36%)-like thinking line */
 323             if(post)
 324             {
 325                 if(OpeningInfo* i = probe_openings(brd))
 326                     output("\t0\t0\t0\t0\t%s: %s (", i->eco, i->name);
 327                 else
 328                     output("\t0\t0\t0\t0\t(");
 329
 330                 for(unsigned int i=0;i<b->num;i++)
 331                 {
 332                     Move m = brd->uncompress_move(b->mv[i].move);
 333                     output("%s%s %.01f%%",
 334                             i!=0 ? "," : "",
 335                             brd->move_to_alg(MoveStr().data(), m),
 336                             b->num == 1 ? 100 : b->mv[i].stat*100.0/1024);
 337                 }
 338                 output(")\n");
 339             }
 340
 341             if(b->num == 1)
 342                 return brd->uncompress_move(b->mv[0].move);
 343
 344             int r = rand()%1024;
 345             for(unsigned int i=0;i<b->num;i++)
 346             {
 347                 r -= b->mv[i].stat;
 348                 if(r<=0)
 349                     return brd->uncompress_move(b->mv[i].move);
 350             }
 351
 352             /* this should never happen */
 353             return Move::None();
 354         }
 355
 356         if(b->right_off == LEAF)
 357             return Move::None();
 358
 359         if(brd->hash < b->key)
 360         {
 361             /* no left entry */
 362             if(b->right_off == 0)
 363                 return Move::None();
 364
 365             /* go on */
 366             delta += ENTRY_SIZE(b->num);
 367         }
 368         else
 369         {
 370             /* no right entry */
 371             if(b->right_off == NO_RIGHT)
 372                 return Move::None();
 373
 374             /* go on */
 375             delta += ENTRY_SIZE(b->num) + b->right_off;
 376         }
 377
 378         if(delta < 0 || delta >= book_size-16 )
 379         {
 380             output("Error! Damaged binary book!\n");
 381             return Move::None();
 382         }
 383     }
 384 }
 385
 386 bool Engine::open_lines(const char *linef)
 387 {
 388     close_lines();
 389
 390     FILE* f = fopen(linef,"r");
 391     if(!f)
 392     {
 393         output("Error, could not open \"%s\" for reading.\n", linef);
 394         return false;
 395     }
 396
 397     while(load_pgn(f))
 398     {
 399         for(int i=mv_done_num-1; i>=0; i--)
 400         {
 401             board.undo_move(mv_done[i], save_buf[--save_buf_num]);
 402
 403             if(mv_done[i].val > 0)
 404             {
 405                 std::map<Move, int>& ml = lines[board.hash];
 406                 ml[mv_done[i]] += mv_done[i].val;
 407             }
 408         }
 409     }
 410     fclose(f);
 411     output("Lines loaded from file \"%s\", good!\n", linef);
 412     return true;
 413 }
 414
 415 void Engine::close_lines()
 416 {
 417     lines.clear();
 418 }
 419
 420 Move Engine::probe_lines(Board *brd)
 421 {
 422     Lines::iterator it = lines.find( brd->hash );
 423     if( it == lines.end() )
 424         return Move::None();
 425
 426     int sum = 0;
 427     for(std::map<Move, int>::iterator mit = it->second.begin(); mit != it->second.end(); ++mit)
 428         sum += mit->second;
 429
 430     if(!sum)
 431         return Move::None();
 432
 433     int r = rand() % sum;
 434     for(std::map<Move, int>::iterator mit = it->second.begin(); mit != it->second.end(); ++mit)
 435     if( (r -= mit->second) < 0)
 436         return mit->first;
 437
 438     return Move::None();
 439 }
 440
 441 bool Engine::open_openings(const char *ecos)
 442 {
 443     close_openings();
 444
 445     FILE* f = fopen(ecos,"r");
 446     if(!f)
 447     {
 448         output("Error, could not open \"%s\" for reading.\n", ecos);
 449         return false;
 450     }
 451     int argc;
 452     char **argv;
 453
 454     while( (argv = fget_tokenized(f, ". \t\v\n\r", &argc)) )
 455     {
 456         if(!argc)
 457         {
 458             free(argv);
 459             continue;
 460         }
 461
 462         board.set_as_default();
 463         int i = 1;
 464         while(i<argc)
 465         {
 466             /* is this a move number? */
 467             char *e;
 468             strtol(argv[i], &e, 10);
 469             if(*e == '\0')
 470             {
 471                 i++;
 472                 continue;
 473             }
 474
 475             Move mv = board.move_from_string(argv[i]);
 476             if(mv.valid())
 477             {
 478                 SaveBuf tmp;
 479                 board.do_move(mv, tmp);
 480                 i++;
 481             }
 482             else
 483             {
 484                 if(mv == Move::None() && i==argc-1)
 485                     openings[board.hash].set(argv[0], argv[i]);
 486                 else
 487                     printf("Error parsing opening! (%s, %s)\n", argv[0], argv[i]);
 488                 break;
 489             }
 490         }
 491
 492         free(argv);
 493     }
 494
 495     fclose(f);
 496     output("ECO codes loaded from file \"%s\", good!\n", ecos);
 497     return true;
 498 }
 499
 500 void Engine::close_openings()
 501 {
 502 }
 503
 504 Engine::OpeningInfo* Engine::probe_openings(Board *b)
 505 {
 506     std::map<HashKey, OpeningInfo>::iterator it = openings.find(b->hash);
 507     if(it == openings.end())
 508         return NULL;
 509     else
 510         return &it->second;
 511 }
 512