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 #if 1
 267     book_mmap = map_file(f, &book_size);
 268     if(!book_mmap)
 269     {
 270         output("Error, could not open and mmap the book file \"%s\".\n", f);
 271         return false;
 272     }
 273     else
 274     {
 275         output("Book file \"%s\" opened and mapped, good!\n", f);
 276         return true;
 277     }
 278 #else
 279     FILE *file = fopen(f, "r");
 280     if(!file)
 281     {
 282         output("Error, could not open and mmap the book file \"%s\" (%s).\n", f, strerror(errno));
 283         return false;
 284     }
 285     else
 286     {
 287         fseek(file, 0, SEEK_END);
 288         book_size = ftell(file);
 289         fseek(file, 0, SEEK_SET);
 290         book_mmap = malloc(book_size);
 291         fread(book_mmap, book_size, 1, file);
 292         fclose(file);
 293
 294         output("Book file \"%s\" opened and mapped, good!\n", f);
 295         return true;
 296     }
 297 #endif
 298 }
 299
 300 void Engine::close_book()
 301 {
 302 #if 1
 303     if(book_mmap)
 304         unmap_file(book_mmap, book_size);
 305 #else
 306     if(book_mmap)
 307         free(book_mmap);
 308 #endif
 309     book_mmap = NULL;
 310 }
 311
 312 Move Engine::probe_book(Board *brd)
 313 {
 314     uint32_t delta = 0;
 315
 316     if(!book_mmap || mv_done_num>50)
 317         return Move::None();
 318
 319     /* walk the in-memory mapped binary search tree */
 320     while(1)
 321     {
 322         BookEntry *b = (BookEntry*)((long)book_mmap+delta);
 323
 324         /* book entry found */
 325         if(b->key == brd->hash)
 326         {
 327             /* print the (e4 64%, d4 36%)-like thinking line */
 328             if(post)
 329             {
 330                 if(OpeningInfo* i = probe_openings(brd))
 331                     output("\t0\t0\t0\t0\t%s: %s (", i->eco, i->name);
 332                 else
 333                     output("\t0\t0\t0\t0\t(");
 334
 335                 for(unsigned int i=0;i<b->num;i++)
 336                 {
 337                     Move m = brd->uncompress_move(b->mv[i].move);
 338                     output("%s%s %.01f%%",
 339                             i!=0 ? "," : "",
 340                             brd->move_to_alg(MoveStr().data(), m),
 341                             b->num == 1 ? 100 : b->mv[i].stat*100.0/1024);
 342                 }
 343                 output(")\n");
 344             }
 345
 346             if(b->num == 1)
 347                 return brd->uncompress_move(b->mv[0].move);
 348
 349             int r = rand()%1024;
 350             for(unsigned int i=0;i<b->num;i++)
 351             {
 352                 r -= b->mv[i].stat;
 353                 if(r<=0)
 354                     return brd->uncompress_move(b->mv[i].move);
 355             }
 356
 357             /* this should never happen */
 358             return Move::None();
 359         }
 360
 361         if(b->right_off == LEAF)
 362             return Move::None();
 363
 364         if(brd->hash < b->key)
 365         {
 366             /* no left entry */
 367             if(b->right_off == 0)
 368                 return Move::None();
 369
 370             /* go on */
 371             delta += ENTRY_SIZE(b->num);
 372         }
 373         else
 374         {
 375             /* no right entry */
 376             if(b->right_off == NO_RIGHT)
 377                 return Move::None();
 378
 379             /* go on */
 380             delta += ENTRY_SIZE(b->num) + b->right_off;
 381         }
 382
 383         if(delta < 0 || delta >= book_size-16 )
 384         {
 385             output("Error! Damaged binary book!\n");
 386             return Move::None();
 387         }
 388     }
 389 }
 390
 391 bool Engine::open_lines(const char *linef)
 392 {
 393     close_lines();
 394
 395     FILE* f = fopen(linef,"r");
 396     if(!f)
 397     {
 398         output("Error, could not open \"%s\" for reading.\n", linef);
 399         return false;
 400     }
 401
 402     while(load_pgn(f))
 403     {
 404         for(int i=mv_done_num-1; i>=0; i--)
 405         {
 406             board.undo_move(mv_done[i], save_buf[--save_buf_num]);
 407
 408             if(mv_done[i].val > 0)
 409             {
 410                 std::map<Move, int>& ml = lines[board.hash];
 411                 ml[mv_done[i]] += mv_done[i].val;
 412             }
 413         }
 414     }
 415     fclose(f);
 416     output("Lines loaded from file \"%s\", good!\n", linef);
 417     return true;
 418 }
 419
 420 void Engine::close_lines()
 421 {
 422     lines.clear();
 423 }
 424
 425 Move Engine::probe_lines(Board *brd)
 426 {
 427     Lines::iterator it = lines.find( brd->hash );
 428     if( it == lines.end() )
 429         return Move::None();
 430
 431     int sum = 0;
 432     for(std::map<Move, int>::iterator mit = it->second.begin(); mit != it->second.end(); ++mit)
 433         sum += mit->second;
 434
 435     if(!sum)
 436         return Move::None();
 437
 438     int r = rand() % sum;
 439     for(std::map<Move, int>::iterator mit = it->second.begin(); mit != it->second.end(); ++mit)
 440     if( (r -= mit->second) < 0)
 441         return mit->first;
 442
 443     return Move::None();
 444 }
 445
 446 bool Engine::open_openings(const char *ecos)
 447 {
 448     close_openings();
 449
 450     FILE* f = fopen(ecos,"r");
 451     if(!f)
 452     {
 453         output("Error, could not open \"%s\" for reading.\n", ecos);
 454         return false;
 455     }
 456     int argc;
 457     char **argv;
 458
 459     while( (argv = fget_tokenized(f, ". \t\v\n\r", &argc)) )
 460     {
 461         if(!argc)
 462         {
 463             free(argv);
 464             continue;
 465         }
 466
 467         board.set_as_default();
 468         int i = 1;
 469         while(i<argc)
 470         {
 471             /* is this a move number? */
 472             char *e;
 473             strtol(argv[i], &e, 10);
 474             if(*e == '\0')
 475             {
 476                 i++;
 477                 continue;
 478             }
 479
 480             Move mv = board.move_from_string(argv[i]);
 481             if(mv.valid())
 482             {
 483                 SaveBuf tmp;
 484                 board.do_move(mv, tmp);
 485                 i++;
 486             }
 487             else
 488             {
 489                 if(mv == Move::None() && i==argc-1)
 490                     openings[board.hash].set(argv[0], argv[i]);
 491                 else
 492                     printf("Error parsing opening! (%s, %s)\n", argv[0], argv[i]);
 493                 break;
 494             }
 495         }
 496
 497         free(argv);
 498     }
 499
 500     fclose(f);
 501     output("ECO codes loaded from file \"%s\", good!\n", ecos);
 502     return true;
 503 }
 504
 505 void Engine::close_openings()
 506 {
 507 }
 508
 509 Engine::OpeningInfo* Engine::probe_openings(Board *b)
 510 {
 511     std::map<HashKey, OpeningInfo>::iterator it = openings.find(b->hash);
 512     if(it == openings.end())
 513         return NULL;
 514     else
 515         return &it->second;
 516 }
 517