Sudden death time controls

[lkaufman]

Now that I think about it, perhaps you take the expected number of remaining moves given the current move number, and divide remaining time by that number. Is that correct? So if it is move ten, and the average number of remaining moves from move ten in the database is forty, you would divide total time by 40.

Yes, that's how it goes in nutshell!

I suppose you measure remaining moves until someone is up by perhaps 2 pawns or so, not until resignation.

Exactly!

When there is also an increment, do you just do the same thing and add the increment, or do you use another method?

[jdart]

I used to have some more complex logic for this, but I took it out, partly because it had some logic that was based on absolute time remaining and didn't scale well to very short time controls. Now I just do time left divided by moves left (with the latter set to a constant if sudden death). The only additional adjustments are searching a little longer when a ponder hit occurs, and a sanity check that avoids the search time ever hitting zero.

I don't think this is worse than what I did before. But it does produce some weird behavior when when you have a tournament type control (like 40 moves in 40 minutes) because if it plays 20 moves from the book, it will play the next 20 moves quite slowly and then speed up suddenly in the next time control block.

--Jon

[zamar]

Now that I think about it, perhaps you take the expected number of remaining moves given the current move number, and divide remaining time by that number. Is that correct? So if it is move ten, and the average number of remaining moves from move ten in the database is forty, you would divide total time by 40.

Yes, that's how it goes in nutshell!

I suppose you measure remaining moves until someone is up by perhaps 2 pawns or so, not until resignation.

Exactly!

When there is also an increment, do you just do the same thing and add the increment, or do you use another method?

It's basically the same method.

What I've written here is a bit oversimplification of what is done in reality, but this is the idea behind the implementation.

[bob]

When playing sudden death games, say game/5', with NO INCREMENT, traditionally I think most programs just set goal time to X% of remaining time per move. We still do so in Komodo, not having researched these time controls too much as the testing organizations don't use them. I haven't even checked open-source programs to see what they do. What is the state-of-the-art on this? Has anyone come up with a better algorithm than this crude but reasonable rule? It seems there should be one, but it's not so obvious.

we simply use a constant, something like:

target = remaining / C where C was tuned somewhat using cluster testing. We have a different C value depending on whether pondering is on or off as well (C is bigger with no pondering since we never save any time)...

We do have some code to use more time right out of the book, but that is really not consequential here...

[bob]

It's much more complicated than just x% of the time, because you will have a very high number of unfinished iterations that way.
What I do (and probably others) is to use time boundaries. One for the absolute maximum allowed (which can be considered for the X%
that you mention, just bigger) and one for the regular slice. If you accomplish the "regular" boundary but the iteration isn't finished yet,
you keep going until the max boundary is reached. On the other hand, if you have let say 70% of the regular finished, don't go for new iteration,
unless something bad is happening (or whatever you decide) - if you do that, use the max boundary.
You have a wide variety with this method and you can choose what part of the max to use and when and so on.

Best Regards!

I've tested this a ton. "unfinished iterations" are not a bad thing. You learn one thing quickly, that is that the previous best move is not as good as you thought. Fail lows happen quicker than fail-highs, and knowing the first move is bad can let you allocate more time, where if you choose to not start the iteration, you never know. In addition, even if you don't get a fail-high or low, or even a best score, when you start the pondering search, a good hash table will get you right back to where you were without wasting any time...

We do have an exceptional case where if we begin to fall behind, we speed up to avoid letting the opponent build up too large a time advantage which can be a killer later on. We do not do anything where we have a big advantage. Thinking too long lets the opponent get ponder hit after ponder hit and search just as long as you do, where it might be better to speed up to his level to avoid letting him ride your back along the time-usage path...

We used to have code that did exactly this, primarily for humans that like to just move back and forth instantly and try to reach a draw by getting their thinking done on our clock (3 0 was the time control of choice for this it seems). That might still be in Crafty, I have not looked recently...

[bob]

I used to have some more complex logic for this, but I took it out, partly because it had some logic that was based on absolute time remaining and didn't scale well to very short time controls. Now I just do time left divided by moves left (with the latter set to a constant if sudden death). The only additional adjustments are searching a little longer when a ponder hit occurs, and a sanity check that avoids the search time ever hitting zero.

I don't think this is worse than what I did before. But it does produce some weird behavior when when you have a tournament type control (like 40 moves in 40 minutes) because if it plays 20 moves from the book, it will play the next 20 moves quite slowly and then speed up suddenly in the next time control block.

--Jon

We do (or did, I will have to look) an "integrating" type of calculation here.

Rather than

target = time_left / moves_left, we did

target = time_left + next time control time/ moves left + next time control moves

That spreads out that extra time over the current TC + the next TC to avoid that large drop at move 40. I have seen programs reach move 40 with an hour left, and burn the whole thing right there, when it would have helped more to carry that over to the next TC and give a larger average time target...

[AlvaroBegue]

I'll describe an idea through an example.

Say you have to play 3 moves in the next 20 minutes and then you have 30 minutes for the next 30 moves, then 30 minutes for the rest of the game. You can decide how much time to use based on either:
* 3 moves in 20 minutes
* 33 moves in 50 minutes
* full game in 80 minutes

Because I want the behavior to converge to sudden death if the number of moves is very large, I cap the number of moves at 30, which is what I use for sudden death (of course you can use a different number or heuristics for this):
* 3 moves in 20 minutes => 400 seconds/move
* 33 moves in 50 minutes => 100 seconds/move (after limiting the number of moves to 30)
* full game in 80 minutes => 160 seconds/move (after limiting the number of moves to 30)

Now take the minimum of those numbers: 100 seconds/move.

That's it. This mechanism doesn't suffer from the problem Jon described, and it also doesn't suffer from pathological behavior if the time control is 1,000,000 moves in 30 minutes (spending 1 minute is more reasonable than 1.8 milliseconds).

In Ruy-López we also have a hard time limit to make sure we don't lose on time if the search gets stuck in a deep subtree, and that hard limit is set by looking only at the next time control.

[jdart]

Does the protocol give you the information to do this? I think in both UCI and xboard you only get info about the current.time control period, until it is over, then you get the next one.

[hgm]

Well, for XBoard we agreed on a protocol extension (activated by feature xlevel=1) that would inform the engine in advance, by piggy-backing the parameters for all future sessions behind those for the upcoming session, separated by semicolons. Like

level 40 40 0; 10 15 0; 0 5 0

where a non-incremental session at the end would imply it is repeated indefinitely.

WinBoard and XBoard do not implement this yet, however. (But I think ChessGUI does.)

[AlvaroBegue]

No, Ruy-López is an old-style chess program, with its own GUI. It seems like a flaw if UCI doesn't describe the full set of conditions under which the game is being played.