per test
[rattatechess.git] / book.cpp
blob3e8a3f22fea6eac412d98d93437d0cb4462cff77
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 ***************************************************************************/
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 ***************************************************************************/
18 #include "engine.h"
19 #include "utils.h"
21 /* each move in the book will be stored in 24 bits */
22 struct PACKED ComprMove
24 unsigned int move : 14;
25 unsigned int stat : 10;
28 /* MoveMark and MoveStat are for the book creation */
29 struct PACKED MoveMark
31 uint16_t move;
32 uint32_t stat;
35 class MoveStat
37 private:
38 MoveMark mv_first;
39 uint16_t oth_size;
40 MoveMark *mv_oth;
42 public:
43 int num;
44 unsigned int tot;
46 MoveMark& operator[](int i) {
47 if(i==0)
48 return mv_first;
49 if(i > oth_size)
51 oth_size = i;
52 mv_oth = (MoveMark*)realloc(mv_oth, oth_size*sizeof(MoveMark));
54 return mv_oth[i-1];
57 MoveStat()
58 : oth_size(0)
59 , mv_oth(NULL)
60 , num(0)
61 , tot(0)
65 ~MoveStat()
67 if(mv_oth)
68 free(mv_oth);
71 void insert(uint32_t m, unsigned int w )
73 for(int i=0;i<num; i++)
74 if((*this)[i].move == m)
76 (*this)[i].stat += w;
77 tot += w;
78 return;
81 (*this)[num].move = m;
82 (*this)[num].stat = w;
83 tot += w;
84 num++;
87 static int sort_mv_marks(const void *a, const void *b)
89 return ((MoveMark*)b)->stat - ((MoveMark*)a)->stat;
92 void sort_moves()
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);
101 typedef std::map< HashKey, MoveStat> BkEntryMap;
104 /* an entry in the book */
105 struct PACKED BookEntry
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];
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)
119 /* the size of the entry in a book with x alternatives */
120 #define ENTRY_SIZE(x) (sizeof(BookEntry) + ((x)-1)*sizeof(ComprMove))
122 static uint32_t calc_book_range_size(BkEntryMap::iterator begin, BkEntryMap::iterator end)
124 uint32_t sz = 0;
125 for(;begin!=end;++begin)
126 sz += ENTRY_SIZE(begin->second.num);
127 return sz;
130 static int write_book_range(FILE* f, BkEntryMap::iterator begin, BkEntryMap::iterator end)
132 if(begin == end)
133 return 0;
135 int num = 0;
136 BkEntryMap::iterator mid = begin;
137 while(mid != end)
139 ++num;
140 ++mid;
143 mid = begin;
144 for(int i=0;i<num/2;i++)
145 mid++;
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);
163 for(int i=1;i<m.num;i++)
165 ComprMove c = { m[i].move, m[i].stat };
166 fwrite(&c, 1, sizeof(ComprMove), f);
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;
175 return besz + lsize + write_book_range(f, mid, end);
178 void Engine::create_book(int argc, char *argv[])
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]);
186 while(load_pgn(f))
188 if(++n % 1000 == 0)
189 output("(%d games processed)\n", n);
191 for(int i=mv_done_num-1; i>=0; i--)
193 board.undo_move(mv_done[i], save_buf[--save_buf_num]);
195 if(i>v_book_creation_max_depth)
196 continue;
198 MoveStat& ms = b[board.hash];
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;
206 ms.insert( board.compress_move(mv_done[i]), weight );
209 fclose(f);
212 /* adjust the entries */
213 output("(preprocessing the tree)\n");
215 for(BkEntryMap::iterator it = b.begin(); it != b.end(); )
217 MoveStat& ms = it->second;
219 /* discard moves played too few times in games */
220 if(ms.tot < (unsigned int)v_book_creation_min_games)
222 b.erase(it++);
223 continue;
225 ++it;
227 /* remove very rare moves) */
228 for(int i=0;i<ms.num;i++)
230 if(ms[i].stat*1000 < ms.tot*v_book_creation_min_probability)
232 ms.tot -= ms[i].stat;
233 ms[i] = ms[ms.num-1];
234 i--;
235 ms.num--;
239 /* renormalize the alternatives up to 1024 */
240 int prev_tot = 0;
241 for(int i=0;i<ms.num;i++)
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;
249 /* sort them so the program will give a nicer output :) */
250 ms.sort_moves();
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);
259 st_computer_color = 0;
262 bool Engine::open_book(const char *f)
264 close_book();
266 #if 1
267 book_mmap = map_file(f, &book_size);
268 if(!book_mmap)
270 output("Error, could not open and mmap the book file \"%s\".\n", f);
271 return false;
273 else
275 output("Book file \"%s\" opened and mapped, good!\n", f);
276 return true;
278 #else
279 FILE *file = fopen(f, "r");
280 if(!file)
282 output("Error, could not open and mmap the book file \"%s\" (%s).\n", f, strerror(errno));
283 return false;
285 else
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);
294 output("Book file \"%s\" opened and mapped, good!\n", f);
295 return true;
297 #endif
300 void Engine::close_book()
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;
312 Move Engine::probe_book(Board *brd)
314 uint32_t delta = 0;
316 if(!book_mmap || mv_done_num>50)
317 return Move::None();
319 /* walk the in-memory mapped binary search tree */
320 while(1)
322 BookEntry *b = (BookEntry*)((long)book_mmap+delta);
324 /* book entry found */
325 if(b->key == brd->hash)
327 /* print the (e4 64%, d4 36%)-like thinking line */
328 if(post)
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(");
335 for(unsigned int i=0;i<b->num;i++)
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);
343 output(")\n");
346 if(b->num == 1)
347 return brd->uncompress_move(b->mv[0].move);
349 int r = rand()%1024;
350 for(unsigned int i=0;i<b->num;i++)
352 r -= b->mv[i].stat;
353 if(r<=0)
354 return brd->uncompress_move(b->mv[i].move);
357 /* this should never happen */
358 return Move::None();
361 if(b->right_off == LEAF)
362 return Move::None();
364 if(brd->hash < b->key)
366 /* no left entry */
367 if(b->right_off == 0)
368 return Move::None();
370 /* go on */
371 delta += ENTRY_SIZE(b->num);
373 else
375 /* no right entry */
376 if(b->right_off == NO_RIGHT)
377 return Move::None();
379 /* go on */
380 delta += ENTRY_SIZE(b->num) + b->right_off;
383 if(delta < 0 || delta >= book_size-16 )
385 output("Error! Damaged binary book!\n");
386 return Move::None();
391 bool Engine::open_lines(const char *linef)
393 close_lines();
395 FILE* f = fopen(linef,"r");
396 if(!f)
398 output("Error, could not open \"%s\" for reading.\n", linef);
399 return false;
402 while(load_pgn(f))
404 for(int i=mv_done_num-1; i>=0; i--)
406 board.undo_move(mv_done[i], save_buf[--save_buf_num]);
408 if(mv_done[i].val > 0)
410 std::map<Move, int>& ml = lines[board.hash];
411 ml[mv_done[i]] += mv_done[i].val;
415 fclose(f);
416 output("Lines loaded from file \"%s\", good!\n", linef);
417 return true;
420 void Engine::close_lines()
422 lines.clear();
425 Move Engine::probe_lines(Board *brd)
427 Lines::iterator it = lines.find( brd->hash );
428 if( it == lines.end() )
429 return Move::None();
431 int sum = 0;
432 for(std::map<Move, int>::iterator mit = it->second.begin(); mit != it->second.end(); ++mit)
433 sum += mit->second;
435 if(!sum)
436 return Move::None();
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;
443 return Move::None();
446 bool Engine::open_openings(const char *ecos)
448 close_openings();
450 FILE* f = fopen(ecos,"r");
451 if(!f)
453 output("Error, could not open \"%s\" for reading.\n", ecos);
454 return false;
456 int argc;
457 char **argv;
459 while( (argv = fget_tokenized(f, ". \t\v\n\r", &argc)) )
461 if(!argc)
463 free(argv);
464 continue;
467 board.set_as_default();
468 int i = 1;
469 while(i<argc)
471 /* is this a move number? */
472 char *e;
473 strtol(argv[i], &e, 10);
474 if(*e == '\0')
476 i++;
477 continue;
480 Move mv = board.move_from_string(argv[i]);
481 if(mv.valid())
483 SaveBuf tmp;
484 board.do_move(mv, tmp);
485 i++;
487 else
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;
497 free(argv);
500 fclose(f);
501 output("ECO codes loaded from file \"%s\", good!\n", ecos);
502 return true;
505 void Engine::close_openings()
509 Engine::OpeningInfo* Engine::probe_openings(Board *b)
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;