How do chess engines manage time when they play real games?

Question

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 ?

Answer 1

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.

Answer 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);
    }
}