From d2e1434f02c278d6f96f054105a90fac05513253 Mon Sep 17 00:00:00 2001 From: H.G.Muller Date: Sun, 11 Feb 2018 13:57:56 +0100 Subject: [PATCH] Implement iterative deepening in QS A depth limit is applied to QS, with the possibility to return a score range when this limit is hit. If a non-null range survives to the root of QS, the limit is increased, and QS redone. It should then extend the tip of the unresolved branches, the resolved branches satisfactorily present (i.e. with null range or as fail high/low) in the TT. --- dropper.c | 66 ++++++++++++++++++++++++++++++++++++++---------------------- 1 files changed, 42 insertions(+), 24 deletions(-) diff --git a/dropper.c b/dropper.c index 766bfa2..34e11f8 100644 --- a/dropper.c +++ b/dropper.c @@ -10,7 +10,7 @@ #include #define DEBUG 0 - +#define IDQS /* Iteratively deepening QS */ #define LMR 2 #define ON 1 @@ -695,12 +695,12 @@ Debug () typedef struct { // 12 bytes unsigned int lock; - short int score; + short int score, lim; unsigned short int move; unsigned char depth; unsigned char flags; unsigned char checker; - char age; + char age[3]; } HashEntry; typedef struct { @@ -710,6 +710,7 @@ typedef struct { int pstEval, newEval, bulk, tpGain; int move, wholeMove, depth; int checker, checkDir, checkDist, xking; + int lim; // for returning upper end of score interval } StackFrame; typedef struct { // move stack sectioning @@ -1116,11 +1117,11 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, int killer1 = killers[ply][0], killer2 = killers[ply][1], hashMove; int bestNr, bestScore, startAlpha, startScore, resultDepth, iterDepth=0, originalReduction = reduction; int hit, hashKeyH, ran=0, ipMask=0; - int curEval, anaEval, score; + int curEval, anaEval, score, upperScore, minScore = -INF, maxScore = INF; // legality int earlyGen = (ff->fromPiece == stm+31); // King was moved - if(ply > 90) { if(DEBUG) Dump("maxply"); ff->depth = 0; return -ff->newEval+150; } + if(ply > 90) { if(DEBUG) Dump("maxply"); ff->depth = 0; ff->lim = ff->newEval-150; return -ff->newEval+150; } f.xking = location[stm+31]; // opponent King, as stm not yet toggled if(!earlyGen && ff->mutation > 0) { // if other piece was moved (not dropped!), abort with +INF score if it was pinned if(Pinned(stm, ff->fromSqr, f.xking)) return INF; @@ -1151,10 +1152,10 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, } reduction = 0; // checks are not reduced } - if((entry->flags & H_LOWER || entry->score <= alpha) && (entry->flags & H_UPPER || entry->score >= beta)) { // compatible bound + if(score >= beta || entry->lim <= alpha || entry->score == entry->lim) { // only take hash cuts from fully resolved results, unless they fail low or high d += (score >= beta & entry->depth >= LMR)*reduction; // fail highs need to satisfy reduced depth only, so we fake higher depth than actually found if((score > alpha && d >= depth || d >= maxDepth) && ply) { // sufficient depth - ff->depth = d + 1; return entry->score; // depth was sufficient, take hash cutoff + ff->depth = d + 1; ff->lim = -entry->score; return entry->lim; // depth was sufficient, take hash cutoff } } hashMove = entry->move; @@ -1172,7 +1173,7 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, if(!ff->victim) board[ff->toSqr] = stm + 31 ^ COLOR; // kludge: after castling we temporarily make Rook a second King to catch passing through check kingCapt = MoveGen(stm, &m, f.rights); board[ff->toSqr] = ff->toPiece; // undo kludge damage - if(kingCapt) { moveSP = oldSP; ff->depth = MAXPLY; return INF; } // make sure we detect if he moved into check + if(kingCapt) { moveSP = oldSP; ff->depth = MAXPLY; ff->lim = -INF; return INF; } // make sure we detect if he moved into check } if((++nodeCount & 0xFFF) == 0) abortFlag |= TimeIsUp(3); // check time limit every 4K nodes @@ -1181,7 +1182,7 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, beta -= (beta <= curEval); if(ff->checker == CK_NONE) killers[ply+1][0] = killers[ply+1][1] /* = killers[ply+1][2]*/ = 0; else if(ply > 0) killers[ply+1][0] = killers[ply-1][0], killers[ply+1][1] = killers[ply-1][1]; // inherit killers after check+evasion - if(-INF >= beta) { moveSP = oldSP; ff->depth = MAXPLY; return -INF+1; } + if(-INF >= beta) { moveSP = oldSP; ff->depth = MAXPLY; ff->lim = INF-1; return INF; } // check test @@ -1202,13 +1203,13 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, if(depth <= 0) { // QS if(ff->checker != CK_NONE && ff->tpGain > 0) anaEval = 50-INF; // forbid stand pat if horizon check tossed material if(anaEval > alpha) { - if(anaEval >= beta) { ff->depth = 1; moveSP = oldSP; anaSP = oldAna; return anaEval + (anaEval < curEval); } // stand-pat cutoff + if(anaEval >= beta) { ff->depth = 1; ff->lim = -anaEval - (anaEval < curEval); moveSP = oldSP; anaSP = oldAna; return INF; } // stand-pat cutoff alpha = startScore = anaEval; maxDepth = 0; // we will not fail low, so no extra iterations } if(maxDepth <= 0) { if(board[toDecode[hashMove&255]] == 0) hashMove = 0; #ifdef IDQS - if(ply >= depthLimit) { ff->depth = 1; moveSP = oldSP; anaSP = oldAna; return anaEval + 150; } // hit depth limit; give hefty stm bonus + if(ply >= depthLimit) { ff->depth = 1; ff->lim = -anaEval-150; moveSP = oldSP; anaSP = oldAna; return anaEval + 150; } // hit depth limit; give hefty stm bonus if(depthLimit == MAXPLY) depthLimit = ply+10; // we just entered pure QS; set up depth limit #endif } @@ -1224,13 +1225,13 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, deprec[ply] = maxDepth << 16 | depth << 8; path[ply++] = 0; score = -Search(stm, -beta, 1-beta, &f, nullDepth, 0, nullDepth); ply--; - if(score >= beta) { ff->depth = f.depth + originalReduction + 3; moveSP = oldSP; anaSP = oldAna; return beta + 1; } + if(score >= beta) { ff->depth = f.depth + originalReduction + 3; ff->lim = -beta-1; moveSP = oldSP; anaSP = oldAna; return INF; } } // move generation if(!earlyGen) { // generate moves if we had not done so yet if(MoveGen(stm, &m, f.rights)) { // impossible (except for hash collision giving wrong in-check status) - if(DEBUG) Dump("King capture"); ff->depth = MAXPLY; moveSP = oldSP; anaSP = oldAna; return INF; + if(DEBUG) Dump("King capture"); ff->depth = MAXPLY; ff->lim = -INF; moveSP = oldSP; anaSP = oldAna; return INF; } if(f.checkDist && maxDepth <= 1) ipMask = SafeIP(&f); } @@ -1250,18 +1251,19 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, bonus += bonus >> 1; int newEval = curEval + bonus; if(newEval > alpha) { - if(newEval >= beta) { ff->depth = 1; moveSP = oldSP; depthLimit = oldLimit; anaSP = oldAna; return newEval; } // stand-pat cutoff + if(newEval >= beta) { ff->depth = 1; ff->lim = -newEval; moveSP = oldSP; depthLimit = oldLimit; anaSP = oldAna; return INF; } // stand-pat cutoff alpha = startScore = newEval; maxDepth = 0; // we will not fail low, so no extra iterations } } + again: // QS IDD loop do { // IID loop int curMove, highDepth; iterDepth++; highDepth = (iterDepth > depth ? iterDepth : depth) - 1; // reply depth for high-failing moves alpha = startAlpha; pvPtr = pvStart; *pvPtr++ = 0; // empty PV - bestScore = startScore; bestNr = 0; // kludge: points to 0 entry in moveStack + bestScore = upperScore = startScore; bestNr = 0; // kludge: points to 0 entry in moveStack resultDepth = MAXPLY; m.stage &= 3; for(curMove=m.firstMove; m.stage<4; curMove++) { @@ -1276,7 +1278,7 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, m.unsorted = curMove + 1; // sorted set now includes move } else { if(maxDepth <= 0) { - resultDepth = 0; if(bestScore < anaEval) bestScore = anaEval; + resultDepth = 0; if(upperScore < anaEval) upperScore = anaEval; if(m.stage) break; moveSP = curMove; if(ff->checker != CK_NONE && depthLimit != MAXPLY && oldLimit == MAXPLY) { // last move before QS was evasion @@ -1351,7 +1353,7 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, else if(gain == pawn || gain >= (400<<21)) score = INF-1; // quasi-repeat with extra piece in hand else if(gain == -pawn || gain <= (-400<<21)) score = 1-INF; // or with one piece less else goto search;// traded one hand piece for another; could still lead somewhere - f.depth = (score >= beta ? highDepth+1 : iterDepth); // minimum required depth + f.lim = score; f.depth = (score >= beta ? highDepth+1 : iterDepth); // minimum required depth *pvPtr = 0; // fake that daughter returned empty PV } else { // not a repeat: search it int lmr; @@ -1363,7 +1365,7 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, // recursion deprec[ply] = (f.checker != CK_NONE ? f.checker : 0)<<24 | maxDepth<<16 | depth<< 8 | iterDepth; path[ply++] = moveStack[curMove] & 0xFFFF; score = -Search(stm, -beta, -alpha+ran, &f, iterDepth-1, lmr, highDepth); - if(ran && score < INF-100 && score > 100-INF) score += ran; + if(ran && score < INF-100 && score > 100-INF) score += ran, f.lim += ran; ply--; repKey[index] = oldRepKey; repDep[index] = oldRepDep; @@ -1372,7 +1374,7 @@ Search (int stm, int alpha, int beta, StackFrame *ff, int depth, int reduction, // unmake UnMake(&f); - } else score = -INF, f.depth = MAXPLY; + } else score = f.lim = -INF, f.depth = MAXPLY; if(PATH){ int m=moveStack[curMove]; printf("%d:%d:%d %2d. %08x %c%d%c%d %6d %6d %6d\n",ply,depth,iterDepth,curMove,m,(m>>8&255)%22+'a',(m>>8&255)/22+1,toDecode[m&255]%22+'a',toDecode[m&255]/22+1,f.pstEval,score,bestScore); @@ -1382,6 +1384,7 @@ printf("%d:%d:%d %2d. %08x %c%d%c%d %6d %6d %6d\n",ply,depth,iterDepth,curMove,m // minimaxing if(f.depth < resultDepth) resultDepth = f.depth; + if(f.lim > upperScore) upperScore = f.lim; if(score > bestScore) { bestScore = score; @@ -1395,7 +1398,7 @@ printf("%d:%d:%d %2d. %08x %c%d%c%d %6d %6d %6d\n",ply,depth,iterDepth,curMove,m if(f.checker == CK_NONE && curMove >= m.nonCapts && moveStack[curMove] != killers[ply][1]) killers[ply][0] = killers[ply][1], killers[ply][1] = moveStack[curMove]; resultDepth = f.depth; - goto cutoff; // done with this node + upperScore = INF; goto cutoff; // done with this node } tail = pvPtr; pvPtr = pvStart; *pvPtr++ = moveStack[curMove]; // alpha < score < beta: move starts new PV while(*pvPtr++ = *tail++); // copy PV of daughter node behind it (including 0 sentinel) @@ -1427,15 +1430,28 @@ printf("%d:%d:%d %2d. %08x %c%d%c%d %6d %6d %6d\n",ply,depth,iterDepth,curMove,m } while(iterDepth < maxDepth && (ply || !TimeIsUp(1))); // IID loop - if(bestScore == -INF) { // we are mated! + if(upperScore == -INF) { // we are mated! if(perpLoses) { // Shogi - if(ff->fromSqr == handSlot[stm]) bestScore = INF; // mated by Pawn drop, so we win! - } else if(f.checker == CK_NONE) bestScore = 0; // stalemate in zh is draw + if(ff->fromSqr == handSlot[stm]) bestScore = upperScore = INF; // mated by Pawn drop, so we win! + } else if(f.checker == CK_NONE) bestScore = upperScore = 0; // stalemate in zh is draw } cutoff: + +#ifdef IDQS + if(depthLimit != MAXPLY) { // we are in iteratively deepening QS + if(bestScore < minScore) { bestScore = minScore; if(upperScore < bestScore) upperScore = bestScore; } // when we aspired with the previous result, fail high and low must mean score is on edge + if(upperScore > maxScore) { upperScore = maxScore; if(upperScore < bestScore) bestScore = upperScore; } + if(oldLimit == MAXPLY && bestScore != upperScore && bestScore < beta && upperScore > alpha) { // we are in the root of QS and the score is unresolved + depthLimit+=10; alpha = startScore = curEval; iterDepth = 0; // increase depth limit and search again + goto again; + } + } +#endif + // delayed-loss bonus bestScore += (bestScore < curEval); + upperScore += (upperScore < curEval); resultDepth -= (f.checker != CK_NONE); // store unextended depth // hash store @@ -1451,6 +1467,7 @@ printf("%d:%d:%d %2d. %08x %c%d%c%d %6d %6d %6d\n",ply,depth,iterDepth,curMove,m entry->lock = hashKeyH; entry->move = moveStack[bestNr]; // if no move was found, bestNr = 0, and moveStack[0] contains INVALID entry->score = bestScore; + entry->lim = upperScore; entry->depth = resultDepth; entry->flags = (bestScore > alpha)*H_LOWER + (bestScore < beta)*H_UPPER; entry->checker = f.checker + 11*(f.checkDist != 0); // encode distant check as off-board checker @@ -1458,7 +1475,8 @@ printf("%d:%d:%d %2d. %08x %c%d%c%d %6d %6d %6d\n",ply,depth,iterDepth,curMove,m // return results moveSP = oldSP; anaSP = oldAna; pvPtr = pvStart; depthLimit = oldLimit; ff->depth = resultDepth + 1 + originalReduction; // report valid depth as seen from parent - return bestScore; + ff->lim = -bestScore; + return upperScore; } int gameMove[MAXMOVES]; // holds the game history -- 1.7.0.4