Your values for X, Y, and Z

[sje]

Your values for X, Y, and Z (all in the 0..1 range)

For a traditional iterative A/B PVS program running under time control AND given a basic time allocation for the search AND the evaluation is within a pawn of the draw score:

1) When finishing an iteration, the next iteration is NOT started (and the search ends) when at least X amount of the basic time allocation has been used.

2) When finishing the sub-search of a root move, the next root move sub-search is NOT started (and the search ends) when at least Y amount of the basic time allocation has been used.

3) When calculating a basic search time allocation at the start of a search in a sudden death time control, the allocated time is set as Z amount of the total time remaining.

[bob]

Your values for X, Y, and Z (all in the 0..1 range)

For a traditional iterative A/B PVS program running under time control AND given a basic time allocation for the search AND the evaluation is within a pawn of the draw score:

1) When finishing an iteration, the next iteration is NOT started (and the search ends) when at least X amount of the basic time allocation has been used.

100%

2) When finishing the sub-search of a root move, the next root move sub-search is NOT started (and the search ends) when at least Y amount of the basic time allocation has been used.

100%

3) When calculating a basic search time allocation at the start of a search in a sudden death time control, the allocated time is set as Z amount of the total time remaining.

Bit harder. We have a dynamic calculation for this that depends on the phase of the game, which depends on material remaining, etc.

[sje]

At the moment I'm experimenting with the values of X and Y. In the past, I've set the next iteration threshold at 0.5 allocated time and the next move threshold at 0.75 allocated time. These values were adjusted when pondering was enabled.

For the sudden death time control allocation fraction, the basic allocation is between 4% and 5% of the remaining time.

Time extensions for X and Y are based on how surprisingly bad an expectation may have gone sour. In all cases, I enforce a hard limit of eight times the base allocation and sometimes this can save an otherwise lost game. This hard limit is checked at every node where an updated elapsed time is available.

In the evolving CIL Toolkit, the routines support a slim (search limiter) structure. It has three components: an iteration limit in ply, an node count limit, and an hard time limit in milliseconds. Any or all of these values can be nil in which case the corresponding limit checks are not performed. The limit checks are performed at every node, but only after a PV has been established. Said establishment is done at the completion of the analysis of the first move in the first iteration. Per next iteration and per next root move time checks are not present -- yet. (I have only just now added a zero width search to implement PVS.)

[jwes]

Your values for X, Y, and Z (all in the 0..1 range)

For a traditional iterative A/B PVS program running under time control AND given a basic time allocation for the search AND the evaluation is within a pawn of the draw score:

1) When finishing an iteration, the next iteration is NOT started (and the search ends) when at least X amount of the basic time allocation has been used.

100%

2) When finishing the sub-search of a root move, the next root move sub-search is NOT started (and the search ends) when at least Y amount of the basic time allocation has been used.

100%

3) When calculating a basic search time allocation at the start of a search in a sudden death time control, the allocated time is set as Z amount of the total time remaining.

Bit harder. We have a dynamic calculation for this that depends on the phase of the game, which depends on material remaining, etc.

Have you tested all these things ?

[sje]

Symbolic has another search termination based on elapsed time. This is its "easy move" feature, stolen from Chess 4.x, where a search is stopped when at least one fourth of the base time allocation has been used and the last N (tunable, usually 5) iterations produced the same best move result.

[bob]

Your values for X, Y, and Z (all in the 0..1 range)

For a traditional iterative A/B PVS program running under time control AND given a basic time allocation for the search AND the evaluation is within a pawn of the draw score:

1) When finishing an iteration, the next iteration is NOT started (and the search ends) when at least X amount of the basic time allocation has been used.

100%

2) When finishing the sub-search of a root move, the next root move sub-search is NOT started (and the search ends) when at least Y amount of the basic time allocation has been used.

100%

3) When calculating a basic search time allocation at the start of a search in a sudden death time control, the allocated time is set as Z amount of the total time remaining.

Bit harder. We have a dynamic calculation for this that depends on the phase of the game, which depends on material remaining, etc.

Have you tested all these things ?

What do you think?

[jwes]

Your values for X, Y, and Z (all in the 0..1 range)

For a traditional iterative A/B PVS program running under time control AND given a basic time allocation for the search AND the evaluation is within a pawn of the draw score:

1) When finishing an iteration, the next iteration is NOT started (and the search ends) when at least X amount of the basic time allocation has been used.

100%

2) When finishing the sub-search of a root move, the next root move sub-search is NOT started (and the search ends) when at least Y amount of the basic time allocation has been used.

100%

3) When calculating a basic search time allocation at the start of a search in a sudden death time control, the allocated time is set as Z amount of the total time remaining.

Bit harder. We have a dynamic calculation for this that depends on the phase of the game, which depends on material remaining, etc.

Have you tested all these things ?

What do you think?

What alternatives did you test and what ELO difference was there?

[bob]

Your values for X, Y, and Z (all in the 0..1 range)

For a traditional iterative A/B PVS program running under time control AND given a basic time allocation for the search AND the evaluation is within a pawn of the draw score:

1) When finishing an iteration, the next iteration is NOT started (and the search ends) when at least X amount of the basic time allocation has been used.

100%

2) When finishing the sub-search of a root move, the next root move sub-search is NOT started (and the search ends) when at least Y amount of the basic time allocation has been used.

100%

3) When calculating a basic search time allocation at the start of a search in a sudden death time control, the allocated time is set as Z amount of the total time remaining.

Bit harder. We have a dynamic calculation for this that depends on the phase of the game, which depends on material remaining, etc.

Have you tested all these things ?

What do you think?

What alternatives did you test and what ELO difference was there?

It is not major unless you go way outside sanity. For example, whether you use 1/20 of your remaining time when you have 20 moves left to next time control, or if you go to 1/15 or 1/25, there is not a lot of difference. There is some, but not a lot.

We experimented with not starting a new iteration if there is not enough time left to get something back. But that generally tests worse, because if you fail low on the next iteration, that happens very quickly compared to getting a real score or failing high, since on a fail low, only a few moves are examined at ply-2 while on a fiil high or real score all must be examined. Knowing that the score dropped significantly is information you can use to search beyond the time allowed to see if you can find a better move.

Another issue is whether to continue at the root if there is little time to find a better move. My answer is always "yes". The remaining root moves fly by very quickly unless one is close to failing high. If time runs out, I never time out "instantly" but instead complete all pending root moves (might be just one with one CPU, or since Crafty splits everywhere including the root on parallel searches, there might be N root moves "in progress" (N = # of threads). I will use up to 2x the original time target before giving up and quitting, in case one of those moves will become a new best. Normally, they are finished almost instantly and this doesn't do a thing. But on occasion, we find a new best move after the original target time was used. This actually is worth 10+ elo when done right...

[sje]

Consider this example:

The time needed to fully process the next iteration for a given program has been observed to take about as much time as all the prior iterations combined. Also, the same program has been observed to spend half the time of each iteration with analyzing the first move of the iteration.

Say that the program is allocating 120 seconds per move. At 80 seconds into a search, the program is ready to start the next iteration. That iteration will likely take another 80 seconds and so will exceed the allocation limit. But the first move of the next iteration is likely to take half of that (40 seconds), and so the search could start the next iteration with an even chance of getting that first move's analysis. Now there are other factors here like parallelism and pondering, but the above numbers could be tweaked to handle these.

The point is that the next iteration should be skipped in the above example if the time used is just a bit over 2/3rds of the allocated time and not 100% of the allocated time.