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]);
 194
 195             if(i>v_book_creation_max_depth)
 196                 continue;
 197
 198             MoveStat& ms = b[board.hash];
 199
 200             unsigned int weight = 2;
 201             if(status == _01)
 202                 weight = board.color_to_move == BLACK ? 3 : 1;
 203             else if(status == _10)
 204                 weight = board.color_to_move == WHITE ? 3 : 1;
 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 bool Engine::probe_book(const HashKey& h, Move* m)
 308 {
 309     uint32_t delta = 0;
 310
 311     if(!book_mmap || mv_done_num>50)
 312         return false;
 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 == h)
 321         {
 322             /* print the (e4 64%, d4 36%)-like thinking line */
 323             if(post)
 324             {
 325                 output("\t0\t0\t0\t0\t(");
 326                 for(unsigned int i=0;i<b->num;i++)
 327                 {
 328                     char str[64];
 329                     Move m = board.uncompress_move(b->mv[i].move);
 330                     if(i!=0)
 331                         output(",");
 332                     output("%s %.01f%%", move_to_alg(str, &m),
 333                             b->num == 1 ? 100 :
 334                         (b->mv[i].stat*100.0)/1024);
 335                 }
 336                 output(")\n");
 337             }
 338
 339             if(b->num == 1)
 340             {
 341                 *m = board.uncompress_move(b->mv[0].move);
 342                 return true;
 343             }
 344
 345             int r = rand()%1024;
 346             for(unsigned int i=0;i<b->num;i++)
 347             {
 348                 r -= b->mv[i].stat;
 349                 if(r<=0)
 350                 {
 351                     *m = board.uncompress_move(b->mv[i].move);
 352                     return true;
 353                 }
 354             }
 355
 356             /* this should never happen */
 357             return false;
 358         }
 359
 360         if(b->right_off == LEAF)
 361             return false;
 362
 363         if(h < b->key)
 364         {
 365             /* no left entry */
 366             if(b->right_off == 0)
 367                 return false;
 368
 369             /* go on */
 370             delta += ENTRY_SIZE(b->num);
 371         }
 372         else
 373         {
 374             /* no right entry */
 375             if(b->right_off == NO_RIGHT)
 376                 return false;
 377
 378             /* go on */
 379             delta += ENTRY_SIZE(b->num) + b->right_off;
 380         }
 381
 382         if(delta < 0 || delta >= book_size-16 )
 383         {
 384             output("Error! Damaged binary book!\n");
 385             return false;
 386         }
 387     }
 388     return false;
 389 }
 390
 391 bool Engine::open_lines(const char *linef)
 392 {
 393     FILE* f = fopen(linef,"r");
 394     if(!f)
 395     {
 396         output("Error, could not open \"%s\" for reading.\n", linef);
 397         return false;
 398     }
 399
 400     while(load_pgn(f))
 401     {
 402         for(int i=mv_done_num-1; i>=0; i--)
 403         {
 404             board.undo_move(mv_done[i]);
 405
 406             if(mv_done[i].val > 0)
 407             {
 408                 std::list< Move >& ml = lines[board.hash];
 409                 ml.push_front(mv_done[i]);
 410
 411                 /*char buf[64];
 412                 output("Good move %s loaded! %lx\n",
 413                     move_to_alg(buf, &mv_done[i]), board.hash.check);
 414                 board.print_board();*/
 415             }
 416         }
 417     }
 418     fclose(f);
 419     output("Lines loaded from file \"%s\", good!\n", linef);
 420     return true;
 421 }
 422
 423 void Engine::close_lines()
 424 {
 425     lines.clear();
 426 }
 427
 428 bool Engine::probe_lines(const HashKey& h, Move* m)
 429 {
 430     Lines::iterator it = lines.find( h );
 431     if( it == lines.end() )
 432     {
 433         //output("Not found! %lx\n", board.hash.check);
 434         return false;
 435     }
 436
 437     int r = rand() % it->second.size();
 438     std::list< Move >::iterator mit = it->second.begin();
 439
 440     for(int i=0;i<r;i++) mit++;
 441     *m = *mit;
 442
 443     return true;
 444 }