7

I was just watching a video on YouTube that analysed a game in between two chess engines. So, chess engines do find good moves but how do they manage their time when they're playing a game ? Is there any algorithm that tells them how much longer they must continue thinking till they make a move, keeping the amount of time left for them in the game in mind ?

0
5

Possibilities:

  • Number of nodes
  • Fixed depth
  • Fixed time
  • Divide a fixed percentage of remaining time
  • By the complexity of the position

Let's take a quick look at Stockfish. Briefly, the file timemann.cpp calculates the minimum time allowed for a move. The default minimum time allowed is about 20 seconds.

Later, during the search it does:

 // Stop the search if only one legal move is available, or if all
 // of the available time has been used, or if we matched an easyMove
 // from the previous search and just did a fast verification.

 ...

 if (   rootMoves.size() == 1
              || Time.elapsed() > Time.optimum() * unstablePvFactor * improvingFactor / 628
              || (mainThread->easyMovePlayed = doEasyMove, doEasyMove))

If the position requires longer thinking (unstable position - unstablePvFactor), the engine would extend the search. How long it extend depend on calibrated parameters.

If there is an obvious move (doEasyMove), Stockfish plays it immediately.

2
  • What is an obvious move ? – Saikat May 13 '17 at 18:26
  • @Saikat e.g. if it's a one-move checkmate or taking a queen without consequences – Nosrep Oct 28 '20 at 21:20
2

Tom Kerrigan's simple chess program uses a scheme to just check every 1024 nodes if a certain amount of time has passed

basically there is a function called think that has the following lines which we jump back to when the time is up...stop_search is set by a function called checkup()

/* some code that lets us longjmp back here and return
    from think() when our time is up */
    stop_search = FALSE;
    setjmp(env);
    if (stop_search) {

        /* make sure to take back the line we were searching */
        while (ply)
            takeback();
        return;
    }    
    start_time = get_ms();
    stop_time = start_time + max_time;    
    ply = 0;
    nodes = 0;

the following lines are part of the search function that gets called by think()

/* do some housekeeping every 1024 nodes */
if ((nodes & 1023) == 0)
    checkup();

You can see that search() calls checkup() every 1024 nodes. In a more complex scheme the think function could dynamically set the amount of time for the searches.

void checkup()
{
    /* is the engine's time up? if so, longjmp back to the
       beginning of think() */
    if (get_ms() >= stop_time) {
        stop_search = TRUE;
        longjmp(env, 0);
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.