« back to all changes in this revision
Viewing changes to book_make.cpp
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Oliver Korff
- Date: 2005-10-09 21:56:20 UTC
- Revision ID: james.westby@ubuntu.com-20051009215620-dcuqynujzvmiglpj
Tags: upstream-1.3
Import upstream version 1.3
- files added:
added
removed
book_make.cpp
1
2
// book_make.cpp
3
4
// includes
5
6
#include <cerrno>
7
#include <cmath>
8
#include <cstdio>
9
#include <cstdlib>
10
#include <cstring>
11
12
#include "board.h"
13
#include "book_make.h"
14
#include "move.h"
15
#include "move_do.h"
16
#include "move_legal.h"
17
#include "pgn.h"
18
#include "san.h"
19
#include "util.h"
20
21
// constants
22
23
static const int COUNT_MAX = 16384;
24
25
static const int NIL = -1;
26
27
// types
28
29
struct entry_t {
30
uint64 key;
31
uint16 move;
32
uint16 n;
33
uint16 sum;
34
uint16 score;
35
};
36
37
struct book_t {
38
int size;
39
int alloc;
40
uint32 mask;
41
entry_t * entry;
42
sint32 * hash;
43
};
44
45
// variables
46
47
static int MaxPly;
48
static int MinGame;
49
static int MinScore;
50
51
static book_t Book[1];
52
53
// prototypes
54
55
static void book_clear ();
56
static void book_insert (const char file_name[]);
57
static void book_score ();
58
static void book_filter ();
59
static void book_sort ();
60
static void book_save (const char file_name[]);
61
62
static int find_entry (const board_t * board, int move);
63
static void resize ();
64
static void halve_stats (uint64 key);
65
66
static bool keep_entry (int pos);
67
68
static int move_score (const entry_t * entry);
69
70
static int key_compare (const void * p1, const void * p2);
71
72
static void write_integer (FILE * file, int size, uint64 n);
73
74
// functions
75
76
// book_make()
77
78
void book_make(int argc, char * argv[]) {
79
80
int i;
81
const char * pgn_file;
82
const char * bin_file;
83
84
pgn_file = NULL;
85
my_string_set(&pgn_file,"book.pgn");
86
87
bin_file = NULL;
88
my_string_set(&bin_file,"book.bin");
89
90
MaxPly = 1024;
91
MinGame = 3;
92
MinScore = 1;
93
94
for (i = 1; i < argc; i++) {
95
96
if (false) {
97
98
} else if (my_string_equal(argv[i],"make-book")) {
99
100
// skip
101
102
} else if (my_string_equal(argv[i],"-pgn")) {
103
104
i++;
105
if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
106
107
my_string_set(&pgn_file,argv[i]);
108
109
} else if (my_string_equal(argv[i],"-bin")) {
110
111
i++;
112
if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
113
114
my_string_set(&bin_file,argv[i]);
115
116
} else if (my_string_equal(argv[i],"-max-ply")) {
117
118
i++;
119
if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
120
121
MaxPly = atoi(argv[i]);
122
123
} else if (my_string_equal(argv[i],"-min-game")) {
124
125
i++;
126
if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
127
128
MinGame = atoi(argv[i]);
129
130
} else if (my_string_equal(argv[i],"-min-score")) {
131
132
i++;
133
if (argv[i] == NULL) my_fatal("book_make(): missing argument\n");
134
135
MinScore = atoi(argv[i]);
136
137
} else {
138
139
my_fatal("book_make(): unknown option \"%s\"\n",argv[i]);
140
}
141
}
142
143
book_clear();
144
145
printf("inserting games ...\n");
146
book_insert(pgn_file);
147
148
printf("scoring entries ...\n");
149
book_score();
150
151
printf("filtering entries ...\n");
152
book_filter();
153
154
printf("sorting entries ...\n");
155
book_sort();
156
157
printf("saving entries ...\n");
158
book_save(bin_file);
159
160
printf("all done!\n");
161
}
162
163
// book_clear()
164
165
static void book_clear() {
166
167
int index;
168
169
Book->alloc = 1;
170
Book->mask = (Book->alloc * 2) - 1;
171
172
Book->entry = (entry_t *) my_malloc(Book->alloc*sizeof(entry_t));
173
Book->size = 0;
174
175
Book->hash = (sint32 *) my_malloc((Book->alloc*2)*sizeof(sint32));
176
for (index = 0; index < Book->alloc*2; index++) {
177
Book->hash[index] = NIL;
178
}
179
}
180
181
// book_insert()
182
183
static void book_insert(const char file_name[]) {
184
185
int game_nb;
186
pgn_t pgn[1];
187
board_t board[1];
188
int ply;
189
int result;
190
char string[256];
191
int move;
192
int pos;
193
194
ASSERT(file_name!=NULL);
195
196
// init
197
198
game_nb = 0;
199
200
// scan loop
201
202
pgn_open(pgn,file_name);
203
204
while (pgn_next_game(pgn)) {
205
206
board_start(board);
207
ply = 0;
208
result = 0;
209
210
if (false) {
211
} else if (my_string_equal(pgn->result,"1-0")) {
212
result = +1;
213
} else if (my_string_equal(pgn->result,"0-1")) {
214
result = -1;
215
}
216
217
while (pgn_next_move(pgn,string,256)) {
218
219
if (ply < MaxPly) {
220
221
move = move_from_san(string,board);
222
223
if (move == MoveNone || !move_is_legal(move,board)) {
224
my_fatal("book_insert(): illegal move \"%s\" at line %d, column %d\n",string,pgn->move_line,pgn->move_column);
225
}
226
227
pos = find_entry(board,move);
228
229
Book->entry[pos].n++;
230
Book->entry[pos].sum += result+1;
231
232
if (Book->entry[pos].n >= COUNT_MAX) {
233
halve_stats(board->key);
234
}
235
236
move_do(board,move);
237
ply++;
238
result = -result;
239
}
240
}
241
242
game_nb++;
243
if (game_nb % 10000 == 0) printf("%d games ...\n",game_nb);
244
}
245
246
pgn_close(pgn);
247
248
printf("%d game%s.\n",game_nb,(game_nb>1)?"s":"");
249
printf("%d entries.\n",Book->size);
250
251
return;
252
}
253
254
// book_score()
255
256
static void book_score() {
257
258
int pos;
259
int score;
260
261
// entry loop
262
263
for (pos = 0; pos < Book->size; pos++) {
264
265
ASSERT(Book->entry[pos].n<65536);
266
267
score = move_score(&Book->entry[pos]);
268
269
ASSERT(score>=0&&score<65536);
270
Book->entry[pos].score = score;
271
}
272
}
273
274
// book_filter()
275
276
static void book_filter() {
277
278
int src, dst;
279
280
// entry loop
281
282
dst = 0;
283
284
for (src = 0; src < Book->size; src++) {
285
if (keep_entry(src)) Book->entry[dst++] = Book->entry[src];
286
}
287
288
ASSERT(dst>=0&&dst<=Book->size);
289
Book->size = dst;
290
291
printf("%d entries.\n",Book->size);
292
}
293
294
// book_sort()
295
296
static void book_sort() {
297
298
// sort keys for binary search
299
300
qsort(Book->entry,Book->size,sizeof(entry_t),&key_compare);
301
}
302
303
// book_save()
304
305
static void book_save(const char file_name[]) {
306
307
FILE * file;
308
int pos;
309
310
ASSERT(file_name!=NULL);
311
312
file = fopen(file_name,"wb");
313
if (file == NULL) my_fatal("book_save(): can't open file \"%s\" for writing: %s\n",file_name,strerror(errno));
314
315
// entry loop
316
317
for (pos = 0; pos < Book->size; pos++) {
318
319
ASSERT(keep_entry(pos));
320
ASSERT(Book->entry[pos].score<65536);
321
322
write_integer(file,8,Book->entry[pos].key);
323
write_integer(file,2,Book->entry[pos].move);
324
write_integer(file,2,Book->entry[pos].score);
325
write_integer(file,2,0);
326
write_integer(file,2,0);
327
}
328
329
fclose(file);
330
}
331
332
// find_entry()
333
334
static int find_entry(const board_t * board, int move) {
335
336
uint64 key;
337
int index;
338
int pos;
339
340
ASSERT(board!=NULL);
341
ASSERT(move_is_ok(move));
342
343
ASSERT(move_is_legal(move,board));
344
345
// init
346
347
key = board->key;
348
349
// search
350
351
for (index = key & Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
352
353
ASSERT(pos>=0&&pos<Book->size);
354
355
if (Book->entry[pos].key == key && Book->entry[pos].move == move) {
356
return pos; // found
357
}
358
}
359
360
// not found
361
362
ASSERT(Book->size<=Book->alloc);
363
364
if (Book->size == Book->alloc) {
365
366
// allocate more memory
367
368
resize();
369
370
for (index = key & Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
371
;
372
}
373
374
// create a new entry
375
376
ASSERT(Book->size<Book->alloc);
377
pos = Book->size++;
378
379
Book->entry[pos].key = key;
380
Book->entry[pos].move = move;
381
Book->entry[pos].n = 0;
382
Book->entry[pos].sum = 0;
383
Book->entry[pos].score = 0;
384
385
// insert into the hash table
386
387
ASSERT(index>=0&&index<Book->alloc*2);
388
ASSERT(Book->hash[index]==NIL);
389
Book->hash[index] = pos;
390
391
ASSERT(pos>=0&&pos<Book->size);
392
393
return pos;
394
}
395
396
// resize()
397
398
static void resize() {
399
400
int size;
401
int pos;
402
int index;
403
404
ASSERT(Book->size==Book->alloc);
405
406
Book->alloc *= 2;
407
Book->mask = (Book->alloc * 2) - 1;
408
409
size = 0;
410
size += Book->alloc * sizeof(entry_t);
411
size += (Book->alloc*2) * sizeof(sint32);
412
413
if (size >= 1048576) printf("allocating %gMB ...\n",double(size)/1048576.0);
414
415
// resize arrays
416
417
Book->entry = (entry_t *) my_realloc(Book->entry,Book->alloc*sizeof(entry_t));
418
Book->hash = (sint32 *) my_realloc(Book->hash,(Book->alloc*2)*sizeof(sint32));
419
420
// rebuild hash table
421
422
for (index = 0; index < Book->alloc*2; index++) {
423
Book->hash[index] = NIL;
424
}
425
426
for (pos = 0; pos < Book->size; pos++) {
427
428
for (index = Book->entry[pos].key & Book->mask; Book->hash[index] != NIL; index = (index+1) & Book->mask)
429
;
430
431
ASSERT(index>=0&&index<Book->alloc*2);
432
Book->hash[index] = pos;
433
}
434
}
435
436
// halve_stats()
437
438
static void halve_stats(uint64 key) {
439
440
int index;
441
int pos;
442
443
// search
444
445
for (index = key & Book->mask; (pos=Book->hash[index]) != NIL; index = (index+1) & Book->mask) {
446
447
ASSERT(pos>=0&&pos<Book->size);
448
449
if (Book->entry[pos].key == key) {
450
Book->entry[pos].n = (Book->entry[pos].n + 1) / 2;
451
Book->entry[pos].sum = (Book->entry[pos].sum + 1) / 2;
452
}
453
}
454
}
455
456
// keep_entry()
457
458
static bool keep_entry(int pos) {
459
460
ASSERT(pos>=0&&pos<Book->size);
461
462
// return move_score(&Book->entry[pos]) > 0;
463
464
return Book->entry[pos].score > 0;
465
}
466
467
// move_score()
468
469
static int move_score(const entry_t * entry) {
470
471
int score;
472
473
ASSERT(entry!=NULL);
474
475
score = 0;
476
477
if (entry->n >= MinGame) {
478
// score = entry->n; // popularity
479
score = entry->sum; // "expectancy"
480
}
481
482
ASSERT(score>=0);
483
484
return score;
485
}
486
487
// key_compare()
488
489
static int key_compare(const void * p1, const void * p2) {
490
491
const entry_t * entry_1, * entry_2;
492
493
ASSERT(p1!=NULL);
494
ASSERT(p2!=NULL);
495
496
entry_1 = (const entry_t *) p1;
497
entry_2 = (const entry_t *) p2;
498
499
if (entry_1->key > entry_2->key) {
500
return +1;
501
} else if (entry_1->key < entry_2->key) {
502
return -1;
503
} else {
504
return entry_2->score - entry_1->score; // highest score first
505
}
506
}
507
508
// write_integer()
509
510
static void write_integer(FILE * file, int size, uint64 n) {
511
512
int i;
513
int b;
514
515
ASSERT(file!=NULL);
516
ASSERT(size>0&&size<=8);
517
ASSERT(size==8||n>>(size*8)==0);
518
519
for (i = size-1; i >= 0; i--) {
520
b = (n >> (i*8)) & 0xFF;
521
ASSERT(b>=0&&b<256);
522
fputc(b,file);
523
}
524
}
525
526
// end of book_make.cpp
527
Loggerhead is a web-based interface for Breezy
Version: 2.0.1