From ca6061cbffe88ff5eb2332e733e0a534b89cc5e7 Mon Sep 17 00:00:00 2001 From: H.G. Muller Date: Tue, 16 Aug 2011 15:29:03 +0200 Subject: [PATCH] Debug position search cache --- args.h | 2 + backend.c | 105 +++++++++++++++++++++++++++++++++++++++---------- common.h | 2 + gamelist.c | 17 +++++++- winboard/resource.h | 6 +++ winboard/wgamelist.c | 2 + winboard/winboard.rc | 23 ++++++++--- winboard/woptions.c | 14 ++++++- xgamelist.c | 2 +- xoptions.c | 7 ++- 10 files changed, 145 insertions(+), 35 deletions(-) diff --git a/args.h b/args.h index 0918244..d3b2d70 100644 --- a/args.h +++ b/args.h @@ -639,6 +639,8 @@ ArgDescriptor argDescriptors[] = { { "eloThresholdBoth", ArgInt, (void *) &appData.eloThreshold2, FALSE, (ArgIniType) 0 }, { "dateThreshold", ArgInt, (void *) &appData.dateThreshold, FALSE, (ArgIniType) 0 }, { "searchMode", ArgInt, (void *) &appData.searchMode, FALSE, (ArgIniType) 1 }, + { "stretch", ArgInt, (void *) &appData.stretch, FALSE, (ArgIniType) 1 }, + { "ignoreColors", ArgBoolean, (void *) &appData.ignoreColors, FALSE, FALSE }, #if ZIPPY { "zippyTalk", ArgBoolean, (void *) &appData.zippyTalk, FALSE, (ArgIniType) ZIPPY_TALK }, diff --git a/backend.c b/backend.c index 286ec32..e670eaf 100644 --- a/backend.c +++ b/backend.c @@ -11175,20 +11175,22 @@ PositionMatches(Board b1, Board b2) #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]; +int counts[EmptySquare], minSought[EmptySquare], minReverse[EmptySquare], maxSought[EmptySquare], maxReverse[EmptySquare]; +Boolean epOK; typedef struct { unsigned char piece, to; } Move; -Move moveDatabase[4000000]; -int movePtr = 0; +#define DATABASESIZE 10000000 /* good for 100k games */ +Move moveDatabase[DATABASESIZE]; +int movePtr; void MakePieceList(Board board, int *counts) { @@ -11201,20 +11203,42 @@ void MakePieceList(Board board, int *counts) 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 } } + epOK = gameInfo.variant != VariantXiangqi && gameInfo.variant != VariantBerolina; } -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; @@ -11223,12 +11247,14 @@ void PackMove(int fromX, int fromY, int toX, int toY, char promoChar) int PackGame(Board board) { - moveDatabase[movePtr++].piece = 0; // terminate previous game + 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 *counts, int *maxCounts) +int QuickCompare(Board board, int *minCounts, int *maxCounts) { // compare according to search mode int r, f; switch(appData.searchMode) @@ -11250,24 +11276,26 @@ int QuickCompare(Board board, int *counts, int *maxCounts) if(board[r][f] != pieceType[quickBoard[(r<<4)+f]]) return FALSE; } // fall through to material comparison case 4: // exact material - for(r=0; r maxCounts[r]) return FALSE; - case 6: // material range - for(r=0; r maxCounts[r]) return FALSE; + case 6: // material range with given imbalance + for(r=0; 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 FALSE; + if(!piece) return -1; if(piece == Q_PROMO) { // promotion, encoded as (Q_PROMO, to) + (piece, promoType) piece = (++move)->piece; from = pieceList[piece]; @@ -11280,11 +11308,12 @@ int QuickScan(Board board, Move *move) 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; } } @@ -11292,11 +11321,39 @@ int QuickScan(Board board, Move *move) quickBoard[from] = 0; quickBoard[to] = piece; pieceList[piece] = to; - if(QuickCompare(soughtBoard, soughtCounts, maxSought)) return TRUE; + 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= 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= 5) { + for(r=BOARD_HEIGHT/2; rgameInfo.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) { + 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); @@ -11387,6 +11447,7 @@ int GameContainsPosition(FILE *f, ListGame *lg) 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; } } diff --git a/common.h b/common.h index 928a85d..c018016 100644 --- a/common.h +++ b/common.h @@ -634,6 +634,8 @@ typedef struct { int eloThreshold2; int dateThreshold; int searchMode; + int stretch; + Boolean ignoreColors; char *userName; int rewindIndex; /* [HGM] autoinc */ int sameColorGames; /* [HGM] alternate */ diff --git a/gamelist.c b/gamelist.c index 11b06ac..fb10fbe 100644 --- a/gamelist.c +++ b/gamelist.c @@ -224,6 +224,7 @@ struct { GameListFree(&gameList); yynewfile(f); gameNumber = 0; + movePtr = 0; lastStart = (ChessMove) 0; yyskipmoves = FALSE; @@ -241,6 +242,7 @@ struct { } currentListGame->number = ++gameNumber; currentListGame->offset = offset; + if(1) { CopyBoard(boards[scratch], initialPosition); plyNr = 0; currentListGame->moves = PackGame(boards[scratch]); } if (currentListGame->gameInfo.event != NULL) { free(currentListGame->gameInfo.event); } @@ -267,6 +269,7 @@ struct { } currentListGame->number = ++gameNumber; currentListGame->offset = offset; + if(1) { CopyBoard(boards[scratch], initialPosition); plyNr = 0; currentListGame->moves = PackGame(boards[scratch]); } lastStart = cm; break; default: @@ -291,7 +294,13 @@ struct { ParsePGNTag(yy_text, ¤tListGame->gameInfo); } } while (cm == PGNTag || cm == Comment); - if(1) { CopyBoard(boards[scratch], initialPosition); plyNr = 0; currentListGame->moves = PackGame(boards[scratch]); } + if(1) { + int btm=0; + if(currentListGame->gameInfo.fen) ParseFEN(boards[scratch], &btm, currentListGame->gameInfo.fen); + else CopyBoard(boards[scratch], initialPosition); + plyNr = (btm != 0); + currentListGame->moves = PackGame(boards[scratch]); + } if(cm != NormalMove) break; case IllegalMove: if(appData.testLegality) break; @@ -306,6 +315,7 @@ struct { } currentListGame->number = ++gameNumber; currentListGame->offset = offset; + if(1) { CopyBoard(boards[scratch], initialPosition); plyNr = 0; currentListGame->moves = PackGame(boards[scratch]); } lastStart = MoveNumberOne; } case WhiteCapturesEnPassant: @@ -332,7 +342,7 @@ struct { toY = currentMoveString[3] - ONE; plyNr++; ApplyMove(fromX, fromY, toX, toY, currentMoveString[4], boards[scratch]); - PackMove(fromX, fromY, toX, toY, currentMoveString[4]); + if(currentListGame->moves) PackMove(fromX, fromY, toX, toY, boards[scratch][toY][toX]); break; case WhiteWins: // [HGM] rescom: save last comment as result details case BlackWins: @@ -358,6 +368,8 @@ struct { } while (cm != (ChessMove) 0); + if(!currentListGame->moves) DisplayError("Game cache overflowed\nPosition-searching might not work properly", 0); + if (appData.debugMode) { for (currentListGame = (ListGame *) gameList.head; currentListGame->node.succ; @@ -370,6 +382,7 @@ struct { } GetTimeMark(&t2);printf("GameListBuild %d msec\n", SubtractTimeMarks(&t2,&t)); quickFlag = 0; + PackGame(boards[scratch]); // for appending end-of-game marker. DisplayTitle("WinBoard"); rewind(f); yyskipmoves = FALSE; diff --git a/winboard/resource.h b/winboard/resource.h index d1d0e9a..4f85a06 100644 --- a/winboard/resource.h +++ b/winboard/resource.h @@ -612,6 +612,12 @@ #define OPT_Subset 1966 #define OPT_Struct 1967 #define OPT_Material 1968 +#define OPT_Range 1969 +#define OPT_Difference 1970 +#define OPT_Stretch 1971 +#define OPT_Stretcht 1972 +#define OPT_Reversed 1973 +#define OPT_SearchMode 1974 #define OPT_Bitmaps 1976 #define OPT_PieceFont 1977 #define OPT_MessageFont8 1978 diff --git a/winboard/wgamelist.c b/winboard/wgamelist.c index 9d15fa1..382f061 100644 --- a/winboard/wgamelist.c +++ b/winboard/wgamelist.c @@ -86,6 +86,8 @@ static int GameListToListBox( HWND hDlg, BOOL boReset, char * pszFilter, struct } } + if(byPos) InitSearch(); + for (nItem = 0; nItem < ((ListGame *) gameList.tailPred)->number; nItem++){ char * st = NULL; BOOL skip = FALSE; diff --git a/winboard/winboard.rc b/winboard/winboard.rc index 19621f2..68994a0 100644 --- a/winboard/winboard.rc +++ b/winboard/winboard.rc @@ -90,7 +90,7 @@ BEGIN PUSHBUTTON "Cancel",IDCANCEL,195,190,40,14 END -DLG_LoadOptions DIALOG DISCARDABLE 10, 18, 166, 184 +DLG_LoadOptions DIALOG DISCARDABLE 10, 18, 170, 248 STYLE DS_MODALFRAME | WS_POPUP | WS_VISIBLE | WS_CAPTION | WS_SYSMENU CAPTION "Load Game Options" FONT 8, "MS Sans Serif" @@ -106,16 +106,25 @@ BEGIN LTEXT "Elo for both players",OPT_elo2t,46,74,90,8,NOT WS_GROUP EDITTEXT OPT_date,16,90,28,14,ES_AUTOHSCROLL LTEXT "or later year",OPT_datet,46,94,94,8,NOT WS_GROUP + EDITTEXT OPT_Stretch,16,110,28,14,ES_AUTOHSCROLL + LTEXT "consecutive positions",OPT_Stretcht,46,114,94,8,NOT WS_GROUP CONTROL "Match exact position",OPT_Exact,"Button", - BS_AUTORADIOBUTTON | WS_GROUP | WS_TABSTOP,4,111,159,10 + BS_AUTORADIOBUTTON | WS_GROUP | WS_TABSTOP,6,136,159,10 CONTROL "Match if position is subset",OPT_Subset,"Button", - BS_AUTORADIOBUTTON | WS_TABSTOP,4,124,159,10 + BS_AUTORADIOBUTTON | WS_TABSTOP,6,149,159,10 CONTROL "Match material with exact pawn structure",OPT_Struct,"Button", - BS_AUTORADIOBUTTON | WS_TABSTOP,4,137,159,10 + BS_AUTORADIOBUTTON | WS_TABSTOP,6,162,159,10 CONTROL "Match material",OPT_Material,"Button", - BS_AUTORADIOBUTTON | WS_TABSTOP,4,150,159,10 - PUSHBUTTON "OK",IDOK,56,165,50,14,WS_GROUP - PUSHBUTTON "Cancel",IDCANCEL,112,165,50,14 + BS_AUTORADIOBUTTON | WS_TABSTOP,6,175,159,10 + CONTROL "Material range (upper board-half is optional)",OPT_Range,"Button", + BS_AUTORADIOBUTTON | WS_TABSTOP,6,188,159,10 + CONTROL "Material difference (optional material balanced)",OPT_Difference,"Button", + BS_AUTORADIOBUTTON | WS_TABSTOP,6,201,159,10 + GROUPBOX "Search Mode: ",OPT_SearchMode,3,126,164,87,WS_GROUP + CONTROL "Also match reversed colors",OPT_Reversed,"Button", + BS_AUTOCHECKBOX | WS_GROUP | WS_TABSTOP,4,214,160,10 + PUSHBUTTON "OK",IDOK,56,229,50,14,WS_GROUP + PUSHBUTTON "Cancel",IDCANCEL,112,229,50,14 END DLG_SaveOptions DIALOG DISCARDABLE 6, 17, 178, 119 diff --git a/winboard/woptions.c b/winboard/woptions.c index d00d4f0..4d579e3 100644 --- a/winboard/woptions.c +++ b/winboard/woptions.c @@ -2441,7 +2441,9 @@ LoadOptionsWhichRadio(HWND hDlg) return (IsDlgButtonChecked(hDlg, OPT_Exact) ? 1 : (IsDlgButtonChecked(hDlg, OPT_Subset) ? 2 : (IsDlgButtonChecked(hDlg, OPT_Struct) ? 3 : - (IsDlgButtonChecked(hDlg, OPT_Material) ? 4 : -1)))); + (IsDlgButtonChecked(hDlg, OPT_Material) ? 4 : + (IsDlgButtonChecked(hDlg, OPT_Range) ? 5 : + (IsDlgButtonChecked(hDlg, OPT_Difference) ? 6 : -1)))))); } VOID @@ -2478,6 +2480,8 @@ LoadOptions(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam) SetDlgItemInt(hDlg, OPT_elo1, appData.eloThreshold1, FALSE); SetDlgItemInt(hDlg, OPT_elo2, appData.eloThreshold2, FALSE); SetDlgItemInt(hDlg, OPT_date, appData.dateThreshold, FALSE); + SetDlgItemInt(hDlg, OPT_Stretch, appData.stretch, FALSE); + CheckDlgButton(hDlg, OPT_Reversed, appData.ignoreColors); switch (appData.searchMode) { case 1: CheckDlgButton(hDlg, OPT_Exact, TRUE); @@ -2491,6 +2495,12 @@ LoadOptions(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam) case 4: CheckDlgButton(hDlg, OPT_Material, TRUE); break; + case 5: + CheckDlgButton(hDlg, OPT_Range, TRUE); + break; + case 6: + CheckDlgButton(hDlg, OPT_Difference, TRUE); + break; } return TRUE; @@ -2512,7 +2522,9 @@ LoadOptions(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam) appData.eloThreshold1 = GetDlgItemInt(hDlg, OPT_elo1, &ok, FALSE); appData.eloThreshold2 = GetDlgItemInt(hDlg, OPT_elo2, &ok, FALSE); appData.dateThreshold = GetDlgItemInt(hDlg, OPT_date, &ok, FALSE); + appData.stretch = GetDlgItemInt(hDlg, OPT_Stretch, &ok, FALSE); appData.searchMode = LoadOptionsWhichRadio(hDlg); + appData.ignoreColors = IsDlgButtonChecked(hDlg, OPT_Reversed); EndDialog(hDlg, TRUE); return TRUE; diff --git a/xgamelist.c b/xgamelist.c index 9b851d4..15165f1 100644 --- a/xgamelist.c +++ b/xgamelist.c @@ -346,7 +346,7 @@ struct { st = glc->strings; lg = (ListGame *) gameList.head; listLength = wins = losses = draws = 0; - if(byPos) MakePieceList(boards[currentMove], soughtCounts), CopyBoard(soughtBoard, boards[currentMove]); + if(byPos) InitSearch(); while (nstrings--) { int pos = -1; line = GameListLine(lg->number, &lg->gameInfo); diff --git a/xoptions.c b/xoptions.c index 4cacc6b..2429c6e 100644 --- a/xoptions.c +++ b/xoptions.c @@ -569,8 +569,9 @@ Option icsOptions[] = { { 0, 0, 0, NULL, (void*) &IcsOptionsOK, "", NULL, EndMark , "" } }; -char *modeNames[] = { N_("Exact match"), N_("Shown position is subset"), N_("Same material and Pawn chain"), N_("Same material"), NULL }; -char *modeValues[] = { "1", "2", "3", "4" }; +char *modeNames[] = { N_("Exact position match"), N_("Shown position is subset"), N_("Same material with exactly same Pawn chain"), + N_("Same material"), N_("Material range (top board half optional)"), N_("Material difference (optional stuff balanced)"), NULL }; +char *modeValues[] = { "1", "2", "3", "4", "5", "6" }; char *searchMode; int LoadOptionsOK() @@ -589,6 +590,8 @@ Option loadOptions[] = { { 0, 0, 5000, NULL, (void*) &appData.eloThreshold2, "", NULL, Spin, N_("Elo of weakest player at least:") }, { 0, 0, 5000, NULL, (void*) &appData.dateThreshold, "", NULL, Spin, N_("No games before year:") }, { 1, 0, 180, NULL, (void*) &searchMode, (char*) modeNames, modeValues, ComboBox, N_("Seach mode:") }, +{ 0, 0, 0, NULL, (void*) &appData.ignoreColors, "", NULL, CheckBox, N_("Also match reversed colors") }, +{ 0, 1, 50, NULL, (void*) &appData.stretch, "", NULL, Spin, N_("Minimum nr consecutive positions:") }, { 0, 0, 0, NULL, (void*) &LoadOptionsOK, "", NULL, EndMark , "" } }; -- 1.7.0.4