Search

#include "stdafx.h"
#include "search.h"
#include "transposition.h"
 
 
#define MAX_DEPTH 100
 
/* symbols used to enhance readability */
#define DO_NULL    1
#define NO_NULL    0
#define IS_PV      1
#define NO_PV      0
 
sSearchDriver sd;
 
int draw_opening = -10; // middlegame draw value
int draw_endgame = 0;   // endgame draw value
int ASPIRATION   = 50;  // size of the aspiration window ( val-ASPITATION, val+ASPIRATION )
 
bool time_over = 0;
 
enum eproto {
    PROTO_NOTHING,
    PROTO_XBOARD,
    PROTO_UCI
} extern mode; 
 
U8 bestmove;         // move id passed between iterations for sorting purposes
smove move_to_make;     // move to be returned when search runs out of time
 
/***************************************************************
*  search_run() is the interface of all the search functions,  *
*  the only function called outside search.cpp. It does some   *
*  preparatory work, and then calls search_iterate();          *
***************************************************************/
 
void search_run() {
 
    if ( chronos.flags & (FTIME | FINC | FMOVESTOGO) ) {
        if ( getBookMove(BOOK_BROAD) ) return;
    }
 
    search_clearDriver(); 
    time_calc_movetime();
    ageHistoryTable();
    if ( mode == PROTO_NOTHING ) printSearchHeader();
 
    search_iterate();
}
 
void search_clearDriver() {
     sd.myside = b.stm;         // remember color - needed in contempt()
     sd.starttime = gettime();
     sd.movetime = 0;
     sd.depth = 0;
 
     // now clear all the statistical data
     sd.nodes = 0;
     sd.q_nodes = 0;
}
 
/**************************************************************
*  search_iterate() calls search_root() with increasing depth *
*  until allocated time is exhausted.                         *
**************************************************************/
 
void search_iterate() {
     int val, temp;
 
    // check the exact number of legal moves in the current position
 
    int move_count = move_countLegal();
 
    // do a full-window 1-ply search to get the first estimate of val 
 
    sd.depth = 1;
    val = search_root( sd.depth, -INF, INF );
 
    // main loop, increasing deph in steps of 1
 
    for (sd.depth=2; sd.depth<=MAX_DEPTH; sd.depth++) {
 
        // breaking conditions - either expired time
        // or just one legal reply and position searched to depth 4
 
        if ( time_stop_root() || time_over  ) break;
        if ( move_count == 1  && sd.depth == 5 ) break;
 
        // this function deals with aspiration window
        val = search_widen(sd.depth, val);
    } 
 
    // after the loop has finished, send the move to the interface
    com_sendmove(move_to_make);
}
 
int search_widen(int depth, int val) {
    int temp = val, 
    alpha = val - 50,
    beta  = val + 50;
 
    temp = search_root(sd.depth, alpha, beta);
    if (temp <= alpha || temp >= beta)
        temp = search_root(sd.depth, -INF, INF);
    return temp;
}
 
int search_root( U8 depth, int alpha, int beta ) {
 
    int flagInCheck;
    smove movelist[256];
    int val = 0;
 
    U8 currmove_legal = 0;
 
    /* Check  extension is done also at  the  root */
 
    flagInCheck = isAttacked( !b.stm, b.KingLoc[b.stm] );
    if ( flagInCheck ) ++depth;
 
    U8 mcount = movegen(movelist, bestmove);
 
    for ( U8 i = 0; i < mcount; i++ ) {
 
        movegen_sort( mcount, movelist, i);
 
        if ( movelist[i].piece_cap == KING ) {
            alpha = INF;
            bestmove = movelist[i].id;
        }
 
        move_make( movelist[i] );
 
        // filter out illegal moves
        if (isAttacked(b.stm, b.KingLoc[!b.stm])) {
            move_unmake( movelist[i] );
            continue; 
        }
 
    //    if ( mode == PROTO_UCI ) 
    //        info_currmove( movelist[i], currmove_legal ); 
 
        currmove_legal ++; 
 
        /* the "if" clause introduces PVS at root */
 
        if ( ( i == 0 ) || 
             ( -Search( depth-1, 0, -alpha-1, -alpha, DO_NULL, NO_PV ) > alpha ) )
           val = -Search(depth-1, 0, -beta, -alpha, DO_NULL, IS_PV );
 
        move_unmake( movelist[i] );
 
        if (time_over) break;
 
        if ( val > alpha ) {
 
           bestmove = movelist[i].id;
            move_to_make = movelist[i];
 
           if ( val > beta ) { // should be >=, see post
              tt_save(depth, beta, TT_BETA, bestmove);
              info_pv( beta );
              return beta;
           }
 
           alpha = val;
           tt_save( depth, alpha, TT_ALPHA, bestmove ); 
 
           info_pv( val );
        } // changing node value finished
    }
 
    tt_save( depth, alpha, TT_EXACT, bestmove ); 
    return alpha;
}
 
int Search( U8 depth, U8 ply, int alpha, int beta, int can_null, int is_pv ) {
 
    int  val = -INF;
    char bestmove;
    char tt_move = INVALID;
    char tt_flag = TT_ALPHA;
    int  flagInCheck;
    int  legal_move = 0;
    int  raised_alpha = 0;
    int  f_prune = 0;
    int  reduction_depth = 0;
    int  moves_tried = 0;
    int  new_depth;
    int  mate_value = INF - ply; // will be used in mate distance pruning
    smove move;
 
    /************************************************************************  
    *  Probably later we will want to probe the transposition table.        *
    *  Tell the cpu to prepare for that event. This is just a minor         *
    *  speed optimization and program would run fine without that.          *
    ************************************************************************/
 
    _mm_prefetch((char *)&tt[b.hash & tt_size], _MM_HINT_NTA);
 
    /************************************************************************
    * Check for timeout. This is quite time-consuming, so we do it only     *
    * every so often. The side effect is that if we want  to limit search   *
    * by number of nodes, it will be slightly inexact.                      *
    ************************************************************************/
 
    if ( !time_over && !(sd.nodes & 4095) )
        time_over = time_stop();
    if ( time_over ) return 0;
 
    /************************************************************************
    * MATE DISTANCE PRUNING - a minor improvement that helps to shave off   *
    * some nodes when the checkmate is near. Basically it prevents looking  *
    * for checkmates taking longer than one we have already found. No Elo   *
    * gain expected, but it's a nice feature. Don't use it at the root,     *
    * since  this code  doesn't return a move, only a value.                *
    ************************************************************************/
 
    if (alpha < -mate_value) alpha = -mate_value;
    if (beta > mate_value - 1) beta = mate_value - 1;
    if (alpha >= beta) return alpha;
 
    /************************************************************************ 
    *  Are we in check? If so, extend. It also means that program will      *
    *  never enter quiescence search while in check.                        *
    ************************************************************************/
 
    flagInCheck = ( isAttacked( !b.stm, b.KingLoc[b.stm] ) );
    if ( flagInCheck ) ++depth;
 
    /************************************************************************ 
    *  At leaf nodes we do quiescence search (captures only) to make sure   *
    *  that only relatively quiet positions with no hanging pieces will be  *
    *  evaluated.                                                           * 
    ************************************************************************/
 
    if ( depth == 0 ) return Quiesce( alpha, beta );            
 
    sd.nodes ++;
 
    if ( isRepetition() ) return contempt();
 
    /************************************************************************
    *  Read the transposition table. We may have already searched current   *
    *  position. If depth was sufficient, then we might use the score       *
    *  of that search. If not, hash move still is expected to be good       *
    *  and should be sorted first.                                          *
    *                                                                       *
    *  NOTE: current implementation is sub-standard, since tt_move is just  *
    *  an index showing move's location on a move list. We should be able   *
    *  to retrieve move without generating full move list instead.          *
    ************************************************************************/
 
    if ( ( val = tt_probe(depth, alpha, beta, &tt_move) ) != INVALID ) {
        // in pv nodes we return only in case of an exact hash hit
        if (!is_pv || (val > alpha && val < beta))
        return val;
    }
 
    /************************************************************************
    * EVAL PRUNING / STATIC NULL MOVE                                       *
    ************************************************************************/
 
    if (depth < 3
        && (!is_pv)
        && (!flagInCheck)
        && (abs(beta - 1) > -INF+100)) 
    {
        int static_eval = eval(alpha, beta, 1);
 
        int eval_margin = 120 * depth;
        if (static_eval - eval_margin >= beta)
            return static_eval - eval_margin;
    }
 
    /************************************************************************ 
    *  Here  we introduce  NULL MOVE PRUNING. It  means  allowing opponent  * 
    *  to execute two moves in a row, i.e. capturing something and escaping *
    *  a recapture. If this cannot  wreck our position, then it is so good  *
    *  that there's  no  point in searching further. The flag "can_null"    *
    *  ensures we don't do  two null moves in a row. Null move is not used  *
    *  in  the endgame because of the risk of zugzwang.                     *
    ************************************************************************/
 
    if ( ( depth > 2) 
    &&     ( can_null ) 
    &&   (!is_pv)
    &&     ( eval(alpha, beta, 1) > beta ) //should be >=, see post
    &&     ( b.PieceMaterial[b.stm] > e.ENDGAME_MAT ) 
    &&     ( !flagInCheck )  ) 
       {
        char ep_old = b.ep;
        move_makeNull();
 
        /******************************************************************** 
        *  We use so-called adaptative null move pruning. Size of reduction *
        *  depends on remaining  depth.                                     *
        ********************************************************************/
 
        char R = 2;
        if ( depth > 6 ) R = 3;
 
        val = -Search( depth - R - 1, ply, -beta, -beta+1, NO_NULL, NO_PV );    
 
        move_unmakeNull(ep_old);
 
        if ( time_over ) return 0;
        if (val >= beta) return beta;
    }
 
    /************************************************************************
    *  Decide  if FUTILITY PRUNING  is  applicable. If we are not in check, *
    *  not searching for a checkmate and eval is below  (alpha - margin),   *
    *  it  might  mean that searching non-tactical moves at  low depths     *
    *  is futile, so we set a flag allowing this pruning.                   *
    ************************************************************************/
 
    int fmargin[4] = {0, 200, 300, 500};
 
    if ( depth <= 3
    &&     !is_pv
    &&     !flagInCheck
    &&     abs(alpha) < 9000
    &&     eval(alpha,beta, 1) + fmargin[depth] <= alpha )
    f_prune = 1;
 
    /* generate moves */
 
    smove movelist[256];
    U8 mcount = movegen( movelist, tt_move );
 
    ReorderMoves( movelist, mcount, ply );
 
    bestmove = movelist[0].id;
 
    /************************************************************************
    *  Now it's time to loop through the move list.                         *
    ************************************************************************/
 
    for (int i = 0; i < mcount; i++) {
 
        movegen_sort( mcount, movelist, i ); // pick the best of untried moves
        move = movelist[i];
        move_make(move);
 
        // filter out illegal moves
        if (isAttacked(b.stm, b.KingLoc[!b.stm])) {
            move_unmake(move);
            continue; 
        }
        moves_tried++;
 
        /********************************************************************
        *  When the futility pruning flag is set, prune moves which do not  *
        *  give  check and do not change material balance.  Some  programs  *
        *  prune insufficient captures as well, but that seems too risky.   *
        ********************************************************************/
 
        if ( f_prune
        &&     legal_move 
        &&  !move_iscapt(move)
        &&    !move_isprom(move) 
        &&  !isAttacked( !b.stm, b.KingLoc[b.stm] )  ) {
                move_unmake(move);
                continue;
        }
 
        reduction_depth = 0;   // this move has not been reduced yet
        new_depth = depth - 1; // decrease depth by one ply
 
        /********************************************************************
        *  Late move reduction. Typically a cutoff occurs on trying one of  *
        *  the first moves. If it doesn't, we are probably in an all-node,  *
        *  which means that all moves will fail low. So we might as well    *
        *  spare some effort, searching to reduced depth. Of course this is *
        *  not a foolproof method, but it works more often than not. Still, *
        *  we  need to exclude certain moves from reduction, in  order  to  *
        *  filter out tactical moves that may cause a late cutoff.          *
        ********************************************************************/
 
        if (!is_pv 
        && new_depth > 3
        && legal_move
        && moves_tried > 3 
        && !isAttacked(!b.stm, b.KingLoc[b.stm])
        && !flagInCheck 
        && (move.from != sd.killers[0][ply].from || move.to != sd.killers[0][ply].to)
        && (move.from != sd.killers[1][ply].from || move.to != sd.killers[1][ply].to)
        && !move_iscapt(move)
        && !move_isprom(move) ) {
 
            /****************************************************************
            * Real programs tend use more advanced formulas to calculate    *
            * reduction depth. Typically they calculate it from both        *  
            * remaining depth and move count. Formula used here is very     *
            * basic and gives only a minimal improvement over uniform       *
            * one ply reduction, and is included for the sake of complete-  *
            * ness only.                                                    *
            ****************************************************************/
 
            reduction_depth = 1; 
            if (moves_tried > 8) reduction_depth += 1; 
 
            new_depth -= reduction_depth;
        }
 
        re_search:
 
        /******************************************************************** 
        *  The code below introduces principal variation search. It  means  *
        *  that once we are in a PV-node (indicated by IS_PV flag) and  we  *
        *  have  found a move that raises alpha, we assume that  the  rest  *
        *  of moves ought to be refuted. This is done  relatively  cheaply  *
        *  by using  a null-window search centered around alpha.  Only  if  *
        *  this search fails high, we are forced repeat it with full window.*
        *                                                                   *
        *  Understanding the shorthand in the first two lines is a bit      *
        *  tricky. If alpha has not been raised, we might be either in      *
        *  a  zero window (scout) node or in an open window (pv)  node,     *
        *  entered after a scout search failed high. In both cases, we      *
        *  need to search with the same alpha, the same beta AND the same   *
        *  node type.                                                       *
        ********************************************************************/
 
        if (!raised_alpha)
            val = -Search(new_depth, ply+1, -beta, -alpha, DO_NULL, is_pv);
        else {
            // first try to refute a move - if this fails, do a real search
            if (-Search(new_depth, ply+1, -alpha - 1, -alpha, DO_NULL, NO_PV) > alpha)
                val = -Search(new_depth, ply+1, -beta, -alpha, DO_NULL, IS_PV);
        }
 
        /********************************************************************
        *  Sometimes reduced search brings us above alpha. This is unusual, *
        *  since we expected reduced move to be bad in first place. It is   *
        *  not certain now, so let's search to the full, unreduced depth.   *
        ********************************************************************/
 
        if (reduction_depth && val > alpha) {
            new_depth += reduction_depth;
            reduction_depth = 0;
            goto re_search;
        }
 
        move_unmake(move);
 
        /******************************************************************** 
        *  If  the  move doesn't return -INF, it means that  the  King      *
        *  couldn't be captured immediately. So the move was legal. In this * 
        *  case we increase the legal_move counter, to look afterwards,     *
        *  whether there were any legal moves on the board at all.          * 
        ********************************************************************/
 
        legal_move += ( val != -INF );
 
        if ( time_over ) return 0;
 
        /******************************************************************** 
        *  We can improve over alpha, so we change the node value together  * 
        *  with  the expected move. Also the raised_alpha flag, needed  to  *
        *  control PVS, is set. In case of a beta cuoff, when our position  *
        *  is  so good that the score will not be accepted one ply before,  *  
        *  we return it immediately.                                        *
        ********************************************************************/ 
 
        if ( val > alpha ) {
 
            bestmove = movelist[i].id;
 
           if ( val >= beta ) {
 
               /*************************************************************
               *  On a quiet move update killer moves and history table     *
               *  in order to enhance move ordering.                        *
               *************************************************************/
 
               if (!move_iscapt(move)
               && !move_isprom(move)) {
                   setKillers(movelist[i], ply);
                   sd.history[move.from][move.to] += depth*depth;
 
                   /********************************************************* 
                   *  With super deep search history table would overflow   *
                   *  - let's prevent it.                                   *
                   *********************************************************/
 
                   if (sd.history[move.from][move.to] > SORT_KILL) {
                       for (int a = 0; a < 128; a++)
                           for (int b = 0; b < 128; b++) {
                               sd.history[a][b] = sd.history[a][b] / 2;
                           }
                   }
               }
               tt_flag = TT_BETA;
               alpha = beta;
               break; // no need to search any further
           }
 
           raised_alpha = 1;
           tt_flag = TT_EXACT;
           alpha = val;
 
        } // changing the node value is finished
 
    }   // end of looping through the moves
 
    /************************************************************************ 
    *  Checkmate and stalemate detection: if we can't find a legal move     *
    *  in the current position, we test if we are in check. If so, mate     *
    *  score relative to search depth is returned. If not, we use  draw     *
    *  evaluation provided by contempt() function.                          *
    ************************************************************************/
 
    if ( !legal_move ) {
        bestmove = -1;
 
        if ( flagInCheck ) alpha = -INF + ply;
        else               alpha = contempt();
    }
 
    /* tt_save() does not save anything when the search is timed out */
    tt_save( depth, alpha, tt_flag, bestmove ); 
 
    return alpha;
}
 
void setKillers(smove m, U8 ply) {
 
    /* if a move isn't a capture, save it as a killer move */
    if ( m.piece_cap == PIECE_EMPTY ) {
 
        /* make sure killer moves will be different 
           before saving secondary killer move */
        if ( m.from != sd.killers[ply][0].from ||
             m.to   != sd.killers[ply][0].to
           )
             sd.killers[ply][1] = sd.killers[ply][0];
 
              /* save primary killer move */
             sd.killers[ply][0] = m;
    }
}
 
void ReorderMoves(smove * m, U8 mcount, U8 ply) {
 
    for ( int j=0; j<mcount; j++ ) {
        if ( ( m[j].from == sd.killers[ply][1].from ) 
         &&      ( m[j].to   == sd.killers[ply][1].to   )
        &&      ( m[j].score < SORT_KILL-1 ) ) {    
               m[j].score = SORT_KILL-1;
        }
 
        if ( ( m[j].from == sd.killers[ply][0].from )
        &&   ( m[j].to   == sd.killers[ply][0].to   )
        &&     ( m[j].score < SORT_KILL ) ) {
               m[j].score = SORT_KILL;
        }
    } 
}
 
int info_currmove(smove m, int nr) {
 
    switch(mode) {
    case PROTO_UCI:
 
        char buffer[64];
        char move[6];
 
        algebraic_writemove(m,move);
        sprintf(buffer, "info depth %d currmove %s currmovenumber %d", sd.depth, move, nr+1);
 
        com_send(buffer);
    }
    return 0;
}
 
int info_pv( int val ) {
    char buffer[2048];
    char score[10];
    char pv[2048];
 
    if (abs( val ) < INF - 2000) {
        sprintf( score,"cp %d", val );
    } else {
        //the mating value is returned in moves not plies ( thats why /2+1)
        if (val > 0) 
            sprintf(score,"mate %d", (INF - val)/2    + 1);
        else
            sprintf(score,"mate %d",-(INF + val)/2 - 1);
    }
 
    U32 nodes = (U32) sd.nodes;
    U32 time = gettime() - sd.starttime;
 
    util_pv(pv);
 
    if ( mode == PROTO_NOTHING )
        sprintf(buffer, " %2d. %9d  %5d %5d %s", sd.depth, nodes, time/10, val, pv);
    else
          sprintf(buffer, "info depth %d score %s time %u nodes %u nps %u pv %s", sd.depth, score, time, nodes, countNps(nodes, time), pv);
 
    com_send(buffer);
 
    return 0;
}
 
/*********************************************************** 
*  countNps() guards against overflow and thus cares  for  *
*  displaying  correct  nps during longer searches.  Node  *
*  count is converted from U64 to unsigned int because of  *
*  some problems with output.                              *
***********************************************************/
 
unsigned int countNps(unsigned int nodes, unsigned int time) {
    if ( time == 0 ) return 0;
 
    if ( time > 20000 )
        return nodes / (time/1000);
    else
        return (nodes*1000) / time;
}
 
/***********************************************************
*  Checking if the current position has been already       *
*  encountered on the current search path. Function        *
*  does NOT check the actual number of repetitions.        *
***********************************************************/
 
int isRepetition() {
 
    for (int i=0; i < b.rep_index; i++) {
        if ( b.rep_stack[i] == b.hash )
            return 1;
    }
 
    return 0;
}
 
/************************************************************
*  Clearing the history table is needed at the beginning    *
*  of a search starting from a new position, like at the    *
*  beginning of a new game.                                 * 
************************************************************/
 
void clearHistoryTable() {
     for (int i = 0; i < 128; i++)
         for (int j = 0; j < 128; j++) {
             sd.history[i][j] = 0;
         }
}
 
/************************************************************
* ageHistoryTable() is run between searches  to  decrease   *
* the  history values used for move sorting. This  causes   *
* obsolete information to disappear gradually. Clearing     *
* the table was worse for the move ordering.                *
************************************************************/
 
void ageHistoryTable() {
     for (int i = 0; i < 128; i++)
         for (int j = 0; j < 128; j++) {
             sd.history[i][j] = sd.history[i][j] / 8;
         }
}
 
/************************************************************
*  contempt() returns a draw value (which may be non-zero)  *
*  relative  to  the side to move and to the  game  stage.  *
*  This  way  we may make our program play for a  draw  or  *
*  strive to avoid it.                                      *
************************************************************/
 
int contempt() {
    int value = draw_opening;
 
    if ( b.PieceMaterial[sd.myside] < e.ENDGAME_MAT )
        value = draw_endgame;
 
    if ( b.stm == sd.myside ) return value;
    else                      return -value;
}

Forum Posts

• value > beta by Robert Pope, CCC, June 10, 2015
• Static NULL Move by thevinenator, OpenChess Forum, December 26, 2016 » Reverse Futility Pruning
• NULL Move code question by thevinenator, OpenChess Forum, January 27, 2017 » Null Move Pruning

What links here?