Cinnamon  1.0
chess engine
Search.cpp
Go to the documentation of this file.
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 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines