From b8bd259a053aef05b8f0ee07886702b5870234cf Mon Sep 17 00:00:00 2001 From: H.G. Muller Date: Sun, 19 Jun 2011 20:30:09 +0200 Subject: [PATCH] Increase efficiency of SAN generation / disambiguation **************** Risky patch! ********************** The algorithm used for disambiguating and generating SAN was extremely inefficient, because it generated all pseudo-legal moves from the relevant position, and then for each of those did a check test (involving generation of all moves of the opponent), before determining if the move matched the (proposed or given) SAN move. While it is pointless to generate moves with a piece that does not match (let alone checking them for legality). And for a piece that matches, it is pointless to test legality of moves that do not match the to-square. To speed up the process GenLegal and GenPseudoLegal have been equiped with an argument that can indicate the piece type of the required move, so they can skip generating moves with other pieces. TestLegality, Disambiguate and CoordsToAlgebraic make use of this facility, and set also (through global variables rFilter and fFilter) a to-square filter to be applied in the GenLegalCallback before it tests the move for legality. This patch is especially tricky for Crazyhouse, where the piece indicated in the move might not be the piece actually on the board, because the latter is a promoted Pawn, and has to be demoted toits base type before the comparison. --- backend.c | 2 +- moves.c | 52 ++++++++++++++++++++++++++++++++-------------------- moves.h | 4 ++-- 3 files changed, 35 insertions(+), 23 deletions(-) diff --git a/backend.c b/backend.c index f028af4..6ad2142 100644 --- a/backend.c +++ b/backend.c @@ -6718,7 +6718,7 @@ MarkTargetSquares(int clear) for(x=0; x1) capt++; if(capt) diff --git a/moves.c b/moves.c index f930231..dcb4300 100644 --- a/moves.c +++ b/moves.c @@ -169,11 +169,12 @@ int CompareBoards(board1, board2) EP_UNKNOWN if we don't know and want to allow all e.p. captures. Promotion moves generated are to Queen only. */ -void GenPseudoLegal(board, flags, callback, closure) +void GenPseudoLegal(board, flags, callback, closure, filter) Board board; int flags; MoveCallback callback; VOIDSTAR closure; + ChessSquare filter; // [HGM] speed: only do moves with this piece type { int rf, ff; int i, j, d, s, fs, rs, rt, ft, m; @@ -193,6 +194,7 @@ void GenPseudoLegal(board, flags, callback, closure) m = 0; piece = board[rf][ff]; if(PieceToChar(piece) == '~') piece = (ChessSquare) ( DEMOTED piece ); + if(filter != EmptySquare && piece != filter) continue; if(gameInfo.variant == VariantShogi) piece = (ChessSquare) ( SHOGI piece ); @@ -712,6 +714,8 @@ typedef struct { VOIDSTAR cl; } GenLegalClosure; +int rFilter, fFilter; // [HGM] speed: sorry, but I get a bit tired of this closure madness + extern void GenLegalCallback P((Board board, int flags, ChessMove kind, int rf, int ff, int rt, int ft, VOIDSTAR closure)); @@ -725,6 +729,8 @@ void GenLegalCallback(board, flags, kind, rf, ff, rt, ft, closure) { register GenLegalClosure *cl = (GenLegalClosure *) closure; + if(rFilter >= 0 && rFilter != rt || fFilter >= 0 && fFilter != ft) return; // [HGM] speed: ignore moves with wrong to-square + if (!(flags & F_IGNORE_CHECK) ) { int check, promo = (gameInfo.variant == VariantSpartan && kind == BlackPromotion); if(promo) board[rf][ff] = BlackKing; // [HGM] spartan: promote to King before check-test @@ -766,11 +772,12 @@ typedef struct { true if castling is not yet ruled out by a move of the king or rook. Return TRUE if the player on move is currently in check and F_IGNORE_CHECK is not set. [HGM] add castlingRights parameter */ -int GenLegal(board, flags, callback, closure) +int GenLegal(board, flags, callback, closure, filter) Board board; int flags; MoveCallback callback; VOIDSTAR closure; + ChessSquare filter; { GenLegalClosure cl; int ff, ft, k, left, right, swap; @@ -779,7 +786,8 @@ int GenLegal(board, flags, callback, closure) cl.cb = callback; cl.cl = closure; - GenPseudoLegal(board, flags, GenLegalCallback, (VOIDSTAR) &cl); + if(filter == EmptySquare) rFilter = fFilter = -1; // [HGM] speed: do not filter on square if we do not filter on piece + GenPseudoLegal(board, flags, GenLegalCallback, (VOIDSTAR) &cl, filter); if (!ignoreCheck && CheckTest(board, flags, -1, -1, -1, -1, FALSE)) return TRUE; @@ -1015,7 +1023,7 @@ int CheckTest(board, flags, rf, ff, rt, ft, enPassant) board[i][cl.fking] == (dir>0 ? BlackWazir : WhiteWazir) ) cl.check++; } - GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl); + GenPseudoLegal(board, flags ^ F_WHITE_ON_MOVE, CheckTestCallback, (VOIDSTAR) &cl, EmptySquare); if(gameInfo.variant != VariantSpartan || cl.check == 0) // in Spartan Chess go on to test if other King is checked too goto undo_move; /* 2-level break */ } @@ -1099,10 +1107,11 @@ ChessMove LegalityTest(board, flags, rf, ff, rt, ft, promoChar) int flags; int rf, ff, rt, ft, promoChar; { - LegalityTestClosure cl; ChessSquare piece, *castlingRights = board[CASTLING]; + LegalityTestClosure cl; ChessSquare piece, filterPiece, *castlingRights = board[CASTLING]; if(rf == DROP_RANK) return LegalDrop(board, flags, ff, rt, ft); - piece = board[rf][ff]; + piece = filterPiece = board[rf][ff]; + if(PieceToChar(piece) == '~') filterPiece = DEMOTED piece; if (appData.debugMode) { int i; @@ -1117,11 +1126,12 @@ ChessMove LegalityTest(board, flags, rf, ff, rt, ft, promoChar) cl.rf = rf; cl.ff = ff; - cl.rt = rt; - cl.ft = ft; + cl.rt = rFilter = rt; // [HGM] speed: filter on to-square + cl.ft = fFilter = ft; cl.kind = IllegalMove; cl.captures = 0; // [HGM] losers: prepare to count legal captures. - GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl); + if(flags & F_MANDATORY_CAPTURE) filterPiece = EmptySquare; // [HGM] speed: do not filter in suicide, to find all captures + GenLegal(board, flags, LegalityTestCallback, (VOIDSTAR) &cl, filterPiece); if((flags & F_MANDATORY_CAPTURE) && cl.captures && board[rt][ft] == EmptySquare && cl.kind != WhiteCapturesEnPassant && cl.kind != BlackCapturesEnPassant) return(IllegalMove); // [HGM] losers: if there are legal captures, non-capts are illegal @@ -1247,7 +1257,7 @@ int MateTest(board, flags) if(myPieces == 1) return MT_BARE; } cl.count = 0; - inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl); + inCheck = GenLegal(board, flags, MateTestCallback, (VOIDSTAR) &cl, EmptySquare); // [HGM] 3check: yet to do! if (cl.count > 0) { return inCheck ? MT_CHECK : MT_NONE; @@ -1331,11 +1341,13 @@ void Disambiguate(board, flags, closure) closure->pieceIn,closure->ffIn,closure->rfIn,closure->ftIn,closure->rtIn, closure->promoCharIn, closure->promoCharIn >= ' ' ? closure->promoCharIn : '-'); } - GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure); + rFilter = closure->rtIn; // [HGM] speed: only consider moves to given to-square + fFilter = closure->ftIn; + GenLegal(board, flags, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); // [HGM] speed: only pieces of requested type if (closure->count == 0) { /* See if it's an illegal move due to check */ illegal = 1; - GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure); + GenLegal(board, flags|F_IGNORE_CHECK, DisambiguateCallback, (VOIDSTAR) closure, closure->pieceIn); if (closure->count == 0) { /* No, it's not even that */ if (appData.debugMode) { int i, j; @@ -1586,18 +1598,19 @@ ChessMove CoordsToAlgebraic(board, flags, rf, ff, rt, ft, promoChar, out) /* Piece move */ cl.rf = rf; cl.ff = ff; - cl.rt = rt; - cl.ft = ft; + cl.rt = rFilter = rt; // [HGM] speed: filter on to-square + cl.ft = fFilter = ft; cl.piece = piece; cl.kind = IllegalMove; cl.rank = cl.file = cl.either = 0; - GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl); + c = PieceToChar(piece) ; + GenLegal(board, flags, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); // [HGM] speed if (cl.kind == IllegalMove && !(flags&F_IGNORE_CHECK)) { /* Generate pretty moves for moving into check, but still return IllegalMove. */ - GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl); + GenLegal(board, flags|F_IGNORE_CHECK, CoordsToAlgebraicCallback, (VOIDSTAR) &cl, c!='~' ? piece : (DEMOTED piece)); if (cl.kind == IllegalMove) break; cl.kind = IllegalMove; } @@ -1607,7 +1620,6 @@ ChessMove CoordsToAlgebraic(board, flags, rf, ff, rt, ft, promoChar, out) else "N1f3" or "N5xf7", else "Ng1f3" or "Ng5xf7". */ - c = PieceToChar(piece) ; if( c == '~' || c == '+') { /* [HGM] print nonexistent piece as its demoted version */ piece = (ChessSquare) (DEMOTED piece); @@ -1799,7 +1811,7 @@ int PerpetualChase(int first, int last) if(appData.debugMode) fprintf(debugFP, "judge position %i\n", i); chaseStackPointer = 0; // clear stack that is going to hold possible chases // determine all captures possible after the move, and put them on chaseStack - GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl); + GenLegal(boards[i+1], PosFlags(i), AttacksCallback, &cl, EmptySquare); if(appData.debugMode) { int n; for(n=0; n