![]() |
Cinnamon
1.0
chess engine
|
00001 #include "Search.h" 00002 00003 Search::Search() { 00004 #ifdef DEBUG_MODE 00005 LazyEvalCuts = cumulativeMovesCount = totGen = 0; 00006 #endif 00007 ponder=nullSearch = false; 00008 } 00009 00010 void Search::setNullMove(bool b) { 00011 nullSearch=!b; 00012 } 00013 00014 void Search::startClock() { 00015 ftime(&startTime); 00016 } 00017 00018 void Search::setMainPly(int m) { 00019 mainDepth = m; 00020 } 00021 00022 int Search::checkTime() { 00023 if (running == 2) 00024 return 2; 00025 if(ponder) 00026 return 1; 00027 struct timeb t_current; 00028 ftime(&t_current); 00029 return _time::diffTime(t_current , startTime) >= maxTimeMillsec ? 0 : 1; 00030 } 00031 00032 Search::~Search() { 00033 } 00034 00035 template <int side> 00036 int Search::quiescence(u64 key, int alpha, int beta, const char promotionPiece, int dep) { 00037 if (!running) 00038 return 0; 00039 ASSERT(dep+mainDepth<MAX_PLY); 00040 ASSERT(chessboard[KING_BLACK+side]); 00041 00042 int score = -_INFINITE; 00043 if (!(numMovesq++ & 1023)) 00044 running = checkTime(); 00045 00046 score =getScore(side,alpha, beta ); 00047 if (score >= beta) { 00048 return beta; 00049 } 00050 #ifndef NO_FP_MODE 00051 /**************Delta Pruning ****************/ 00052 char fprune = 0; 00053 int fscore; 00054 if ((fscore = score + (promotionPiece == -1 ? VALUEQUEEN : 2 * VALUEQUEEN)) < alpha) { 00055 fprune = 1; 00056 } 00057 /************ end Delta Pruning *************/ 00058 #endif 00059 if (score > alpha) 00060 alpha = score; 00061 incListId(); 00062 00063 u64 friends=getBitBoard<side>(); 00064 u64 enemies=getBitBoard<side^1>(); 00065 if (generateCaptures<side>(enemies,friends,&key)) { 00066 gen_list[listId--].size = 0; 00067 return _INFINITE - (mainDepth - dep); 00068 } 00069 int listcount = gen_list[listId].size; 00070 if (!listcount) { 00071 --listId; 00072 return score; 00073 } 00074 _Tmove * move; 00075 u64 oldKey = key; 00076 while ((move = getNextMove(&gen_list[listId])) ) { 00077 makemove(move, &key,false); 00078 #ifndef NO_FP_MODE 00079 /**************Delta Pruning ****************/ 00080 if (fprune && ((move->type & 0x3) != PROMOTION_MOVE_MASK) 00081 && fscore + PIECES_VALUE[move->capturedPiece] <= alpha ) { 00082 INC(nCutFp); 00083 takeback(move, &key, oldKey,false); 00084 continue; 00085 } 00086 /************ end Delta Pruning *************/ 00087 #endif 00088 int val = -quiescence<side^1>(key, -beta, -alpha, move->promotionPiece, dep + 1); 00089 score = max(score, val); 00090 takeback(move, &key, oldKey,false); 00091 if (score >= beta) { 00092 gen_list[listId--].size = 0; 00093 return beta; 00094 } 00095 if (score > alpha) { 00096 alpha = score; 00097 } 00098 } 00099 gen_list[listId--].size = 0; 00100 return alpha; 00101 } 00102 00103 void Search::setPonder(bool r) { 00104 ponder = r; 00105 } 00106 00107 void Search::setRunning(int r) { 00108 running = r; 00109 if(!r)maxTimeMillsec=0; 00110 } 00111 00112 int Search::getRunning() { 00113 return running; 00114 } 00115 00116 void Search::setMaxTimeMillsec(int n) { 00117 maxTimeMillsec = n; 00118 } 00119 00120 int Search::getMaxTimeMillsec() { 00121 return maxTimeMillsec; 00122 } 00123 00124 void Search::sortHashMoves(int listId1, _Thash* phashe) { 00125 for (int r = 0; r < gen_list[listId1].size; r++) { 00126 _Tmove * mos = &gen_list[listId1].moveList[r]; 00127 if (phashe && phashe->from == mos->from && phashe->to == mos->to) { 00128 mos->score = _INFINITE / 2; 00129 return; 00130 } 00131 } 00132 } 00133 00134 bool Search::checkDraw(u64 key) { 00135 int o=0; 00136 int count=0; 00137 for(int i=repetitionMapCount-1; i>=0; i--) { 00138 if(repetitionMap[i]==0) 00139 return false; 00140 if(++count>=99) { 00141 return true; 00142 } 00143 if(repetitionMap[i]==key && ++o >2) { 00144 return true; 00145 } 00146 } 00147 return false; 00148 } 00149 00150 int Search::search( int depth, int alpha, int beta, _TpvLine * pline) { 00151 #ifndef NO_HASH_MODE 00152 ASSERT(zobristKey); 00153 #endif 00154 return getSide()? 00155 search<WHITE>(zobristKey, depth, alpha, beta, pline) 00156 : 00157 search<BLACK>(zobristKey, depth, alpha, beta, pline); 00158 } 00159 00160 template <int side> 00161 int Search::search(u64 key, int depth, int alpha, int beta, _TpvLine * pline) { 00162 if (!running) 00163 return 0; 00164 00165 if( mainDepth!=depth && checkDraw(key) ) { 00166 return -lazyEval<side>()*2; 00167 } 00168 00169 u64 oldKey = key; 00170 INC(cumulativeMovesCount); 00171 00172 #ifdef DEBUG_MODE 00173 double betaEfficencyCount = 0.0; 00174 #endif 00175 ASSERT(chessboard[KING_BLACK]); 00176 ASSERT(chessboard[KING_WHITE]); 00177 ASSERT(chessboard[KING_BLACK+side]); 00178 00179 _TpvLine line; 00180 line.cmove = 0; 00181 int is_incheck_side = inCheck<side>(); 00182 int extension = 0; 00183 if (is_incheck_side) 00184 extension++; 00185 depth += extension; 00186 if (depth == 0) { 00187 return quiescence<side>(key, alpha, beta, -1, 0); 00188 } 00189 _Thash * phashe_greater = NULL; 00190 _Thash * phashe_always = NULL; 00191 bool hash_greater = false; 00192 bool hash_always = false; 00193 //************* hash **************** 00194 char hashf = hashfALPHA; 00195 #ifndef NO_HASH_MODE 00196 ASSERT(key); 00197 bool updatePvFromHash=false; 00198 phashe_greater = &(hash_array_greater[side][key % HASH_SIZE]); 00199 if (phashe_greater->key == key) { 00200 if (phashe_greater->from !=phashe_greater->to && (phashe_greater->flags == hashfEXACT || phashe_greater->flags == hashfBETA)) 00201 hash_greater = true; 00202 if ( phashe_greater->depth >= depth) { 00203 INC(probeHash); 00204 if(!currentPly) { 00205 if(phashe_greater->flags==hashfBETA) incKillerHeuristic(phashe_greater->from, phashe_greater->to, 1 ); 00206 } else { 00207 switch (phashe_greater->flags) { 00208 case hashfEXACT: 00209 INC(n_cut_hashE); 00210 00211 if (phashe_greater->from != phashe_greater->to) { 00212 updatePvFromHash=true; 00213 updatePv<side>(pline, &line, phashe_greater->from, phashe_greater->to); 00214 } 00215 if (phashe_greater->score >= beta) { 00216 return beta; 00217 } 00218 break; 00219 00220 case hashfBETA: 00221 incKillerHeuristic(phashe_greater->from, phashe_greater->to, 1 ); 00222 if (phashe_greater->score >= beta ) { 00223 INC(n_cut_hashB); 00224 return beta; 00225 } 00226 break; 00227 case hashfALPHA: 00228 00229 if (phashe_greater->score <= alpha) { 00230 INC(n_cut_hashA); 00231 return alpha; 00232 } 00233 break; 00234 default: 00235 break; 00236 } 00237 INC(cutFailed); 00238 } 00239 } 00240 } 00241 phashe_always = &(hash_array_always[side][key % HASH_SIZE]); 00242 if (phashe_always->key == key) { 00243 if (phashe_always->from !=phashe_always->to && (phashe_always->flags == hashfEXACT || phashe_always->flags == hashfBETA)) 00244 hash_always = true; 00245 if ( phashe_always->depth >= depth) { 00246 INC(probeHash); 00247 if(!currentPly) { 00248 if(phashe_always->flags==hashfBETA) incKillerHeuristic(phashe_always->from, phashe_always->to, 1 ); 00249 } else { 00250 switch (phashe_always->flags) { 00251 case hashfEXACT: 00252 INC(n_cut_hashE); 00253 if (!updatePvFromHash && phashe_always->from != phashe_always->to) { 00254 updatePv<side>(pline, &line, phashe_always->from, phashe_always->to); 00255 } 00256 if (phashe_always->score >= beta) { 00257 return beta; 00258 } 00259 break; 00260 00261 case hashfBETA: 00262 incKillerHeuristic(phashe_always->from, phashe_always->to, 1 ); 00263 if (phashe_always->score >= beta) { 00264 INC(n_cut_hashB); 00265 return beta; 00266 } 00267 break; 00268 case hashfALPHA: 00269 if (phashe_always->score <= alpha) { 00270 INC(n_cut_hashA); 00271 return alpha; 00272 } 00273 break; 00274 default: 00275 break; 00276 } 00277 INC(cutFailed); 00278 } 00279 } 00280 } 00281 #endif 00282 //********** end hash *************** 00283 if (!(numMoves & 1023)) 00284 running = checkTime(); 00285 int score = -_INFINITE; 00286 ++numMoves; 00287 //********* null move *********** 00288 int n_pieces_side; 00289 if (!is_incheck_side && !nullSearch && depth>=3 &&(n_pieces_side=getNpiecesNoPawnNoKing<side>()) >=3 ) { 00290 nullSearch = true; 00291 int nullScore = -search<side^1>(key, depth - (2+(depth > (3+( n_pieces_side<2 ? 2:0)))) - 1, -beta, -beta + 1, &line); 00292 nullSearch = false; 00293 if (nullScore >= beta) { 00294 INC(nNullMoveCut); 00295 return nullScore; 00296 } 00297 } 00299 #ifndef NO_FP_MODE 00300 /**************Futility Pruning****************/ 00301 /**************Futility Pruning razor at pre-pre-frontier*****/ 00302 00303 ASSERT(score == -_INFINITE); 00304 bool futilPrune=false; 00305 int futilScore = 0; 00306 if (depth <= 3 && !is_incheck_side) { 00307 int matBalance = lazyEval<side>(); 00308 if ((futilScore = matBalance + FUTIL_MARGIN) <= alpha) { 00309 if (depth == 3 && (matBalance + RAZOR_MARGIN) <= alpha && getNpiecesNoPawnNoKing<side^1>() > 3 ) { 00310 INC(nCutRazor); 00311 depth--; 00312 } else 00313 //**************Futility Pruning at pre-frontier***** 00314 if (depth == 2 && (futilScore = matBalance + EXT_FUTILY_MARGIN) <= alpha) { 00315 futilPrune = true; 00316 score = futilScore; 00317 } else 00318 //**************Futility Pruning at frontier***** 00319 if (depth == 1 /*&& (futilScore = matBalance + FUTIL_MARGIN) <= alpha*/) { 00320 futilPrune = true; 00321 score = futilScore; 00322 } 00323 } 00324 } 00325 /************ end Futility Pruning*************/ 00326 #endif 00327 00328 incListId(); 00329 00330 ASSERT(KING_BLACK + side >= 0 && KING_BLACK + side < 12); 00331 ASSERT(KING_BLACK + (side^1) >= 0 && KING_BLACK + (side^1) < 12); 00332 friendKing[side] = BITScanForward(chessboard[KING_BLACK + side]); 00333 friendKing[side^1] = BITScanForward(chessboard[KING_BLACK + (side^1)]); 00334 u64 friends=getBitBoard<side>(); 00335 u64 enemies=getBitBoard<side^1>(); 00336 if (generateCaptures<side>(enemies,friends,&key)) { 00337 gen_list[listId--].size = 0; 00338 score = _INFINITE - (mainDepth - depth + 1); 00339 return score; 00340 } 00341 generateMoves<side>(friends|enemies); 00342 int listcount = gen_list[listId].size; 00343 if (!listcount) { 00344 --listId; 00345 if (is_incheck_side) 00346 return -_INFINITE + (mainDepth - depth + 1); 00347 else 00348 return -lazyEval<side>()*2; 00349 } 00350 00351 _Tmove* best = NULL; 00352 bool check_alpha = false; 00353 if(hash_greater) 00354 sortHashMoves(listId, phashe_greater); 00355 else if(hash_always) 00356 sortHashMoves(listId, phashe_always); 00357 INC(totGen); 00358 _Tmove * move; 00359 while ((move = getNextMove(&gen_list[listId]))) { 00360 INC(betaEfficencyCount); 00361 makemove(move, &key,true); 00362 #ifndef NO_FP_MODE 00363 if (futilPrune && check_alpha && ((move->type & 0x3) != PROMOTION_MOVE_MASK) 00364 && futilScore + PIECES_VALUE[move->capturedPiece] <= alpha && !inCheck<side>()) { 00365 INC(nCutFp); 00366 takeback(move, &key, oldKey,true); 00367 continue; 00368 } 00369 #endif 00370 00371 int doMws = (score > -_INFINITE + 100); 00372 int lwb = max(alpha, score); 00373 int upb = (doMws ? (lwb + 1) : beta); 00374 currentPly++; 00375 int val = -search<side^1>(key, depth - 1, -upb, -lwb, &line); 00376 currentPly--; 00377 if (doMws && (lwb < val) && (val < beta)) { 00378 currentPly++; 00379 val = -search<side^1>(key, depth - 1, -beta, -val + 1, &line); 00380 currentPly--; 00381 } 00382 score = max(score, val); 00383 takeback(move, &key, oldKey,true); 00384 move->score = score; 00385 if (score > alpha) { 00386 if (score >= beta) { 00387 gen_list[listId--].size = 0; 00388 ASSERT(move->score == score); 00389 INC(nCutAB); 00390 #ifdef DEBUG_MODE 00391 betaEfficency += betaEfficencyCount / (double) listcount * 100.0; 00392 #endif 00393 recordHash(running, phashe_greater,phashe_always, depth - extension, hashfBETA, key, score, move); 00394 setKillerHeuristic(move->from, move->to, 0x400); 00395 return score; 00396 } 00397 alpha = score; 00398 check_alpha = true; 00399 hashf = hashfEXACT; 00400 best = move; 00401 move->score = score; 00402 updatePv(pline, &line, move); 00403 } 00404 } 00405 recordHash(running, phashe_greater,phashe_always, depth - extension, hashf, key, score, best); 00406 gen_list[listId--].size = 0; 00407 return score; 00408 } 00409 00410 void Search::updatePv(_TpvLine * pline, const _TpvLine * line, const _Tmove * move) { 00411 ASSERT(line->cmove < MAX_PLY - 1); 00412 memcpy(&(pline->argmove[0]), move, sizeof(_Tmove)); 00413 memcpy(pline->argmove + 1, line->argmove, line->cmove * sizeof(_Tmove)); 00414 ASSERT(line->cmove >= 0); 00415 pline->cmove = line->cmove + 1; 00416 } 00417 00418 void Search::pushMovesPath(char move) { 00419 movesPath+= move; 00420 } 00421 00422 void Search::clearMovesPath() { 00423 movesPath.clear(); 00424 } 00425 00426 string Search::getMovesPath() { 00427 return movesPath; 00428 } 00429 00430 template <int side> 00431 void Search::updatePv(_TpvLine * pline, const _TpvLine * line, const int from, const int to) { 00432 ASSERT(line->cmove < MAX_PLY - 1); 00433 _Tmove mos; 00434 int type = STANDARD_MOVE_MASK; 00435 mos.side = (char) side; 00436 mos.capturedPiece = getPieceAt<side^1>(POW2[to]); 00437 int pieceFrom = getPieceAt<side>( POW2[from]); 00438 mos.from = from; 00439 mos.to = to; 00440 mos.promotionPiece = -1; 00441 if ((pieceFrom == PAWN_WHITE && from > 55) || (pieceFrom == PAWN_BLACK && from < 8)) { 00442 type = PROMOTION_MOVE_MASK; 00443 mos.promotionPiece = QUEEN_BLACK + side; 00444 } 00445 //TODO enpassant 00446 mos.type = RIGHT_CASTLE | type; 00447 memcpy(&(pline->argmove[0]), &mos, sizeof(_Tmove)); 00448 memcpy(pline->argmove + 1, line->argmove, line->cmove * sizeof(_Tmove)); 00449 ASSERT(line->cmove >= 0); 00450 pline->cmove = line->cmove + 1; 00451 }