From f214727e064bfa242138148a3993177f0aa7b5e7 Mon Sep 17 00:00:00 2001 From: H.G. Muller Date: Mon, 15 Aug 2011 16:59:39 +0200 Subject: [PATCH] Quickscan --- backend.c | 170 +++++++++++++++++++++++++++++++++++++++++++++++------------ backend.h | 1 + gamelist.c | 50 +++++++++++++++--- xgamelist.c | 9 +++ 4 files changed, 189 insertions(+), 41 deletions(-) diff --git a/backend.c b/backend.c index 9259013..e235dc1 100644 --- a/backend.c +++ b/backend.c @@ -11173,6 +11173,130 @@ PositionMatches(Board b1, Board b2) return TRUE; } +#define Q_PROMO 4 +#define Q_EP 3 +#define Q_WCASTL 2 +#define Q_BCASTL 1 + +int pieceList[256], quickBoard[256]; +ChessSquare pieceType[256] = { EmptySquare }; +Board soughtBoard, reverseBoard; +int counts[EmptySquare], soughtCounts[EmptySquare], reverseCounts[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare]; + +typedef struct { + unsigned char piece, to; +} Move; + +Move moveDatabase[4000000]; +int movePtr = 0; + +void MakePieceList(Board board, int *counts) +{ + int r, f, n=Q_PROMO; + for(r=0;r maxCounts[r]) return FALSE; + case 6: // material range + for(r=0; r maxCounts[r]) return FALSE; + return TRUE; + } +} + +int QuickScan(Board board, Move *move) +{ // reconstruct game,and compare all positions in it + MakePieceList(board, counts); + do { + int piece = move->piece; + int to = move->to, from = pieceList[piece]; + if(piece <= Q_PROMO) { // special moves encoded by otherwise invalid piece numbers 1-4 + if(!piece) return FALSE; + if(piece == Q_PROMO) { // promotion, encoded as (Q_PROMO, to) + (piece, promoType) + piece = (++move)->piece; + from = pieceList[piece]; + counts[pieceType[piece]]--; + pieceType[piece] = (ChessSquare) move->to; + counts[move->to]++; + } else if(piece == Q_EP) { // e.p. capture, encoded as (Q_EP, ep-sqr) + (piece, to) + counts[pieceType[quickBoard[to]]]--; + quickBoard[to] = 0; + move++; + continue; + } else if(piece <= Q_BCASTL) { // castling, encoded as (Q_XCASTL, king-to) + (rook, rook-to) + from = pieceList[piece]; // first two elements of pieceList contain initial King positions + piece = quickBoard[from]; // so this must be King + quickBoard[from] = 0; + quickBoard[to] = piece; + pieceList[piece] = to; + continue; + } + } + if(appData.searchMode > 2) counts[pieceType[quickBoard[to]]]--; // account capture + quickBoard[from] = 0; + quickBoard[to] = piece; + pieceList[piece] = to; + if(QuickCompare(soughtBoard, soughtCounts, maxSought)) return TRUE; + move++; + } while(1); +} + GameInfo dummyInfo; int GameContainsPosition(FILE *f, ListGame *lg) @@ -11182,44 +11306,30 @@ int GameContainsPosition(FILE *f, ListGame *lg) char promoChar; static int initDone=FALSE; + // weed out games based on numerical tag comparison + if(lg->gameInfo.variant != gameInfo.variant) return -1; // wrong variant + if(appData.eloThreshold1 && (lg->gameInfo.whiteRating < appData.eloThreshold1 && lg->gameInfo.blackRating < appData.eloThreshold1)) return -1; + if(appData.eloThreshold2 && (lg->gameInfo.whiteRating < appData.eloThreshold2 || lg->gameInfo.blackRating < appData.eloThreshold2)) return -1; + if(appData.dateThreshold && (!lg->gameInfo.date || atoi(lg->gameInfo.date) < appData.dateThreshold)) return -1; if(!initDone) { for(next = WhitePawn; next>8 ^ random()<<6 ^random()<<20; initDone = TRUE; } - dummyInfo.variant = VariantNormal; - FREE(dummyInfo.fen); dummyInfo.fen = NULL; - dummyInfo.whiteRating = 0; - dummyInfo.blackRating = 0; - FREE(dummyInfo.date); dummyInfo.date = NULL; + if(lg->gameInfo.fen) ParseFEN(boards[scratch], &btm, lg->gameInfo.fen); + else CopyBoard(boards[scratch], initialPosition); // default start position + if(lg->moves && !QuickScan( boards[scratch], &moveDatabase[lg->moves] )) return -1; // quick scan rules out it is there + if(btm) CopyBoard(boards[scratch+1], boards[scratch]), plyNr++; + if(PositionMatches(boards[scratch + plyNr], boards[currentMove])) return plyNr; fseek(f, lg->offset, 0); yynewfile(f); - CopyBoard(boards[scratch], initialPosition); // default start position while(1) { yyboardindex = scratch + (plyNr&1); - quickFlag = 1; + quickFlag = 1; next = Myylex(); - quickFlag = 0; + quickFlag = 0; switch(next) { case PGNTag: if(plyNr) return -1; // after we have seen moves, any tags will be start of next game -#if 0 - ParsePGNTag(yy_text, &dummyInfo); // this has a bad memory leak... - if(dummyInfo.fen) ParseFEN(boards[scratch], &btm, dummyInfo.fen), free(dummyInfo.fen), dummyInfo.fen = NULL; -#else - // do it ourselves avoiding malloc - { char *p = yy_text+1, *q; - while(!isdigit(*p) && !isalpha(*p)) p++; - q = p; while(*p != ' ' && *p != '\t' && *p != '\n') p++; - *p = NULLCHAR; - if(!StrCaseCmp(q, "Date") && (p = strchr(p+1, '"'))) { if(atoi(p+1) < appData.dateThreshold) return -1; } else - if(!StrCaseCmp(q, "Variant") && (p = strchr(p+1, '"'))) dummyInfo.variant = StringToVariant(p+1); else - if(!StrCaseCmp(q, "WhiteElo") && (p = strchr(p+1, '"'))) dummyInfo.whiteRating = atoi(p+1); else - if(!StrCaseCmp(q, "BlackElo") && (p = strchr(p+1, '"'))) dummyInfo.blackRating = atoi(p+1); else - if(!StrCaseCmp(q, "WhiteUSCF") && (p = strchr(p+1, '"'))) dummyInfo.whiteRating = atoi(p+1); else - if(!StrCaseCmp(q, "BlackUSCF") && (p = strchr(p+1, '"'))) dummyInfo.blackRating = atoi(p+1); else - if(!StrCaseCmp(q, "FEN") && (p = strchr(p+1, '"'))) ParseFEN(boards[scratch], &btm, p+1); - } -#endif default: continue; @@ -11274,14 +11384,6 @@ int GameContainsPosition(FILE *f, ListGame *lg) break; } // Move encountered; peform it. We need to shuttle between two boards, as even/odd index determines side to move - if(plyNr == 0) { // but first figure out variant and initial position - if(dummyInfo.variant != gameInfo.variant) return -1; // wrong variant - if(appData.eloThreshold1 && (dummyInfo.whiteRating < appData.eloThreshold1 && dummyInfo.blackRating < appData.eloThreshold1)) return -1; - if(appData.eloThreshold2 && (dummyInfo.whiteRating < appData.eloThreshold2 || dummyInfo.blackRating < appData.eloThreshold2)) return -1; - if(appData.dateThreshold && (!dummyInfo.date || atoi(dummyInfo.date) < appData.dateThreshold)) return -1; - if(btm) CopyBoard(boards[scratch+1], boards[scratch]), plyNr++; - if(PositionMatches(boards[scratch + plyNr], boards[currentMove])) return plyNr; - } CopyBoard(boards[scratch + (plyNr+1&1)], boards[scratch + (plyNr&1)]); plyNr++; ApplyMove(fromX, fromY, toX, toY, promoChar, boards[scratch + (plyNr&1)]); diff --git a/backend.h b/backend.h index 6f08f91..460ae48 100644 --- a/backend.h +++ b/backend.h @@ -280,6 +280,7 @@ typedef struct _ListGame { ListNode node; int number; int position; + int moves; unsigned long offset; /* Byte offset of game within file. */ GameInfo gameInfo; /* Note that some entries may be NULL. */ } ListGame; diff --git a/gamelist.c b/gamelist.c index a36af7a..712d9b9 100644 --- a/gamelist.c +++ b/gamelist.c @@ -47,7 +47,9 @@ /* Variables */ List gameList; - +extern Board initialPosition; +extern int quickFlag; +extern int movePtr; /* Local function prototypes */ @@ -212,18 +214,22 @@ int GameListBuild(f) ChessMove cm, lastStart; int gameNumber; ListGame *currentListGame = NULL; - int error; + int error, scratch=100, plyNr=0, fromX, fromY, toX, toY; int offset; char lastComment[MSG_SIZ], buf[MSG_SIZ]; - +struct { + long sec; /* Assuming this is >= 32 bits */ + int ms; /* Assuming this is >= 16 bits */ +} t,t2; GetTimeMark(&t); GameListFree(&gameList); yynewfile(f); gameNumber = 0; + quickFlag = 1; lastStart = (ChessMove) 0; yyskipmoves = FALSE; do { - yyboardindex = 0; + yyboardindex = scratch + (plyNr & 1); offset = yyoffset(); cm = (ChessMove) Myylex(); switch (cm) { @@ -285,10 +291,13 @@ int GameListBuild(f) ParsePGNTag(yy_text, ¤tListGame->gameInfo); } } while (cm == PGNTag || cm == Comment); - break; + if(1) { CopyBoard(boards[scratch], initialPosition); plyNr = 0; currentListGame->moves = PackGame(boards[scratch]); } + if(cm != NormalMove) break; + case IllegalMove: + if(appData.testLegality) break; case NormalMove: /* Allow the first game to start with an unnumbered move */ - yyskipmoves = TRUE; + yyskipmoves = FALSE; if (lastStart == (ChessMove) 0) { if ((error = GameListNewGame(¤tListGame))) { rewind(f); @@ -299,6 +308,32 @@ int GameListBuild(f) currentListGame->offset = offset; lastStart = MoveNumberOne; } + case WhiteCapturesEnPassant: + case BlackCapturesEnPassant: + case WhitePromotion: + case BlackPromotion: + case WhiteNonPromotion: + case BlackNonPromotion: + case WhiteKingSideCastle: + case WhiteQueenSideCastle: + case BlackKingSideCastle: + case BlackQueenSideCastle: + case WhiteKingSideCastleWild: + case WhiteQueenSideCastleWild: + case BlackKingSideCastleWild: + case BlackQueenSideCastleWild: + case WhiteHSideCastleFR: + case WhiteASideCastleFR: + case BlackHSideCastleFR: + case BlackASideCastleFR: + fromX = currentMoveString[0] - AAA; + fromY = currentMoveString[1] - ONE; + toX = currentMoveString[2] - AAA; + toY = currentMoveString[3] - ONE; + CopyBoard(boards[scratch + (plyNr+1&1)], boards[scratch + (plyNr&1)]); + plyNr++; + ApplyMove(fromX, fromY, toX, toY, currentMoveString[4], boards[scratch + (plyNr&1)]); + PackMove(fromX, fromY, toX, toY, currentMoveString[4]); break; case WhiteWins: // [HGM] rescom: save last comment as result details case BlackWins: @@ -334,7 +369,8 @@ int GameListBuild(f) PrintPGNTags(debugFP, ¤tListGame->gameInfo); } } - +GetTimeMark(&t2);printf("GameListBuild %d msec\n", SubtractTimeMarks(&t2,&t)); + quickFlag = 0; DisplayTitle("WinBoard"); rewind(f); yyskipmoves = FALSE; diff --git a/xgamelist.c b/xgamelist.c index 5767b98..9b851d4 100644 --- a/xgamelist.c +++ b/xgamelist.c @@ -326,12 +326,19 @@ GameListCreate(name, callback, client_data) return shell; } +extern int soughtCounts[]; +extern Board soughtBoard; + static int GameListPrepare(int byPos) { // [HGM] filter: put in separate routine, to make callable from call-back int nstrings; ListGame *lg; char **st, *line; +struct { + long sec; /* Assuming this is >= 32 bits */ + int ms; /* Assuming this is >= 16 bits */ +} t,t2; GetTimeMark(&t); if(st = glc->strings) while(*st) free(*st++); nstrings = ((ListGame *) gameList.tailPred)->number; @@ -339,6 +346,7 @@ GameListPrepare(int byPos) st = glc->strings; lg = (ListGame *) gameList.head; listLength = wins = losses = draws = 0; + if(byPos) MakePieceList(boards[currentMove], soughtCounts), CopyBoard(soughtBoard, boards[currentMove]); while (nstrings--) { int pos = -1; line = GameListLine(lg->number, &lg->gameInfo); @@ -357,6 +365,7 @@ GameListPrepare(int byPos) lg->position = pos; lg = (ListGame *) lg->node.succ; } +GetTimeMark(&t2);printf("GameListPrepare %d msec\n", SubtractTimeMarks(&t2,&t)); DisplayTitle("XBoard"); *st = NULL; return listLength; -- 1.7.0.4