int LoadGameFromFile P((char *filename, int n, char *title, int useList));
int LoadPositionFromFile P((char *filename, int n, char *title));
int SavePositionToFile P((char *filename));
-void ApplyMove P((int fromX, int fromY, int toX, int toY, int promoChar,
- Board board));
void MakeMove P((int fromX, int fromY, int toX, int toY, int promoChar));
void ShowMove P((int fromX, int fromY, int toX, int toY));
int FinishMove P((ChessMove moveType, int fromX, int fromY, int toX, int toY,
void ResetClocks P((void));
char *PGNDate P((void));
void SetGameInfo P((void));
-Boolean ParseFEN P((Board board, int *blackPlaysFirst, char *fen));
int RegisterMove P((void));
void MakeRegisteredMove P((void));
void TruncateGame P((void));
#define Q_PROMO 4
#define Q_EP 3
-#define Q_WCASTL 2
-#define Q_BCASTL 1
+#define Q_BCASTL 2
+#define Q_WCASTL 1
int pieceList[256], quickBoard[256];
ChessSquare pieceType[256] = { EmptySquare };
-Board soughtBoard, reverseBoard;
-int counts[EmptySquare], soughtCounts[EmptySquare], reverseCounts[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare];
+Board soughtBoard, reverseBoard, flipBoard, rotateBoard;
+int counts[EmptySquare], minSought[EmptySquare], minReverse[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare];
+int soughtTotal, turn;
+Boolean epOK, flipSearch;
typedef struct {
unsigned char piece, to;
} Move;
-Move moveDatabase[4000000];
-int movePtr = 0;
+#define DSIZE (250000)
-void MakePieceList(Board board, int *counts)
+Move initialSpace[DSIZE+1000]; // gamble on that game will not be more than 500 moves
+Move *moveDatabase = initialSpace;
+unsigned int movePtr, dataSize = DSIZE;
+
+int MakePieceList(Board board, int *counts)
{
- int r, f, n=Q_PROMO;
+ int r, f, n=Q_PROMO, total=0;
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);
pieceList[n] = sq;
pieceType[n] = board[r][f];
counts[board[r][f]]++;
- if(board[r][f] == WhiteKing) pieceList[1] = sq; else
- if(board[r][f] == BlackKing) pieceList[2] = sq; // remember where Kings start, for castling
+ if(board[r][f] == WhiteKing) pieceList[1] = n; else
+ if(board[r][f] == BlackKing) pieceList[2] = n; // remember which are Kings, for castling
+ total++;
}
}
+ epOK = gameInfo.variant != VariantXiangqi && gameInfo.variant != VariantBerolina;
+ return total;
}
-void PackMove(int fromX, int fromY, int toX, int toY, char promoChar)
+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(promoChar) {
-
+ 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;
int PackGame(Board board)
{
- moveDatabase[movePtr++].piece = 0; // terminate previous game
+ Move *newSpace = NULL;
+ moveDatabase[movePtr].piece = 0; // terminate previous game
+ if(movePtr > dataSize) {
+ if(appData.debugMode) fprintf(debugFP, "move-cache overflow, enlarge to %d MB\n", dataSize/128);
+ dataSize *= 8; // increase size by factor 8 (512KB -> 4MB -> 32MB -> 256MB -> 2GB)
+ if(dataSize) newSpace = (Move*) calloc(8*dataSize + 1000, sizeof(Move));
+ if(newSpace) {
+ int i;
+ Move *p = moveDatabase, *q = newSpace;
+ for(i=0; i<movePtr; i++) *q++ = *p++; // copy to newly allocated space
+ if(dataSize > 8*DSIZE) free(moveDatabase); // and free old space (if it was allocated)
+ moveDatabase = newSpace;
+ } else { // calloc failed, we must be out of memory. Too bad...
+ dataSize = 0; // prevent calloc events for all subsequent games
+ return 0; // and signal this one isn't cached
+ }
+ }
+ movePtr++;
MakePieceList(board, counts);
return movePtr;
}
-int QuickCompare(Board board, int *counts, int *maxCounts)
+int QuickCompare(Board board, int *minCounts, int *maxCounts)
{ // compare according to search mode
int r, f;
switch(appData.searchMode)
{
case 1: // exact position match
+ if(!(turn & board[EP_STATUS-1])) return FALSE; // wrong side to move
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;
}
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] != soughtCounts[r]) return FALSE;
+ for(r=0; r<EmptySquare; r++) if(counts[r] != maxCounts[r]) return FALSE;
return TRUE;
- case 5: // material range with given imbalance
- for(r=0; r<EmptySquare; r++) if(counts[r] < soughtCounts[r] || counts[r] > maxCounts[r]) return FALSE;
- case 6: // material range
- for(r=0; r<EmptySquare; r++) if(counts[r] < soughtCounts[r] || counts[r] > maxCounts[r]) return FALSE;
+ 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
- MakePieceList(board, counts);
+ int cnt=0, stretch=0, total = 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) return -1;
if(piece == Q_PROMO) { // promotion, encoded as (Q_PROMO, to) + (piece, promoType)
piece = (++move)->piece;
from = pieceList[piece];
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;
+ quickBoard[to] = 0; total--;
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
+ 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
+ if((total -= (quickBoard[to] != 0)) < soughtTotal) return -1; // piece count dropped below what we search for
quickBoard[from] = 0;
quickBoard[to] = piece;
pieceList[piece] = to;
- if(QuickCompare(soughtBoard, soughtCounts, maxSought)) return TRUE;
+ cnt++; turn ^= 3;
+ if(QuickCompare(soughtBoard, minSought, maxSought) ||
+ appData.ignoreColors && QuickCompare(reverseBoard, minReverse, maxReverse) ||
+ flipSearch && (QuickCompare(flipBoard, minSought, maxSought) ||
+ appData.ignoreColors && QuickCompare(rotateBoard, 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);
}
+void InitSearch()
+{
+ int r, f;
+ flipSearch = FALSE;
+ CopyBoard(soughtBoard, boards[currentMove]);
+ soughtTotal = MakePieceList(soughtBoard, maxSought);
+ soughtBoard[EP_STATUS-1] = (currentMove & 1) + 1;
+ if(currentMove == 0 && gameMode == EditPosition) soughtBoard[EP_STATUS-1] = blackPlaysFirst + 1; // (!)
+ 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;
+ }
+ reverseBoard[EP_STATUS-1] = soughtBoard[EP_STATUS-1] ^ 3;
+ for(r=0; r<6; r++) reverseBoard[CASTLING][r] = boards[currentMove][CASTLING][(r+3)%6];
+ if(appData.findMirror && appData.searchMode <= 3 && (!nrCastlingRights
+ || (boards[currentMove][CASTLING][2] == NoRights ||
+ boards[currentMove][CASTLING][0] == NoRights && boards[currentMove][CASTLING][1] == NoRights )
+ && (boards[currentMove][CASTLING][5] == NoRights ||
+ boards[currentMove][CASTLING][3] == NoRights && boards[currentMove][CASTLING][4] == NoRights ) )
+ ) {
+ flipSearch = TRUE;
+ CopyBoard(flipBoard, soughtBoard);
+ CopyBoard(rotateBoard, reverseBoard);
+ for(r=0; r<BOARD_HEIGHT; r++) for(f=BOARD_LEFT; f<BOARD_RGHT; f++) {
+ flipBoard[r][f] = soughtBoard[r][BOARD_WIDTH-1-f];
+ rotateBoard[r][f] = reverseBoard[r][BOARD_WIDTH-1-f];
+ }
+ }
+ 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];
+ }
+ if(gameInfo.variant == VariantCrazyhouse || gameInfo.variant == VariantShogi || gameInfo.variant == VariantBughouse)
+ soughtTotal = 0; // in drop games nr of pieces does not fall monotonously
+}
+
GameInfo dummyInfo;
int GameContainsPosition(FILE *f, ListGame *lg)
}
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(lg->moves) {
+ turn = btm + 1;
+ 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);
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;
+ if(appData.findMirror) {
+ if(PositionMatches(boards[scratch], flipBoard)) return plyNr;
+ if(appData.ignoreColors && PositionMatches(boards[scratch], rotateBoard)) return plyNr;
+ }
}
}
projects / xboard.git / blobdiff