Search { final public int negaScout(int alpha, int beta, int ply, int depth, int recaptureSquare, final boolean inCheck) throws StopSearch { if (log != null) { SearchTreeInfo sti = searchTreeInfo[ply-1]; long idx = log.logNodeStart(sti.nodeIdx, sti.currentMove, alpha, beta, ply, depth/plyScale); searchTreeInfo[ply].nodeIdx = idx; } if (nodesToGo <= 0) { nodesToGo = nodesBetweenTimeCheck; long tNow = System.currentTimeMillis(); long timeLimit = searchNeedMoreTime ? maxTimeMillis : minTimeMillis; if ( ((timeLimit >= 0) && (tNow - tStart >= timeLimit)) || ((maxNodes >= 0) && (totalNodes >= maxNodes))) { throw new StopSearch(); } if (maxNPS > 0) { long time = tNow - tStart; if (totalNodes * 1000.0 > maxNPS * Math.max(1, time)) { long wantedTime = totalNodes * 1000 / maxNPS; long sleepTime = wantedTime - time; if (sleepTime > 0) try { Thread.sleep(sleepTime); } catch (InterruptedException ignore) {} } } if (tNow - tLastStats >= 1000) { notifyStats(); } } if (verbose) { if (ply < 20) nodesPlyVec[ply]++; if (depth < 20*plyScale) nodesDepthVec[depth/plyScale]++; } final long hKey = pos.historyHash(); if (canClaimDraw50(pos)) { if (MoveGen.canTakeKing(pos)) { int score = MATE0 - ply; if (log != null) log.logNodeEnd(searchTreeInfo[ply].nodeIdx, score, TTEntry.T_EXACT, UNKNOWN_SCORE, hKey); return score; } if (inCheck) { MoveGen.MoveList moves = moveGen.pseudoLegalMoves(pos); MoveGen.removeIllegal(pos, moves); if (moves.size == 0) { int score = -(MATE0-(ply+1)); if (log != null) log.logNodeEnd(searchTreeInfo[ply].nodeIdx, score, TTEntry.T_EXACT, UNKNOWN_SCORE, hKey); moveGen.returnMoveList(moves); return score; } moveGen.returnMoveList(moves); } if (log != null) log.logNodeEnd(searchTreeInfo[ply].nodeIdx, 0, TTEntry.T_EXACT, UNKNOWN_SCORE, hKey); return 0; } if (canClaimDrawRep(pos, posHashList, posHashListSize, posHashFirstNew)) { if (log != null) log.logNodeEnd(searchTreeInfo[ply].nodeIdx, 0, TTEntry.T_EXACT, UNKNOWN_SCORE, hKey); return 0; } int evalScore = UNKNOWN_SCORE; TTEntry ent = tt.probe(hKey); Move hashMove = null; SearchTreeInfo sti = searchTreeInfo[ply]; if (ent.type != TTEntry.T_EMPTY) { int score = ent.getScore(ply); evalScore = ent.evalScore; int plyToMate = MATE0 - Math.abs(score); int eDepth = ent.getDepth(); hashMove = sti.hashMove; ent.getMove(hashMove); if ((beta == alpha + 1) && ((eDepth >= depth) || (eDepth >= plyToMate*plyScale))) { if ( (ent.type == TTEntry.T_EXACT) || (ent.type == TTEntry.T_GE) && (score >= beta) || (ent.type == TTEntry.T_LE) && (score <= alpha)) { if (score >= beta) { hashMove = sti.hashMove; if ((hashMove != null) && (hashMove.from != hashMove.to)) if (pos.getPiece(hashMove.to) == Piece.EMPTY) kt.addKiller(ply, hashMove); } sti.bestMove = hashMove; if (log != null) log.logNodeEnd(searchTreeInfo[ply].nodeIdx, score, ent.type, evalScore, hKey); return score; } } } int posExtend = inCheck ? plyScale : 0; if (depth + posExtend <= 0) { q0Eval = evalScore; sti.bestMove.clear(); int score = quiesce(alpha, beta, ply, 0, inCheck); int type = TTEntry.T_EXACT; if (score <= alpha) { type = TTEntry.T_LE; } else if (score >= beta) { type = TTEntry.T_GE; } sti.bestMove.score = score; tt.insert(hKey, sti.bestMove, type, ply, depth, q0Eval); if (log != null) log.logNodeEnd(sti.nodeIdx, score, type, q0Eval, hKey); return score; } if ((Math.abs(alpha) <= MATE0 / 2) && (depth < 4*plyScale) && (beta == alpha + 1)) { if (evalScore == UNKNOWN_SCORE) { evalScore = eval.evalPos(pos); } final int razorMargin = 250; if (evalScore < beta - razorMargin) { q0Eval = evalScore; int score = quiesce(alpha-razorMargin, beta-razorMargin, ply, 0, inCheck); if (score <= alpha-razorMargin) { emptyMove.score = score; tt.insert(hKey, emptyMove, TTEntry.T_LE, ply, depth, q0Eval); if (log != null) log.logNodeEnd(sti.nodeIdx, score, TTEntry.T_LE, q0Eval, hKey); return score; } } } if (!inCheck && (depth < 5*plyScale) && (posExtend == 0) && (Math.abs(alpha) <= MATE0 / 2) && (Math.abs(beta) <= MATE0 / 2)) { boolean mtrlOk; if (pos.whiteMove) { mtrlOk = (pos.wMtrl > pos.wMtrlPawns) && (pos.wMtrlPawns > 0); } else { mtrlOk = (pos.bMtrl > pos.bMtrlPawns) && (pos.bMtrlPawns > 0); } if (mtrlOk) { int margin; if (depth <= plyScale) margin = 204; else if (depth <= 2*plyScale) margin = 420; else if (depth <= 3*plyScale) margin = 533; else margin = 788; if (evalScore == UNKNOWN_SCORE) evalScore = eval.evalPos(pos); if (evalScore - margin >= beta) { emptyMove.score = evalScore - margin; tt.insert(hKey, emptyMove, TTEntry.T_GE, ply, depth, evalScore); if (log != null) log.logNodeEnd(sti.nodeIdx, evalScore - margin, TTEntry.T_GE, evalScore, hKey); return evalScore - margin; } } } sti.currentMove = emptyMove; if ( (depth >= 3*plyScale) && !inCheck && sti.allowNullMove && (Math.abs(beta) <= MATE0 / 2)) { if (MoveGen.canTakeKing(pos)) { int score = MATE0 - ply; if (log != null) log.logNodeEnd(sti.nodeIdx, score, TTEntry.T_EXACT, evalScore, hKey); return score; } boolean nullOk; if (pos.whiteMove) { nullOk = (pos.wMtrl > pos.wMtrlPawns) && (pos.wMtrlPawns > 0); } else { nullOk = (pos.bMtrl > pos.bMtrlPawns) && (pos.bMtrlPawns > 0); } if (nullOk) { if (evalScore == UNKNOWN_SCORE) evalScore = eval.evalPos(pos); if (evalScore < beta) nullOk = false; } if (nullOk) { final int R = (depth > 6*plyScale) ? 4*plyScale : 3*plyScale; pos.setWhiteMove(!pos.whiteMove); int epSquare = pos.getEpSquare(); pos.setEpSquare(-1); searchTreeInfo[ply+1].allowNullMove = false; searchTreeInfo[ply+1].bestMove.clear(); int score = -negaScout(-beta, -(beta - 1), ply + 1, depth - R, -1, false); searchTreeInfo[ply+1].allowNullMove = true; pos.setEpSquare(epSquare); pos.setWhiteMove(!pos.whiteMove); if (score >= beta) { if (score > MATE0 / 2) score = beta; emptyMove.score = score; tt.insert(hKey, emptyMove, TTEntry.T_GE, ply, depth, evalScore); if (log != null) log.logNodeEnd(sti.nodeIdx, score, TTEntry.T_GE, evalScore, hKey); return score; } else { if ((searchTreeInfo[ply-1].lmr > 0) && (depth < 5*plyScale)) { Move m1 = searchTreeInfo[ply-1].currentMove; Move m2 = searchTreeInfo[ply+1].bestMove; if (relatedMoves(m1, m2)) { if (log != null) log.logNodeEnd(sti.nodeIdx, alpha, TTEntry.T_LE, evalScore, hKey); return alpha; } } } } } boolean futilityPrune = false; int futilityScore = alpha; if (!inCheck && (depth < 5*plyScale) && (posExtend == 0)) { if ((Math.abs(alpha) <= MATE0 / 2) && (Math.abs(beta) <= MATE0 / 2)) { int margin; if (depth <= plyScale) margin = 61; else if (depth <= 2*plyScale) margin = 144; else if (depth <= 3*plyScale) margin = 268; else margin = 334; if (evalScore == UNKNOWN_SCORE) evalScore = eval.evalPos(pos); futilityScore = evalScore + margin; if (futilityScore <= alpha) futilityPrune = true; } } if ((depth > 4*plyScale) && ((hashMove == null) || (hashMove.from == hashMove.to))) { boolean isPv = beta > alpha + 1; if (isPv || (depth > 8 * plyScale)) { long savedNodeIdx = sti.nodeIdx; int newDepth = isPv ? depth - 2 * plyScale : depth * 3 / 8; negaScout(alpha, beta, ply, newDepth, -1, inCheck); sti.nodeIdx = savedNodeIdx; ent = tt.probe(hKey); if (ent.type != TTEntry.T_EMPTY) { hashMove = sti.hashMove; ent.getMove(hashMove); } } } MoveGen.MoveList moves; if (inCheck) moves = moveGen.checkEvasions(pos); else moves = moveGen.pseudoLegalMoves(pos); boolean seeDone = false; boolean hashMoveSelected = true; if (!selectHashMove(moves, hashMove)) { scoreMoveList(moves, ply); seeDone = true; hashMoveSelected = false; } UndoInfo ui = sti.undoInfo; boolean haveLegalMoves = false; int illegalScore = -(MATE0-(ply+1)); int b = beta; int bestScore = illegalScore; int bestMove = -1; int lmrCount = 0; for (int mi = 0; mi < moves.size; mi++) { if ((mi == 1) && !seeDone) { scoreMoveList(moves, ply, 1); seeDone = true; } if ((mi > 0) || !hashMoveSelected) { selectBest(moves, mi); } Move m = moves.m[mi]; if (pos.getPiece(m.to) == (pos.whiteMove ? Piece.BKING : Piece.WKING)) { moveGen.returnMoveList(moves); int score = MATE0-ply; if (log != null) log.logNodeEnd(sti.nodeIdx, score, TTEntry.T_EXACT, evalScore, hKey); return score; } int newCaptureSquare = -1; boolean isCapture = (pos.getPiece(m.to) != Piece.EMPTY); boolean isPromotion = (m.promoteTo != Piece.EMPTY); int sVal = Integer.MIN_VALUE; boolean mayReduce = (m.score < 53) && (!isCapture || m.score < 0) && !isPromotion; boolean givesCheck = MoveGen.givesCheck(pos, m); boolean doFutility = false; if (mayReduce && haveLegalMoves && !givesCheck && !passedPawnPush(pos, m)) { if ((Math.abs(alpha) <= MATE0 / 2) && (Math.abs(beta) <= MATE0 / 2)) { int moveCountLimit; if (depth <= plyScale) moveCountLimit = 3; else if (depth <= 2 * plyScale) moveCountLimit = 6; else if (depth <= 3 * plyScale) moveCountLimit = 12; else if (depth <= 4 * plyScale) moveCountLimit = 24; else moveCountLimit = 256; if (mi >= moveCountLimit) continue; } if (futilityPrune) doFutility = true; } int score; if (doFutility) { score = futilityScore; } else { int moveExtend = 0; if (posExtend == 0) { final int pV = Evaluate.pV; if ((m.to == recaptureSquare)) { if (sVal == Integer.MIN_VALUE) sVal = SEE(m); int tVal = Evaluate.pieceValue[pos.getPiece(m.to)]; if (sVal > tVal - pV / 2) moveExtend = plyScale; } if ((moveExtend < plyScale) && isCapture && (pos.wMtrlPawns + pos.bMtrlPawns > pV)) { int capVal = Evaluate.pieceValue[pos.getPiece(m.to)]; if (pos.whiteMove) { if ((pos.wMtrl == pos.wMtrlPawns) && (pos.bMtrl - pos.bMtrlPawns == capVal)) moveExtend = plyScale; } else { if ((pos.bMtrl == pos.bMtrlPawns) && (pos.wMtrl - pos.wMtrlPawns == capVal)) moveExtend = plyScale; } } } int extend = Math.max(posExtend, moveExtend); int lmr = 0; if ((depth >= 3*plyScale) && mayReduce && (extend == 0)) { if (!givesCheck && !passedPawnPush(pos, m)) { lmrCount++; if ((lmrCount > 3) && (depth > 3*plyScale) && !isCapture) { lmr = 2*plyScale; } else { lmr = 1*plyScale; } } } int newDepth = depth - plyScale + extend - lmr; if (isCapture && (givesCheck || (depth + extend) > plyScale)) { int fVal = Evaluate.pieceValue[pos.getPiece(m.from)]; int tVal = Evaluate.pieceValue[pos.getPiece(m.to)]; final int pV = Evaluate.pV; if (Math.abs(tVal - fVal) < pV / 2) { sVal = SEE(m); if (Math.abs(sVal) < pV / 2) newCaptureSquare = m.to; } } posHashList[posHashListSize++] = pos.zobristHash(); pos.makeMove(m, ui); nodes++; totalNodes++; nodesToGo--; sti.currentMove = m; sti.lmr = lmr; score = -negaScout(-b, -alpha, ply + 1, newDepth, newCaptureSquare, givesCheck); if (((lmr > 0) && (score > alpha)) || ((score > alpha) && (score < beta) && (b != beta) && (score != illegalScore))) { sti.lmr = 0; newDepth += lmr; score = -negaScout(-beta, -alpha, ply + 1, newDepth, newCaptureSquare, givesCheck); } posHashListSize--; pos.unMakeMove(m, ui); } if (weak && haveLegalMoves) if (weakPlaySkipMove(pos, m, ply)) score = illegalScore; m.score = score; if (score != illegalScore) { haveLegalMoves = true; } bestScore = Math.max(bestScore, score); if (score > alpha) { alpha = score; bestMove = mi; sti.bestMove.from = m.from; sti.bestMove.to = m.to; sti.bestMove.promoteTo = m.promoteTo; } if (alpha >= beta) { if (pos.getPiece(m.to) == Piece.EMPTY) { kt.addKiller(ply, m); ht.addSuccess(pos, m, depth/plyScale); for (int mi2 = mi - 1; mi2 >= 0; mi2--) { Move m2 = moves.m[mi2]; if (pos.getPiece(m2.to) == Piece.EMPTY) ht.addFail(pos, m2, depth/plyScale); } } tt.insert(hKey, m, TTEntry.T_GE, ply, depth, evalScore); moveGen.returnMoveList(moves); if (log != null) log.logNodeEnd(sti.nodeIdx, alpha, TTEntry.T_GE, evalScore, hKey); return alpha; } b = alpha + 1; } if (!haveLegalMoves && !inCheck) { moveGen.returnMoveList(moves); if (log != null) log.logNodeEnd(sti.nodeIdx, 0, TTEntry.T_EXACT, evalScore, hKey); return 0; } if (bestMove >= 0) { tt.insert(hKey, moves.m[bestMove], TTEntry.T_EXACT, ply, depth, evalScore); if (log != null) log.logNodeEnd(sti.nodeIdx, bestScore, TTEntry.T_EXACT, evalScore, hKey); } else { emptyMove.score = bestScore; tt.insert(hKey, emptyMove, TTEntry.T_LE, ply, depth, evalScore); if (log != null) log.logNodeEnd(sti.nodeIdx, bestScore, TTEntry.T_LE, evalScore, hKey); } moveGen.returnMoveList(moves); return bestScore; } Search(Position pos, long[] posHashList, int posHashListSize, TranspositionTable tt,
                  History ht); void setListener(Listener listener); final void timeLimit(int minTimeLimit, int maxTimeLimit); final void setStrength(int strength, long randomSeed, int maxNPS); final Move iterativeDeepening(MoveGen.MoveList scMovesIn,
            int maxDepth, long initialMaxNodes, boolean verbose); final int negaScout(int alpha, int beta, int ply, int depth, int recaptureSquare,
                               final boolean inCheck); final int signSEE(Move m); final boolean negSEE(Move m); final int SEE(Move m); static boolean canClaimDraw50(Position pos); static boolean canClaimDrawRep(Position pos, long[] posHashList, int posHashListSize, int posHashFirstNew); public int nodesBetweenTimeCheck; final static int MATE0; final static int UNKNOWN_SCORE; }
@Test public void testDrawRep() throws ChessParseError, StopSearch { System.out.println("drawRep"); final int mate0 = Search.MATE0; Position pos = TextIO.readFEN("7k/5RR1/8/8/8/8/q3q3/2K5 w - - 0 1"); Search sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; final int plyScale = Search.plyScale; int score = sc.negaScout(-mate0, mate0, 0, 3*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(0, score); pos = TextIO.readFEN("7k/5RR1/8/8/8/8/q3q3/2K5 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 3).score; assertEquals(0, score); pos = TextIO.readFEN("7k/5RR1/8/8/8/8/1q3q2/3K4 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 4).score; assertTrue(score < 0); pos = TextIO.readFEN("7k/5RR1/8/8/8/8/1q3q2/3K4 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = sc.negaScout(-mate0, mate0, 0, 3*plyScale, -1, MoveGen.inCheck(pos)); assertTrue(score < 0); pos = TextIO.readFEN("qn6/qn4k1/pp3R2/5R2/8/8/8/K7 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 7).score; assertEquals(0, score); }
@Test public void testNegaScout() throws ChessParseError, StopSearch { System.out.println("negaScout"); final int mate0 = Search.MATE0; Position pos = TextIO.readFEN("3k4/8/3K2R1/8/8/8/8/8 w - - 0 1"); Search sc = new Search(pos, nullHist, 0, tt, ht); final int plyScale = Search.plyScale; int score = sc.negaScout(-mate0, mate0, 0, 2*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(mate0 - 2, score); int score2 = idSearch(sc, 2).score; assertEquals(score, score2); pos = TextIO.readFEN("8/1P6/k7/2K5/8/8/8/8 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); score = sc.negaScout(-mate0, mate0, 0, 4*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(mate0 - 4, score); score2 = idSearch(sc, 4).score; assertEquals(score, score2); pos = TextIO.readFEN("8/5P1k/5K2/8/8/8/8/8 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); score = sc.negaScout(-mate0, mate0, 0, 5*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(mate0 - 4, score); score2 = idSearch(sc, 5).score; assertEquals(score, score2); pos = TextIO.readFEN("4k3/8/3K1Q2/8/8/8/8/8 b - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); score = sc.negaScout(-mate0, mate0, 0, 2*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(0, score); pos = TextIO.readFEN("3kB3/8/1N1K4/8/8/8/8/8 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); score = sc.negaScout(-mate0, mate0, 0, 3*plyScale, -1, MoveGen.inCheck(pos)); assertTrue(Math.abs(score) < 50); score2 = idSearch(sc, 5).score; assertEquals(score, score2); pos = TextIO.readFEN("8/8/2K5/3QP3/P6P/1q6/8/k7 w - - 31 51"); sc = new Search(pos, nullHist, 0, tt, ht); Move bestM = idSearch(sc, 2); assertTrue(!TextIO.moveToString(pos, bestM, false).equals("Qxb3")); }
@Test public void testDraw50() throws ChessParseError, StopSearch { System.out.println("draw50"); final int mate0 = Search.MATE0; final int mateInOne = mate0 - 2; final int matedInOne = -mate0 + 3; final int mateInTwo = mate0 - 4; final int mateInThree = mate0 - 6; Position pos = TextIO.readFEN("8/1R2k3/R7/8/8/8/8/1K6 b - - 0 1"); Search sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; final int plyScale = Search.plyScale; int score = sc.negaScout(-mate0, mate0, 0, 2*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(matedInOne, score); pos = TextIO.readFEN("8/1R2k3/R7/8/8/8/8/1K6 b - - 99 80"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = sc.negaScout(-mate0, mate0, 0, 2*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(0, score); pos = TextIO.readFEN("8/1R2k3/R7/8/8/8/8/1K6 b - - 98 80"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = sc.negaScout(-mate0, mate0, 0, 2*plyScale, -1, MoveGen.inCheck(pos)); assertEquals(matedInOne, score); pos = TextIO.readFEN("8/1R2k3/R7/8/8/8/8/1K6 b - - 99 80"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 3).score; assertEquals(0, score); pos = TextIO.readFEN("3k4/1R6/R7/8/8/8/8/1K6 w - - 100 80"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 2).score; assertEquals(mateInOne, score); pos = TextIO.readFEN("8/7k/1R6/R7/8/7P/8/1K6 w - - 0 1"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 3).score; assertEquals(mateInTwo, score); pos = TextIO.readFEN("8/7k/1R6/R7/8/7P/8/1K6 w - - 98 1"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 6).score; assertEquals(mateInThree, score); pos = TextIO.readFEN("8/7k/1R6/R7/8/7P/8/1K6 w - - 125 1"); sc = new Search(pos, nullHist, 0, tt, ht); sc.maxTimeMillis = -1; score = idSearch(sc, 6).score; assertEquals(mateInThree, score); }