From: H.G. Muller Date: Thu, 29 Nov 2012 22:38:18 +0000 (+0100) Subject: Implement book-creation functions X-Git-Url: http://winboard.nl/cgi-bin?p=xboard.git;a=commitdiff_plain;h=74506c0e852b35465c651f331e010ca7e60e7dd3 Implement book-creation functions A new menu item triggers conversion of the currently loaded PGN file to a Polyglot book, saved with the GUI-book filename. A (volatile) option -mcBookMode alters the probing algorithm to build a book from scratch by playing games (and using a form of learning). --- diff --git a/args.h b/args.h index 91270dd..ea3e8c0 100644 --- a/args.h +++ b/args.h @@ -580,6 +580,7 @@ ArgDescriptor argDescriptors[] = { { "bookDepth", ArgInt, (void *) &appData.bookDepth, TRUE, (ArgIniType) 12 }, { "bookVariation", ArgInt, (void *) &appData.bookStrength, TRUE, (ArgIniType) 50 }, { "discourageOwnBooks", ArgBoolean, (void *) &appData.defNoBook, TRUE, (ArgIniType) FALSE }, + { "mcBookMode", ArgTrue, (void *) &mcMode, FALSE, (ArgIniType) FALSE }, { "defaultHashSize", ArgInt, (void *) &appData.defaultHashSize, TRUE, (ArgIniType) 64 }, { "defaultCacheSizeEGTB", ArgInt, (void *) &appData.defaultCacheSizeEGTB, TRUE, (ArgIniType) 4 }, { "defaultPathEGTB", ArgFilename, (void *) &appData.defaultPathEGTB, TRUE, (ArgIniType) "c:\\egtb" }, diff --git a/backend.c b/backend.c index 13afbc5..93c3dcf 100644 --- a/backend.c +++ b/backend.c @@ -10647,6 +10647,7 @@ GameEnds (ChessMove result, char *resultDetails, int whosays) if (*appData.savePositionFile != NULLCHAR) { SavePositionToFile(appData.savePositionFile); } + AddGameToBook(FALSE); // Only does something during Monte-Carlo book building } } @@ -11779,6 +11780,7 @@ InitSearch () } GameInfo dummyInfo; +static int creatingBook; int GameContainsPosition (FILE *f, ListGame *lg) @@ -12242,6 +12244,7 @@ LoadGame (FILE *f, int gameNumber, char *title, int useList) cm = (ChessMove) Myylex(); } + if(!creatingBook) { if (first.pr == NoProc) { StartChessProgram(&first); } @@ -12254,6 +12257,7 @@ LoadGame (FILE *f, int gameNumber, char *title, int useList) } DisplayBothClocks(); } + } /* [HGM] server: flag to write setup moves in broadcast file as one */ loadFlag = appData.suppressLoadMoves; @@ -12323,6 +12327,7 @@ LoadGame (FILE *f, int gameNumber, char *title, int useList) keepInfo = 0; } + if(creatingBook) return TRUE; if (!matchMode && pos > 0) { ToNrEvent(pos); // [HGM] no autoplay if selected on position } else @@ -15037,6 +15042,40 @@ HintEvent () } void +CreateBookEvent () +{ + ListGame * lg = (ListGame *) gameList.head; + FILE *f; + int nItem; + static int secondTime = FALSE; + + if( !(f = GameFile()) || ((ListGame *) gameList.tailPred)->number <= 0 ) { + DisplayError(_("Game list not loaded or empty"), 0); + return; + } + + if(!secondTime && (f = fopen(appData.polyglotBook, "r"))) { + fclose(f); + secondTime++; + DisplayNote(_("Book file exists! Try again for overwrite.")); + return; + } + + creatingBook = TRUE; + secondTime = FALSE; + + /* Get list size */ + for (nItem = 1; nItem <= ((ListGame *) gameList.tailPred)->number; nItem++){ + LoadGame(f, nItem, "", TRUE); + AddGameToBook(TRUE); + lg = (ListGame *) lg->node.succ; + } + + creatingBook = FALSE; + FlushBook(); +} + +void BookEvent () { if (appData.noChessProgram) return; diff --git a/backend.h b/backend.h index c678e26..2a3d3d8 100644 --- a/backend.h +++ b/backend.h @@ -112,6 +112,7 @@ extern char marker[BOARD_RANKS][BOARD_FILES]; extern char lastMsg[MSG_SIZ]; extern Boolean bookUp; extern int tinyLayout, smallLayout; +extern Boolean mcMode; char *CmailMsg P((void)); /* Tord: Added the useFEN960 parameter in PositionToFEN() below */ @@ -243,6 +244,8 @@ void ApplyMove P((int fromX, int fromY, int toX, int toY, int promoChar, Board b void PackMove P((int fromX, int fromY, int toX, int toY, ChessSquare promoPiece)); void ics_printf P((char *format, ...)); int GetEngineLine P((char *nick, int engine)); +void AddGameToBook P((int always)); +void FlushBook P((void)); char *StrStr P((char *string, char *match)); char *StrCaseStr P((char *string, char *match)); @@ -437,6 +440,7 @@ int MultiPV P((ChessProgramState *cps)); void MoveHistorySet P(( char movelist[][2*MOVE_LEN], int first, int last, int current, ChessProgramStats_Move * pvInfo )); void MakeEngineOutputTitle P((void)); void LoadTheme P((void)); +void CreateBookEvent P((void)); /* A point in time */ typedef struct { diff --git a/book.c b/book.c index c40cd92..98dde33 100644 --- a/book.c +++ b/book.c @@ -76,7 +76,7 @@ entry_t entry_none = { 0, 0, 0, 0 }; -char *promote_pieces=" nbrqac="; +char *promote_pieces=" nbrqac=+"; uint64 Random64[781] = { U64(0x9D39247E33776D41), U64(0x2AF7398005AAA5C7), U64(0x44DB015024623547), U64(0x9C15F73E62A76AE2), @@ -380,12 +380,42 @@ hash (int moveNr) #define MOVE_BUF 100 +// fs routines read from memory buffer if no file specified + +static unsigned char *memBuf, *memPtr; +static int bufSize; +Boolean mcMode; + +int +fsseek (FILE *f, int n, int mode) +{ + if(f) return fseek(f, n, mode); + if(mode == SEEK_SET) memPtr = memBuf + n; else + if(mode == SEEK_END) memPtr = memBuf + 16*bufSize + n; + return memPtr < memBuf || memPtr > memBuf + 16*bufSize; +} + +int +fstell (FILE *f) +{ + if(f) return ftell(f); + return memPtr - memBuf; +} + +int +fsgetc (FILE *f) +{ + if(f) return fgetc(f); + if(memPtr >= memBuf + 16*bufSize) return EOF; + return *memPtr++ ; +} + int int_from_file (FILE *f, int l, uint64 *r) { int i,c; for(i=0;ikey=r; @@ -423,12 +454,12 @@ find_key (FILE *f, uint64 key, entry_t *entry) int first, last, middle; entry_t last_entry,middle_entry; first=-1; - if(fseek(f,-16,SEEK_END)){ + if(fsseek(f,-16,SEEK_END)){ *entry=entry_none; entry->key=key+1; //hack return -1; } - last=ftell(f)/16; + last=fstell(f)/16; entry_from_file(f,&last_entry); while(1){ if(last-first==1){ @@ -436,7 +467,7 @@ find_key (FILE *f, uint64 key, entry_t *entry) return last; } middle=(first+last)/2; - fseek(f,16*middle,SEEK_SET); + fsseek(f,16*middle,SEEK_SET); entry_from_file(f,&middle_entry); if(key<=middle_entry.key){ last=middle; @@ -454,20 +485,21 @@ move_to_string (char move_s[6], uint16 move) int width = BOARD_RGHT - BOARD_LEFT, size; // allow for alternative board formats size = width * BOARD_HEIGHT; + p = move / (size*size); + move = move % (size*size); f = move / size; fr = f / width; ff = f % width; t = move % size; tr = t / width; tf = t % width; - p = move / (size*size); move_s[0] = ff + 'a'; move_s[1] = fr + '1' - (BOARD_HEIGHT > 9); move_s[2] = tf + 'a'; move_s[3] = tr + '1' - (BOARD_HEIGHT > 9); // kludge: encode drops as special promotion code - if(gameInfo.holdingsSize && p == 8) { + if(gameInfo.holdingsSize && p == 9) { move_s[0] = f + '@'; // from square encodes piece type move_s[1] = '@'; // drop symbol p = 0; @@ -497,29 +529,14 @@ move_to_string (char move_s[6], uint16 move) } int -GetBookMoves (int moveNr, char *book, entry_t entries[]) +GetBookMoves (FILE *f, int moveNr, entry_t entries[], int max) { // retrieve all entries for given position from book in 'entries', return number. - static FILE *f = NULL; - static char curBook[MSG_SIZ]; entry_t entry; int offset; uint64 key; int count; int ret; - if(book == NULL || moveNr >= 2*appData.bookDepth) return -1; -// if(gameInfo.variant != VariantNormal) return -1; // Zobrist scheme only works for normal Chess, so far - if(!f || strcmp(book, curBook)){ // keep book file open until book changed - strncpy(curBook, book, MSG_SIZ); - if(f) fclose(f); - f = fopen(book,"rb"); - } - if(!f){ - DisplayError(_("Polyglot book not valid"), 0); - appData.usePolyglotBook = FALSE; - return -1; - } - key = hash(moveNr); if(appData.debugMode) fprintf(debugFP, "book key = %08x%08x\n", (unsigned int)(key>>32), (unsigned int)key); @@ -529,7 +546,7 @@ GetBookMoves (int moveNr, char *book, entry_t entries[]) } entries[0] = entry; count=1; - fseek(f, 16*(offset+1), SEEK_SET); + fsseek(f, 16*(offset+1), SEEK_SET); while(1){ ret=entry_from_file(f, &entry); if(ret){ @@ -538,22 +555,127 @@ GetBookMoves (int moveNr, char *book, entry_t entries[]) if(entry.key != key){ break; } - if(count == MOVE_BUF) break; + if(count == max) break; entries[count++] = entry; } return count; } +int +ReadFromBookFile (int moveNr, char *book, entry_t entries[]) +{ // retrieve all entries for given position from book in 'entries', return number. + static FILE *f = NULL; + static char curBook[MSG_SIZ]; + + if(book == NULL) return -1; + if(!f || strcmp(book, curBook)){ // keep book file open until book changed + strncpy(curBook, book, MSG_SIZ); + if(f) fclose(f); + f = fopen(book,"rb"); + } + if(!f){ + DisplayError("Polyglot book not valid", 0); + appData.usePolyglotBook = FALSE; + return -1; + } + + return GetBookMoves(f, moveNr, entries, MOVE_BUF); +} + +// next three made into subroutines to facilitate future changes in storage scheme (e.g. 2 x 3 bytes) + +static int +wins(entry_t *e) +{ + return e->learnPoints; +} + +static int +losses(entry_t *e) +{ + return e->learnCount; +} + +static void +CountMove (entry_t *e, int result) +{ + switch(result) { + case 0: e->learnCount ++; break; + case 1: e->learnCount ++; // count draw as win + loss + case 2: e->learnPoints ++; break; + } +} + +#define MERGESIZE 2048 +#define HASHSIZE 1024*1024*4 + +entry_t *memBook, *hashTab, *mergeBuf; +int bookSize=1, mergeSize=1, mask = HASHSIZE-1; + +void +InitMemBook () +{ + static int initDone = FALSE; + if(initDone) return; + memBook = (entry_t *) calloc(1024*1024, sizeof(entry_t)); + hashTab = (entry_t *) calloc(HASHSIZE, sizeof(entry_t)); + mergeBuf = (entry_t *) calloc(MERGESIZE+5, sizeof(entry_t)); + memBook[0].key = -1LL; + mergeBuf[0].key = -1LL; + initDone = TRUE; +} + char * -ProbeBook (int moveNr, char *book) +MCprobe (moveNr) { + int count, count2, games, i, choice=0; + entry_t entries[MOVE_BUF]; + float nominal[MOVE_BUF], tot, deficit, max, min; + static char move_s[6]; + + InitMemBook(); + memBuf = (unsigned char*) memBook; bufSize = bookSize; // in MC mode book resides in memory + count = GetBookMoves(NULL, moveNr, entries, MOVE_BUF); + if(count < 0) count = 0; // don't care about miss yet + memBuf = (unsigned char*) mergeBuf; bufSize = mergeSize; // there could be moves still waiting to be merged + count2 = count + GetBookMoves(NULL, moveNr, entries+count, MOVE_BUF - count); + if(appData.debugMode) fprintf(debugFP, "MC probe: %d/%d (%d+%d)\n", count, count2,bookSize,mergeSize); + if(!count2) return NULL; + tot = games = 0; + for(i=0; i max) max = deficit, choice = i; + if(deficit < min) min = deficit; + } // note that a single move will never be underplayed + if(max - min > 0.5*sqrt(nominal[choice])) { // if one of the listed moves is significantly under-played, play it now. + move_to_string(move_s, entries[choice].move); + if(appData.debugMode) fprintf(debugFP, "book move field = %d\n", entries[choice].move); + return move_s; + } + return NULL; // otherwise fake book miss to force engine think, hoping for hitherto unplayed move. +} + +char +*ProbeBook (int moveNr, char *book) +{ // entry_t entries[MOVE_BUF]; int count; int i, j; static char move_s[6]; int total_weight; - if((count = GetBookMoves(moveNr, book, entries)) <= 0) return NULL; // no book, or no hit + if(moveNr >= 2*appData.bookDepth) return NULL; + if(mcMode) return MCprobe(moveNr); + + if((count = ReadFromBookFile(moveNr, book, entries)) <= 0) return NULL; // no book, or no hit if(appData.bookStrength != 50) { // transform weights double power = 0, maxWeight = 0.0; @@ -587,11 +709,11 @@ extern char yy_textstr[]; entry_t lastEntries[MOVE_BUF]; char * -MovesToText (int count, entry_t *entries) +MovesToText(int count, entry_t *entries) { int i, totalWeight = 0; char algMove[6]; - char *p = (char*) malloc(30*count+1); + char *p = (char*) malloc(40*count+1); for(i=0; i writepos) { - fseek(f, readpos, SEEK_SET); + fsseek(f, readpos, SEEK_SET); readpos += len1 = fread(buf1, 1, 4096, f); } else len1 = 0; // wrote already past old EOF - fseek(f, writepos, SEEK_SET); + fsseek(f, writepos, SEEK_SET); fwrite(buf2, 1, len2, f); writepos += len2; } while(len1); @@ -727,3 +855,145 @@ SaveToBook (char *text) fclose(f); } +void +NewEntry (entry_t *e, uint64 key, int move, int result) +{ + e->key = key; + e->move = move; + e->learnPoints = 0; + e->learnCount = 0; + CountMove(e, result); +} + +void +Merge () +{ + int i; + + if(appData.debugMode) fprintf(debugFP, "book merge %d moves (old size %d)\n", mergeSize, bookSize); + + bookSize += --mergeSize; + for(i=bookSize-1; mergeSize; i--) { + while(mergeSize && (i < mergeSize || mergeBuf[mergeSize-1].key >= memBook[i-mergeSize].key)) + memBook[i--] = mergeBuf[--mergeSize]; + if(i < 0) break; + memBook[i] = memBook[i-mergeSize]; + } + if(mergeSize) DisplayFatalError("merge error", 0, 0); // impossible + mergeSize = 1; + mergeBuf[0].key = -1LL; +} + +void +AddToBook (int moveNr, int result) +{ + entry_t entry; + int offset, start, move; + uint64 key; + int i, j, fromY, toY; + char fromX, toX, promo; +extern char moveList[][MOVE_LEN]; + + if(!moveList[moveNr][0] || moveList[moveNr][0] == '\n') return; // could be terminal position + + if(appData.debugMode) fprintf(debugFP, "add move %d to book %s", moveNr, moveList[moveNr]); + + // calculate key and book representation of move + key = hash(moveNr); + if(moveList[moveNr][1] == '@') { + sscanf(moveList[moveNr], "%c@%c%d", &promo, &toX, &toY); + fromX = CharToPiece(WhiteOnMove(moveNr) ? ToUpper(promo) : ToLower(promo)); + fromY = DROP_RANK; promo = NULLCHAR; + } else sscanf(moveList[moveNr], "%c%d%c%d%c", &fromX, &fromY, &toX, &toY, &promo), fromX -= AAA, fromY -= ONE - '0'; + move = CoordsToMove(fromX, fromY, toX-AAA, toY-ONE+'0', promo); + + // if move already in book, just add count + memBuf = (unsigned char*) memBook; bufSize = bookSize; // in MC mode book resides in memory + offset = find_key(NULL, key, &entry); + while(memBook[offset].key == key) { + if(memBook[offset].move == move) { + CountMove(memBook+offset, result); return; + } else offset++; + } + // move did not occur in the main book + memBuf = (unsigned char*) mergeBuf; bufSize = mergeSize; // it could be amongst moves still waiting to be merged + start = offset = find_key(NULL, key, &entry); + while(mergeBuf[offset].key == key) { + if(mergeBuf[offset].move == move) { + if(appData.debugMode) fprintf(debugFP, "found in book merge buf @ %d\n", offset); + CountMove(mergeBuf+offset, result); return; + } else offset++; + } + if(start != offset) { // position was in mergeBuf, but move is new + if(appData.debugMode) fprintf(debugFP, "add in book merge buf @ %d\n", offset); + for(i=mergeSize++; i>offset; i--) mergeBuf[i] = mergeBuf[i-1]; // make room + NewEntry(mergeBuf+offset, key, move, result); + return; + } + // position was not in mergeBuf; look in hash table + i = (key & mask); offset = -1; + while(hashTab[i].key) { // search in hash table (necessary because sought item could be re-hashed) + if(hashTab[i].key == 1 && offset < 0) offset = i; // remember first invalidated entry we pass + if(!((hashTab[i].key - key) & ~1)) { // hit + if(hashTab[i].move == move) { + CountMove(hashTab+i, result); + for(j=mergeSize++; j>start; j--) mergeBuf[j] = mergeBuf[j-1]; + } else { + // position already in hash now occurs with different move; move both moves to mergeBuf + for(j=mergeSize+1; j>start+1; j--) mergeBuf[j] = mergeBuf[j-2]; + NewEntry(mergeBuf+start+1, key, move, result); mergeSize += 2; + } + hashTab[i].key = 1; // kludge to invalidate hash entry + mergeBuf[start] = hashTab[i]; mergeBuf[start].key = key; + if(mergeSize >= MERGESIZE) Merge(); + return; + } + i = i+1 & mask; // wrap! + } + // position did not yet occur in hash table. Put it there + if(offset < 0) offset = i; + NewEntry(hashTab+offset, key, move, result); + if(appData.debugMode) + fprintf(debugFP, "book hash @ %d (%d-%d)\n", offset, hashTab[offset].learnPoints, hashTab[offset].learnCount); +} + +void +AddGameToBook (int always) +{ + int i, result; + + if(!mcMode && !always) return; + + InitMemBook(); + switch(gameInfo.result) { + case GameIsDrawn: result = 1; break; + case WhiteWins: result = 2; break; + case BlackWins: result = 0; break; + default: return; // don't treat games with unknown result + } + + if(appData.debugMode) fprintf(debugFP, "add game to book (%d-%d)\n", backwardMostMove, forwardMostMove); + + for(i=backwardMostMove; ifp : NULL; +} + void GameListDestroy () { diff --git a/winboard/resource.h b/winboard/resource.h index 7b07764..7ad0f61 100644 --- a/winboard/resource.h +++ b/winboard/resource.h @@ -71,6 +71,7 @@ #define IDM_MachineBoth 186 #define IDM_MuteSounds 187 #define IDM_Match 188 +#define IDM_CreateBook 189 #define OPT_TCtext1 202 #define OPT_TCTime 203 #define OPT_TCtext2 204 diff --git a/winboard/wgamelist.c b/winboard/wgamelist.c index 7aec90d..886b02c 100644 --- a/winboard/wgamelist.c +++ b/winboard/wgamelist.c @@ -420,6 +420,11 @@ VOID GameListPopUp(FILE *fp, char *filename) gameListUp = TRUE; } +FILE *GameFile() +{ + return gameFile; +} + VOID GameListPopDown(void) { CheckMenuItem(GetMenu(hwndMain), IDM_ShowGameList, MF_UNCHECKED); diff --git a/winboard/winboard.c b/winboard/winboard.c index 8420e3b..df3a37f 100644 --- a/winboard/winboard.c +++ b/winboard/winboard.c @@ -4867,6 +4867,10 @@ WndProc(HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam) } break; + case IDM_CreateBook: + CreateBookEvent(); + break; + case IDM_CopyGame: CopyGameToClipboard(); break; diff --git a/winboard/winboard.rc b/winboard/winboard.rc index ee32188..2c47038 100644 --- a/winboard/winboard.rc +++ b/winboard/winboard.rc @@ -1166,6 +1166,7 @@ BEGIN MENUITEM "S&ave Position...\tCtrl+Shift+S",IDM_SavePosition MENUITEM SEPARATOR MENUITEM "Save as &Diagram...", IDM_SaveDiagram + MENUITEM "Save Games to Book", IDM_CreateBook MENUITEM SEPARATOR MENUITEM "&Quit", IDM_Exit END diff --git a/winboard/wsettings.c b/winboard/wsettings.c index 269837b..dbfecfe 100644 --- a/winboard/wsettings.c +++ b/winboard/wsettings.c @@ -781,7 +781,7 @@ Option themeOptions[] = { { 0, 0, 0, NULL, (void*) &appData.useBorder, NULL, NULL, CheckBox, N_("Draw border around board") }, { 0, 0, 32+0, NULL, (void*) &appData.border, NULL, NULL, FileName, N_("Optional border bitmap:") }, { 0, 0, 0, NULL, NULL, NULL, NULL, Label, N_(" Beware: a specified piece font will prevail over piece bitmaps") }, - { 0, 0, 0, NULL, (void*) &appData.bitmapDirectory, NULL, NULL, PathName, N_("Directory with piece bitmaps:") }, + { 0, 0, 0, NULL, (void*) &appData.pieceDirectory, NULL, NULL, PathName, N_("Directory with piece bitmaps:") }, { 0, 0, 0, NULL, (void*) &appData.useFont, NULL, NULL, CheckBox, N_("Use piece font") }, { 0, 50, 150, NULL, (void*) &appData.fontPieceSize, "", NULL, Spin, N_("Font size (%):") }, { 0, 0, 0, NULL, (void*) &appData.renderPiecesWithFont, NULL, NULL, TextBox, N_("Font name:") },