return TRUE;
}
+#define Q_PROMO 4
+#define Q_EP 3
+#define Q_BCASTL 2
+#define Q_WCASTL 1
+
+int pieceList[256], quickBoard[256];
+ChessSquare pieceType[256] = { EmptySquare };
+Board soughtBoard, reverseBoard;
+int counts[EmptySquare], minSought[EmptySquare], minReverse[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare];
+Boolean epOK;
+
+typedef struct {
+ unsigned char piece, to;
+} Move;
+
+#define DATABASESIZE 10000000 /* good for 100k games */
+Move moveDatabase[DATABASESIZE];
+int movePtr;
+
+void MakePieceList(Board board, int *counts)
+{
+ int r, f, n=Q_PROMO;
+ for(r=0;r<EmptySquare;r++) counts[r] = 0; // piece-type counts
+ for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+ int sq = f + (r<<4);
+ if(board[r][f] == EmptySquare) quickBoard[sq] = 0; else {
+ quickBoard[sq] = ++n;
+ pieceList[n] = sq;
+ pieceType[n] = board[r][f];
+ counts[board[r][f]]++;
+ if(board[r][f] == WhiteKing) pieceList[1] = n; else
+ if(board[r][f] == BlackKing) pieceList[2] = n; // remember which are Kings, for castling
+ }
+ }
+ epOK = gameInfo.variant != VariantXiangqi && gameInfo.variant != VariantBerolina;
+}
+
+void PackMove(int fromX, int fromY, int toX, int toY, ChessSquare promoPiece)
+{
+ int sq = fromX + (fromY<<4);
+ int piece = quickBoard[sq];
+ quickBoard[sq] = 0;
+ moveDatabase[movePtr].to = pieceList[piece] = sq = toX + (toY<<4);
+ if(piece == pieceList[1] && fromY == toY && (toX > fromX+1 || toX < fromX-1) && fromX != BOARD_LEFT && fromX != BOARD_RGHT-1) {
+ int from = toX>fromX ? BOARD_RGHT-1 : BOARD_LEFT;
+ moveDatabase[movePtr++].piece = Q_WCASTL;
+ quickBoard[sq] = piece;
+ piece = quickBoard[from]; quickBoard[from] = 0;
+ moveDatabase[movePtr].to = pieceList[piece] = sq = toX>fromX ? sq-1 : sq+1;
+ } else
+ if(piece == pieceList[2] && fromY == toY && (toX > fromX+1 || toX < fromX-1) && fromX != BOARD_LEFT && fromX != BOARD_RGHT-1) {
+ int from = (toX>fromX ? BOARD_RGHT-1 : BOARD_LEFT) + (BOARD_HEIGHT-1 <<4);
+ moveDatabase[movePtr++].piece = Q_BCASTL;
+ quickBoard[sq] = piece;
+ piece = quickBoard[from]; quickBoard[from] = 0;
+ moveDatabase[movePtr].to = pieceList[piece] = sq = toX>fromX ? sq-1 : sq+1;
+ } else
+ if(epOK && (pieceType[piece] == WhitePawn || pieceType[piece] == BlackPawn) && fromX != toX && quickBoard[sq] == 0) {
+ quickBoard[(fromY<<4)+toX] = 0;
+ moveDatabase[movePtr].piece = Q_EP;
+ moveDatabase[movePtr++].to = (fromY<<4)+toX;
+ moveDatabase[movePtr].to = sq;
+ } else
+ if(promoPiece != pieceType[piece]) {
+ moveDatabase[movePtr++].piece = Q_PROMO;
+ moveDatabase[movePtr].to = pieceType[piece] = (int) promoPiece;
+ }
+ moveDatabase[movePtr].piece = piece;
+ quickBoard[sq] = piece;
+ movePtr++;
+}
+
+int PackGame(Board board)
+{
+ moveDatabase[movePtr].piece = 0; // terminate previous game
+ if(movePtr > DATABASESIZE - 500) return 0; // gamble on that game will not be more than 250 moves
+ movePtr++;
+ MakePieceList(board, counts);
+ return movePtr;
+}
+
+int QuickCompare(Board board, int *minCounts, int *maxCounts)
+{ // compare according to search mode
+ int r, f;
+ switch(appData.searchMode)
+ {
+ case 1: // exact position match
+ for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+ if(board[r][f] != pieceType[quickBoard[(r<<4)+f]]) return FALSE;
+ }
+ return TRUE;
+ case 2: // can have extra material on empty squares
+ for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+ if(board[r][f] == EmptySquare) continue;
+ if(board[r][f] != pieceType[quickBoard[(r<<4)+f]]) return FALSE;
+ }
+ return TRUE;
+ case 3: // material with exact Pawn structure
+ for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+ if(board[r][f] != WhitePawn && board[r][f] != BlackPawn) continue;
+ if(board[r][f] != pieceType[quickBoard[(r<<4)+f]]) return FALSE;
+ } // fall through to material comparison
+ case 4: // exact material
+ for(r=0; r<EmptySquare; r++) if(counts[r] != maxCounts[r]) return FALSE;
+ return TRUE;
+ case 6: // material range with given imbalance
+ for(r=0; r<BlackPawn; r++) if(counts[r] - minCounts[r] != counts[r+BlackPawn] - minCounts[r+BlackPawn]) return FALSE;
+ // fall through to range comparison
+ case 5: // material range
+ for(r=0; r<EmptySquare; r++) if(counts[r] < minCounts[r] || counts[r] > maxCounts[r]) return FALSE;
+ return TRUE;
+ }
+}
+
+int QuickScan(Board board, Move *move)
+{ // reconstruct game,and compare all positions in it
+ int cnt=0, stretch=0;
+ 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 -1;
+ 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)
+ piece = pieceList[piece]; // first two elements of pieceList contain King numbers
+ from = pieceList[piece]; // so this must be King
+ quickBoard[from] = 0;
+ quickBoard[to] = piece;
+ pieceList[piece] = to;
+ move++;
+ continue;
+ }
+ }
+ if(appData.searchMode > 2) counts[pieceType[quickBoard[to]]]--; // account capture
+ quickBoard[from] = 0;
+ quickBoard[to] = piece;
+ pieceList[piece] = to;
+ cnt++;
+ if(QuickCompare(soughtBoard, minSought, maxSought) ||
+ appData.ignoreColors && QuickCompare(reverseBoard, minReverse, maxReverse)) {
+ static int lastCounts[EmptySquare+1];
+ int i;
+ if(stretch) for(i=0; i<EmptySquare; i++) if(lastCounts[i] != counts[i]) { stretch = 0; break; } // reset if material changes
+ if(stretch++ == 0) for(i=0; i<EmptySquare; i++) lastCounts[i] = counts[i]; // remember actual material
+ } else stretch = 0;
+ if(stretch && (appData.searchMode == 1 || stretch >= appData.stretch)) return cnt + 1 - stretch;
+ move++;
+ } while(1);
+}
+
+InitSearch()
+{
+ int r, f;
+ CopyBoard(soughtBoard, boards[currentMove]);
+ MakePieceList(soughtBoard, maxSought);
+ CopyBoard(reverseBoard, boards[currentMove]);
+ for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+ int piece = boards[currentMove][BOARD_HEIGHT-1-r][f];
+ if(piece < BlackPawn) piece += BlackPawn; else if(piece < EmptySquare) piece -= BlackPawn; // color-flip
+ reverseBoard[r][f] = piece;
+ }
+ for(r=0; r<6; r++) reverseBoard[CASTLING][r] = boards[currentMove][CASTLING][(r+3)%6];
+ for(r=0; r<BlackPawn; r++) maxReverse[r] = maxSought[r+BlackPawn], maxReverse[r+BlackPawn] = maxSought[r];
+ if(appData.searchMode >= 5) {
+ for(r=BOARD_HEIGHT/2; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) soughtBoard[r][f] = EmptySquare;
+ MakePieceList(soughtBoard, minSought);
+ for(r=0; r<BlackPawn; r++) minReverse[r] = minSought[r+BlackPawn], minReverse[r+BlackPawn] = minSought[r];
+ }
+}
+
GameInfo dummyInfo;
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<EmptySquare; next++) keys[next] = random()>>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) {
+ if((next = QuickScan( boards[scratch], &moveDatabase[lg->moves] )) < 0) return -1; // quick scan rules out it is there
+ if(appData.searchMode >= 4) return next; // for material searches, trust QuickScan.
+ }
+ if(btm) plyNr++;
+ if(PositionMatches(boards[scratch], 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;
+ yyboardindex = scratch;
+ quickFlag = plyNr+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;
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)]);
- if(PositionMatches(boards[scratch + (plyNr&1)], boards[currentMove])) return plyNr;
+ ApplyMove(fromX, fromY, toX, toY, promoChar, boards[scratch]);
+ if(PositionMatches(boards[scratch], boards[currentMove])) return plyNr;
+ if(appData.ignoreColors && PositionMatches(boards[scratch], reverseBoard)) return plyNr;
}
}
projects / xboard.git / blobdiff