Time Managment translating to SMP

[AndrewGrant]

So I've been putting a lot of work into the time management of Ethereal, and found some nice gains.

One part I was looking into is when I terminate my search. At the start of the search I compute two values, optimalTime, and maxiumTime. If time used ever passes maxiumTime then search aborts the partial depth search. If the search aborts before finishing a depth, that time is for the most part wasted (Sure, PV could change, Hash could gain value).

so I did the following to try to avoid some of the times when time is wasted.

Code: Select all

            // Check to see if we expect to be able to complete the next depth
            if (thread->limits->limitedBySelf){
                double lastTime = info->timeUsage[depth];
                double timeFactor = MIN(2, info->timeUsage[depth] / info->timeUsage[lastDepth]);
                double estimatedUsage = lastTime * (timeFactor + .25);
                double estiamtedEndtime = getRealTime() + estimatedUsage - thread->starttime;
                
                if (estiamtedEndtime > thread->maxusage){
                    for &#40;i = 0; i < thread->nthreads; i++)
                        thread->threads&#91;i&#93;.abort = ABORT_ALL;
                    
                    pthread_mutex_unlock&#40;thread->lock&#41;;
                    
                    break;
                &#125;
            &#125;

Basically I look at the time branch factor of the last depth completed, and try to stop the search early if I don't expect to have enough time.

I tested it in the following 5 ways, and found elo gains between 9 and 13.

* 20+.2s 1Thread
* 5+.05s 1Thread
* 40/4.0s 1Thread
* 40/40.0s 1Thread
* 40/4.0s 3Thread

I was worried about how this change scales with more than 1 thread. With 1 thread, search completion times are fairly predicable, but with lazy SMP the time between finishing depths varies greatly. I've tried testing with 6Threads, but cannot find the same level of improvement.

Has anyone gone down this path? Any thoughts to share?

-- Andrew

[nitrocan]

Don’t ever wait for anything to finish, as soon as you go over the time you’ve alloted, immediately cancel the search ASAP and return the result.

[bob]

Don’t ever wait for anything to finish, as soon as you go over the time you’ve alloted, immediately cancel the search ASAP and return the result.

Seems dangerous. Suppose you just failed low on the current move. Stop and play it if you reach your target time? Or continue searching the remaining moves to see if one solves this problem?

[nitrocan]

Don’t ever wait for anything to finish, as soon as you go over the time you’ve alloted, immediately cancel the search ASAP and return the result.

Seems dangerous. Suppose you just failed low on the current move. Stop and play it if you reach your target time? Or continue searching the remaining moves to see if one solves this problem?

I’d consider that a different thing altogether. Of course some extra time should be used when failing low but waiting for the current depth to finish will easily cause you time problems.

[bob]

Don’t ever wait for anything to finish, as soon as you go over the time you’ve alloted, immediately cancel the search ASAP and return the result.

Seems dangerous. Suppose you just failed low on the current move. Stop and play it if you reach your target time? Or continue searching the remaining moves to see if one solves this problem?

I’d consider that a different thing altogether. Of course some extra time should be used when failing low but waiting for the current depth to finish will easily cause you time problems.

You might be surprised. Quite often, you take longer than expected to complete an iteration because some new move is popping to the top of the list. You might not want to miss making that move. There are lots of ways to save time, such as shortening the time control every iteration that you don't change from the original best move, or increasing the target time when you do. But stopping "just because you reach some time limit that you set at the start of the search" might not be as good as you want.