Time Management

See Mediocre v0.12b

In order for the engine not to run out of time, and to think as deep as possible with the time given, we need a way to determine how long to think on each move.

Allocate time

To start off we need to determine how much time to allocate on each move.

We could keep an internal timer to keep track of the time, but both the WinBoard and UCI protocols submits the time left for both sides after each move. So we have that information for free.

See the corresponding protocol for how to receive that information from the interface. (or look in my code once I release the next version)

My method to determine how much time to use looks like this:

// Use 2.25% of the time + half of the increment
int timeForThisMove = timeLeft/40+(increment/2);

// If the increment puts us above the total time left
// use the timeleft - 0.5 seconds
if(timeForThisMove >= timeLeft)
timeForThisMove = timeLeft -500;

// If 0.5 seconds puts us below 0
// use 0.1 seconds to atleast get some move.
if(timeForThisMove < 0)
timeForThisMove = 100;

return timeForThisMove;

I take 2.25% of the total time left and give a bonus if the time controls includes an increment (extra time after each move). To make sure we do not run out of time due to the increment bonus I make a check to see that we do not allocate more time than the total time left.

This seems to work ok in most situations, but I am sure some tweaking can be done.

Hard stop

As I mentioned in an earlier post it is not enough to check for allocated time being up after each iteration of the iterative deepening loop.

Let us say we allocated 2 seconds for this move, and after searching 4 plies we have used 1.9 seconds. Since the time is not up we start searching the next depth, this search could take say 5 seconds, making the search run for 6.9 seconds instead of 2.

We need a way to stop the search even if we have started the alpha-beta sequence.

What I have done is add the following code at the top of the alphaBeta()-method:

nextTimeCheck--;
if(nextTimeCheck == 0) // Time to check the time
{
nextTimeCheck = TIME_CHECK_INTERVAL;
if((System.currentTimeMillis() - startTime) > timeForThisMove)
{
stopSearch = true;
return 0;
}
}

I used this idea from the King's Out engine but it is a pretty basic concept.

Every few alphaBeta() calls we check if the time is up, if it is we immediately return 0 and set stopSearch to true.

When stopSearch is true we do not make any more searching in the alphaBeta().

Once we get back to the iterative deepening loop if stopSearch is true, we break the loop and discard any results the last alpha-beta call might have produced.

This is called a hard stop and allows us to break the recursive alphaBeta-calls very quickly.

One more check

While the hard stop allows us to stop searching when the time is up, we still have a problem.

If we allocated 30 seconds on the move, and searching up to 7 ply used 16 seconds so far, we would go to the next depth and start searching. If the 8 ply search takes 35 seconds we would break it with the hard stop at 30 seconds thus wasting 14 seconds on a search that we discarded.

It is impossible to know exactly how long a certain depth search will take, but we can estimate it.

There are probably ellaborate ways to do this, but what I did was assume that the next search depth will take atleast twice as long as the previous.

So before going to the next depth I make a check to see if we have enough time left to search for 2 times the last depth's time. Like this:

if((System.currentTimeMillis() - startTime) * 2 > timeForThisMove)
break;

In the example above where we allocated 30 seconds and a 7 ply search took 16 seconds, we would check if 16*2 is within the allocated time before starting the next search. Since 16*2>30 we would not start the next search and simply return the 7 ply result.

Nuances

There are plenty of things to do to optimize the time we use on moves. Complicated middle games migth require a bit more time, and if we noticed a mate threat in the last search it could be worth searching for a bit longer just to make sure.

These are things to consider, but the basic setup I explained above works well.

Edits:
2007-01-09 - Changed the increment bonus example to work with milliseconds instead of full seconds