Time Managment translating to SMP

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
AndrewGrant
Posts: 490
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Time Managment translating to SMP

Post by AndrewGrant » Sat Dec 23, 2017 7:45 am

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
Posts: 17
Joined: Fri Sep 15, 2017 9:52 pm

Re: Time Managment translating to SMP

Post by nitrocan » Sat Dec 23, 2017 6:39 pm

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
Posts: 20566
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Time Managment translating to SMP

Post by bob » Sun Dec 24, 2017 4:40 pm

nitrocan wrote: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
Posts: 17
Joined: Fri Sep 15, 2017 9:52 pm

Re: Time Managment translating to SMP

Post by nitrocan » Sun Dec 24, 2017 8:32 pm

bob wrote:
nitrocan wrote: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
Posts: 20566
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Time Managment translating to SMP

Post by bob » Tue Dec 26, 2017 5:05 am

nitrocan wrote:
bob wrote:
nitrocan wrote: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.

Post Reply