Time management question

[xmas79]

Hi all,
I actually have a very trivial time management code. I allocate some time for each search, and when I have no more time I stop the search (wherever it is), drop the current search result and keep the previous iteration score. This obviously is sub-optimal, as I'm throwing away the last iteration, which is where the program spent some amount of time that goes directly to the bin...

So I would like to "predict" (more or less....) if I can start the new iteration N+1 or the allocated and spent time will not allow me to complete this iteration N+1, so it's best to make the best move now and save time.

Should I look at the BF of my engine? Can I simply assume that the iteration N+1 will take "BF times" the time it took for the iteraion N? Can I see the BF as (time_spent_on_iteration_X/time_spent_on_iteration_X_minus_1) ? Even if we know that we are comparing even and odd iterations (one has less nodes so will complete in shorter "equivalent" time)?

Best regards,
Natale.

[hgm]

Searching the PV move of iteration N is a similar search to the entire iteration N-1. So unless the position is extremely asymmetric, you expect it to take similar time. To prove other root moves are worse takes much less time (per move). That is, if they are actually worse. If one of them fails high, and eventually overturnes the old PV move, it takes just as long again as the original PV move, and probably longer. (Because the previous PV move would benefit more from what the previous iteration left in the hash table.)

Now a new iteration that is interrupted after searching only the PV move doesn't do you any good at all. You might have a more reliable score on that move now, but you still have to play it, even if that score is disastrous. A new iteration only brings you anything when you give it the chance to change the move from what the previous iteration found. That thus takes 2.5-3 times as long as that previous iteration. If you cannot afford to let it run for at least that time, you might as well not start it.

And even this assumes that you would play the best move found so far in the interrupted iteration, rather than always falling back on the best move of the previous iteration (which might already have been proven inferior to some other move in the interrupted iteration, and although that might not be the best move, it would still be better to play that one than the old PV move).

Of course this means that very often you think much shorter than the maximum time (perhaps as short as only 25% of it), so that on average you also move faster, which you can compensate by allowing a larger max time (perhaps double, so that your thinking time now varies between 50% and 200% for an average of 100%) of what you are using now (timeLeft/movesLeft). Unless you are close to the end of a session, where you have to be careful not to flag. (So you could use max = 2*timeLeft/(movesLeft+1) rather than 2*(timeLeft/movesLeft), so that even when movesLeft=1 you will never think longer than timeLeft.)

[bob]

Hi all,
I actually have a very trivial time management code. I allocate some time for each search, and when I have no more time I stop the search (wherever it is), drop the current search result and keep the previous iteration score. This obviously is sub-optimal, as I'm throwing away the last iteration, which is where the program spent some amount of time that goes directly to the bin...

So I would like to "predict" (more or less....) if I can start the new iteration N+1 or the allocated and spent time will not allow me to complete this iteration N+1, so it's best to make the best move now and save time.

Should I look at the BF of my engine? Can I simply assume that the iteration N+1 will take "BF times" the time it took for the iteraion N? Can I see the BF as (time_spent_on_iteration_X/time_spent_on_iteration_X_minus_1) ? Even if we know that we are comparing even and odd iterations (one has less nodes so will complete in shorter "equivalent" time)?

Best regards,
Natale.

Why do you throw away the current iteration if it is incomplete? If you have searched the first move completely and gotten a best move back, no reason to throw that away. If you have searched further and found a replacement before time runs out, no need to throw that away either. That will solve 95% of your issues...

[AlvaroBegue]

I have a function to determine whether to try another ply or not:

Code: Select all

bool Engine::dare_to_try_another_ply(int depth) {
  if (depth <= 1)
    return true;
  if (depth > max_depth)
    return false;
  if (pondering)
    return true;
  double elapsed = now() - start_time;
  return elapsed < time_per_move * difficult_situation_multiplier * 0.3;
}

`time_per_move' is my target of how much time to spend in this move. `difficult_situation_multiplier' is usually 1, but it can go to 3 or even 6 if the score drops a lot.

The other variable I use to control time is a hard deadline, which has a complicated formula, but is basically 5*time_per_move. If I reach that time, I abort wherever I am (with a C++ exception).

Bob is right that you should use whatever you have discovered at the time you stop thinking. The way I organize my search at the root, whenever I find a new best move, I move it to the top of the list. That way I can always just return `moves[0]'.

[xmas79]

I have a function to determine whether to try another ply or not:

Code: Select all

bool Engine::dare_to_try_another_ply(int depth) {
  if (depth <= 1)
    return true;
  if (depth > max_depth)
    return false;
  if (pondering)
    return true;
  double elapsed = now() - start_time;
  return elapsed < time_per_move * difficult_situation_multiplier * 0.3;
}

`time_per_move' is my target of how much time to spend in this move. `difficult_situation_multiplier' is usually 1, but it can go to 3 or even 6 if the score drops a lot.

The other variable I use to control time is a hard deadline, which has a complicated formula, but is basically 5*time_per_move. If I reach that time, I abort wherever I am (with a C++ exception).

Bob is right that you should use whatever you have discovered at the time you stop thinking. The way I organize my search at the root, whenever I find a new best move, I move it to the top of the list. That way I can always just return `moves[0]'.

My search structure is similar to this, and when the score drops down (failing low at root) I reallocate more time (up to 6x).

But now I'm puzzled: if I did understand HGM post well he says:

Now a new iteration that is interrupted after searching only the PV move doesn't do you any good at all

which in my ears sounds like "if you have an interrupted iteration discard the results", but then

...You might have a more reliable score on that move now, but you still have to play it, even if that score is disastrous. A new iteration only brings you anything when you give it the chance to change the move from what the previous iteration found.

that in my ears sounds like "ok, let the next iteration run, and take the best move that this iteration finds. If you stop search before it finds a best move then fall back to the previous iteration best move".

Now it seems to me pretty safe to play a (best) move found in an interrupted iteration.

But a new question arises (mixing up things):
In a fail-hard framework, where a fail low at root give no root move, you must research with another window. Here there nothing to say because the score you got back was alpha, and don't know which move is best (because every move returned alpha).

In a fail-soft framework, instead, we always have a best move, since we start with bestScore=-INF and at least the first move will raise the best score... On a fail-low root node, all the root moves will be searched and the best score will be picked. What's the point on research with a lower alpha bound? If I have an aspiration window of [-100,100] and fail (soft) low with a score of say -600, that really means I can get at best -600 with (say the 9th move)? When I search again with [-700, -500] can I assume I will get back that 9th move with a score of -600? I bet no... I couldn't have multiple fail-lows in a row...

So on any fail low at root, I should never update the best move found so far, and if reach the allotted time, then the previous iteration best move should be played.

Did I got it right?

Natale.

[bob]

I have a function to determine whether to try another ply or not:

Code: Select all

bool Engine::dare_to_try_another_ply(int depth) {
  if (depth <= 1)
    return true;
  if (depth > max_depth)
    return false;
  if (pondering)
    return true;
  double elapsed = now() - start_time;
  return elapsed < time_per_move * difficult_situation_multiplier * 0.3;
}

`time_per_move' is my target of how much time to spend in this move. `difficult_situation_multiplier' is usually 1, but it can go to 3 or even 6 if the score drops a lot.

The other variable I use to control time is a hard deadline, which has a complicated formula, but is basically 5*time_per_move. If I reach that time, I abort wherever I am (with a C++ exception).

Bob is right that you should use whatever you have discovered at the time you stop thinking. The way I organize my search at the root, whenever I find a new best move, I move it to the top of the list. That way I can always just return `moves[0]'.

My search structure is similar to this, and when the score drops down (failing low at root) I reallocate more time (up to 6x).

But now I'm puzzled: if I did understand HGM post well he says:

Now a new iteration that is interrupted after searching only the PV move doesn't do you any good at all

which in my ears sounds like "if you have an interrupted iteration discard the results", but then

...You might have a more reliable score on that move now, but you still have to play it, even if that score is disastrous. A new iteration only brings you anything when you give it the chance to change the move from what the previous iteration found.

that in my ears sounds like "ok, let the next iteration run, and take the best move that this iteration finds. If you stop search before it finds a best move then fall back to the previous iteration best move".

Now it seems to me pretty safe to play a (best) move found in an interrupted iteration.

But a new question arises (mixing up things):
In a fail-hard framework, where a fail low at root give no root move, you must research with another window. Here there nothing to say because the score you got back was alpha, and don't know which move is best (because every move returned alpha).

In a fail-soft framework, instead, we always have a best move, since we start with bestScore=-INF and at least the first move will raise the best score... On a fail-low root node, all the root moves will be searched and the best score will be picked. What's the point on research with a lower alpha bound? If I have an aspiration window of [-100,100] and fail (soft) low with a score of say -600, that really means I can get at best -600 with (say the 9th move)? When I search again with [-700, -500] can I assume I will get back that 9th move with a score of -600? I bet no... I couldn't have multiple fail-lows in a row...

So on any fail low at root, I should never update the best move found so far, and if reach the allotted time, then the previous iteration best move should be played.

Did I got it right?

Natale.

There are lots of ways to handle a fail-low at the root, but most end up being special-cases of two specific alternatives.

(1) continue searching with same window. If you find a move that doesn't fail low, you win with this approach. If you search all moves and everything fails low, you have to relax alpha and re-search everything, where you now lose with this approach.

(2) as soon as the first move is searched and returns alpha, you can relax alpha and re-search this move to get a real score before going into other moves. In the second case in (1) above, this is significantly better.

So the question you have to answer is "When I fail low on the first move, do I find a different move that is pretty close (making option (1) above good) or do I find that all moves are worse (making option (2) above better).

I use option (2) for several reasons. First, it gives me a score. Now I know how bad the best move is, compared to what I was expecting, and I can choose to spend more time trying to find something better. With option (1) you are not sure whether just the first move was worse, or all moves are worse, so you almost have to search a really long time to figure that out, otherwise you move too quickly and make a move you KNOW is going to lose (big score drop) without knowing how bad the move is...

One can make a case for either of the above. There are other ways to find a new best move quicker. For example, if you are at iteration 20 when you fail low, return to iteration 1 and start over. The hash entries will continue to make the old best move fail low, giving you a chance of finding a different "better move" at shallow depths, improving later move ordering. There are other variations as well, but you get the idea... I'm not sure there is any one right answer.

[Volker Annuss]

Hi Natale,

yes, you can use the branching factor for an estimation how long iteration N+1 will take. But sometimes the next iteration will take much longer than predicted. So I have a panic time in my engine to interrupt the search when it takes much too long. If you or anyone else has a better solution, please tell me.

When you work on your time management there is more you can do.

It is more likely, that the best move will change in iteration N+1, when it changed in iteration N and to a lesser degree also, when it changed in iteration N-1 or even N-2. So you can spend more time in this situation.
It is also more likely that the best move will change, when the score dropped from iteration N-1 to iteration N.

It is less likely, that the best move will change in iteration N+1, when the best move is a capture move. This is even true if there is another move that can capture the same piece.

[Volker Annuss]

In my engines Hermann and Arminius there is an option to log information that is used for time management. This is used to calculate a probability if the best move will change when going one ply deeper.
And finally there is the information if the best move changed after doing this iteration.

After loading some recent data from my engine Arminius into a spread sheet I calculated how much a change in the best move was correlated whith the data I had before the iteration.
Here some correlations for the most important data.

Code: Select all

 0.21 Best move changed from iteration N-1 to iteration N
 0.15 Best move changed from iteration N-2 to iteration N-1
 0.14 Best move changed from iteration N-3 to iteration N-2
 0.15 2nd move from PV (ponder move) changed from iteration N-1 to iteration N
 0.15 3rd move from PV changed from iteration N-1 to iteration N
-0.08 Best move is capture or promotion
 0.11 Number of legal moves
-0.15 Nodes spent on the best move / nodes spent on all moves
-0.07 win_percentage_from_score(score[N]) - win_percentage_from_score(score[N-1])

 0.33 all of the above + some others combined to a predicted probability for the best move changing

For win_percentage_from_score see chess programming wiki.